import type { ITermDictionary } from '../dictionary/ITermDictionary';
import type { IRdfStoreOptions } from '../IRdfStoreOptions';
import type { EncodedQuadTerms, QuadPatternTerms, QuadTerms } from '../PatternTerm';
import { TermOrder } from '../TermOrder';
import type { IRdfStoreIndex } from './IRdfStoreIndex';
/**
 * Tuning options for {@link RdfStoreIndexBTree}.
 * The defaults come from a parameter sweep over WatDiv (1.1M triples), and should rarely need changing.
 */
export interface IRdfStoreIndexBTreeOptions {
    /**
     * The maximum number of quads per leaf.
     * Larger leaves make scans and memory use more compact, but make every single insert shift more quads.
     * On WatDiv, 128 and 256 were up to 1.5 times slower on exact lookups and single inserts,
     * and 512 to 2048 performed the same.
     * @default 512
     */
    leafCapacity?: number;
    /**
     * A batch is merged into the leaves when it holds at least one in this many of the quads in the index,
     * and is inserted one quad at a time otherwise, which is cheaper for small batches into large indexes.
     * On WatDiv, both took about as long for a batch of 7% of the index.
     * @default 32
     */
    mergeThreshold?: number;
    /**
     * The number of quads checked one by one when skipping a group of quads that share a prefix, before
     * searching for its end instead. Groups are often short, for example when counting distinct objects.
     * On WatDiv, 0 made counting distinct objects twice as slow, and 4 to 32 performed the same.
     * @default 8
     */
    linearProbes?: number;
}
/**
 * A position within the leaves of an index.
 * A leaf index equal to the number of leaves means the end has been reached.
 */
export interface IBTreeCursor {
    leaf: number;
    offset: number;
}
/**
 * The quoted triples that a quoted triple pattern at some level of an index can match.
 */
export interface IBTreeCandidates {
    /**
     * The encodings of the matching quoted triples.
     */
    members: Set<number>;
    /**
     * The same encodings, in term order, to jump from one to the next.
     */
    sorted: number[];
}
/**
 * An RDF store index that keeps its quads sorted, in a B+tree of height two:
 * a directory of fixed-size leaves, each of which holds a sorted run of quads as a flat Int32Array.
 *
 * Quads are ordered lexicographically on the order of their terms, which a shared {@link TermOrder}
 * defines. Scans therefore produce sorted results, can skip ahead to a term with a binary search,
 * and count a range without visiting it.
 *
 * Inserting one quad costs a binary search and a shift within one leaf. {@link RdfStoreIndexBTree#setAll}
 * inserts many quads at once by sorting them a single time and merging them into the leaves.
 *
 * Only dictionaries that encode to 32-bit integers are supported, and values are not stored:
 * every quad in the index maps to `true`.
 */
export declare class RdfStoreIndexBTree implements IRdfStoreIndex<number, boolean> {
    readonly features: {
        quotedTripleFiltering: boolean;
    };
    readonly termOrder: TermOrder;
    protected readonly dictionary: ITermDictionary<number>;
    private readonly leafCapacity;
    private readonly mergeThreshold;
    private readonly linearProbes;
    /**
     * The leaves, each holding `sizes[i]` quads of four encodings each. Only the first leaf may be empty,
     * and only when the whole index is.
     */
    leaves: Int32Array[];
    sizes: number[];
    /**
     * Incremented on every change, so that iterators can notice that their position is stale.
     */
    version: number;
    private quadCount;
    /**
     * Distinct term counts by their arguments, which are only valid for the version they were counted at.
     * Unlike nested maps, this index can not read such a count off a map size, and query engines tend to
     * ask for the same counts over and over.
     */
    private readonly termCounts;
    private termCountsVersion;
    /**
     * @param options The store options.
     * @param indexOptions Tuning options for this index.
     */
    constructor(options: IRdfStoreOptions<number>, indexOptions?: IRdfStoreIndexBTreeOptions);
    /**
     * The number of quads in this index.
     */
    get size(): number;
    /**
     * Compare the first `length` components of the quad at `offset` in `data` with those of `key`.
     * @param data A leaf.
     * @param offset The offset of a quad within the leaf.
     * @param key An encoded quad or prefix of one.
     * @param length The number of components to compare.
     */
    compare(data: Int32Array, offset: number, key: ArrayLike<number>, length: number): number;
    /**
     * Move a cursor forward to the first quad for which `skip` is false.
     * `skip` must hold for a (possibly empty) run of quads starting at the cursor, and for none after it.
     * This gallops over the leaves and then searches within one, so it costs logarithmic time in the
     * distance moved.
     * @param cursor The cursor to move.
     * @param skip Whether the quad at an offset within a leaf must be skipped.
     */
    advance(cursor: IBTreeCursor, skip: (data: Int32Array, offset: number) => boolean): void;
    /**
     * A cursor at the first quad whose first `length` components are not before those of `key`.
     * @param key An encoded quad or prefix of one.
     * @param length The number of components to compare.
     * @param after If the cursor must instead be placed after all quads with those components.
     */
    seekKey(key: ArrayLike<number>, length: number, after: boolean): IBTreeCursor;
    /**
     * A cursor at the first quad, or at the end if the index is empty.
     */
    start(): IBTreeCursor;
    /**
     * Move the cursor to the next quad.
     * @param cursor A cursor that is not at the end.
     */
    step(cursor: IBTreeCursor): void;
    /**
     * The number of quads from one cursor up to another.
     * @param from The first cursor.
     * @param to A cursor at or after the first one.
     */
    distance(from: IBTreeCursor, to: IBTreeCursor): number;
    /**
     * Move the cursor past all quads that share their first `length` components with the quad at the cursor.
     *
     * Groups are often only a few quads long, for example when counting distinct objects, so a few quads
     * are checked one by one before falling back to a binary search.
     * @param cursor A cursor that is not at the end.
     * @param length The number of components that define the group.
     */
    skipGroup(cursor: IBTreeCursor, length: number): void;
    /**
     * Move the cursor to the first quad, from the cursor onwards, whose components at the given levels
     * equal those of `ids`, or are among the candidates for that level, skipping over the quads that
     * can not match with a binary search.
     * @param cursor The cursor to move.
     * @param ids The encoded terms to match, of which only the entries at `levels` are considered.
     * @param levels The levels that must match, in ascending order.
     * @param leading The number of levels that are bound to a single term from the first one onwards without a gap.
     * @param candidates For levels with a quoted triple pattern, the quoted triples it matches.
     * @return boolean If a matching quad was found, rather than the end.
     */
    nextMatch(cursor: IBTreeCursor, ids: ArrayLike<number | undefined>, levels: number[], leading: number, candidates?: (IBTreeCandidates | undefined)[]): boolean;
    /**
     * The first of the given encodings, in term order, whose label is above the given one.
     * @param sorted Encodings in term order.
     * @param label A label.
     */
    private nextCandidate;
    /**
     * For each level that holds a quoted triple pattern, the quoted triples in this index that it matches.
     * @param terms Pattern terms, in the component order of this index.
     * @return The candidates per level, undefined if no level holds a quoted triple pattern,
     *         or null if some quoted triple pattern matches nothing.
     */
    protected quotedCandidates(terms: QuadPatternTerms): (IBTreeCandidates | undefined)[] | undefined | null;
    set(key: EncodedQuadTerms<number>, value: boolean): boolean;
    private insertAt;
    remove(key: EncodedQuadTerms<number>): boolean;
    /**
     * Add many quads at once, to the quads that are already present.
     * Nothing is removed, and quads that are already present, or occur more than once in `keys`, are only kept once.
     *
     * The quads are sorted a single time and then merged into the leaves, instead of being inserted one
     * by one, and every new term is added to the term order in a single pass as well.
     * A batch that is small compared to this index is inserted one quad at a time instead,
     * as merging would rewrite every leaf.
     * @param keys Encoded quads in the component order of this index, four entries per quad.
     * @param count The number of quads in `keys`.
     * @return number The number of quads that were not yet present.
     */
    setAll(keys: Int32Array, count: number): number;
    /**
     * Sort encoded quads on the term order, and drop duplicates.
     *
     * This is a least-significant-digit radix sort on term ranks, sixteen bits per pass,
     * which skips the passes in which all quads share the same digit.
     * @param keys Encoded quads, four entries per quad.
     * @param count The number of quads.
     * @return A new array with the sorted unique quads, and the number of quads in it.
     */
    protected sortUnique(keys: Int32Array, count: number): [Int32Array, number];
    get(key: QuadTerms): boolean | undefined;
    getEncoded(key: EncodedQuadTerms<number>): boolean | undefined;
    find(terms: QuadPatternTerms): IterableIterator<QuadTerms>;
    findEncoded(ids: EncodedQuadTerms<number | undefined>, terms: QuadPatternTerms): IterableIterator<EncodedQuadTerms<number>>;
    count(terms: QuadPatternTerms): number;
    /**
     * Count the quads matching `ids` at `levels`, by jumping over each run of matches that share the
     * first `groupLength` components rather than visiting them.
     * @param ids The encoded terms to match.
     * @param levels The levels that must match, in ascending order.
     * @param groupLength A prefix length at which all quads of a group either match or do not.
     * @param candidates For levels with a quoted triple pattern, the quoted triples it matches.
     */
    private countGroups;
    /**
     * The number of levels that are bound to a single term from the first one onwards without a gap.
     * @param levels Bound levels in ascending order.
     * @param candidates For levels with a quoted triple pattern, the quoted triples it matches.
     */
    static leadingLevels(levels: number[], candidates?: (IBTreeCandidates | undefined)[]): number;
    private static filterLevels;
    findTerms(matchTerms: boolean[], filterTerms?: (number | undefined)[]): IterableIterator<number[]>;
    countTerms(matchTerms: boolean[], filterTerms?: (number | undefined)[]): number;
    private countTermsUncached;
}