Vihren Atlas

src/vs/base/common/ternarySearchTree.ts

796 LOC · 774 covered · 22 uncovered · 263 ranges · 10093 concepts · 101 introducers · 5199 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.

Files sharing a concept 2

A concept that introduces code in this file also introduces code in these files.

Files with a broader (ancestor) concept 142

These files introduce code for a direct ancestor — a broader, larger-extent concept — of a concept that introduces code here.

showing 50 of 142

Files with a narrower (descendant) concept 8

These files introduce code for a direct descendant — a narrower, larger-intent concept — of a concept that introduces code here.

1 > /*--------------------------------------------------------------------------------------------- ternarySearchTree.ts ×60
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 { shuffle } from './arrays.js';
7 > import { assert } from './assert.js';
8 > import { CharCode } from './charCode.js';
9 > import { compare, compareIgnoreCase, compareSubstring, compareSubstringIgnoreCase } from './strings.js';
10 > import { URI } from './uri.js';
11 >
12 > export interface IKeyIterator<K> {
13 > reset(key: K): this;
14 > next(): this;
15 >
16 > hasNext(): boolean;
17 > cmp(a: string): number;
18 > value(): string;
19 > }
20 >
21 > export class StringIterator implements IKeyIterator<string> {
22 > ternarySearchTree.ts ×5
23 > private _value: string = '';
24 > private _pos: number = 0;
25 > ternarySearchTree.ts ×60
26 > reset(key: string): this {
27 > this._value = key; ternarySearchTree.ts ×5
28 > this._pos = 0;
29 > return this;
30 > }
31 > ternarySearchTree.ts ×60
32 > next(): this {
33 > this._pos += 1; ternarySearchTree.ts ×1
34 > return this;
35 > }
36 > ternarySearchTree.ts ×60
37 > hasNext(): boolean {
38 > return this._pos < this._value.length - 1; ternarySearchTree.ts ×5
39 > }
40 > ternarySearchTree.ts ×60
41 > cmp(a: string): number {
42 > const aCode = a.charCodeAt(0); ternarySearchTree.ts ×5
43 > const thisCode = this._value.charCodeAt(this._pos);
44 > return aCode - thisCode;
45 > }
46 > ternarySearchTree.ts ×60
47 > value(): string {
48 > return this._value[this._pos]; ternarySearchTree.ts ×5
49 > }
50 > } ternarySearchTree.ts ×60
51 >
52 > export class ConfigKeysIterator implements IKeyIterator<string> {
53 >
54 > private _value!: string;
55 > private _from!: number;
56 > private _to!: number;
57 >
58 > constructor(
59 > private readonly _caseSensitive: boolean = true ternarySearchTree.ts ×7
60 > ) { }
61 > ternarySearchTree.ts ×60
62 > reset(key: string): this {
63 > this._value = key; ternarySearchTree.ts ×7
64 > this._from = 0;
65 > this._to = 0;
66 > return this.next();
67 > }
68 > ternarySearchTree.ts ×60
69 > hasNext(): boolean {
70 > return this._to < this._value.length; ternarySearchTree.ts ×7
71 > }
72 > ternarySearchTree.ts ×60
73 > next(): this {
74 > // this._data = key.split(/[\\/]/).filter(s => !!s); ternarySearchTree.ts ×7
75 > this._from = this._to;
76 > let justSeps = true;
77 > for (; this._to < this._value.length; this._to++) {
78 > const ch = this._value.charCodeAt(this._to);
79 > if (ch === CharCode.Period) {
80 > if (justSeps) {
81 > this._from++;
82 > } else {
83 > break;
84 > }
85 > } else {
86 > justSeps = false;
87 > }
88 > }
89 > return this;
90 > }
91 > ternarySearchTree.ts ×60
92 > cmp(a: string): number {
93 > return this._caseSensitive ternarySearchTree.ts ×7
94 > ? compareSubstring(a, this._value, 0, a.length, this._from, this._to)
95 : compareSubstringIgnoreCase(a, this._value, 0, a.length, this._from, this._to);
96 > } ternarySearchTree.ts ×7
97 > ternarySearchTree.ts ×60
98 > value(): string {
99 > return this._value.substring(this._from, this._to); ternarySearchTree.ts ×7
100 > }
101 > } ternarySearchTree.ts ×60
102 >
103 > export class PathIterator implements IKeyIterator<string> {
104 >
105 > private _value!: string;
106 > private _valueLen!: number;
107 > private _from!: number;
108 > private _to!: number;
109 >
110 > constructor(
111 > private readonly _splitOnBackslash: boolean = true, ternarySearchTree.ts ×1
112 > private readonly _caseSensitive: boolean = true
113 > ) { }
114 > ternarySearchTree.ts ×60
115 > reset(key: string): this {
116 > this._from = 0; ternarySearchTree.ts ×3
117 > this._to = 0;
118 > this._value = key;
119 > this._valueLen = key.length;
120 > for (let pos = key.length - 1; pos >= 0; pos--, this._valueLen--) {
121 > const ch = this._value.charCodeAt(pos);
122 > if (!(ch === CharCode.Slash || this._splitOnBackslash && ch === CharCode.Backslash)) {
123 > break;
124 > }
125 > }
126 >
127 > return this.next();
128 > }
129 > ternarySearchTree.ts ×60
130 > hasNext(): boolean {
131 > return this._to < this._valueLen; ternarySearchTree.ts ×1
132 > }
133 > ternarySearchTree.ts ×60
134 > next(): this {
135 > // this._data = key.split(/[\\/]/).filter(s => !!s); ternarySearchTree.ts ×3
136 > this._from = this._to;
137 > let justSeps = true;
138 > for (; this._to < this._valueLen; this._to++) {
139 > const ch = this._value.charCodeAt(this._to);
140 > if (ch === CharCode.Slash || this._splitOnBackslash && ch === CharCode.Backslash) {
141 > if (justSeps) { ternarySearchTree.ts ×1
142 > this._from++;
143 > } else {
144 > break; ternarySearchTree.ts ×1
145 > }
146 > } else { ternarySearchTree.ts ×3
147 > justSeps = false;
148 > }
149 > }
150 > return this;
151 > }
152 > ternarySearchTree.ts ×60
153 > cmp(a: string): number {
154 > return this._caseSensitive ternarySearchTree.ts ×2
155 > ? compareSubstring(a, this._value, 0, a.length, this._from, this._to) ternarySearchTree.ts ×1
156 > : compareSubstringIgnoreCase(a, this._value, 0, a.length, this._from, this._to); ternarySearchTree.ts ×1
157 > } ternarySearchTree.ts ×2
158 > ternarySearchTree.ts ×60
159 > value(): string {
160 > return this._value.substring(this._from, this._to); ternarySearchTree.ts ×1
161 > }
162 > } ternarySearchTree.ts ×60
163 >
164 > const enum UriIteratorState {
165 > Scheme = 1, Authority = 2, Path = 3, Query = 4, Fragment = 5
166 > }
167 >
168 > export class UriIterator implements IKeyIterator<URI> {
169 >
170 > private _pathIterator!: PathIterator;
171 > private _value!: URI;
172 > private _states: UriIteratorState[] = [];
173 > private _stateIdx: number = 0;
174 >
175 > constructor(
176 > private readonly _ignorePathCasing: (uri: URI) => boolean, ternarySearchTree.ts ×1
177 > private readonly _ignoreQueryAndFragment: (uri: URI) => boolean) { }
178 > ternarySearchTree.ts ×60
179 > reset(key: URI): this {
180 > this._value = key; ternarySearchTree.ts ×10
181 > this._states = [];
182 > if (this._value.scheme) {
183 > this._states.push(UriIteratorState.Scheme);
184 > }
185 > if (this._value.authority) {
186 > this._states.push(UriIteratorState.Authority); ternarySearchTree.ts ×3
187 > }
188 > if (this._value.path) { ternarySearchTree.ts ×10
189 > this._pathIterator = new PathIterator(false, !this._ignorePathCasing(key));
190 > this._pathIterator.reset(key.path);
191 > if (this._pathIterator.value()) {
192 > this._states.push(UriIteratorState.Path);
193 > }
194 > }
195 > if (!this._ignoreQueryAndFragment(key)) {
196 > if (this._value.query) { ternarySearchTree.ts ×3
197 > this._states.push(UriIteratorState.Query); ternarySearchTree.ts ×3
198 > }
199 > if (this._value.fragment) { ternarySearchTree.ts ×3
200 this._states.push(UriIteratorState.Fragment);
201 }
202 > } ternarySearchTree.ts ×3
203 > this._stateIdx = 0; ternarySearchTree.ts ×10
204 > return this;
205 > }
206 > ternarySearchTree.ts ×60
207 > next(): this {
208 > if (this._states[this._stateIdx] === UriIteratorState.Path && this._pathIterator.hasNext()) { ternarySearchTree.ts ×10
209 > this._pathIterator.next(); ternarySearchTree.ts ×1
210 > } else { ternarySearchTree.ts ×10
211 > this._stateIdx += 1;
212 > }
213 > return this;
214 > }
215 > ternarySearchTree.ts ×60
216 > hasNext(): boolean {
217 > return (this._states[this._stateIdx] === UriIteratorState.Path && this._pathIterator.hasNext()) ternarySearchTree.ts ×10
218 > || this._stateIdx < this._states.length - 1;
219 > }
220 > ternarySearchTree.ts ×60
221 > cmp(a: string): number {
222 > if (this._states[this._stateIdx] === UriIteratorState.Scheme) { ternarySearchTree.ts ×10
223 > return compareIgnoreCase(a, this._value.scheme);
224 > } else if (this._states[this._stateIdx] === UriIteratorState.Authority) {
225 > return compareIgnoreCase(a, this._value.authority); ternarySearchTree.ts ×3
226 > } else if (this._states[this._stateIdx] === UriIteratorState.Path) { ternarySearchTree.ts ×2
227 > return this._pathIterator.cmp(a); ternarySearchTree.ts ×1
228 > } else if (this._states[this._stateIdx] === UriIteratorState.Query) { ternarySearchTree.ts ×1
229 > return compare(a, this._value.query); ternarySearchTree.ts ×3
230 > } else if (this._states[this._stateIdx] === UriIteratorState.Fragment) {
231 return compare(a, this._value.fragment);
232 }
233 throw new Error();
234 > } ternarySearchTree.ts ×10
235 > ternarySearchTree.ts ×60
236 > value(): string {
237 > if (this._states[this._stateIdx] === UriIteratorState.Scheme) { ternarySearchTree.ts ×10
238 > return this._value.scheme;
239 > } else if (this._states[this._stateIdx] === UriIteratorState.Authority) {
240 > return this._value.authority; ternarySearchTree.ts ×3
241 > } else if (this._states[this._stateIdx] === UriIteratorState.Path) { ternarySearchTree.ts ×2
242 > return this._pathIterator.value();
243 > } else if (this._states[this._stateIdx] === UriIteratorState.Query) {
244 > return this._value.query; ternarySearchTree.ts ×3
245 > } else if (this._states[this._stateIdx] === UriIteratorState.Fragment) {
246 return this._value.fragment;
247 }
248 throw new Error();
249 > } ternarySearchTree.ts ×10
250 > } ternarySearchTree.ts ×60
251 >
252 > abstract class Undef {
253 >
254 > static readonly Val: unique symbol = Symbol('undefined_placeholder');
255 >
256 > static wrap<V>(value: V | undefined): V | typeof Undef.Val {
257 > return value === undefined ? Undef.Val : value; ternarySearchTree.ts ×8
258 > }
259 > ternarySearchTree.ts ×60
260 > static unwrap<V>(value: V | typeof Undef.Val): V | undefined {
261 > return value === Undef.Val ? undefined : value; ternarySearchTree.ts ×8
262 > }
263 > } ternarySearchTree.ts ×60
264 >
265 > class TernarySearchTreeNode<K, V> { ternarySearchTree.ts ×8
266 > height: number = 1;
267 > segment!: string;
268 > value: V | typeof Undef.Val | undefined = undefined;
269 > key: K | undefined = undefined;
270 > left: TernarySearchTreeNode<K, V> | undefined = undefined;
271 > mid: TernarySearchTreeNode<K, V> | undefined = undefined;
272 > right: TernarySearchTreeNode<K, V> | undefined = undefined;
273 > ternarySearchTree.ts ×60
274 > isEmpty(): boolean {
275 return !this.left && !this.mid && !this.right && this.value === undefined;
276 }
277 > ternarySearchTree.ts ×60
278 > rotateLeft() {
279 > const tmp = this.right!; ternarySearchTree.ts ×1
280 > this.right = tmp.left;
281 > tmp.left = this;
282 > this.updateHeight();
283 > tmp.updateHeight();
284 > return tmp;
285 > }
286 > ternarySearchTree.ts ×60
287 > rotateRight() {
288 > const tmp = this.left!; ternarySearchTree.ts ×1
289 > this.left = tmp.right;
290 > tmp.right = this;
291 > this.updateHeight();
292 > tmp.updateHeight();
293 > return tmp;
294 > }
295 > ternarySearchTree.ts ×60
296 > updateHeight() {
297 > this.height = 1 + Math.max(this.heightLeft, this.heightRight); ternarySearchTree.ts ×6
298 > }
299 > ternarySearchTree.ts ×60
300 > balanceFactor() {
301 > return this.heightRight - this.heightLeft; ternarySearchTree.ts ×6
302 > }
303 > ternarySearchTree.ts ×60
304 > get heightLeft() {
305 > return this.left?.height ?? 0; ternarySearchTree.ts ×6
306 > }
307 > ternarySearchTree.ts ×60
308 > get heightRight() {
309 > return this.right?.height ?? 0; ternarySearchTree.ts ×6
310 > }
311 > } ternarySearchTree.ts ×60
312 >
313 > const enum Dir {
314 > Left = -1,
315 > Mid = 0,
316 > Right = 1
317 > }
318 >
319 > export class TernarySearchTree<K, V> {
320 >
321 > static forUris<E>(ignorePathCasing: (key: URI) => boolean = () => false, ignoreQueryAndFragment: (key: URI) => boolean = () => false): TernarySearchTree<URI, E> {
322 > return new TernarySearchTree<URI, E>(new UriIterator(ignorePathCasing, ignoreQueryAndFragment)); ternarySearchTree.ts ×1
323 > }
324 > ternarySearchTree.ts ×60
325 > static forPaths<E>(ignorePathCasing = false): TernarySearchTree<string, E> {
326 > return new TernarySearchTree<string, E>(new PathIterator(undefined, !ignorePathCasing)); ternarySearchTree.ts ×1
327 > }
328 > ternarySearchTree.ts ×60
329 > static forStrings<E>(): TernarySearchTree<string, E> {
330 > return new TernarySearchTree<string, E>(new StringIterator()); ternarySearchTree.ts ×1
331 > }
332 > ternarySearchTree.ts ×60
333 > static forConfigKeys<E>(): TernarySearchTree<string, E> {
334 > return new TernarySearchTree<string, E>(new ConfigKeysIterator()); ternarySearchTree.ts ×1
335 > }
336 > ternarySearchTree.ts ×60
337 > private _iter: IKeyIterator<K>;
338 > private _root: TernarySearchTreeNode<K, V> | undefined;
339 >
340 > constructor(segments: IKeyIterator<K>) {
341 > this._iter = segments; ternarySearchTree.ts ×1
342 > }
343 > ternarySearchTree.ts ×60
344 > clear(): void {
345 > this._root = undefined; ternarySearchTree.ts ×1
346 > }
347 > ternarySearchTree.ts ×60
348 > /**
349 > * Fill the tree with the same value of the given keys
350 > */
351 > fill(element: V, keys: readonly K[]): void;
352 > /**
353 > * Fill the tree with given [key,value]-tuples
354 > */
355 > fill(values: readonly [K, V][]): void;
356 > fill(values: readonly [K, V][] | V, keys?: readonly K[]): void {
357 > if (keys) { arrays.ts ×3
358 > const arr = keys.slice(0); ternarySearchTree.ts ×1
359 > shuffle(arr);
360 > for (const k of arr) {
361 > this.set(k, (<V>values));
362 > }
363 > } else { arrays.ts ×3
364 > const arr = (<[K, V][]>values).slice(0); ternarySearchTree.ts ×1
365 > shuffle(arr);
366 > for (const entry of arr) {
367 > this.set(entry[0], entry[1]);
368 > }
369 > }
370 > } arrays.ts ×3
371 > ternarySearchTree.ts ×60
372 > set(key: K, element: V): V | undefined {
373 > const iter = this._iter.reset(key); ternarySearchTree.ts ×8
374 > let node: TernarySearchTreeNode<K, V>;
375 >
376 > if (!this._root) {
377 > this._root = new TernarySearchTreeNode<K, V>();
378 > this._root.segment = iter.value();
379 > }
380 > const stack: [Dir, TernarySearchTreeNode<K, V>][] = [];
381 >
382 > // find insert_node
383 > node = this._root;
384 > while (true) {
385 > const val = iter.cmp(node.segment);
386 > if (val > 0) {
387 > // left ternarySearchTree.ts ×1
388 > if (!node.left) {
389 > node.left = new TernarySearchTreeNode<K, V>();
390 > node.left.segment = iter.value();
391 > }
392 > stack.push([Dir.Left, node]);
393 > node = node.left;
394 >
395 > } else if (val < 0) { ternarySearchTree.ts ×8
396 > // right ternarySearchTree.ts ×2
397 > if (!node.right) {
398 > node.right = new TernarySearchTreeNode<K, V>(); ternarySearchTree.ts ×1
399 > node.right.segment = iter.value();
400 > }
401 > stack.push([Dir.Right, node]); ternarySearchTree.ts ×2
402 > node = node.right;
403 >
404 > } else if (iter.hasNext()) { ternarySearchTree.ts ×8
405 > // mid ternarySearchTree.ts ×1
406 > iter.next();
407 > if (!node.mid) {
408 > node.mid = new TernarySearchTreeNode<K, V>();
409 > node.mid.segment = iter.value();
410 > }
411 > stack.push([Dir.Mid, node]);
412 > node = node.mid;
413 > } else { ternarySearchTree.ts ×8
414 > break;
415 > }
416 > }
417 >
418 > // set value
419 > const oldElement = Undef.unwrap(node.value);
420 > node.value = Undef.wrap(element);
421 > node.key = key;
422 >
423 > // balance
424 > for (let i = stack.length - 1; i >= 0; i--) {
425 > const node = stack[i][1]; ternarySearchTree.ts ×6
426 >
427 > node.updateHeight();
428 > const bf = node.balanceFactor();
429 >
430 > if (bf < -1 || bf > 1) {
431 > // needs rotate ternarySearchTree.ts ×5
432 > const d1 = stack[i][0];
433 > const d2 = stack[i + 1][0];
434 >
435 > if (d1 === Dir.Right && d2 === Dir.Right) {
436 > //right, right -> rotate left ternarySearchTree.ts ×1
437 > stack[i][1] = node.rotateLeft();
438 >
439 > } else if (d1 === Dir.Left && d2 === Dir.Left) { ternarySearchTree.ts ×5
440 > // left, left -> rotate right ternarySearchTree.ts ×1
441 > stack[i][1] = node.rotateRight();
442 >
443 > } else if (d1 === Dir.Right && d2 === Dir.Left) { ternarySearchTree.ts ×1
444 > // right, left -> double rotate right, left ternarySearchTree.ts ×1
445 > node.right = stack[i + 1][1] = stack[i + 1][1].rotateRight();
446 > stack[i][1] = node.rotateLeft();
447 >
448 > } else if (d1 === Dir.Left && d2 === Dir.Right) { ternarySearchTree.ts ×1
449 > // left, right -> double rotate left, right ternarySearchTree.ts ×1
450 > node.left = stack[i + 1][1] = stack[i + 1][1].rotateLeft();
451 > stack[i][1] = node.rotateRight();
452 >
453 > } else {
454 throw new Error();
455 }
456 > ternarySearchTree.ts ×5
457 > // patch path to parent
458 > if (i > 0) {
459 > switch (stack[i - 1][0]) { ternarySearchTree.ts ×4
460 > case Dir.Left:
461 > stack[i - 1][1].left = stack[i][1]; ternarySearchTree.ts ×1
462 > break;
463 > case Dir.Right: ternarySearchTree.ts ×4
464 > stack[i - 1][1].right = stack[i][1]; ternarySearchTree.ts ×1
465 > break;
466 > case Dir.Mid: ternarySearchTree.ts ×4
467 > stack[i - 1][1].mid = stack[i][1]; ternarySearchTree.ts ×1
468 > break;
469 > } ternarySearchTree.ts ×4
470 > } else { ternarySearchTree.ts ×5
471 > this._root = stack[0][1]; ternarySearchTree.ts ×1
472 > }
473 > } ternarySearchTree.ts ×5
474 > } ternarySearchTree.ts ×6
475 > ternarySearchTree.ts ×8
476 > return oldElement;
477 > }
478 > ternarySearchTree.ts ×60
479 > get(key: K): V | undefined {
480 > return Undef.unwrap(this._getNode(key)?.value); ternarySearchTree.ts ×1
481 > }
482 > ternarySearchTree.ts ×60
483 > private _getNode(key: K) {
484 > const iter = this._iter.reset(key); ternarySearchTree.ts ×2
485 > let node = this._root;
486 > while (node) {
487 > const val = iter.cmp(node.segment); ternarySearchTree.ts ×5
488 > if (val > 0) {
489 > // left ternarySearchTree.ts ×1
490 > node = node.left;
491 > } else if (val < 0) { ternarySearchTree.ts ×5
492 > // right ternarySearchTree.ts ×1
493 > node = node.right;
494 > } else if (iter.hasNext()) { ternarySearchTree.ts ×5
495 > // mid ternarySearchTree.ts ×1
496 > iter.next();
497 > node = node.mid;
498 > } else { ternarySearchTree.ts ×5
499 > break; ternarySearchTree.ts ×1
500 > }
501 > } ternarySearchTree.ts ×5
502 > return node; ternarySearchTree.ts ×2
503 > }
504 > ternarySearchTree.ts ×60
505 > has(key: K): boolean {
506 > const node = this._getNode(key); ternarySearchTree.ts ×1
507 > return !(node?.value === undefined && node?.mid === undefined);
508 > }
509 > ternarySearchTree.ts ×60
510 > delete(key: K): void {
511 > return this._delete(key, false); ternarySearchTree.ts ×5
512 > }
513 > ternarySearchTree.ts ×60
514 > deleteSuperstr(key: K): void {
515 > return this._delete(key, true); ternarySearchTree.ts ×2
516 > }
517 > ternarySearchTree.ts ×60
518 > private _delete(key: K, superStr: boolean): void {
519 > const iter = this._iter.reset(key); ternarySearchTree.ts ×13
520 > const stack: [Dir, TernarySearchTreeNode<K, V>][] = [];
521 > let node = this._root;
522 >
523 > // find node
524 > while (node) {
525 > const val = iter.cmp(node.segment);
526 > if (val > 0) {
527 > // left ternarySearchTree.ts ×1
528 > stack.push([Dir.Left, node]);
529 > node = node.left;
530 > } else if (val < 0) { ternarySearchTree.ts ×13
531 > // right ternarySearchTree.ts ×1
532 > stack.push([Dir.Right, node]);
533 > node = node.right;
534 > } else if (iter.hasNext()) { ternarySearchTree.ts ×13
535 > // mid ternarySearchTree.ts ×1
536 > iter.next();
537 > stack.push([Dir.Mid, node]);
538 > node = node.mid;
539 > } else { ternarySearchTree.ts ×13
540 > break;
541 > }
542 > }
543 >
544 > if (!node) {
545 > // node not found ternarySearchTree.ts ×1
546 > return;
547 > }
548 > ternarySearchTree.ts ×13
549 > if (superStr) {
550 > // removing children, reset height ternarySearchTree.ts ×2
551 > node.left = undefined;
552 > node.mid = undefined;
553 > node.right = undefined;
554 > node.height = 1;
555 > } else { ternarySearchTree.ts ×13
556 > // removing element ternarySearchTree.ts ×5
557 > node.key = undefined;
558 > node.value = undefined;
559 > }
560 > ternarySearchTree.ts ×13
561 > // BST node removal
562 > if (!node.mid && !node.value) {
563 > if (node.left && node.right) { ternarySearchTree.ts ×5
564 > // full node ternarySearchTree.ts ×6
565 > // replace deleted-node with the min-node of the right branch.
566 > // If there is no true min-node leave things as they are
567 > const stack2: typeof stack = [[Dir.Right, node]];
568 > const min = this._min(node.right, stack2);
569 >
570 > if (min.key) {
571 >
572 > node.key = min.key;
573 > node.value = min.value;
574 > node.segment = min.segment;
575 >
576 > // remove NODE (inorder successor can only have right child)
577 > const newChild = min.right;
578 > if (stack2.length > 1) {
579 > const [dir, parent] = stack2[stack2.length - 1]; ternarySearchTree.ts ×3
580 > switch (dir) {
581 > case Dir.Left: parent.left = newChild; break;
582 > case Dir.Mid: assert(false);
583 > case Dir.Right: assert(false);
584 > }
585 > } else { ternarySearchTree.ts ×6
586 > node.right = newChild;
587 > }
588 >
589 > // balance right branch and UPDATE parent pointer for stack
590 > const newChild2 = this._balanceByStack(stack2)!;
591 > if (stack.length > 0) {
592 > const [dir, parent] = stack[stack.length - 1]; ternarySearchTree.ts ×1
593 > switch (dir) {
594 > case Dir.Left: parent.left = newChild2; break;
595 > case Dir.Mid: parent.mid = newChild2; break;
596 > case Dir.Right: parent.right = newChild2; break;
597 > }
598 > } else { ternarySearchTree.ts ×6
599 > this._root = newChild2; ternarySearchTree.ts ×1
600 > }
601 > } ternarySearchTree.ts ×6
602 >
603 > } else { ternarySearchTree.ts ×5
604 > // empty or half empty ternarySearchTree.ts ×2
605 > const newChild = node.left ?? node.right;
606 > if (stack.length > 0) {
607 > const [dir, parent] = stack[stack.length - 1];
608 > switch (dir) {
609 > case Dir.Left: parent.left = newChild; break;
610 > case Dir.Mid: parent.mid = newChild; break;
611 > case Dir.Right: parent.right = newChild; break;
612 > }
613 > } else {
614 > this._root = newChild; ternarySearchTree.ts ×1
615 > }
616 > } ternarySearchTree.ts ×2
617 > } ternarySearchTree.ts ×5
618 > ternarySearchTree.ts ×13
619 > // AVL balance
620 > this._root = this._balanceByStack(stack) ?? this._root;
621 > }
622 > ternarySearchTree.ts ×60
623 > private _min(node: TernarySearchTreeNode<K, V>, stack: [Dir, TernarySearchTreeNode<K, V>][]): TernarySearchTreeNode<K, V> {
624 > while (node.left) { ternarySearchTree.ts ×6
625 > stack.push([Dir.Left, node]); ternarySearchTree.ts ×3
626 > node = node.left;
627 > }
628 > return node; ternarySearchTree.ts ×6
629 > }
630 > ternarySearchTree.ts ×60
631 > private _balanceByStack(stack: [Dir, TernarySearchTreeNode<K, V>][]) {
632 > ternarySearchTree.ts ×13
633 > for (let i = stack.length - 1; i >= 0; i--) {
634 > const node = stack[i][1];
635 >
636 > node.updateHeight();
637 > const bf = node.balanceFactor();
638 > if (bf > 1) {
639 > // right heavy ternarySearchTree.ts ×3
640 > if (node.right!.balanceFactor() >= 0) {
641 > // right, right -> rotate left
642 > stack[i][1] = node.rotateLeft();
643 > } else {
644 > // right, left -> double rotate ternarySearchTree.ts ×3
645 > node.right = node.right!.rotateRight();
646 > stack[i][1] = node.rotateLeft();
647 > }
648 > ternarySearchTree.ts ×3
649 > } else if (bf < -1) { ternarySearchTree.ts ×13
650 > // left heavy ternarySearchTree.ts ×3
651 > if (node.left!.balanceFactor() <= 0) {
652 > // left, left -> rotate right ternarySearchTree.ts ×3
653 > stack[i][1] = node.rotateRight();
654 > } else { ternarySearchTree.ts ×3
655 > // left, right -> double rotate ternarySearchTree.ts ×1
656 > node.left = node.left!.rotateLeft();
657 > stack[i][1] = node.rotateRight();
658 > }
659 > } ternarySearchTree.ts ×3
660 > ternarySearchTree.ts ×13
661 > // patch path to parent
662 > if (i > 0) {
663 > switch (stack[i - 1][0]) { ternarySearchTree.ts ×3
664 > case Dir.Left:
665 > stack[i - 1][1].left = stack[i][1]; ternarySearchTree.ts ×1
666 > break;
667 > case Dir.Right: ternarySearchTree.ts ×3
668 > stack[i - 1][1].right = stack[i][1]; ternarySearchTree.ts ×1
669 > break;
670 > case Dir.Mid: ternarySearchTree.ts ×3
671 > stack[i - 1][1].mid = stack[i][1];
672 > break;
673 > }
674 > } else { ternarySearchTree.ts ×13
675 > return stack[0][1];
676 > }
677 > }
678 > ternarySearchTree.ts ×1
679 > return undefined;
680 > } ternarySearchTree.ts ×13
681 > ternarySearchTree.ts ×60
682 > findSubstr(key: K): V | undefined {
683 > const iter = this._iter.reset(key); ternarySearchTree.ts ×2
684 > let node = this._root;
685 > let candidate: V | undefined = undefined;
686 > while (node) {
687 > const val = iter.cmp(node.segment); ternarySearchTree.ts ×3
688 > if (val > 0) {
689 > // left ternarySearchTree.ts ×1
690 > node = node.left;
691 > } else if (val < 0) { ternarySearchTree.ts ×3
692 > // right ternarySearchTree.ts ×1
693 > node = node.right;
694 > } else if (iter.hasNext()) { ternarySearchTree.ts ×1
695 > // mid
696 > iter.next();
697 > candidate = Undef.unwrap(node.value) || candidate;
698 > node = node.mid;
699 > } else {
700 > break; ternarySearchTree.ts ×1
701 > }
702 > } ternarySearchTree.ts ×3
703 > return node && Undef.unwrap(node.value) || candidate; ternarySearchTree.ts ×2
704 > }
705 > ternarySearchTree.ts ×60
706 > findSuperstr(key: K): IterableIterator<[K, V]> | undefined {
707 > return this._findSuperstrOrElement(key, false); ternarySearchTree.ts ×3
708 > }
709 > ternarySearchTree.ts ×60
710 > private _findSuperstrOrElement(key: K, allowValue: true): IterableIterator<[K, V]> | V | undefined;
711 > private _findSuperstrOrElement(key: K, allowValue: false): IterableIterator<[K, V]> | undefined;
712 > private _findSuperstrOrElement(key: K, allowValue: boolean): IterableIterator<[K, V]> | V | undefined {
713 > const iter = this._iter.reset(key); ternarySearchTree.ts ×3
714 > let node = this._root;
715 > while (node) {
716 > const val = iter.cmp(node.segment); ternarySearchTree.ts ×5
717 > if (val > 0) {
718 > // left ternarySearchTree.ts ×1
719 > node = node.left;
720 > } else if (val < 0) { ternarySearchTree.ts ×5
721 > // right ternarySearchTree.ts ×1
722 > node = node.right;
723 > } else if (iter.hasNext()) { ternarySearchTree.ts ×5
724 > // mid ternarySearchTree.ts ×1
725 > iter.next();
726 > node = node.mid;
727 > } else { ternarySearchTree.ts ×5
728 > // collect ternarySearchTree.ts ×2
729 > if (!node.mid) {
730 if (allowValue) {
731 return Undef.unwrap(node.value);
732 } else {
733 return undefined;
734 }
735 > } else { ternarySearchTree.ts ×2
736 > return this._entries(node.mid);
737 > }
738 > }
739 > } ternarySearchTree.ts ×5
740 > return undefined; ternarySearchTree.ts ×3
741 > }
742 > ternarySearchTree.ts ×60
743 > hasElementOrSubtree(key: K): boolean {
744 return this._findSuperstrOrElement(key, true) !== undefined;
745 }
746 > ternarySearchTree.ts ×60
747 > forEach(callback: (value: V, index: K) => unknown): void {
748 > for (const [key, value] of this) { ternarySearchTree.ts ×2
749 > callback(value, key); ternarySearchTree.ts ×1
750 > }
751 > } ternarySearchTree.ts ×2
752 > ternarySearchTree.ts ×60
753 > *[Symbol.iterator](): IterableIterator<[K, V]> {
754 > yield* this._entries(this._root); ternarySearchTree.ts ×1
755 > }
756 > ternarySearchTree.ts ×60
757 > private _entries(node: TernarySearchTreeNode<K, V> | undefined): IterableIterator<[K, V]> {
758 > const result: [K, V][] = []; ternarySearchTree.ts ×3
759 > this._dfsEntries(node, result);
760 > return result[Symbol.iterator]();
761 > }
762 > ternarySearchTree.ts ×60
763 > private _dfsEntries(node: TernarySearchTreeNode<K, V> | undefined, bucket: [K, V][]) {
764 > // DFS ternarySearchTree.ts ×3
765 > if (!node) {
766 > return; ternarySearchTree.ts ×1
767 > }
768 > if (node.left) { ternarySearchTree.ts ×3
769 > this._dfsEntries(node.left, bucket); ternarySearchTree.ts ×1
770 > }
771 > if (node.value !== undefined) { ternarySearchTree.ts ×3
772 > bucket.push([node.key!, Undef.unwrap(node.value)!]);
773 > }
774 > if (node.mid) {
775 > this._dfsEntries(node.mid, bucket); ternarySearchTree.ts ×1
776 > }
777 > if (node.right) { ternarySearchTree.ts ×3
778 > this._dfsEntries(node.right, bucket); ternarySearchTree.ts ×1
779 > }
780 > } ternarySearchTree.ts ×3
781 > ternarySearchTree.ts ×60
782 > // for debug/testing
783 > _isBalanced(): boolean {
784 > const nodeIsBalanced = (node: TernarySearchTreeNode<unknown, unknown> | undefined): boolean => { ternarySearchTree.ts ×2
785 > if (!node) {
786 > return true;
787 > }
788 > const bf = node.balanceFactor();
789 > if (bf < -1 || bf > 1) {
790 return false;
791 }
792 > return nodeIsBalanced(node.left) && nodeIsBalanced(node.right); ternarySearchTree.ts ×2
793 > };
794 > return nodeIsBalanced(this._root);
795 > }
796 > } ternarySearchTree.ts ×60