RedBlackTree Class
Signature
export declare class RedBlackTree<TKey, TData> implements SortedDictionary<TKey, TData>
Implements: SortedDictionary
Type Parameters
| Parameter | Description |
|---|---|
| TKey | |
| TData |
Constructors
| Constructor | Description |
|---|---|
| (constructor)(compareKeys, aug) | Constructs a new instance of the RedBlackTree class |
Methods
| Method | Return Type | Description |
|---|---|---|
| ceil(key) | RBNode<TKey, TData> | undefined | |
| floor(key) | RBNode<TKey, TData> | undefined | |
| gather(key, matcher) | RBNode<TKey, TData>[] | |
| get(key) | RBNode<TKey, TData> | undefined | |
| isEmpty() | boolean | |
| keys() | TKey[] | |
| map(action, accum) | void | |
| mapRange(action, accum, start, end) | void | |
| max() | RBNode<TKey, TData> | undefined | |
| min() | RBNode<TKey, TData> | undefined | |
| put(key, data, conflict) | void | |
| remove(key) | void | |
| removeExisting(key) | void | |
| size() | number | |
| walk(actions) | void | Depth-first traversal with custom action; if action returns false, traversal is halted. |
| walkBackward(actions) | void | |
| walkExactMatchesBackward(compareFn, actionFn, continueLeftFn, continueRightFn) | void | |
| walkExactMatchesForward(compareFn, actionFn, continueLeftFn, continueRightFn) | void |
Constructor Details
(constructor)
Constructs a new instance of the RedBlackTree class
Signature
constructor(compareKeys: KeyComparer<TKey>, aug?: IRBAugmentation<TKey, TData> | undefined);
Parameters
| Parameter | Modifiers | Type | Description |
|---|---|---|---|
| compareKeys | KeyComparer<TKey> | ||
| aug | optional | IRBAugmentation<TKey, TData> | undefined |
Method Details
ceil
Signature
ceil(key: TKey): RBNode<TKey, TData> | undefined;
Parameters
| Parameter | Type | Description |
|---|---|---|
| key | TKey |
Returns
Return type: RBNode<TKey, TData> | undefined
floor
Signature
floor(key: TKey): RBNode<TKey, TData> | undefined;
Parameters
| Parameter | Type | Description |
|---|---|---|
| key | TKey |
Returns
Return type: RBNode<TKey, TData> | undefined
gather
Signature
gather(key: TKey, matcher: IRBMatcher<TKey, TData>): RBNode<TKey, TData>[];
Parameters
| Parameter | Type | Description |
|---|---|---|
| key | TKey | |
| matcher | IRBMatcher<TKey, TData> |
Returns
Return type: RBNode<TKey, TData>[]
get
Signature
get(key: TKey): RBNode<TKey, TData> | undefined;
Parameters
| Parameter | Type | Description |
|---|---|---|
| key | TKey |
Returns
Return type: RBNode<TKey, TData> | undefined
isEmpty
Signature
isEmpty(): boolean;
Returns
Return type: boolean
keys
Signature
keys(): TKey[];
Returns
Return type: TKey[]
map
Signature
map<TAccum>(action: PropertyAction<TKey, TData>, accum?: TAccum): void;
Type Parameters
| Parameter | Description |
|---|---|
| TAccum |
Parameters
| Parameter | Modifiers | Type | Description |
|---|---|---|---|
| action | PropertyAction<TKey, TData> | ||
| accum | optional | TAccum |
mapRange
Signature
mapRange<TAccum>(action: PropertyAction<TKey, TData>, accum?: TAccum, start?: TKey, end?: TKey): void;
Type Parameters
| Parameter | Description |
|---|---|
| TAccum |
Parameters
| Parameter | Modifiers | Type | Description |
|---|---|---|---|
| action | PropertyAction<TKey, TData> | ||
| accum | optional | TAccum | |
| start | optional | TKey | |
| end | optional | TKey |
max
Signature
max(): RBNode<TKey, TData> | undefined;
Returns
Return type: RBNode<TKey, TData> | undefined
min
Signature
min(): RBNode<TKey, TData> | undefined;
Returns
Return type: RBNode<TKey, TData> | undefined
put
Signature
put(key: TKey, data: TData, conflict?: ConflictAction<TKey, TData>): void;
Parameters
| Parameter | Modifiers | Type | Description |
|---|---|---|---|
| key | TKey | ||
| data | TData | ||
| conflict | optional | ConflictAction<TKey, TData> |
remove
Signature
remove(key: TKey): void;
Parameters
| Parameter | Type | Description |
|---|---|---|
| key | TKey |
removeExisting
Signature
removeExisting(key: TKey): void;
Parameters
| Parameter | Type | Description |
|---|---|---|
| key | TKey |
size
Signature
size(): number;
Returns
Return type: number
walk
Depth-first traversal with custom action; if action returns false, traversal is halted.
Signature
walk(actions: RBNodeActions<TKey, TData>): void;
Parameters
| Parameter | Type | Description |
|---|---|---|
| actions | RBNodeActions<TKey, TData> |
walkBackward
Signature
walkBackward(actions: RBNodeActions<TKey, TData>): void;
Parameters
| Parameter | Type | Description |
|---|---|---|
| actions | RBNodeActions<TKey, TData> |
walkExactMatchesBackward
Signature
walkExactMatchesBackward(compareFn: (node: RBNode<TKey, TData>) => number, actionFn: (node: RBNode<TKey, TData>) => void, continueLeftFn: (number: number) => boolean, continueRightFn: (number: number) => boolean): void;
Parameters
| Parameter | Type | Description |
|---|---|---|
| compareFn | (node: RBNode<TKey, TData>) => number | |
| actionFn | (node: RBNode<TKey, TData>) => void | |
| continueLeftFn | (number: number) => boolean | |
| continueRightFn | (number: number) => boolean |
walkExactMatchesForward
Signature
walkExactMatchesForward(compareFn: (node: RBNode<TKey, TData>) => number, actionFn: (node: RBNode<TKey, TData>) => void, continueLeftFn: (number: number) => boolean, continueRightFn: (number: number) => boolean): void;
Parameters
| Parameter | Type | Description |
|---|---|---|
| compareFn | (node: RBNode<TKey, TData>) => number | |
| actionFn | (node: RBNode<TKey, TData>) => void | |
| continueLeftFn | (number: number) => boolean | |
| continueRightFn | (number: number) => boolean |