UNPKG

6.22 kBTypeScriptView Raw
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
6declare 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
189declare function createRBTree<K, V>(compare?: (key1: K, key2: K) => number): createRBTree.Tree<K, V>;
190export = createRBTree;