/*!
 * Copyright (c) Microsoft Corporation and contributors. All rights reserved.
 * Licensed under the MIT License.
 */
import type { SequenceInterval } from "../intervals/index.js";
/**
 * Intervals sorted by (start, end, interval ID), with a max-end segment tree used to prune
 * overlap searches. Neither records a resolved position - the order is over reference positions,
 * and the tree over indices into that order - and edits preserve the relative order of reference
 * positions, so neither needs rebuilding when the text changes. Adding or removing does
 * invalidate the tree; the next overlap query rebuilds it.
 */
export declare class SequenceIntervalOverlapSet {
    private readonly ordered;
    /**
     * Implicit segment tree over `ordered`: root 1, children of `n` at `2n` and `2n + 1`. Each
     * node holds the *index* of the interval with the greatest end position in its range. Indices
     * rather than intervals so that a stale entry cannot keep a removed interval alive, which in
     * turn lets a mutation mark the tree rather than discard it.
     *
     * A negative root means a rebuild is owed, so the root has to exist from the start for a set
     * which has never been queried to read as stale.
     */
    private readonly maxEnds;
    get intervals(): readonly SequenceInterval[];
    isEmpty(): boolean;
    /**
     * Requires `matches` to be false over a prefix and true thereafter. Returns the first
     * matching index, or this set's size when nothing matches.
     */
    private firstIndexWhere;
    private lowerBound;
    private upperBound;
    /**
     * Returns the interval's index if present, or its insertion point if not. Matches on
     * endpoints and ID rather than object identity, since callers may pass a second instance of
     * an interval this set already holds.
     */
    private locate;
    add(interval: SequenceInterval): void;
    remove(interval: SequenceInterval): void;
    /**
     * Marks the segment tree as owing a rebuild. The nodes are left in place: they are indices, so
     * they hold nothing alive, and retaining the array means a rebuild at the same size reuses it
     * rather than reallocating.
     *
     * A set which has been emptied gives the array up, since nothing will query it and so nothing
     * will rebuild over it - `detachIndex` empties an index one interval at a time, so this is a
     * path the API drives itself. It keeps the two entries the root sentinel needs, there being
     * nothing to gain by trimming below the index written next.
     */
    private discardMaxEnds;
    /** Builds node `node`, covering `[lo, hi)`, and returns the index of its greatest end. */
    private buildMaxEnds;
    private rebuildMaxEndsIfStale;
    /**
     * Collects intervals overlapping `query` from node `node`, covering `[lo, hi)`. `limit` is
     * the first index whose start is after `query`'s end, so ranges beginning at or after it
     * cannot overlap and are skipped, as are subtrees whose greatest end precedes `query`.
     */
    private gatherOverlapping;
    /**
     * Returns the overlapping intervals in set order. Touching endpoints count as overlapping and
     * interval sides are ignored, matching {@link SequenceInterval.overlaps}.
     */
    findOverlapping(query: SequenceInterval): SequenceInterval[];
    /**
     * Returns the run of intervals comparing equal to `query`. `compare` must agree with this
     * set's ordering - comparing a leading prefix of its keys does - so that both bound
     * predicates stay monotone and the run is contiguous.
     */
    private equalRange;
    withSameStart(query: SequenceInterval): SequenceInterval[];
    withSameEndpoints(query: SequenceInterval): SequenceInterval[];
    /**
     * Unlike its siblings this scans every interval, because the set is ordered by start and so
     * intervals sharing an end are not contiguous.
     */
    withSameEnd(query: SequenceInterval): SequenceInterval[];
}
//# sourceMappingURL=sequenceIntervalOverlapSet.d.ts.map