/*!
 * Copyright (c) Microsoft Corporation and contributors. All rights reserved.
 * Licensed under the MIT License.
 */
import type { AttributionKey } from "@fluidframework/runtime-definitions/internal";
import type { IAttributionCollection } from "./attributionCollection.js";
import { LocalReferenceCollection, type LocalReferencePosition } from "./localReference.js";
import { TrackingGroupCollection, type ITrackingGroup } from "./mergeTreeTracking.js";
import type { IJSONSegment, IMarkerDef, ReferenceType } from "./ops.js";
import type { PartialSequenceLengths } from "./partialLengths.js";
import { type Perspective } from "./perspective.js";
import { type PropertySet, type MapLike } from "./properties.js";
import type { ReferencePosition } from "./referencePositions.js";
import type { SegmentGroupCollection } from "./segmentGroupCollection.js";
import { type IHasInsertionInfo, type IMergeNodeInfo, type SegmentWithInfo } from "./segmentInfos.js";
import type { PropertiesManager } from "./segmentPropertiesManager.js";
import type { Side } from "./sequencePlace.js";
import type { OperationStamp, SliceRemoveOperationStamp } from "./stamps.js";
/**
 * This interface exposes internal things to dds that leverage merge tree,
 * like sequence and matrix.
 *
 * We use tiered interface to control visibility of segment properties.
 * This sits between ISegment and ISegmentPrivate. It should only expose
 * things tagged internal.
 *
 * Everything added here beyond ISegment should be optional to keep the ability
 * to implicitly convert between the tiered interfaces.
 *
 * @internal
 */
export interface ISegmentInternal extends ISegment {
    localRefs?: LocalReferenceCollection;
    /**
     * Whether or not this segment is a special segment denoting the start or
     * end of the tree
     *
     * Endpoint segments are imaginary segments positioned immediately before or
     * after the tree. These segments cannot be referenced by regular operations
     * and exist primarily as a bucket for local references to slide onto during
     * deletion of regular segments.
     */
    readonly endpointType?: "start" | "end";
}
/**
 * We use tiered interface to control visibility of segment properties.
 * This is the lowest interface and is not exported, it site below ISegment and ISegmentInternal.
 * It should only expose unexported things.
 *
 * Everything added here beyond ISegmentInternal should be optional to keep the ability
 * to implicitly convert between the tiered interfaces.
 *
 * someday we may split tree leaves from segments, but for now they are the same
 * this is just a convenience type that makes it clear that we need something that is both a segment and a leaf node
 */
export interface ISegmentPrivate extends ISegmentInternal {
    segmentGroups?: SegmentGroupCollection;
    propertyManager?: PropertiesManager;
}
/**
 * Segment leafs are segments that have both IMergeNodeInfo and IHasInsertionInfo. This means they
 * are inserted at a position, and bound via their parent MergeBlock to the merge tree. MergeBlocks'
 * children are either a segment leaf, or another merge block for interior nodes of the tree. When working
 * within the tree it is generally unnecessary to use type coercions methods common to the infos, and segment
 * leafs, as the children of MergeBlocks are already well typed. However, when segments come from outside the
 * merge tree, like via client's public methods, it becomes necessary to use the type coercions methods
 * to ensure the passed in segment objects are correctly bound to the merge tree.
 */
export type ISegmentLeaf = SegmentWithInfo<IMergeNodeInfo & IHasInsertionInfo>;
/**
 * A type-guard which determines if the segment has segment leaf, and
 * returns true if it does, along with applying strong typing.
 * @param nodeLike - The segment-like object to check.
 * @returns True if the segment is a segment leaf, otherwise false.
 */
export declare const isSegmentLeaf: (segmentLike: unknown) => segmentLike is ISegmentLeaf;
/**
 * Converts a segment-like object to a segment leaf object if possible.
 *
 * @param segmentLike - The segment-like object to convert.
 * @returns The segment leaf if the conversion is possible, otherwise undefined.
 */
export declare const toSegmentLeaf: (segmentLike: unknown) => ISegmentLeaf | undefined;
/**
 * Asserts that the segment is a segment leaf. Usage of this function should not produce a user facing error.
 *
 * @param segmentLike - The segment-like object to check.
 * @throws Will throw an error if the segment is not a segment leaf.
 */
export declare const assertSegmentLeaf: (segmentLike: unknown) => asserts segmentLike is ISegmentLeaf;
/**
 * This type is used for building MergeBlocks from segments and other MergeBlocks. We need this
 * type as segments may not yet be bound to the tree, so lack merge node info which is required for
 * segment leafs.
 */
export type IMergeNodeBuilder = MergeBlock | SegmentWithInfo<IHasInsertionInfo>;
/**
 * This type is used by MergeBlocks to define their children, which are either segments or other
 * MergeBlocks.
 */
export type IMergeNode = MergeBlock | ISegmentLeaf;
/**
 * A segment representing a portion of the merge tree.
 * Segments are leaf nodes of the merge tree and contain data.
 * @legacy @beta
 */
export interface ISegment {
    readonly type: string;
    readonly trackingCollection: TrackingGroupCollection;
    /**
     * The length of the contents of the node.
     */
    cachedLength: number;
    /**
     * Stores attribution keys associated with offsets of this segment.
     * This data is only persisted if MergeTree's `attributions.track` flag is set to true.
     * Pending segments (i.e. ones that only exist locally and haven't been acked by the server) also have
     * `attribution === undefined` until ack.
     *
     * Keys can be used opaquely with an IAttributor or a container runtime that provides attribution.
     * @remarks There are plans to make the shape of the data stored extensible in a couple ways:
     *
     * 1. Injection of custom attribution information associated with the segment (ex: copy-paste of
     * content but keeping the old attribution information).
     *
     * 2. Storage of multiple "channels" of information (ex: track property changes separately from insertion,
     * or only attribute certain property modifications, etc.)
     */
    attribution?: IAttributionCollection<AttributionKey>;
    /**
     * Properties that have been added to this segment via annotation.
     */
    properties?: PropertySet;
    clone(): ISegment;
    canAppend(segment: ISegment): boolean;
    append(segment: ISegment): void;
    splitAt(pos: number): ISegment | undefined;
    toJSONObject(): any;
    isLeaf(): this is ISegment;
}
/**
 * Determine if a segment has been removed.
 * @legacy @beta
 */
export declare function segmentIsRemoved(segment: ISegment): boolean;
/**
 * @legacy @beta
 */
export interface ISegmentAction<TClientData> {
    (segment: ISegment, pos: number, refSeq: number, clientId: number, start: number, end: number, accum: TClientData): boolean;
}
export interface ISegmentChanges {
    next?: SegmentWithInfo<IHasInsertionInfo>;
    replaceCurrent?: SegmentWithInfo<IHasInsertionInfo>;
}
export interface InsertContext {
    candidateSegment?: SegmentWithInfo<IHasInsertionInfo>;
    leaf: (segment: ISegmentLeaf | undefined, pos: number, ic: InsertContext) => ISegmentChanges;
    continuePredicate?: (continueFromBlock: MergeBlock) => boolean;
}
export interface ObliterateInfo {
    start: LocalReferencePosition;
    startSide: Side;
    end: LocalReferencePosition;
    endSide: Side;
    refSeq: number;
    stamp: SliceRemoveOperationStamp;
    segmentGroup: SegmentGroup | undefined;
    /**
     * Defined only for unacked obliterates.
     *
     * Contains all segments inserted into the range this obliterate affects where at the time of insertion,
     * this obliterate was the newest concurrent obliterate that overlapped the insertion point (this information
     * is relevant for the tiebreak policy of allowing last-obliterater to insert).
     *
     * We need to keep this around for unacked ops because on reconnect, outstanding local obliterates may have set `obliteratePrecedingInsertion`
     * (tiebreak) on segments they no longer apply to, since the reissued obliterate may affect a smaller range than the original one when content
     * near the obliterate's endpoints was removed by another client between the time of the original obliterate and reissuing.
     */
    tiebreakTrackingGroup: ITrackingGroup | undefined;
}
export interface SegmentGroup {
    segments: ISegmentLeaf[];
    previousProps?: PropertySet[];
    localSeq?: number;
    refSeq: number;
    obliterateInfo?: ObliterateInfo;
}
/**
 * Note that the actual branching factor of the MergeTree is `MaxNodesInBlock - 1`.  This is because
 * the MergeTree always inserts first, then checks for overflow and splits if the child count equals
 * `MaxNodesInBlock`.  (i.e., `MaxNodesInBlock` contains 1 extra slot for temporary storage to
 * facilitate splits.)
 */
export declare const MaxNodesInBlock = 8;
export declare class MergeBlock implements Partial<IMergeNodeInfo> {
    childCount: number;
    children: IMergeNode[];
    needsScour?: boolean;
    parent?: MergeBlock;
    index: number;
    ordinal: string;
    cachedLength: number | undefined;
    /**
     * Maps each tile label in this block to the rightmost (i.e. furthest) marker associated with that tile label.
     * When combined with the tree structure of MergeBlocks, this allows accelerated queries for nearest tile
     * with a certain label before a given position
     */
    rightmostTiles: Readonly<MapLike<Marker>>;
    /**
     * Maps each tile label in this block to the leftmost (i.e. nearest) marker associated with that tile label.
     * When combined with the tree structure of MergeBlocks, this allows accelerated queries for nearest tile
     * with a certain label before a given position
     */
    leftmostTiles: Readonly<MapLike<Marker>>;
    isLeaf(): this is ISegmentInternal;
    /**
     * Supports querying the total length of all descendants of this IMergeBlock from the perspective of any
     * (clientId, seq) within the collab window.
     *
     * @remarks This is only optional for implementation reasons (internal nodes can be created/moved without
     * immediately initializing the partial lengths). Aside from mid-update on tree operations, these lengths
     * objects are always defined.
     */
    partialLengths?: PartialSequenceLengths;
    constructor(childCount: number);
    setOrdinal(child: IMergeNode, index: number): void;
}
export declare function assignChild<C extends IMergeNodeBuilder>(parent: MergeBlock, child: C, index: number, updateOrdinal?: boolean): asserts child is C & IMergeNodeInfo;
export declare function seqLTE(seq: number, minOrRefSeq: number): boolean;
/**
 * @legacy @beta
 */
export declare abstract class BaseSegment implements ISegment {
    cachedLength: number;
    readonly trackingCollection: TrackingGroupCollection;
    /***/
    attribution?: IAttributionCollection<AttributionKey>;
    properties?: PropertySet;
    abstract readonly type: string;
    constructor(properties?: PropertySet);
    hasProperty(key: string): boolean;
    isLeaf(): this is ISegment;
    protected cloneInto(b: ISegment): void;
    canAppend(segment: ISegment): boolean;
    protected addSerializedProps(jseg: IJSONSegment): void;
    abstract toJSONObject(): any;
    splitAt(pos: number): ISegment | undefined;
    abstract clone(): ISegment;
    append(other: ISegment): void;
    protected abstract createSplitSegmentAt(pos: number): BaseSegment | undefined;
}
/**
 * The special-cased property key that tracks the id of a {@link Marker}.
 *
 * @remarks In general, marker ids should be accessed using the inherent method
 * {@link Marker.getId}. Marker ids should not be updated after creation.
 * @legacy @beta
 */
export declare const reservedMarkerIdKey = "markerId";
/**
 * @internal
 */
export declare const reservedMarkerSimpleTypeKey = "markerSimpleType";
/**
 * @legacy @beta
 */
export interface IJSONMarkerSegment extends IJSONSegment {
    marker: IMarkerDef;
}
/**
 * Markers are a special kind of segment that do not hold any content.
 *
 * Markers with a reference type of {@link ReferenceType.Tile} support spatially
 * accelerated queries for finding the next marker to the left or right of it in
 * sub-linear time. This is useful, for example, in the case of jumping from the
 * start of a paragraph to the end, assuming a paragraph is bound by markers at
 * the start and end.
 *
 * @legacy @beta
 */
export declare class Marker extends BaseSegment implements ReferencePosition, ISegment {
    refType: ReferenceType;
    static readonly type = "Marker";
    static is(segment: ISegment): segment is Marker;
    readonly type = "Marker";
    static make(refType: ReferenceType, props?: PropertySet): Marker;
    constructor(refType: ReferenceType, props?: PropertySet);
    toJSONObject(): IJSONMarkerSegment;
    static fromJSONObject(spec: IJSONSegment): Marker | undefined;
    clone(): Marker;
    getSegment(): Marker;
    getOffset(): number;
    getProperties(): PropertySet | undefined;
    getId(): string | undefined;
    toString(): string;
    protected createSplitSegmentAt(pos: number): undefined;
    canAppend(segment: ISegment): boolean;
    append(): void;
}
/**
 * Returns a stamp that occurs at the minimum sequence number.
 * @privateRemarks
 * This is a free function over something obtainable on CollaborationWindow to avoid exposing Perspective
 * and OperationStamp from the package (even internally), at least for now.
 * If/when `Client`'s API is refactored to be structured similarly to MergeTree (so that SharedString passes in
 * things closer to `Perspective`s when calling methods on `Client` rather than refSeq/localSeq/clientId etc),
 * it may be more reasonable to expose this more directly on `CollaborationWindow`.
 */
export declare function getMinSeqStamp(collabWindow: CollaborationWindow): OperationStamp;
/**
 * Returns a perspective representing a readonly client's view of the tree at the minimum sequence number.
 * @privateRemarks
 * This is a free function over something obtainable on CollaborationWindow to avoid exposing Perspective
 * and OperationStamp from the package (even internally), at least for now.
 * If/when `Client`'s API is refactored to be structured similarly to MergeTree (so that SharedString passes in
 * things closer to `Perspective`s when calling methods on `Client` rather than refSeq/localSeq/clientId etc),
 * it may be more reasonable to expose this more directly on `CollaborationWindow`.
 */
export declare function getMinSeqPerspective(collabWindow: CollaborationWindow): Perspective;
/**
 * This class is used to track facts about the current window of collaboration. This window is defined by the server
 * specified minimum sequence number to the last sequence number seen. Additionally, it track state for outstanding
 * local operations.
 * @internal
 */
export declare class CollaborationWindow {
    clientId: number;
    collaborating: boolean;
    /**
     * Lowest-numbered segment in window; no client can reference a state before this one
     */
    minSeq: number;
    /**
     * Highest-numbered segment in window and current reference sequence number for this client.
     */
    currentSeq: number;
    /**
     * Highest-numbered localSeq used for a pending segment.
     * Semantically, `localSeq`s provide an ordering on in-flight merge-tree operations:
     * for operations stamped with localSeqs `a` and `b`, `a < b` if and only if `a` was submitted before `b`.
     *
     * @remarks This field is analogous to the `clientSequenceNumber` field on ops, but it's accessible to merge-tree
     * at op submission time rather than only at ack time. This enables more natural state tracking for in-flight ops.
     *
     * It's useful to stamp ops with such an incrementing counter because it enables reasoning about which segments existed from
     * the perspective of the local client at a given point in 'un-acked' time, which is necessary to support the reconnect flow.
     *
     * For example, imagine a client with initial state "123456" submits some ops to create the text "123456ABC".
     * If they insert the "C" first, then "B", then "A", their local segment state might look like this:
     * ```js
     * [
     *     { seq: 0, text: "1234" },
     *     { seq: 5, text: "56" },
     *     { localSeq: 3, seq: UnassignedSequenceNumber, text: "A" },
     *     { localSeq: 2, seq: UnassignedSequenceNumber, text: "B" },
     *     { localSeq: 1, seq: UnassignedSequenceNumber, text: "C" },
     * ]
     * ```
     * (note that localSeq tracks the localSeq at which a segment was inserted)
     *
     * Suppose the client then disconnects and reconnects before any of its insertions are acked. The reconnect flow will necessitate
     * that the client regenerates and resubmits ops based on its current segment state as well as the original op that was sent.
     *
     * It will generate the ops
     * 1. \{ pos: 6, text: "C" \}
     * 2. \{ pos: 6, text: "B" \}
     * 3. \{ pos: 6, text: "A" \}
     *
     * since when submitting the first op, remote clients don't know that this client is about to submit the "A" and "B".
     *
     * On the other hand, imagine if the client had originally submitted the ops in the order "A", "B", "C"
     * such that the segments' local state was instead:
     *
     * ```js
     * [
     *     { seq: 0, text: "1234" },
     *     { seq: 5, text: "56" },
     *     { localSeq: 1, seq: UnassignedSequenceNumber, text: "A" },
     *     { localSeq: 2, seq: UnassignedSequenceNumber, text: "B" },
     *     { localSeq: 3, seq: UnassignedSequenceNumber, text: "C" },
     * ]
     * ```
     *
     * The resubmitted ops should instead be:
     * 1. \{ pos: 6, text: "A" \}
     * 2. \{ pos: 7, text: "B" \}
     * 3. \{ pos: 8, text: "C" \}
     *
     * since remote clients will have seen the "A" when processing the "B" as well as both the "A" and "B" when processing the "C".
     * As can be seen, the list of resubmitted ops is different in the two cases despite the merge-tree's segment state only differing
     * in `localSeq`.
     *
     * This example is a bit simplified from the general scenario: since no remote clients modified the merge-tree while the client
     * was disconnected, the resubmitted ops end up matching the original ops exactly.
     * However, this is not generally true: the production reconnect code takes into account visibility of segments based on both acked
     * and local information as appropriate.
     * Nonetheless, this simple scenario is enough to understand why it's useful to be able to determine if a segment should be visible
     * from a given (seq, localSeq) perspective.
     */
    localSeq: number;
    localPerspective: Perspective;
    loadFrom(a: CollaborationWindow): void;
    mintNextLocalOperationStamp(): OperationStamp;
}
/**
 * Compares two numbers.
 */
export declare const compareNumbers: (a: number, b: number) => number;
/**
 * Compares two strings.
 */
export declare const compareStrings: (a: string, b: string) => number;
//# sourceMappingURL=mergeTreeNodes.d.ts.map