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