/*!
 * Copyright (c) Microsoft Corporation and contributors. All rights reserved.
 * Licensed under the MIT License.
 */
import { Heap, DoublyLinkedList } from "@fluidframework/core-utils/internal";
import type { IAttributionCollectionSerializer } from "./attributionCollection.js";
import type { Client } from "./client.js";
import { EndOfTreeSegment, StartOfTreeSegment } from "./endOfTreeSegment.js";
import { type LocalReferencePosition, SlidingPreference } from "./localReference.js";
import { type IMergeTreeDeltaOpArgs, type MergeTreeDeltaCallback, type MergeTreeMaintenanceCallback } from "./mergeTreeDeltaCallback.js";
import { CollaborationWindow, type IMergeNode, type ISegmentAction, Marker, MergeBlock, type SegmentGroup, type ISegmentInternal, type ISegmentLeaf, type ISegmentPrivate, type ObliterateInfo } from "./mergeTreeNodes.js";
import { type IRelativePosition, ReferenceType, type IMergeTreeOp } from "./ops.js";
import { type Perspective } from "./perspective.js";
import { type PropertySet } from "./properties.js";
import { type ReferencePosition } from "./referencePositions.js";
import { type IHasInsertionInfo, type IHasRemovalInfo, type SegmentWithInfo } from "./segmentInfos.js";
import { type PropsOrAdjust } from "./segmentPropertiesManager.js";
import { type InteriorSequencePlace } from "./sequencePlace.js";
import type { OperationStamp } from "./stamps.js";
export declare function isRemovedAndAcked(segment: ISegmentPrivate): segment is ISegmentLeaf & IHasRemovalInfo;
/**
 * @legacy @beta
 */
export interface IMergeTreeOptions {
    catchUpBlobName?: string;
    /**
     * Whether or not reference positions can slide to special endpoint segments
     * denoting the positions immediately before the start and immediately after
     * the end of the string.
     *
     * This is primarily useful in the case of interval stickiness.
     */
    mergeTreeReferencesCanSlideToEndpoint?: boolean;
    mergeTreeSnapshotChunkSize?: number;
    /**
     * Whether to use the SnapshotV1 format over SnapshotLegacy.
     *
     * SnapshotV1 stores a view of the merge-tree at the current sequence number, preserving merge metadata
     * (e.g. clientId, seq, etc.) only for segment changes within the collab window.
     *
     * SnapshotLegacy stores a view of the merge-tree at the minimum sequence number along with the ops between
     * the minimum sequence number and the current sequence number.
     *
     * Both formats merge segments where possible (see {@link ISegment.canAppend})
     *
     * default: false
     *
     * @remarks
     * Despite the "legacy"/"V1" naming, both formats are actively used at the time of writing. SharedString
     * uses legacy and Matrix uses V1.
     */
    newMergeTreeSnapshotFormat?: boolean;
    /**
     * Enables support for the obliterate operation -- a stronger form of remove
     * which deletes concurrently inserted segments
     *
     * Obliterate is currently experimental and may not work in all scenarios.
     *
     * Default value: false
     */
    mergeTreeEnableObliterate?: boolean;
    /**
     * Enables support for reconnecting when obliterate operations are present
     *
     * Obliterate is currently experimental and may not work in all scenarios.
     *
     * @defaultValue `false`
     */
    mergeTreeEnableObliterateReconnect?: boolean;
    /**
     * Enables support for obliterate endpoint expansion.
     * When enabled, obliterate operations can have sidedness specified for their endpoints.
     * If an endpoint is externally anchored
     * (aka the start is after a given position, or the end is before a given position),
     * then concurrent inserts adjacent to the exclusive endpoint of an obliterated range will be included in the obliteration
     *
     * @defaultValue `false`
     */
    mergeTreeEnableSidedObliterate?: boolean;
    /**
     * Enables support for annotate adjust operations, which allow for specifying
     * a summand which is summed with the current value to compute the new value.
     *
     * @defaultValue `false`
     */
    mergeTreeEnableAnnotateAdjust?: boolean;
}
/**
 * @internal
 */
export interface IMergeTreeOptionsInternal extends IMergeTreeOptions {
    /**
     * Options related to attribution
     */
    attribution?: IMergeTreeAttributionOptions;
}
export declare function errorIfOptionNotTrue(options: IMergeTreeOptions | undefined, option: keyof IMergeTreeOptions): void;
/**
 * @internal
 */
export interface IMergeTreeAttributionOptions {
    /**
     * If enabled, segments will store attribution keys which can be used with the runtime to determine
     * attribution information (i.e. who created the content and when it was created).
     *
     * This flag only applied to new documents: if a snapshot is loaded, whether or not attribution keys
     * are tracked is determined by the presence of existing attribution keys in the snapshot.
     *
     * default: false
     */
    track?: boolean;
    /**
     * Provides a policy for how to track attribution data on segments.
     * This option must be provided if either:
     * - `track` is set to true
     * - a document containing existing attribution information is loaded
     */
    policyFactory?: () => AttributionPolicy;
}
/**
 * Implements policy dictating which kinds of operations should be attributed and how.
 * @sealed
 * @internal
 */
export interface AttributionPolicy {
    /**
     * Enables tracking attribution information for operations on this merge-tree.
     * This function is expected to subscribe to appropriate change events in order
     * to manage any attribution data it stores on segments.
     *
     * This must be done in an eventually consistent fashion.
     */
    attach: (client: Client) => void;
    /**
     * Disables tracking attribution information on segments.
     */
    detach: () => void;
    /***/
    isAttached: boolean;
    /**
     * Serializer capable of serializing any attribution data this policy stores on segments.
     */
    serializer: IAttributionCollectionSerializer;
}
/**
 * @internal
 */
export interface LRUSegment {
    segment?: ISegmentLeaf;
    maxSeq: number;
}
export interface IRootMergeBlock extends MergeBlock {
    mergeTree?: MergeTree;
}
export declare function findRootMergeBlock(segmentOrNode: IMergeNode | undefined): IRootMergeBlock | undefined;
/**
 * Returns the position to slide a reference to if a slide is required.
 * @param segoff - The segment and offset to slide from
 * @returns segment and offset to slide the reference to
 * @internal
 */
export declare function getSlideToSegoff(segoff: {
    segment: ISegmentInternal;
    offset: number;
} | undefined, slidingPreference?: SlidingPreference, perspective?: Perspective, canSlideToEndpoint?: boolean): {
    segment: ISegmentInternal;
    offset: number;
} | undefined;
/**
 * @internal
 */
export declare class MergeTree {
    options?: IMergeTreeOptionsInternal | undefined;
    static readonly options: {
        incrementalUpdate: boolean;
        insertAfterRemovedSegs: boolean;
        zamboniSegments: boolean;
    };
    /**
     * A sentinel value that indicates an inserting walk should continue to the next block sibling.
     * This can occur for example when tie-break forces insertion of a segment past an entire block (and
     * the inserting walk first recurses into the block before realizing that).
     */
    private static readonly theUnfinishedNode;
    readonly collabWindow: CollaborationWindow;
    readonly pendingSegments: DoublyLinkedList<SegmentGroup>;
    readonly segmentsToScour: Heap<LRUSegment>;
    readonly attributionPolicy: AttributionPolicy | undefined;
    get localPerspective(): Perspective;
    /**
     * Whether or not all blocks in the mergeTree currently have information about local partial lengths computed.
     * This information is only necessary on reconnect, and otherwise costly to bookkeep.
     * This field enables tracking whether partials need to be recomputed using localSeq information.
     */
    private localPartialsComputed;
    private readonly idToMarker;
    mergeTreeDeltaCallback?: MergeTreeDeltaCallback;
    mergeTreeMaintenanceCallback?: MergeTreeMaintenanceCallback;
    private readonly obliterates;
    constructor(options?: IMergeTreeOptionsInternal | undefined);
    rebaseObliterateTo(existing: ObliterateInfo, newObliterate: ObliterateInfo | undefined): void;
    private _root;
    get root(): IRootMergeBlock;
    set root(value: IRootMergeBlock);
    makeBlock(childCount: number): MergeBlock;
    /**
     * Compute the net length of this segment leaf from some perspective.
     * @returns Undefined if the segment has been removed and its removal is common knowledge to all collaborators (and therefore
     * may not even be present on clients that have loaded from a summary beyond this point). Otherwise, the length of the segment.
     */
    leafLength(segment: ISegmentLeaf, perspective?: Perspective): number | undefined;
    unlinkMarker(marker: Marker): void;
    private addNode;
    reloadFromSegments(segments: SegmentWithInfo<IHasInsertionInfo>[]): void;
    startCollaboration(localClientId: number, minSeq: number, currentSeq: number): void;
    private addToLRUSet;
    getLength(perspective: Perspective): number;
    /**
     * Returns the current length of the MergeTree for the local client.
     */
    get length(): number | undefined;
    getPosition(node: IMergeNode, perspective: Perspective): number;
    getContainingSegment(pos: number, perspective: Perspective): {
        segment: ISegmentLeaf;
        offset: number;
    } | undefined;
    /**
     * Slides or removes references from the provided list of segments.
     *
     * The order of the references is preserved for references of the same sliding
     * preference. Relative order between references that slide backward and those
     * that slide forward is not preserved, even in the case when they slide to
     * the same segment.
     *
     * @remarks
     *
     * 1. Preserving the order of the references is a useful property for reference-based undo/redo
     * (see revertibles.ts).
     *
     * 2. For use cases which necessitate eventual consistency across clients,
     * this method should only be called with segments for which the current client sequence number is
     * max(remove segment sequence number, add reference sequence number).
     * See `packages\dds\merge-tree\REFERENCEPOSITIONS.md`
     *
     * @param segments - An array of (not necessarily contiguous) segments with increasing ordinals.
     */
    private slideAckedRemovedSegmentReferences;
    /**
     * Compute local partial length information
     *
     * Public only for use by internal tests
     */
    computeLocalPartials(refSeq: number): void;
    private nodeLength;
    setMinSeq(minSeq: number): void;
    /**
     * Returns the count of elements before the given reference position from the given perspective.
     *
     * @param refPos - The reference position to resolve.
     * @param refSeq - The number of the latest sequenced change to consider.
     * Defaults to including all edits which have been applied.
     * @param clientId - The ID of the client from whose perspective to resolve this reference. Defaults to the current client.
     * @param localSeq - The local sequence number to consider. Defaults to including all local edits.
     */
    referencePositionToLocalPosition(refPos: ReferencePosition, refSeq?: number, clientId?: number, localSeq?: number | undefined): number;
    /**
     * Returns the immediately adjacent segment in the specified direction from this perspective.
     * There may actually be multiple segments between the given segment and the returned segment,
     * but they were either inserted after this perspective, or have been removed before this perspective.
     *
     * @param segment - The segment to start from.
     * @param forward - The direction to search.
     * @returns the next segment in the specified direction, or the start or end of the tree if there is no next segment.
     */
    private nextSegment;
    /**
     * Finds the nearest reference with ReferenceType.Tile to `startPos` in the direction dictated by `forwards`.
     * Uses depthFirstNodeWalk in addition to block-accelerated functionality. The search position will be included in
     * the nodes to walk, so searching on all positions, including the endpoints, can be considered inclusive.
     * Any out of bound search positions will return undefined, so in order to search the whole string, a forward
     * search can begin at 0, or a backward search can begin at length-1.
     *
     * @param startPos - Position at which to start the search
     * @param clientId - clientId dictating the perspective to search from
     * @param markerLabel - Label of the marker to search for
     * @param forwards - Whether the string should be searched in the forward or backward direction
     */
    searchForMarker(startPos: number, markerLabel: string, forwards?: boolean): Marker | undefined;
    private updateRoot;
    /**
     * Assign sequence number to existing segments affected by an op; update partial lengths to reflect the change
     */
    ackOp(opArgs: IMergeTreeDeltaOpArgs): void;
    private addToPendingList;
    getMarkerFromId(id: string): Marker | undefined;
    /**
     * Given a position specified relative to a marker id, lookup the marker
     * and convert the position to a character position.
     * @param relativePos - Id of marker (may be indirect) and whether position is before or after marker.
     * @param refseq - The reference sequence number at which to compute the position.
     * @param clientId - The client id with which to compute the position.
     */
    posFromRelativePos(relativePos: IRelativePosition, perspective: Perspective): number;
    insertSegments(pos: number, segments: ISegmentPrivate[], perspective: Perspective, stampArg: OperationStamp, opArgs: IMergeTreeDeltaOpArgs | undefined): void;
    /**
     * Resolves a remote client's position against the local sequence
     * and returns the remote client's position relative to the local
     * sequence. The client ref seq must be above the minimum sequence number
     * or the return value will be undefined.
     * Generally this method is used in conjunction with signals which provide
     * point in time values for the below parameters, and is useful for things
     * like displaying user position. It should not be used with persisted values
     * as persisted values will quickly become invalid as the remoteClientRefSeq
     * moves below the minimum sequence number
     * @param remoteClientPosition - The remote client's position to resolve
     * @param remoteClientRefSeq - The reference sequence number of the remote client
     * @param remoteClientId - The client id of the remote client
     */
    resolveRemoteClientPosition(remoteClientPosition: number, remoteClientRefSeq: number, remoteClientId: number): number | undefined;
    private blockInsert;
    private computeObliteratePrecedingInsertion;
    private readonly splitLeafSegment;
    private ensureIntervalBoundary;
    private breakTie;
    private insertingWalk;
    private insertRecursive;
    private split;
    nodeUpdateOrdinals(block: MergeBlock): void;
    /**
     * Annotate a range with properties
     * @param start - The inclusive start position of the range to annotate
     * @param end - The exclusive end position of the range to annotate
     * @param propsOrAdjust - The properties or adjustments to annotate the range with
     * @param refSeq - The reference sequence number to use to apply the annotate
     * @param clientId - The id of the client making the annotate
     * @param seq - The sequence number of the annotate operation
     * @param opArgs - The op args for the annotate op. this is passed to the merge tree callback if there is one
     */
    annotateRange(start: number, end: number, propsOrAdjust: PropsOrAdjust, perspective: Perspective, stamp: OperationStamp, opArgs: IMergeTreeDeltaOpArgs): void;
    private obliterateRangeSided;
    obliterateRange(start: number | InteriorSequencePlace, end: number | InteriorSequencePlace, perspective: Perspective, stampArg: OperationStamp, opArgs: IMergeTreeDeltaOpArgs): void;
    markRangeRemoved(start: number, end: number, perspective: Perspective, stampArg: OperationStamp, opArgs: IMergeTreeDeltaOpArgs): void;
    /**
     * Revert an unacked local op
     */
    rollback(op: IMergeTreeOp, localOpMetadata: SegmentGroup | SegmentGroup[]): void;
    /**
     * Walk the segments up to the current segment and calculate its position
     */
    private findRollbackPosition;
    nodeUpdateLengthNewStructure(node: MergeBlock, recur?: boolean): void;
    removeLocalReferencePosition(lref: LocalReferencePosition): LocalReferencePosition | undefined;
    startOfTree: StartOfTreeSegment;
    endOfTree: EndOfTreeSegment;
    createLocalReferencePosition(_segment: ISegmentPrivate | "start" | "end", offset: number, refType: ReferenceType, properties: PropertySet | undefined, slidingPreference?: SlidingPreference, canSlideToEndpoint?: boolean): LocalReferencePosition;
    /**
     * Segments should either be removed remotely, removed locally, or inserted locally
     *
     * See description of {@link normalizeSegmentsOnRebase}.
     *
     * This normalizes a block of adjacent segments whose positions have collapsed between the time of the original submission and now
     * such that removed segments come after ones that still exist.
     *
     * TODO:AB#34898: It looks like this method has some bugs, search code for this tag for an example test that demonstrates
     * segment normalization yielding an order that remote clients wouldn't have seen.
     */
    private normalizeAdjacentSegments;
    /**
     * Normalizes the segments nearby `segmentGroup` to be ordered as they would if the op submitting `segmentGroup`
     * is rebased to the current sequence number.
     * This primarily affects the ordering of adjacent segments that were removed between the original submission of
     * the local ops and now.
     * Consider the following sequence of events:
     * Initial state: "hi my friend" (seq: 0)
     * - Client 1 inserts "good " to make "hi my good friend" (op1, refSeq: 0)
     * - Client 2 deletes "my " to make "hi friend" (op2, refSeq: 0)
     * - op2 is sequenced giving seq 1
     * - Client 1 disconnects and reconnects at seq: 1.
     *
     * At this point in time, client 1 will have segments ["hi ", Removed"my ", Local"good ", "friend"].
     * However, the rebased op that it submits will cause client 2 to have segments
     * ["hi ", Local"good ", Removed"my ", "friend"].
     *
     * The difference in ordering can be problematic for tie-breaking concurrently inserted segments in some scenarios.
     * Rather than incur extra work tie-breaking these scenarios for all clients, when client 1 rebases its operation,
     * it can fix up its local state to align with what would be expected of the op it resubmits.
     */
    normalizeSegmentsOnRebase(): void;
    private blockUpdate;
    blockUpdatePathLengths(startBlock: MergeBlock | undefined, stamp: OperationStamp, newStructure?: boolean): void;
    private blockUpdateLength;
    /**
     * Map over all visible segments in a given range
     *
     * A segment is visible if its length is greater than 0
     *
     * See `this.nodeMap` for additional documentation
     */
    mapRange<TClientData>(handler: ISegmentAction<TClientData>, perspective: Perspective, accum: TClientData, start?: number, end?: number, splitRange?: boolean, visibilityPerspective?: Perspective): void;
    /**
     * Map over all visible segments in a given range
     *
     * A segment is visible if its length is greater than 0
     *
     * @param refSeq - The sequence number used to determine the range (start
     * and end positions) of segments to iterate over.
     *
     * @param visibilitySeq - An additional sequence number to further configure
     * segment visibility during traversal. This is the same as refSeq, except
     * in the case of obliterate.
     *
     * In the case where `refSeq == visibilitySeq`, mapping is done on all
     * visible segments from `start` to `end`.
     *
     * If a segment is invisible at both `visibilitySeq` and `refSeq`, then it
     * will not be traversed and mapped. Otherwise, if the segment is visible at
     * either seq, it will be mapped.
     *
     * If a segment is only visible at `visibilitySeq`, it will still be mapped,
     * but it will not count as a segment within the range. That is, it will be
     * ignored for the purposes of tracking when traversal should end.
     */
    private nodeMap;
}
//# sourceMappingURL=mergeTree.d.ts.map