/*!
 * Copyright (c) Microsoft Corporation and contributors. All rights reserved.
 * Licensed under the MIT License.
 */
/**
 * @internal
 */
export declare const RBColor: {
    readonly RED: 0;
    readonly BLACK: 1;
};
/**
 * @internal
 */
export type RBColor = (typeof RBColor)[keyof typeof RBColor];
/**
 * @internal
 */
export interface RBNode<TKey, TData> {
    key: TKey;
    data: TData;
    left: RBNode<TKey, TData> | undefined;
    right: RBNode<TKey, TData> | undefined;
    color: RBColor;
    size: number;
}
/**
 * @internal
 */
export interface IRBAugmentation<TKey, TData> {
    update(node: RBNode<TKey, TData>): void;
}
/**
 * @internal
 */
export interface IRBMatcher<TKey, TData> {
    continueSubtree(node: RBNode<TKey, TData> | undefined, key: TKey): boolean;
    matchNode(node: RBNode<TKey, TData> | undefined, key: TKey): boolean;
}
/**
 * @internal
 */
export interface RBNodeActions<TKey, TData> {
    infix?(node: RBNode<TKey, TData>): boolean;
    pre?(node: RBNode<TKey, TData>): boolean;
    post?(node: RBNode<TKey, TData>): boolean;
    showStructure?: boolean;
}
/**
 * @internal
 */
export interface KeyComparer<TKey> {
    (a: TKey, b: TKey): number;
}
/**
 * @internal
 */
export interface Property<TKey, TData> {
    key: TKey;
    data: TData;
}
/**
 * @internal
 */
export interface PropertyAction<TKey, TData> {
    <TAccum>(p: Property<TKey, TData>, accum?: TAccum): boolean;
}
/**
 * @internal
 */
export interface QProperty<TKey, TData> {
    key?: TKey;
    data?: TData;
}
/**
 * @internal
 */
export type ConflictAction<TKey, TData> = (key: TKey, currentKey: TKey, data: TData, currentData: TData) => QProperty<TKey, TData>;
/**
 * @internal
 */
export interface SortedDictionary<TKey, TData> extends Dictionary<TKey, TData> {
    max(): Property<TKey, TData> | undefined;
    min(): Property<TKey, TData> | undefined;
    mapRange<TAccum>(action: PropertyAction<TKey, TData>, accum?: TAccum, start?: TKey, end?: TKey): void;
}
/**
 * @internal
 */
export interface Dictionary<TKey, TData> {
    get(key: TKey): Property<TKey, TData> | undefined;
    put(key: TKey, data: TData, conflict?: ConflictAction<TKey, TData>): void;
    remove(key: TKey): void;
    map<TAccum>(action: PropertyAction<TKey, TData>, accum?: TAccum): void;
}
/**
 * @internal
 */
export declare class RedBlackTree<TKey, TData> implements SortedDictionary<TKey, TData> {
    private readonly compareKeys;
    private readonly aug?;
    private root;
    constructor(compareKeys: KeyComparer<TKey>, aug?: IRBAugmentation<TKey, TData> | undefined);
    private makeNode;
    private isRed;
    private nodeSize;
    size(): number;
    isEmpty(): boolean;
    get(key: TKey): RBNode<TKey, TData> | undefined;
    private nodeGet;
    private contains;
    gather(key: TKey, matcher: IRBMatcher<TKey, TData>): RBNode<TKey, TData>[];
    private nodeGather;
    walkExactMatchesForward(compareFn: (node: RBNode<TKey, TData>) => number, actionFn: (node: RBNode<TKey, TData>) => void, continueLeftFn: (number: number) => boolean, continueRightFn: (number: number) => boolean): void;
    private nodeWalkExactMatchesForward;
    walkExactMatchesBackward(compareFn: (node: RBNode<TKey, TData>) => number, actionFn: (node: RBNode<TKey, TData>) => void, continueLeftFn: (number: number) => boolean, continueRightFn: (number: number) => boolean): void;
    private nodeWalkExactMatchesBackward;
    put(key: TKey, data: TData, conflict?: ConflictAction<TKey, TData>): void;
    private nodePut;
    private updateLocal;
    private nodeRemoveMin;
    remove(key: TKey): void;
    removeExisting(key: TKey): void;
    private nodeRemove;
    /**
     * Finds the largest node that is less than or equal to a given key.
     */
    floor(key: TKey): RBNode<TKey, TData> | undefined;
    private nodeFloor;
    /**
     * Finds the smallest node that is greater than or equal to a given key.
     */
    ceil(key: TKey): RBNode<TKey, TData> | undefined;
    private nodeCeil;
    min(): RBNode<TKey, TData> | undefined;
    private nodeMin;
    max(): RBNode<TKey, TData> | undefined;
    private nodeMax;
    private rotateRight;
    private rotateLeft;
    private oppositeColor;
    private flipColors;
    private moveRedLeft;
    private moveRedRight;
    private balance;
    mapRange<TAccum>(action: PropertyAction<TKey, TData>, accum?: TAccum, start?: TKey, end?: TKey): void;
    map<TAccum>(action: PropertyAction<TKey, TData>, accum?: TAccum): void;
    keys(): TKey[];
    /**
     * Depth-first traversal with custom action; if action returns
     * false, traversal is halted.
     * @param action - action to apply to each node
     */
    walk(actions: RBNodeActions<TKey, TData>): void;
    walkBackward(actions: RBNodeActions<TKey, TData>): void;
    private nodeWalk;
    private nodeWalkBackward;
    private nodeMap;
}
//# sourceMappingURL=rbTree.d.ts.map