src/vs/base/common/prefixTree.ts
259 LOC · 251 covered · 8 uncovered · 61 ranges · 184 concepts · 26 introducers · 116 tests
File neighbourhood
The centred file is linked to every concept that introduces one of its ranges, every test that runs code from the file, and the gray connector concepts standing between those tests and the file's own introducer concepts. Undirected links join concepts to every file where they introduce source and concepts to the tests they introduce; arrows show specialization between the displayed concepts and bridge only concepts omitted from this view. Concept colors match the source ranges below; connector concepts have no source color and are shown in gray.
Focused file, its introducer and connector concepts, their introduced files, and tests that run code from the file
In the embedded map, ordinary wheel input scrolls the page; use the visible controls to zoom and drag to pan. Open the full-screen map for canvas navigation: wheel pans, Ctrl/Command plus wheel zooms, and arrow keys pan when this region is focused. On touch screens, open the full-screen map to pan or pinch. If JavaScript or WebGL is unavailable, use the related-file, concept, and source links on this page.
Graph controls are ready.
Interactive rendering requires JavaScript and WebGL. Use the related-file, concept, and source links on this page while the interactive map is unavailable.
1
>
/*---------------------------------------------------------------------------------------------
prefixTree.ts ×19
2
>
* Copyright (c) Microsoft Corporation. All rights reserved.
3
>
* Licensed under the MIT License. See License.txt in the project root for license information.
4
>
*--------------------------------------------------------------------------------------------*/
5
>
6
>
import { Iterable } from './iterator.js';
7
>
8
>
const unset = Symbol('unset');
9
>
10
>
export interface IPrefixTreeNode<T> {
11
>
/** Possible children of the node. */
12
>
children?: ReadonlyMap<string, Node<T>>;
13
>
14
>
/** The value if data exists for this node in the tree. Mutable. */
15
>
value: T | undefined;
16
>
}
17
>
18
>
/**
19
>
* A simple prefix tree implementation where a value is stored based on
20
>
* well-defined prefix segments.
21
>
*/
22
>
export class WellDefinedPrefixTree<V> {
24
>
private _size = 0;
26
>
/** Tree size, not including the root. */
27
>
public get size() {
29
>
}
31
>
/** Gets the top-level nodes of the tree */
32
>
public get nodes(): Iterable<IPrefixTreeNode<V>> {
33
return this.root.children?.values() || Iterable.empty();
34
}
36
>
/** Gets the top-level nodes of the tree */
37
>
public get entries(): Iterable<[string, IPrefixTreeNode<V>]> {
38
return this.root.children?.entries() || Iterable.empty();
39
}
41
>
/**
42
>
* Inserts a new value in the prefix tree.
43
>
* @param onNode - called for each node as we descend to the insertion point,
44
>
* including the insertion point itself.
45
>
*/
46
>
insert(key: Iterable<string>, value: V, onNode?: (n: IPrefixTreeNode<V>) => void): void {
48
>
}
50
>
/** Mutates a value in the prefix tree. */
51
>
mutate(key: Iterable<string>, mutate: (value?: V) => V): void {
52
>
this.opNode(key, n => n._value = mutate(n._value === unset ? undefined : n._value));
prefixTree.ts ×1
53
>
}
55
>
/** Mutates nodes along the path in the prefix tree. */
56
>
mutatePath(key: Iterable<string>, mutate: (node: IPrefixTreeNode<V>) => void): void {
57
this.opNode(key, () => { }, n => mutate(n));
58
}
60
>
/** Deletes a node from the prefix tree, returning the value it contained. */
61
>
delete(key: Iterable<string>): V | undefined {
63
>
if (!path) {
65
>
}
67
>
let i = path.length - 1;
68
>
const value = path[i].node._value;
69
>
if (value === unset) {
71
>
}
73
>
this._size--;
74
>
path[i].node._value = unset;
75
>
76
>
for (; i > 0; i--) {
78
>
if (node.children?.size || node._value !== unset) {
79
>
break;
80
>
}
81
>
82
>
path[i - 1].node.children!.delete(part);
83
>
}
85
>
return value;
88
>
/** Deletes a subtree from the prefix tree, returning the values they contained. */
89
>
*deleteRecursive(key: Iterable<string>): Iterable<V> {
91
>
if (!path) {
93
>
}
95
>
const subtree = path[path.length - 1].node;
96
>
97
>
// important: run the deletion before we start to yield results, so that
98
>
// it still runs even if the caller doesn't consumer the iterator
99
>
for (let i = path.length - 1; i > 0; i--) {
101
>
parent.node.children!.delete(path[i].part);
102
>
if (parent.node.children!.size > 0 || parent.node._value !== unset) {
103
>
break;
104
>
}
105
>
}
107
>
for (const node of bfsIterate(subtree)) {
108
>
if (node._value !== unset) {
109
>
this._size--;
110
>
yield node._value;
111
>
}
112
>
}
113
>
114
>
// special case for the root note
115
>
if (subtree === this.root) {
117
>
this.root.children = undefined;
118
>
}
121
>
/** Gets a value from the tree. */
122
>
find(key: Iterable<string>): V | undefined {
124
>
for (const segment of key) {
126
>
if (!next) {
128
>
}
130
>
node = next;
131
>
}
133
>
return node._value === unset ? undefined : node._value;
134
>
}
136
>
/** Gets whether the tree has the key, or a parent of the key, already inserted. */
137
>
hasKeyOrParent(key: Iterable<string>): boolean {
139
>
for (const segment of key) {
140
>
const next = node.children?.get(segment);
141
>
if (!next) {
142
>
return false;
143
>
}
144
>
if (next._value !== unset) {
145
>
return true;
146
>
}
147
>
148
>
node = next;
149
>
}
150
>
151
>
return false;
152
>
}
154
>
/** Gets whether the tree has the given key or any children. */
155
>
hasKeyOrChildren(key: Iterable<string>): boolean {
157
>
for (const segment of key) {
158
>
const next = node.children?.get(segment);
159
>
if (!next) {
160
>
return false;
161
>
}
162
>
163
>
node = next;
164
>
}
165
>
166
>
return true;
167
>
}
169
>
/** Gets whether the tree has the given key. */
170
>
hasKey(key: Iterable<string>): boolean {
172
>
for (const segment of key) {
173
>
const next = node.children?.get(segment);
174
>
if (!next) {
175
>
return false;
176
>
}
177
>
178
>
node = next;
179
>
}
180
>
181
>
return node._value !== unset;
182
>
}
184
>
private getPathToKey(key: Iterable<string>) {
186
>
let i = 0;
187
>
for (const part of key) {
189
>
if (!node) {
191
>
}
193
>
path.push({ part, node });
194
>
i++;
195
>
}
197
>
return path;
198
>
}
200
>
private opNode(key: Iterable<string>, fn: (node: Node<V>) => void, onDescend?: (node: Node<V>) => void): void {
202
>
for (const part of key) {
204
>
const next = new Node<V>();
205
>
node.children = new Map([[part, next]]);
206
>
node = next;
207
>
} else if (!node.children.has(part)) {
209
>
node.children.set(part, next);
210
>
node = next;
212
>
node = node.children.get(part)!;
213
>
}
215
>
}
217
>
const sizeBefore = node._value === unset ? 0 : 1;
218
>
fn(node);
219
>
const sizeAfter = node._value === unset ? 0 : 1;
220
>
this._size += sizeAfter - sizeBefore;
221
>
}
223
>
/** Returns an iterable of the tree values in no defined order. */
224
>
*values() {
226
>
if (_value !== unset) {
227
>
yield _value;
228
>
}
229
>
}
230
>
}
232
>
234
>
const stack = [root];
235
>
while (stack.length > 0) {
236
>
const node = stack.pop()!;
237
>
yield node;
238
>
239
>
if (node.children) {
240
>
for (const child of node.children.values()) {
241
>
stack.push(child);
242
>
}
243
>
}
244
>
}
245
>
}
248
>
public children?: Map<string, Node<T>>;
249
>
250
>
public get value() {
251
>
return this._value === unset ? undefined : this._value;
252
>
}
253
>
254
>
public set value(value: T | undefined) {
255
this._value = value === undefined ? unset : value;
256
}
258
>
public _value: T | typeof unset = unset;