1 | import { IIterable, IIterator, IRetroable, IterableOrArrayLike } from "@phosphor/algorithm";
|
2 |
|
3 |
|
4 |
|
5 |
|
6 |
|
7 |
|
8 | export declare class BPlusTree<T> implements IIterable<T>, IRetroable<T> {
|
9 | |
10 |
|
11 |
|
12 |
|
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 | */
|
232 | export declare namespace BPlusTree {
|
233 | |
234 |
|
235 |
|
236 |
|
237 |
|
238 |
|
239 |
|
240 |
|
241 |
|
242 |
|
243 |
|
244 |
|
245 | function from<T>(items: IterableOrArrayLike<T>, cmp: (a: T, b: T) => number): BPlusTree<T>;
|
246 | }
|