/*!
 * Copyright (c) Microsoft Corporation and contributors. All rights reserved.
 * Licensed under the MIT License.
 */
import type { MergeTree } from "./mergeTree.js";
import { type CollaborationWindow, type MergeBlock } from "./mergeTreeNodes.js";
/**
 * Tracks length information for a part of a MergeTree (block) at a given time (seq).
 * These objects are associated with internal nodes (i.e. blocks).
 */
export interface PartialSequenceLength {
    /**
     * Sequence number
     */
    seq: number;
    /**
     * The length of the associated block.
     */
    len: number;
    /**
     * The delta between the current length of the associated block and its length at the previous seq number.
     */
    seglen: number;
    /**
     * clientId for the client that submitted the op with sequence number `seq`.
     */
    clientId?: number;
}
export interface PartialSequenceLengthsOptions {
    verifier?: (partialLengths: PartialSequenceLengths) => void;
    verifyExpected?: (mergeTree: MergeTree, node: MergeBlock, refSeq: number, clientId: number, localSeq?: number) => void;
    zamboni: boolean;
}
/**
 * Keeps track of partial sums of segment lengths for all sequence numbers in the current collaboration window.
 * Only used during active collaboration.
 *
 * This class is associated with an internal node (block) of a MergeTree. It efficiently answers queries of the form
 * "What is the length of `block` from the perspective of some particular seq and clientId?".
 *
 * It also supports incremental updating of state for newly-sequenced ops that don't affect the structure of the
 * MergeTree (in most cases--see AB#31003 or comments on {@link PartialSequenceLengths.update}).
 *
 * To answer these queries, it pre-builds several lists which track the length of the block at a per-sequence-number
 * level. These lists are:
 *
 * 1. (`partialLengths`): Stores the total length of the block.
 * 2. (`perClientAdjustments[clientId]`): Stores adjustments to the base length which account for all changes submitted by `clientId`. [see footnote]
 *
 * The reason both lists are necessary is that resolving the length of the block from the perspective of
 * (clientId, refSeq) requires including both of the following types of segments:
 * 1. Segments sequenced before `refSeq`
 * 2. Segments submitted by `clientId`
 *
 * This is possible with the above bookkeeping, using:
 *
 * (length of the block at the minimum sequence number)
 * + (partialLengths total length at refSeq)
 * + (clientSeqNumbers total length at most recent op)
 * - (clientSeqNumbers total length at refSeq)
 *
 * where the subtraction avoids double-counting segments submitted by clientId sequenced within the collab window.
 *
 * To enable reconnect, if constructed with `computeLocalPartials === true` it also supports querying for the length of
 * the block from the perspective of the local client at a particular `refSeq` and `localSeq`. This computation is
 * similar to the above:
 *
 * (length of the block at the minimum sequence number)
 * + (partialLengths total length at refSeq)
 * + (unsequenced edits' total length submitted before localSeq)
 * + (adjustments for changes double-counted by happening at or before both localSeq and refSeq)
 *
 * This algorithm scales roughly linearly with number of editing clients and the size of the collab window.
 * (certain unlikely sequences of operations may introduce log factors on those variables)
 *
 * @privateRemarks
 * If you are looking to understand this class in more detail, a suggested order of internalization is:
 *
 * 1. The above description and how it relates to the implementation of `getPartialLength` (which implements the above high-level description
 * 2. `PartialSequenceLengthsSet`, which allows binary searching for overall length deltas at a given sequence number and handles updates.
 * 3. The `fromLeaves` method, which is the base case for the [potential] recursion in `combine`
 * 4. The logic in `combine` to aggregate smaller block entries into larger ones
 * 5. The incremental code path of `update`
 */
export declare class PartialSequenceLengths {
    /**
     * The minimumSequenceNumber as defined by the collab window used in the last call to `update`,
     * or if no such calls have been made, the one used on construction.
     */
    minSeq: number;
    static options: PartialSequenceLengthsOptions;
    /**
     * Length of the block this PartialSequenceLength corresponds to when viewed at `minSeq`.
     */
    private minLength;
    /**
     * Total number of segments in the subtree rooted at the block this PartialSequenceLength corresponds to.
     */
    private segmentCount;
    /**
     * List of PartialSequenceLength objects--ordered by increasing seq--giving length information about
     * the block associated with this PartialSequenceLengths object.
     *
     * `minLength + partialLengths[i].len` gives the length of this block when considering the perspective of an observer
     * client who has received edits up to (and including) sequence number `i`.
     */
    private readonly partialLengths;
    /**
     * perClientAdjustments[clientId] contains a PartialSequenceLengthsSet of adjustments to the observer client's
     * perspective (see {@link PartialSequenceLengths.partialLengths}) necessary to account for changes made by
     * that client.
     *
     * As per doc comment on {@link PartialSequenceLengths}, the overall adjustment performed for the perspective of
     * (clientId, refSeq) is given by the sum of length deltas in `perClientAdjustments[clientId]`
     * for all sequence numbers S such that S \>= refSeq.
     *
     * (since these are ordered by sequence number and we cache cumulative sums, this is implemented using two lookups and a subtraction).
     *
     * The specific adjustments are roughly categorized as follows:
     *
     * - Ops submitted by a given client generally receive a partial lengths entry corresponding to their sequence number.
     * e.g. insert of "ABC" at seq 5 will have a per-client adjustment entry of \{ seq: 5, seglen: 3 \}.
     *
     * - When client A deletes a segment concurrently with client B and loses the race (B's delete is sequenced first),
     * A's per-client adjustments will contain an entry with a negative `seglen` corresponding to the length of the segment
     * and a sequence number corresponding to that of B's delete. It will *not* receive a per-client adjustment for its own delete.
     * This ensures that for perspectives (A, refSeq), the deleted segment will show up as a negative delta for all values of refSeq, since:
     * 1. For refSeq \< B's delete, the per-client adjustment will apply and be added to the total length
     * 2. For refSeq \>= B's delete, B's partial length entry in the overall set will apply, and the per-client adjustment will not apply
     *
     * - When client A attempts to insert a segment into a location that is concurrently obliterated by client B immediately upon insertion,
     * A's per-client adjustments will again not include an entry for its own insert.
     * Instead, the entry which would normally contain `seq` equal to that of A's insert would instead have `seq` equal to that of B's obliterate.
     * This gives the overall correct behavior: for any perspective which isn't client A, there is no adjustment necessary anywhere (it's as if
     * the segment never existed). For client A's perspective, the segment should be considered visible until A has acked B's obliterate.
     * This is accomplished as for the perspective (A, refSeq):
     * 1. For refSeq \< B's obliterate, the segment length will be included as part of the per-client adjustment for A
     * 2. For refSeq \>= B's obliterate, the segment will be omitted from the per-client adjustment for A
     *
     * Note that the special-casing for inserting segments that are immediately obliterated is only necessary for segments that never were visible
     * in the tree. If an insert and obliterate are concurrent but the insert is sequenced first, the normal per-client adjustment is fine.
     *
     * The second case (overlapping removal) applies to any combination of remove / obliterate operations.
     */
    private readonly perClientAdjustments;
    /**
     * Contains information required to answer queries for the length of this segment from the perspective of
     * the local client but not including all local segments (i.e., `localSeq !== collabWindow.localSeq`).
     * This field is only computed if requested in the constructor (i.e. `computeLocalPartials === true`).
     *
     * Note that the usage pattern for this list is a bit different from perClientAdjustments: when dealing with perspectives of remote clients,
     * we generally want to know what their view of the block was accounting for all changes made by that client as well as all \<= some refSeq.
     *
     * However, when dealing with perspectives relevant to the local client, we are still interested in changes made \<= some refSeq, but instead
     * of caring about all changes made by the local client, we additionally want the subset of them that were made \<= some localSeq.
     *
     * The PartialSequenceLengthsSets stored in this field therefore track localSeqs rather than seqs (it's still named seq for ease of implementation).
     * Furthermore, when computing the length of the block at a given refSeq/localSeq perspective,
     * rather than add something like `perClientAdjustments[clientId].latestLeq(latestSeq) - perClientAdjustments[clientId].latestLeq(refSeq)` [to
     * get the tail end of adjustments necessary for a remote client client], we instead add `unsequencedRecords.partialLengths.latestLeq(localSeq)`
     * [to get the head end of adjustments necessary for the local client].
     */
    private unsequencedRecords;
    constructor(
    /**
     * The minimumSequenceNumber as defined by the collab window used in the last call to `update`,
     * or if no such calls have been made, the one used on construction.
     */
    minSeq: number, computeLocalPartials: boolean);
    /**
     * Combine the partial lengths of block's children
     * @param block - an interior node. If `recur` is false, it is assumed that each interior node child of this block
     * has its partials up to date.
     * @param collabWindow - segment window of the segment tree containing `block`.
     * @param recur - whether to recursively compute partial lengths for internal children of `block`.
     * This incurs more work, but gives correct bookkeeping in the case that a descendant in the merge tree has been
     * modified without bubbling up the resulting partial length change to this block's partials.
     * @param computeLocalPartials - whether to compute partial length information about local unsequenced ops.
     * This enables querying for the length of the block at a given localSeq, but incurs extra work.
     * Local partial information doesn't support `update`.
     */
    static combine(block: MergeBlock, collabWindow: CollaborationWindow, recur?: boolean, computeLocalPartials?: boolean): PartialSequenceLengths;
    /**
     * Create a `PartialSequenceLengths` which tracks only changes incurred by direct child leaves of `block`.
     */
    private static fromLeaves;
    /**
     * Assuming this segment was removed on insertion, inserts length information about that operation
     * into the appropriate per-client adjustments (the overall view needs no such adjustment since
     * from an observing client's perspective, the segment never exists).
     */
    private static accountForRemoveOnInsert;
    /**
     * Inserts length information about the insertion of `segment` into
     * `combinedPartialLengths.partialLengths` and the appropriate per-client adjustments.
     */
    private static accountForInsertion;
    /**
     * Inserts length information about the removal or obliteration of `segment` into
     * `combinedPartialLengths.partialLengths` and the appropriate per-client adjustments.
     */
    private static accountForRemoval;
    /**
     * If incremental update of partial lengths fails, this gets set to the seq of the failed update.
     * When higher up blocks attempt to incrementally update, they first check if the seq they are updating for
     * matches this value. If it does, they propagate a full refresh instead.
     */
    private lastIncrementalInvalidationSeq;
    update(node: MergeBlock, seq: number, clientId: number, collabWindow: CollaborationWindow): void;
    /**
     * Returns the length of this block as viewed from the perspective of `clientId` at `refSeq`.
     * This is the total length of all segments sequenced at or before refSeq OR submitted by `clientId`.
     * If `clientId` is the local client, `localSeq` can also be provided. In that case, it is the total
     * length of all segments submitted at or before `refSeq` in addition to any local, unacked segments
     * with `segment.localSeq <= localSeq`.
     *
     * Note: the local case (where `localSeq !== undefined`) is only supported on a PartialSequenceLength object
     * constructed with `computeLocalPartials` set to true and not subsequently updated with `update`.
     */
    getPartialLength(refSeq: number, clientId: number, localSeq?: number): number;
    /**
     * Computes the seglen for the double-counted removed overlap at (refSeq, localSeq).
     *
     * Reconnect happens to only need to compute these lengths for two refSeq values: before and
     * after the rebase. Since these lists potentially scale with O(collab window * number of local edits)
     * and potentially need to be queried for each local op that gets rebased,
     * we cache the results for a given refSeq in `this.unsequencedRecords.cachedOverlappingByRefSeq` so
     * that they can be binary-searched the same way the usual partialLengths lists are.
     */
    private computeOverallRefSeqAdjustment;
    toString(glc?: (id: number) => string, indentCount?: number): string;
    private zamboni;
    private addClientAdjustment;
    private addLocalAdjustment;
    /**
     * Returns the partial lengths associated with the latest change associated with `clientId` at or before `refSeq`.
     * Returns undefined if no such change exists.
     */
    private latestClientEntryLEQ;
    /**
     * Get the partial lengths associated with the most recent change received by `clientId`, or undefined
     * if this client has made no changes in this block within the collab window.
     */
    private latestClientEntry;
}
export declare function verifyExpectedPartialLengths(mergeTree: MergeTree, node: MergeBlock, refSeq: number, clientId: number, localSeq?: number): void;
export declare function verifyPartialLengths(partialSeqLengths: PartialSequenceLengths): void;
//# sourceMappingURL=partialLengths.d.ts.map