1 | declare namespace createRBTree {
|
2 | /** Represents a functional red-black tree. */
|
3 | interface Tree<K, V> {
|
4 | /** Returns the root node of the tree. */
|
5 | root: Node<K, V>;
|
6 |
|
7 | /** A sorted array of all keys in the tree. */
|
8 | readonly keys: K[];
|
9 |
|
10 | /** An array of all values in the tree, sorted by key. */
|
11 | readonly values: V[];
|
12 |
|
13 | /** The number of items in the tree. */
|
14 | readonly length: number;
|
15 |
|
16 | /**
|
17 | * Creates a new tree with the new `key/value` pair inserted.
|
18 | *
|
19 | * @param key The key of the item to insert.
|
20 | * @param value The value of the item to insert.
|
21 | * @returns A new tree with `key` and `value` inserted.
|
22 | */
|
23 | insert: (key: K, value: V) => Tree<K, V>;
|
24 |
|
25 | /**
|
26 | * Walks a visitor function over the nodes of the tree in order.
|
27 | *
|
28 | * @param visitor The callback to be executed on each node. If a truthy
|
29 | * value is returned from the visitor, then iteration is stopped.
|
30 | * @param lo An optional start of the range to visit (inclusive).
|
31 | * @param hi An optional end of the range to visit (non-inclusive).
|
32 | * @returns The last value returned by the callback.
|
33 | */
|
34 | forEach: {
|
35 | <T>(visitor: (key: K, value: V) => T): T;
|
36 | // tslint:disable-next-line:unified-signatures
|
37 | <T>(visitor: (key: K, value: V) => T, lo: K, hi?: K): T;
|
38 | };
|
39 |
|
40 | /** An iterator pointing to the first element in the tree. */
|
41 | readonly begin: Iterator<K, V>;
|
42 |
|
43 | /** An iterator pointing to the last element in the tree. */
|
44 | readonly end: Iterator<K, V>;
|
45 |
|
46 | /**
|
47 | * Finds an iterator starting at the given element.
|
48 | *
|
49 | * @param position The index at which the iterator gets created.
|
50 | * @returns An iterator starting at `position`.
|
51 | */
|
52 | at: (idx: number) => Iterator<K, V>;
|
53 |
|
54 | /**
|
55 | * Finds the first item in the tree whose key is >= `key`.
|
56 | *
|
57 | * @param key The key to search for.
|
58 | * @returns An iterator at the given element.
|
59 | */
|
60 | ge: (key: K) => Iterator<K, V>;
|
61 |
|
62 | /**
|
63 | * Finds the first item in the tree whose key is > `key`.
|
64 | *
|
65 | * @param key The key to search for.
|
66 | * @returns An iterator at the given element.
|
67 | */
|
68 | gt: (key: K) => Iterator<K, V>;
|
69 |
|
70 | /**
|
71 | * Finds the last item in the tree whose key is < `key`.
|
72 | *
|
73 | * @param key The key to search for.
|
74 | * @returns An iterator at the given element.
|
75 | */
|
76 | lt: (key: K) => Iterator<K, V>;
|
77 |
|
78 | /**
|
79 | * Finds the last item in the tree whose key is <= `key`.
|
80 | *
|
81 | * @param key The key to search for.
|
82 | * @returns An iterator at the given element.
|
83 | */
|
84 | le: (key: K) => Iterator<K, V>;
|
85 |
|
86 | /**
|
87 | * @returns An iterator pointing to the first item in the tree with `key`, otherwise null.
|
88 | */
|
89 | find: (key: K) => Iterator<K, V>;
|
90 |
|
91 | /**
|
92 | * Removes the first item with `key` in the tree.
|
93 | *
|
94 | * @param key The key of the item to remove.
|
95 | * @returns A new tree with the given item removed, if it exists.
|
96 | */
|
97 | remove: (key: K) => Tree<K, V>;
|
98 |
|
99 | /**
|
100 | * Retrieves the value associated with `key`.
|
101 | *
|
102 | * @param key The key of the item to look up.
|
103 | * @returns The value of the first node associated with `key`.
|
104 | */
|
105 | // eslint-disable-next-line @typescript-eslint/no-invalid-void-type
|
106 | get: (key: K) => V | void;
|
107 | }
|
108 |
|
109 | /** Iterates through the nodes in a red-black tree. */
|
110 | interface Iterator<K, V> {
|
111 | /** The tree associated with the iterator. */
|
112 | tree: Tree<K, V>;
|
113 |
|
114 | /** Checks if the iterator is valid. */
|
115 | readonly valid: boolean;
|
116 |
|
117 | /**
|
118 | * The value of the node at the iterator's current position, or null if the
|
119 | * iterator is invalid.
|
120 | */
|
121 | readonly node: Node<K, V> | null;
|
122 |
|
123 | /** Makes a copy of the iterator. */
|
124 | clone: () => Iterator<K, V>;
|
125 |
|
126 | /**
|
127 | * Removes the iterator's current item form the tree.
|
128 | *
|
129 | * @returns A new binary search tree with the item removed.
|
130 | */
|
131 | remove: () => Tree<K, V>;
|
132 |
|
133 | /** The key of the iterator's current item. */
|
134 | readonly key?: K | undefined;
|
135 |
|
136 | /** The value of the iterator's current item. */
|
137 | readonly value?: V | undefined;
|
138 |
|
139 | /** Returns the position of the iterator in the sequence. */
|
140 | readonly index: number;
|
141 |
|
142 | /** Advances the iterator to the next position. */
|
143 | next: () => void;
|
144 |
|
145 | /** If true, then the iterator is not at the end of the sequence. */
|
146 | readonly hasNext: boolean;
|
147 |
|
148 | /**
|
149 | * Updates the value of the iterator's current item.
|
150 | *
|
151 | * @returns A new binary search tree with the corresponding node updated.
|
152 | */
|
153 | update: (value: V) => Tree<K, V>;
|
154 |
|
155 | /** Moves the iterator backward one element. */
|
156 | prev: () => void;
|
157 |
|
158 | /** If true, then the iterator is not at the beginning of the sequence. */
|
159 | readonly hasPrev: boolean;
|
160 | }
|
161 |
|
162 | /** Represents a node in a red-black tree. */
|
163 | interface Node<K, V> {
|
164 | /** The key associated with the node. */
|
165 | key: K;
|
166 |
|
167 | /** The value associated with the node. */
|
168 | value: V;
|
169 |
|
170 | /** The left subtree of the node. */
|
171 | left: Tree<K, V>;
|
172 |
|
173 | /** The right subtree of the node. */
|
174 | right: Tree<K, V>;
|
175 | }
|
176 | }
|
177 |
|
178 | /**
|
179 | * Creates an empty red-black tree.
|
180 | *
|
181 | * @param compare Optional comparison function, same semantics as array.sort().
|
182 | * @returns An empty tree ordered by `compare`.
|
183 | */
|
184 | // eslint-disable-next-line @definitelytyped/no-unnecessary-generics
|
185 | declare function createRBTree<K, V>(compare?: (key1: K, key2: K) => number): createRBTree.Tree<K, V>;
|
186 | export = createRBTree;
|