UNPKG

7.37 kBTypeScriptView Raw
1import { IIterable, IIterator, IRetroable, IterableOrArrayLike } from "@phosphor/algorithm";
2/**
3 * A generic B+ tree.
4 *
5 * #### Notes
6 * Most operations have `O(log32 n)` or better complexity.
7 */
8export declare class BPlusTree<T> implements IIterable<T>, IRetroable<T> {
9 /**
10 * Construct a new B+ tree.
11 *
12 * @param cmp - The item comparison function for the tree.
13 */
14 constructor(cmp: (a: T, b: T) => number);
15 /**
16 * The item comparison function for the tree.
17 *
18 * #### Complexity
19 * `O(1)`
20 */
21 readonly cmp: (a: T, b: T) => number;
22 /**
23 * Whether the tree is empty.
24 *
25 * #### Complexity
26 * `O(1)`
27 */
28 readonly isEmpty: boolean;
29 /**
30 * The size of the tree.
31 *
32 * #### Complexity
33 * `O(1)`
34 */
35 readonly size: number;
36 /**
37 * The first item in the tree.
38 *
39 * This is `undefined` if the tree is empty.
40 *
41 * #### Complexity
42 * `O(log32 n)`
43 */
44 readonly first: T | undefined;
45 /**
46 * The last item in the tree.
47 *
48 * This is `undefined` if the tree is empty.
49 *
50 * #### Complexity
51 * `O(log32 n)`
52 */
53 readonly last: T | undefined;
54 /**
55 * Create an iterator over the items in the tree.
56 *
57 * @returns A new iterator starting with the first item.
58 *
59 * #### Complexity
60 * `O(log32 n)`
61 */
62 iter(): IIterator<T>;
63 /**
64 * Create a reverse iterator over the items in the tree.
65 *
66 * @returns A new iterator starting with the last item.
67 *
68 * #### Complexity
69 * `O(log32 n)`
70 */
71 retro(): IIterator<T>;
72 /**
73 * Create an iterator for a slice of items in the tree.
74 *
75 * @param start - The index of the first item, inclusive. This
76 * should be `< stop`. Negative values are taken as an offset
77 * from the end of the tree. The default is `0`.
78 *
79 * @param stop - The index of the last item, exclusive. This
80 * should be `> start`. Negative values are taken as an offset
81 * from the end of the tree. The default is `size`.
82 *
83 * @returns A new iterator starting with the specified item.
84 *
85 * #### Complexity
86 * `O(log32 n)`
87 */
88 slice(start?: number, stop?: number): IIterator<T>;
89 /**
90 * Create a reverse iterator for a slice of items in the tree.
91 *
92 * @param start - The index of the first item, inclusive. This
93 * should be `> stop`. Negative values are taken as an offset
94 * from the end of the tree. The default is `size - 1`.
95 *
96 * @param stop - The index of the last item, exclusive. This
97 * should be `< start`. Negative values are taken as an offset
98 * from the end of the tree. The default is `-size - 1`.
99 *
100 * @returns A new reverse iterator starting with the specified item.
101 *
102 * #### Complexity
103 * `O(log32 n)`
104 */
105 retroSlice(start?: number, stop?: number): IIterator<T>;
106 /**
107 * Get the item at a particular index.
108 *
109 * @param index - The index of the item of interest. Negative
110 * values are taken as an offset from the end of the tree.
111 *
112 * @returns The item at the specified index, or `undefined` if
113 * the index is out of range.
114 *
115 * #### Complexity
116 * `O(log32 n)`
117 */
118 at(index: number): T | undefined;
119 /**
120 * Test whether the tree has an item which matches a key.
121 *
122 * @param key - The key of interest.
123 *
124 * @param cmp - A function which compares an item against the key.
125 *
126 * @returns `true` if the tree has an item which matches the given
127 * key, `false` otherwise.
128 *
129 * #### Complexity
130 * `O(log32 n)`
131 */
132 has<U>(key: U, cmp: (item: T, key: U) => number): boolean;
133 /**
134 * Get the index of an item which matches a key.
135 *
136 * @param key - The key of interest.
137 *
138 * @param cmp - A function which compares an item against the key.
139 *
140 * @returns The index of the item which matches the given key. A
141 * negative value means that a matching item does not exist in
142 * the tree, but if one did it would reside at `-index - 1`.
143 *
144 * #### Complexity
145 * `O(log32 n)`
146 */
147 indexOf<U>(key: U, cmp: (item: T, key: U) => number): number;
148 /**
149 * Get the item which matches a key.
150 *
151 * @param item - The key of interest.
152 *
153 * @param cmp - A function which compares an item against the key.
154 *
155 * @returns The item which matches the given key, or `undefined` if
156 * the tree does not have a matching item.
157 *
158 * #### Complexity
159 * `O(log32 n)`
160 */
161 get<U>(key: U, cmp: (item: T, key: U) => number): T | undefined;
162 /**
163 * Assign new items to the tree, replacing all current items.
164 *
165 * @param items - The items to assign to the tree.
166 *
167 * #### Complexity
168 * `O(n log32 n)`
169 */
170 assign(items: IterableOrArrayLike<T>): void;
171 /**
172 * Insert an item into the tree.
173 *
174 * @param item - The item of interest.
175 *
176 * @returns If the given item matches an existing item in the tree,
177 * the given item will replace it, and the existing item will be
178 * returned. Otherwise, this method returns `undefined`.
179 *
180 * #### Complexity
181 * `O(log32 n)`
182 */
183 insert(item: T): T | undefined;
184 /**
185 * Update the tree with multiple items.
186 *
187 * @param items - The items to insert into the tree.
188 *
189 * #### Complexity
190 * `O(k log32 n)`
191 */
192 update(items: IterableOrArrayLike<T>): void;
193 /**
194 * Delete an item which matches a particular key.
195 *
196 * @param key - The key of interest.
197 *
198 * @param cmp - A function which compares an item against the key.
199 *
200 * @returns The item removed from the tree, or `undefined` if no
201 * item matched the given key.
202 *
203 * #### Complexity
204 * `O(log32 n)`
205 */
206 delete<U>(key: U, cmp: (item: T, key: U) => number): T | undefined;
207 /**
208 * Remove an item at a particular index.
209 *
210 * @param index - The index of the item to remove. Negative
211 * values are taken as an offset from the end of the tree.
212 *
213 * @returns The item removed from the tree, or `undefined` if
214 * the given index is out of range.
215 *
216 * #### Complexity
217 * `O(log32 n)`
218 */
219 remove(index: number): T | undefined;
220 /**
221 * Clear the contents of the tree.
222 *
223 * #### Complexity
224 * `O(n)`
225 */
226 clear(): void;
227 private _root;
228}
229/**
230 * The namespace for the `BPlusTree` class statics.
231 */
232export declare namespace BPlusTree {
233 /**
234 * Create a new B+ tree populated with the given items.
235 *
236 * @param items - The items to add to the tree.
237 *
238 * @param cmp - The item comparison function for the tree.
239 *
240 * @returns A new B+ tree populated with the given items.
241 *
242 * #### Complexity
243 * `O(n log32 n)`
244 */
245 function from<T>(items: IterableOrArrayLike<T>, cmp: (a: T, b: T) => number): BPlusTree<T>;
246}