UNPKG

6.06 kBTypeScriptView Raw
1declare 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
185declare function createRBTree<K, V>(compare?: (key1: K, key2: K) => number): createRBTree.Tree<K, V>;
186export = createRBTree;