src/vs/editor/common/model/intervalTree.ts
1281 LOC · 1177 covered · 104 uncovered · 299 ranges · 1817 concepts · 113 introducers · 886 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
>
/*---------------------------------------------------------------------------------------------
intervalTree.ts ×44
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 { Range } from '../core/range.js';
7
>
import { TrackedRangeStickiness, TrackedRangeStickiness as ActualTrackedRangeStickiness } from '../model.js';
8
>
import { ModelDecorationOptions } from './textModel.js';
9
>
10
>
//
11
>
// The red-black tree is based on the "Introduction to Algorithms" by Cormen, Leiserson and Rivest.
12
>
//
13
>
14
>
export const enum ClassName {
15
>
EditorHintDecoration = 'squiggly-hint',
16
>
EditorInfoDecoration = 'squiggly-info',
17
>
EditorWarningDecoration = 'squiggly-warning',
18
>
EditorErrorDecoration = 'squiggly-error',
19
>
EditorUnnecessaryDecoration = 'squiggly-unnecessary',
20
>
EditorUnnecessaryInlineDecoration = 'squiggly-inline-unnecessary',
21
>
EditorDeprecatedInlineDecoration = 'squiggly-inline-deprecated'
22
>
}
23
>
24
>
export const enum NodeColor {
25
>
Black = 0,
26
>
Red = 1,
27
>
}
28
>
29
>
const enum Constants {
30
>
ColorMask = 0b00000001,
31
>
ColorMaskInverse = 0b11111110,
32
>
ColorOffset = 0,
33
>
34
>
IsVisitedMask = 0b00000010,
35
>
IsVisitedMaskInverse = 0b11111101,
36
>
IsVisitedOffset = 1,
37
>
38
>
IsForValidationMask = 0b00000100,
39
>
IsForValidationMaskInverse = 0b11111011,
40
>
IsForValidationOffset = 2,
41
>
42
>
StickinessMask = 0b00011000,
43
>
StickinessMaskInverse = 0b11100111,
44
>
StickinessOffset = 3,
45
>
46
>
CollapseOnReplaceEditMask = 0b00100000,
47
>
CollapseOnReplaceEditMaskInverse = 0b11011111,
48
>
CollapseOnReplaceEditOffset = 5,
49
>
50
>
IsMarginMask = 0b01000000,
51
>
IsMarginMaskInverse = 0b10111111,
52
>
IsMarginOffset = 6,
53
>
54
>
AffectsFontMask = 0b10000000,
55
>
AffectsFontMaskInverse = 0b01111111,
56
>
AffectsFontOffset = 7,
57
>
58
>
/**
59
>
* Due to how deletion works (in order to avoid always walking the right subtree of the deleted node),
60
>
* the deltas for nodes can grow and shrink dramatically. It has been observed, in practice, that unless
61
>
* the deltas are corrected, integer overflow will occur.
62
>
*
63
>
* The integer overflow occurs when 53 bits are used in the numbers, but we will try to avoid it as
64
>
* a node's delta gets below a negative 30 bits number.
65
>
*
66
>
* MIN SMI (SMall Integer) as defined in v8.
67
>
* one bit is lost for boxing/unboxing flag.
68
>
* one bit is lost for sign flag.
69
>
* See https://thibaultlaurens.github.io/javascript/2013/04/29/how-the-v8-engine-works/#tagged-values
70
>
*/
71
>
MIN_SAFE_DELTA = -(1 << 30),
72
>
/**
73
>
* MAX SMI (SMall Integer) as defined in v8.
74
>
* one bit is lost for boxing/unboxing flag.
75
>
* one bit is lost for sign flag.
76
>
* See https://thibaultlaurens.github.io/javascript/2013/04/29/how-the-v8-engine-works/#tagged-values
77
>
*/
78
>
MAX_SAFE_DELTA = 1 << 30,
79
>
}
80
>
81
>
export function getNodeColor(node: IntervalNode): NodeColor {
83
>
}
85
>
node.metadata = (
86
>
(node.metadata & Constants.ColorMaskInverse) | (color << Constants.ColorOffset)
87
>
);
88
>
}
90
>
return ((node.metadata & Constants.IsVisitedMask) >>> Constants.IsVisitedOffset) === 1;
91
>
}
93
>
node.metadata = (
94
>
(node.metadata & Constants.IsVisitedMaskInverse) | ((value ? 1 : 0) << Constants.IsVisitedOffset)
95
>
);
96
>
}
97
function getNodeIsForValidation(node: IntervalNode): boolean {
98
return ((node.metadata & Constants.IsForValidationMask) >>> Constants.IsForValidationOffset) === 1;
99
}
100
>
function setNodeIsForValidation(node: IntervalNode, value: boolean): void {
intervalTree.ts ×44
101
>
node.metadata = (
102
>
(node.metadata & Constants.IsForValidationMaskInverse) | ((value ? 1 : 0) << Constants.IsForValidationOffset)
103
>
);
104
>
}
105
function getNodeIsInGlyphMargin(node: IntervalNode): boolean {
106
return ((node.metadata & Constants.IsMarginMask) >>> Constants.IsMarginOffset) === 1;
107
}
108
>
function setNodeIsInGlyphMargin(node: IntervalNode, value: boolean): void {
intervalTree.ts ×44
109
>
node.metadata = (
110
>
(node.metadata & Constants.IsMarginMaskInverse) | ((value ? 1 : 0) << Constants.IsMarginOffset)
111
>
);
112
>
}
113
function getNodeAffectsFont(node: IntervalNode): boolean {
114
return ((node.metadata & Constants.AffectsFontMask) >>> Constants.AffectsFontOffset) === 1;
115
}
117
>
node.metadata = (
118
>
(node.metadata & Constants.AffectsFontMaskInverse) | ((value ? 1 : 0) << Constants.AffectsFontOffset)
119
>
);
120
>
}
122
>
return ((node.metadata & Constants.StickinessMask) >>> Constants.StickinessOffset);
123
>
}
124
>
function _setNodeStickiness(node: IntervalNode, stickiness: TrackedRangeStickiness): void {
intervalTree.ts ×44
125
>
node.metadata = (
126
>
(node.metadata & Constants.StickinessMaskInverse) | (stickiness << Constants.StickinessOffset)
127
>
);
128
>
}
130
>
return ((node.metadata & Constants.CollapseOnReplaceEditMask) >>> Constants.CollapseOnReplaceEditOffset) === 1;
131
>
}
132
>
function setCollapseOnReplaceEdit(node: IntervalNode, value: boolean): void {
intervalTree.ts ×44
133
>
node.metadata = (
134
>
(node.metadata & Constants.CollapseOnReplaceEditMaskInverse) | ((value ? 1 : 0) << Constants.CollapseOnReplaceEditOffset)
135
>
);
136
>
}
137
>
export function setNodeStickiness(node: IntervalNode, stickiness: ActualTrackedRangeStickiness): void {
139
>
}
141
>
export class IntervalNode {
142
>
143
>
/**
144
>
* contains binary encoded information for color, visited, isForValidation and stickiness.
145
>
*/
146
>
public metadata: number;
147
>
148
>
public parent: IntervalNode;
149
>
public left: IntervalNode;
150
>
public right: IntervalNode;
151
>
152
>
public start: number;
153
>
public end: number;
154
>
public delta: number;
155
>
public maxEnd: number;
156
>
157
>
public id: string;
158
>
public ownerId: number;
159
>
public options: ModelDecorationOptions;
160
>
161
>
public cachedVersionId: number;
162
>
public cachedAbsoluteStart: number;
163
>
public cachedAbsoluteEnd: number;
164
>
public range: Range | null;
165
>
166
>
constructor(id: string, start: number, end: number) {
167
>
this.metadata = 0;
168
>
169
>
this.parent = this;
170
>
this.left = this;
171
>
this.right = this;
172
>
setNodeColor(this, NodeColor.Red);
173
>
174
>
this.start = start;
175
>
this.end = end;
176
>
// FORCE_OVERFLOWING_TEST: this.delta = start;
177
>
this.delta = 0;
178
>
this.maxEnd = end;
179
>
180
>
this.id = id;
181
>
this.ownerId = 0;
182
>
this.options = null!;
183
>
setNodeIsForValidation(this, false);
184
>
setNodeIsInGlyphMargin(this, false);
185
>
_setNodeStickiness(this, TrackedRangeStickiness.NeverGrowsWhenTypingAtEdges);
186
>
setCollapseOnReplaceEdit(this, false);
187
>
setNodeAffectsFont(this, false);
188
>
189
>
this.cachedVersionId = 0;
190
>
this.cachedAbsoluteStart = start;
191
>
this.cachedAbsoluteEnd = end;
192
>
this.range = null;
193
>
194
>
setNodeIsVisited(this, false);
195
>
}
196
>
197
>
public reset(versionId: number, start: number, end: number, range: Range): void {
199
>
this.end = end;
200
>
this.maxEnd = end;
201
>
this.cachedVersionId = versionId;
202
>
this.cachedAbsoluteStart = start;
203
>
this.cachedAbsoluteEnd = end;
204
>
this.range = range;
205
>
}
207
>
public setOptions(options: ModelDecorationOptions) {
209
>
const className = this.options.className;
210
>
setNodeIsForValidation(this, (
211
>
className === ClassName.EditorErrorDecoration
212
>
|| className === ClassName.EditorWarningDecoration
213
>
|| className === ClassName.EditorInfoDecoration
214
>
));
215
>
setNodeIsInGlyphMargin(this, this.options.glyphMarginClassName !== null);
216
>
_setNodeStickiness(this, <number>this.options.stickiness);
217
>
setCollapseOnReplaceEdit(this, this.options.collapseOnReplaceEdit);
218
>
setNodeAffectsFont(this, this.options.affectsFont ?? false);
219
>
}
221
>
public setCachedOffsets(absoluteStart: number, absoluteEnd: number, cachedVersionId: number): void {
224
>
}
226
>
this.cachedAbsoluteStart = absoluteStart;
227
>
this.cachedAbsoluteEnd = absoluteEnd;
228
>
}
230
>
public detach(): void {
232
>
this.left = null!;
233
>
this.right = null!;
234
>
}
236
>
237
>
export const SENTINEL: IntervalNode = new IntervalNode(null!, 0, 0);
238
>
SENTINEL.parent = SENTINEL;
239
>
SENTINEL.left = SENTINEL;
240
>
SENTINEL.right = SENTINEL;
241
>
setNodeColor(SENTINEL, NodeColor.Black);
242
>
243
>
export class IntervalTree {
244
>
245
>
public root: IntervalNode;
246
>
public requestNormalizeDelta: boolean;
247
>
248
>
constructor() {
250
>
this.requestNormalizeDelta = false;
251
>
}
253
>
public intervalSearch(start: number, end: number, filterOwnerId: number, filterOutValidation: boolean, filterFontDecorations: boolean, cachedVersionId: number, onlyMarginDecorations: boolean): IntervalNode[] {
256
>
}
257
>
return intervalSearch(this, start, end, filterOwnerId, filterOutValidation, filterFontDecorations, cachedVersionId, onlyMarginDecorations);
intervalTree.ts ×9
258
>
}
260
>
public search(filterOwnerId: number, filterOutValidation: boolean, filterFontDecorations: boolean, cachedVersionId: number, onlyMarginDecorations: boolean): IntervalNode[] {
262
>
return [];
263
>
}
264
>
return search(this, filterOwnerId, filterOutValidation, filterFontDecorations, cachedVersionId, onlyMarginDecorations);
intervalTree.ts ×1
267
>
/**
268
>
* Will not set `cachedAbsoluteStart` nor `cachedAbsoluteEnd` on the returned nodes!
269
>
*/
270
>
public collectNodesFromOwner(ownerId: number): IntervalNode[] {
272
>
}
274
>
/**
275
>
* Will not set `cachedAbsoluteStart` nor `cachedAbsoluteEnd` on the returned nodes!
276
>
*/
277
>
public collectNodesPostOrder(): IntervalNode[] {
279
>
}
281
>
public insert(node: IntervalNode): void {
283
>
this._normalizeDeltaIfNecessary();
284
>
}
286
>
public delete(node: IntervalNode): void {
288
>
this._normalizeDeltaIfNecessary();
289
>
}
291
>
public resolveNode(node: IntervalNode, cachedVersionId: number): void {
293
>
let delta = 0;
294
>
while (node !== this.root) {
295
if (node === node.parent.right) {
296
delta += node.parent.delta;
297
}
298
node = node.parent;
299
}
301
>
const nodeStart = initialNode.start + delta;
302
>
const nodeEnd = initialNode.end + delta;
303
>
initialNode.setCachedOffsets(nodeStart, nodeEnd, cachedVersionId);
304
>
}
306
>
public acceptReplace(offset: number, length: number, textLength: number, forceMoveMarkers: boolean): void {
307
>
// Our strategy is to remove all directly impacted nodes, and then add them back to the tree.
intervalTree.ts ×7
308
>
309
>
// (1) collect all nodes that are intersecting this edit as nodes of interest
310
>
const nodesOfInterest = searchForEditing(this, offset, offset + length);
311
>
312
>
// (2) remove all nodes that are intersecting this edit
313
>
for (let i = 0, len = nodesOfInterest.length; i < len; i++) {
315
>
rbTreeDelete(this, node);
316
>
}
318
>
319
>
// (3) edit all tree nodes except the nodes of interest
320
>
noOverlapReplace(this, offset, offset + length, textLength);
321
>
this._normalizeDeltaIfNecessary();
322
>
323
>
// (4) edit the nodes of interest and insert them back in the tree
324
>
for (let i = 0, len = nodesOfInterest.length; i < len; i++) {
326
>
node.start = node.cachedAbsoluteStart;
327
>
node.end = node.cachedAbsoluteEnd;
328
>
nodeAcceptEdit(node, offset, (offset + length), textLength, forceMoveMarkers);
329
>
node.maxEnd = node.end;
330
>
rbTreeInsert(this, node);
331
>
}
333
>
}
335
>
public getAllInOrder(): IntervalNode[] {
337
>
}
339
>
private _normalizeDeltaIfNecessary(): void {
341
>
return;
342
>
}
343
this.requestNormalizeDelta = false;
344
normalizeDelta(this);
347
>
348
>
//#region Delta Normalization
349
function normalizeDelta(T: IntervalTree): void {
350
let node = T.root;
351
let delta = 0;
352
while (node !== SENTINEL) {
353
354
if (node.left !== SENTINEL && !getNodeIsVisited(node.left)) {
355
// go left
356
node = node.left;
357
continue;
358
}
359
360
if (node.right !== SENTINEL && !getNodeIsVisited(node.right)) {
361
// go right
362
delta += node.delta;
363
node = node.right;
364
continue;
365
}
366
367
// handle current node
368
node.start = delta + node.start;
369
node.end = delta + node.end;
370
node.delta = 0;
371
recomputeMaxEnd(node);
372
373
setNodeIsVisited(node, true);
374
375
// going up from this node
376
setNodeIsVisited(node.left, false);
377
setNodeIsVisited(node.right, false);
378
if (node === node.parent.right) {
379
delta -= node.parent.delta;
380
}
381
node = node.parent;
382
}
383
384
setNodeIsVisited(T.root, false);
385
}
387
>
388
>
//#region Editing
389
>
390
>
const enum MarkerMoveSemantics {
391
>
MarkerDefined = 0,
392
>
ForceMove = 1,
393
>
ForceStay = 2
394
>
}
395
>
396
>
function adjustMarkerBeforeColumn(markerOffset: number, markerStickToPreviousCharacter: boolean, checkOffset: number, moveSemantics: MarkerMoveSemantics): boolean {
intervalTree.ts ×3
397
>
if (markerOffset < checkOffset) {
399
>
}
402
>
}
405
>
}
408
>
}
410
>
}
412
>
/**
413
>
* This is a lot more complicated than strictly necessary to maintain the same behaviour
414
>
* as when decorations were implemented using two markers.
415
>
*/
416
>
export function nodeAcceptEdit(node: IntervalNode, start: number, end: number, textLength: number, forceMoveMarkers: boolean): void {
418
>
const startStickToPreviousCharacter = (
419
>
nodeStickiness === TrackedRangeStickiness.AlwaysGrowsWhenTypingAtEdges
422
>
const endStickToPreviousCharacter = (
423
>
nodeStickiness === TrackedRangeStickiness.NeverGrowsWhenTypingAtEdges
426
>
427
>
const deletingCnt = (end - start);
428
>
const insertingCnt = textLength;
429
>
const commonLength = Math.min(deletingCnt, insertingCnt);
430
>
431
>
const nodeStart = node.start;
432
>
let startDone = false;
433
>
434
>
const nodeEnd = node.end;
435
>
let endDone = false;
436
>
437
>
if (start <= nodeStart && nodeEnd <= end && getCollapseOnReplaceEdit(node)) {
439
>
// and the decoration has asked to become collapsed
440
>
node.start = start;
441
>
startDone = true;
442
>
node.end = start;
443
>
endDone = true;
444
>
}
446
>
{
447
>
const moveSemantics = forceMoveMarkers ? MarkerMoveSemantics.ForceMove : (deletingCnt > 0 ? MarkerMoveSemantics.ForceStay : MarkerMoveSemantics.MarkerDefined);
448
>
if (!startDone && adjustMarkerBeforeColumn(nodeStart, startStickToPreviousCharacter, start, moveSemantics)) {
450
>
}
451
>
if (!endDone && adjustMarkerBeforeColumn(nodeEnd, endStickToPreviousCharacter, start, moveSemantics)) {
intervalTree.ts ×13
453
>
}
455
>
456
>
if (commonLength > 0 && !forceMoveMarkers) {
457
>
const moveSemantics = (deletingCnt > insertingCnt ? MarkerMoveSemantics.ForceStay : MarkerMoveSemantics.MarkerDefined);
intervalTree.ts ×3
458
>
if (!startDone && adjustMarkerBeforeColumn(nodeStart, startStickToPreviousCharacter, start + commonLength, moveSemantics)) {
460
>
}
461
>
if (!endDone && adjustMarkerBeforeColumn(nodeEnd, endStickToPreviousCharacter, start + commonLength, moveSemantics)) {
intervalTree.ts ×3
463
>
}
466
>
{
467
>
const moveSemantics = forceMoveMarkers ? MarkerMoveSemantics.ForceMove : MarkerMoveSemantics.MarkerDefined;
468
>
if (!startDone && adjustMarkerBeforeColumn(nodeStart, startStickToPreviousCharacter, end, moveSemantics)) {
470
>
startDone = true;
471
>
}
472
>
if (!endDone && adjustMarkerBeforeColumn(nodeEnd, endStickToPreviousCharacter, end, moveSemantics)) {
intervalTree.ts ×13
474
>
endDone = true;
475
>
}
477
>
478
>
// Finish
479
>
const deltaColumn = (insertingCnt - deletingCnt);
480
>
if (!startDone) {
482
>
}
485
>
}
487
>
if (node.start > node.end) {
489
>
}
492
>
function searchForEditing(T: IntervalTree, start: number, end: number): IntervalNode[] {
intervalTree.ts ×7
493
>
// https://en.wikipedia.org/wiki/Interval_tree#Augmented_tree
494
>
// Now, it is known that two intervals A and B overlap only when both
495
>
// A.low <= B.high and A.high >= B.low. When searching the trees for
496
>
// nodes overlapping with a given interval, you can immediately skip:
497
>
// a) all nodes to the right of nodes whose low value is past the end of the given interval.
498
>
// b) all nodes that have their maximum 'high' value below the start of the given interval.
499
>
let node = T.root;
500
>
let delta = 0;
501
>
let nodeMaxEnd = 0;
502
>
let nodeStart = 0;
503
>
let nodeEnd = 0;
504
>
const result: IntervalNode[] = [];
505
>
let resultLen = 0;
506
>
while (node !== SENTINEL) {
508
>
// going up from this node
509
>
setNodeIsVisited(node.left, false);
510
>
setNodeIsVisited(node.right, false);
511
>
if (node === node.parent.right) {
513
>
}
515
>
continue;
516
>
}
517
>
518
>
if (!getNodeIsVisited(node.left)) {
519
>
// first time seeing this node
520
>
nodeMaxEnd = delta + node.maxEnd;
521
>
if (nodeMaxEnd < start) {
523
>
// there is no need to search this node or its children
524
>
setNodeIsVisited(node, true);
525
>
continue;
526
>
}
528
>
if (node.left !== SENTINEL) {
530
>
node = node.left;
531
>
continue;
532
>
}
535
>
// handle current node
536
>
nodeStart = delta + node.start;
537
>
if (nodeStart > end) {
539
>
// there is no need to search this node or its right subtree
540
>
setNodeIsVisited(node, true);
541
>
continue;
542
>
}
544
>
nodeEnd = delta + node.end;
545
>
if (nodeEnd >= start) {
546
>
node.setCachedOffsets(nodeStart, nodeEnd, 0);
547
>
result[resultLen++] = node;
548
>
}
549
>
setNodeIsVisited(node, true);
550
>
553
>
delta += node.delta;
554
>
node = node.right;
555
>
continue;
556
>
}
559
>
setNodeIsVisited(T.root, false);
560
>
561
>
return result;
562
>
}
564
>
function noOverlapReplace(T: IntervalTree, start: number, end: number, textLength: number): void {
intervalTree.ts ×7
565
>
// https://en.wikipedia.org/wiki/Interval_tree#Augmented_tree
566
>
// Now, it is known that two intervals A and B overlap only when both
567
>
// A.low <= B.high and A.high >= B.low. When searching the trees for
568
>
// nodes overlapping with a given interval, you can immediately skip:
569
>
// a) all nodes to the right of nodes whose low value is past the end of the given interval.
570
>
// b) all nodes that have their maximum 'high' value below the start of the given interval.
571
>
let node = T.root;
572
>
let delta = 0;
573
>
let nodeMaxEnd = 0;
574
>
let nodeStart = 0;
575
>
const editDelta = (textLength - (end - start));
576
>
while (node !== SENTINEL) {
578
>
// going up from this node
579
>
setNodeIsVisited(node.left, false);
580
>
setNodeIsVisited(node.right, false);
581
>
if (node === node.parent.right) {
582
delta -= node.parent.delta;
583
}
585
>
node = node.parent;
586
>
continue;
587
>
}
588
>
589
>
if (!getNodeIsVisited(node.left)) {
590
>
// first time seeing this node
591
>
nodeMaxEnd = delta + node.maxEnd;
592
>
if (nodeMaxEnd < start) {
594
>
// there is no need to search this node or its children
595
>
setNodeIsVisited(node, true);
596
>
continue;
597
>
}
599
>
if (node.left !== SENTINEL) {
601
>
node = node.left;
602
>
continue;
603
>
}
606
>
// handle current node
607
>
nodeStart = delta + node.start;
608
>
if (nodeStart > end) {
609
>
node.start += editDelta;
610
>
node.end += editDelta;
611
>
node.delta += editDelta;
612
>
if (node.delta < Constants.MIN_SAFE_DELTA || node.delta > Constants.MAX_SAFE_DELTA) {
613
T.requestNormalizeDelta = true;
614
}
616
>
// there is no need to search this node or its right subtree
617
>
setNodeIsVisited(node, true);
618
>
continue;
619
>
}
620
621
setNodeIsVisited(node, true);
622
624
// go right
625
delta += node.delta;
626
node = node.right;
627
continue;
628
}
631
>
setNodeIsVisited(T.root, false);
632
>
}
634
>
//#endregion
635
>
636
>
//#region Searching
637
>
638
>
function collectNodesFromOwner(T: IntervalTree, ownerId: number): IntervalNode[] {
intervalTree.ts ×4
639
>
let node = T.root;
640
>
const result: IntervalNode[] = [];
641
>
let resultLen = 0;
642
>
while (node !== SENTINEL) {
643
>
if (getNodeIsVisited(node)) {
644
>
// going up from this node
645
>
setNodeIsVisited(node.left, false);
646
>
setNodeIsVisited(node.right, false);
647
>
node = node.parent;
648
>
continue;
649
>
}
650
>
651
>
if (node.left !== SENTINEL && !getNodeIsVisited(node.left)) {
652
// go left
653
node = node.left;
654
continue;
655
}
657
>
// handle current node
658
>
if (node.ownerId === ownerId) {
659
>
result[resultLen++] = node;
660
>
}
661
>
662
>
setNodeIsVisited(node, true);
663
>
664
>
if (node.right !== SENTINEL && !getNodeIsVisited(node.right)) {
665
// go right
666
node = node.right;
667
continue;
668
}
670
>
671
>
setNodeIsVisited(T.root, false);
672
>
673
>
return result;
674
>
}
677
>
let node = T.root;
678
>
const result: IntervalNode[] = [];
679
>
let resultLen = 0;
680
>
while (node !== SENTINEL) {
682
>
// going up from this node
683
>
setNodeIsVisited(node.left, false);
684
>
setNodeIsVisited(node.right, false);
685
>
node = node.parent;
686
>
continue;
687
>
}
688
>
689
>
if (node.left !== SENTINEL && !getNodeIsVisited(node.left)) {
690
>
// go left
691
>
node = node.left;
692
>
continue;
693
>
}
694
>
695
>
if (node.right !== SENTINEL && !getNodeIsVisited(node.right)) {
696
>
// go right
697
>
node = node.right;
698
>
continue;
699
>
}
700
>
701
>
// handle current node
702
>
result[resultLen++] = node;
703
>
setNodeIsVisited(node, true);
704
>
}
706
>
setNodeIsVisited(T.root, false);
707
>
708
>
return result;
709
>
}
711
>
function search(T: IntervalTree, filterOwnerId: number, filterOutValidation: boolean, filterFontDecorations: boolean, cachedVersionId: number, onlyMarginDecorations: boolean): IntervalNode[] {
intervalTree.ts ×8
712
>
let node = T.root;
713
>
let delta = 0;
714
>
let nodeStart = 0;
715
>
let nodeEnd = 0;
716
>
const result: IntervalNode[] = [];
717
>
let resultLen = 0;
718
>
while (node !== SENTINEL) {
719
>
if (getNodeIsVisited(node)) {
720
>
// going up from this node
721
>
setNodeIsVisited(node.left, false);
722
>
setNodeIsVisited(node.right, false);
723
>
if (node === node.parent.right) {
725
>
}
727
>
continue;
728
>
}
729
>
730
>
if (node.left !== SENTINEL && !getNodeIsVisited(node.left)) {
732
>
node = node.left;
733
>
continue;
734
>
}
736
>
// handle current node
737
>
nodeStart = delta + node.start;
738
>
nodeEnd = delta + node.end;
739
>
740
>
node.setCachedOffsets(nodeStart, nodeEnd, cachedVersionId);
741
>
742
>
let include = true;
743
>
if (filterOwnerId && node.ownerId && node.ownerId !== filterOwnerId) {
744
include = false;
745
}
747
include = false;
748
}
750
include = false;
751
}
753
include = false;
754
}
756
>
if (include) {
757
>
result[resultLen++] = node;
758
>
}
759
>
760
>
setNodeIsVisited(node, true);
761
>
762
>
if (node.right !== SENTINEL && !getNodeIsVisited(node.right)) {
764
>
delta += node.delta;
765
>
node = node.right;
766
>
continue;
767
>
}
769
>
770
>
setNodeIsVisited(T.root, false);
771
>
772
>
return result;
773
>
}
775
>
function intervalSearch(T: IntervalTree, intervalStart: number, intervalEnd: number, filterOwnerId: number, filterOutValidation: boolean, filterFontDecorations: boolean, cachedVersionId: number, onlyMarginDecorations: boolean): IntervalNode[] {
intervalTree.ts ×9
776
>
// https://en.wikipedia.org/wiki/Interval_tree#Augmented_tree
777
>
// Now, it is known that two intervals A and B overlap only when both
778
>
// A.low <= B.high and A.high >= B.low. When searching the trees for
779
>
// nodes overlapping with a given interval, you can immediately skip:
780
>
// a) all nodes to the right of nodes whose low value is past the end of the given interval.
781
>
// b) all nodes that have their maximum 'high' value below the start of the given interval.
782
>
783
>
let node = T.root;
784
>
let delta = 0;
785
>
let nodeMaxEnd = 0;
786
>
let nodeStart = 0;
787
>
let nodeEnd = 0;
788
>
const result: IntervalNode[] = [];
789
>
let resultLen = 0;
790
>
while (node !== SENTINEL) {
791
>
if (getNodeIsVisited(node)) {
792
>
// going up from this node
793
>
setNodeIsVisited(node.left, false);
794
>
setNodeIsVisited(node.right, false);
795
>
if (node === node.parent.right) {
797
>
}
799
>
continue;
800
>
}
801
>
802
>
if (!getNodeIsVisited(node.left)) {
803
>
// first time seeing this node
804
>
nodeMaxEnd = delta + node.maxEnd;
805
>
if (nodeMaxEnd < intervalStart) {
807
>
// there is no need to search this node or its children
808
>
setNodeIsVisited(node, true);
809
>
continue;
810
>
}
812
>
if (node.left !== SENTINEL) {
814
>
node = node.left;
815
>
continue;
816
>
}
818
>
819
>
// handle current node
820
>
nodeStart = delta + node.start;
821
>
if (nodeStart > intervalEnd) {
823
>
// there is no need to search this node or its right subtree
824
>
setNodeIsVisited(node, true);
825
>
continue;
826
>
}
828
>
nodeEnd = delta + node.end;
829
>
830
>
if (nodeEnd >= intervalStart) {
832
>
node.setCachedOffsets(nodeStart, nodeEnd, cachedVersionId);
833
>
834
>
let include = true;
835
>
if (filterOwnerId && node.ownerId && node.ownerId !== filterOwnerId) {
836
include = false;
837
}
839
include = false;
840
}
842
include = false;
843
}
845
include = false;
846
}
848
>
if (include) {
849
>
result[resultLen++] = node;
850
>
}
851
>
}
853
>
setNodeIsVisited(node, true);
854
>
855
>
if (node.right !== SENTINEL && !getNodeIsVisited(node.right)) {
857
>
delta += node.delta;
858
>
node = node.right;
859
>
continue;
860
>
}
862
>
863
>
setNodeIsVisited(T.root, false);
864
>
865
>
return result;
866
>
}
868
>
//#endregion
869
>
870
>
//#region Insertion
871
>
function rbTreeInsert(T: IntervalTree, newNode: IntervalNode): IntervalNode {
intervalTree.ts ×3
872
>
if (T.root === SENTINEL) {
873
>
newNode.parent = SENTINEL;
874
>
newNode.left = SENTINEL;
875
>
newNode.right = SENTINEL;
876
>
setNodeColor(newNode, NodeColor.Black);
877
>
T.root = newNode;
878
>
return T.root;
879
>
}
881
>
treeInsert(T, newNode);
882
>
883
>
recomputeMaxEndWalkToRoot(newNode.parent);
884
>
885
>
// repair tree
886
>
let x = newNode;
890
>
891
>
if (getNodeColor(y) === NodeColor.Red) {
893
>
setNodeColor(y, NodeColor.Black);
894
>
setNodeColor(x.parent.parent, NodeColor.Red);
895
>
x = x.parent.parent;
899
>
leftRotate(T, x);
900
>
}
902
>
setNodeColor(x.parent.parent, NodeColor.Red);
903
>
rightRotate(T, x.parent.parent);
904
>
}
907
>
908
>
if (getNodeColor(y) === NodeColor.Red) {
910
>
setNodeColor(y, NodeColor.Black);
911
>
setNodeColor(x.parent.parent, NodeColor.Red);
912
>
x = x.parent.parent;
916
>
rightRotate(T, x);
917
>
}
919
>
setNodeColor(x.parent.parent, NodeColor.Red);
920
>
leftRotate(T, x.parent.parent);
921
>
}
925
>
setNodeColor(T.root, NodeColor.Black);
926
>
927
>
return newNode;
928
>
}
931
>
let delta: number = 0;
932
>
let x = T.root;
933
>
const zAbsoluteStart = z.start;
934
>
const zAbsoluteEnd = z.end;
935
>
while (true) {
936
>
const cmp = intervalCompare(zAbsoluteStart, zAbsoluteEnd, x.start + delta, x.end + delta);
937
>
if (cmp < 0) {
939
>
// => it is not affected by the node's delta
940
>
if (x.left === SENTINEL) {
941
>
z.start -= delta;
942
>
z.end -= delta;
943
>
z.maxEnd -= delta;
944
>
x.left = z;
945
>
break;
946
>
} else {
948
>
}
951
>
// => it is not affected by the node's delta
952
>
if (x.right === SENTINEL) {
953
>
z.start -= (delta + x.delta);
954
>
z.end -= (delta + x.delta);
955
>
z.maxEnd -= (delta + x.delta);
956
>
x.right = z;
957
>
break;
958
>
} else {
960
>
x = x.right;
961
>
}
964
>
965
>
z.parent = x;
966
>
z.left = SENTINEL;
967
>
z.right = SENTINEL;
968
>
setNodeColor(z, NodeColor.Red);
969
>
}
971
>
972
>
//#region Deletion
974
>
975
>
let x: IntervalNode;
976
>
let y: IntervalNode;
977
>
978
>
// RB-DELETE except we don't swap z and y in case c)
979
>
// i.e. we always delete what's pointed at by z.
980
>
981
>
if (z.left === SENTINEL) {
983
>
y = z;
984
>
985
>
// x's delta is no longer influenced by z's delta
986
>
x.delta += z.delta;
987
>
if (x.delta < Constants.MIN_SAFE_DELTA || x.delta > Constants.MAX_SAFE_DELTA) {
988
T.requestNormalizeDelta = true;
989
}
991
>
x.end += z.delta;
992
>
995
>
y = z;
996
>
999
>
x = y.right;
1000
>
1001
>
// y's delta is no longer influenced by z's delta,
1002
>
// but we don't want to walk the entire right-hand-side subtree of x.
1003
>
// we therefore maintain z's delta in y, and adjust only x
1004
>
x.start += y.delta;
1005
>
x.end += y.delta;
1006
>
x.delta += y.delta;
1007
>
if (x.delta < Constants.MIN_SAFE_DELTA || x.delta > Constants.MAX_SAFE_DELTA) {
1008
T.requestNormalizeDelta = true;
1009
}
1011
>
y.start += z.delta;
1012
>
y.end += z.delta;
1013
>
y.delta = z.delta;
1014
>
if (y.delta < Constants.MIN_SAFE_DELTA || y.delta > Constants.MAX_SAFE_DELTA) {
1015
T.requestNormalizeDelta = true;
1016
}
1019
>
if (y === T.root) {
1021
>
setNodeColor(x, NodeColor.Black);
1022
>
1023
>
z.detach();
1024
>
resetSentinel();
1025
>
recomputeMaxEnd(x);
1026
>
T.root.parent = SENTINEL;
1027
>
return;
1028
>
}
1030
>
const yWasRed = (getNodeColor(y) === NodeColor.Red);
1031
>
1032
>
if (y === y.parent.left) {
1036
>
}
1038
>
if (y === z) {
1042
>
if (y.parent === z) {
1046
>
}
1048
>
y.left = z.left;
1049
>
y.right = z.right;
1050
>
y.parent = z.parent;
1051
>
setNodeColor(y, getNodeColor(z));
1052
>
1053
>
if (z === T.root) {
1060
>
}
1063
>
if (y.left !== SENTINEL) {
1064
>
y.left.parent = y;
1065
>
}
1066
>
if (y.right !== SENTINEL) {
1068
>
}
1071
>
z.detach();
1072
>
1073
>
if (yWasRed) {
1075
>
if (y !== z) {
1077
>
recomputeMaxEndWalkToRoot(y.parent);
1078
>
}
1080
>
return;
1081
>
}
1083
>
recomputeMaxEndWalkToRoot(x);
1084
>
recomputeMaxEndWalkToRoot(x.parent);
1085
>
if (y !== z) {
1087
>
recomputeMaxEndWalkToRoot(y.parent);
1088
>
}
1090
>
// RB-DELETE-FIXUP
1091
>
let w: IntervalNode;
1094
>
if (x === x.parent.left) {
1096
>
1097
>
if (getNodeColor(w) === NodeColor.Red) {
1099
>
setNodeColor(x.parent, NodeColor.Red);
1100
>
leftRotate(T, x.parent);
1101
>
w = x.parent.right;
1102
>
}
1104
>
if (getNodeColor(w.left) === NodeColor.Black && getNodeColor(w.right) === NodeColor.Black) {
1106
>
x = x.parent;
1109
setNodeColor(w.left, NodeColor.Black);
1110
setNodeColor(w, NodeColor.Red);
1111
rightRotate(T, w);
1112
w = x.parent.right;
1113
}
1115
>
setNodeColor(w, getNodeColor(x.parent));
1116
>
setNodeColor(x.parent, NodeColor.Black);
1117
>
setNodeColor(w.right, NodeColor.Black);
1118
>
leftRotate(T, x.parent);
1119
>
x = T.root;
1120
>
}
1124
>
1125
>
if (getNodeColor(w) === NodeColor.Red) {
1127
>
setNodeColor(x.parent, NodeColor.Red);
1128
>
rightRotate(T, x.parent);
1129
>
w = x.parent.left;
1130
>
}
1132
>
if (getNodeColor(w.left) === NodeColor.Black && getNodeColor(w.right) === NodeColor.Black) {
1134
>
x = x.parent;
1135
>
1137
>
if (getNodeColor(w.left) === NodeColor.Black) {
1138
>
setNodeColor(w.right, NodeColor.Black);
1139
>
setNodeColor(w, NodeColor.Red);
1140
>
leftRotate(T, w);
1141
>
w = x.parent.left;
1142
>
}
1143
>
1144
>
setNodeColor(w, getNodeColor(x.parent));
1145
>
setNodeColor(x.parent, NodeColor.Black);
1146
>
setNodeColor(w.left, NodeColor.Black);
1147
>
rightRotate(T, x.parent);
1148
>
x = T.root;
1149
>
}
1150
>
}
1153
>
setNodeColor(x, NodeColor.Black);
1154
>
resetSentinel();
1155
>
}
1158
>
while (node.left !== SENTINEL) {
1160
>
}
1162
>
}
1165
>
SENTINEL.parent = SENTINEL;
1166
>
SENTINEL.delta = 0; // optional
1167
>
SENTINEL.start = 0; // optional
1168
>
SENTINEL.end = 0; // optional
1169
>
}
1171
>
1172
>
//#region Rotations
1174
>
const y = x.right; // set y.
1175
>
1176
>
y.delta += x.delta; // y's delta is no longer influenced by x's delta
1177
>
if (y.delta < Constants.MIN_SAFE_DELTA || y.delta > Constants.MAX_SAFE_DELTA) {
1178
T.requestNormalizeDelta = true;
1179
}
1181
>
y.end += x.delta;
1182
>
1183
>
x.right = y.left; // turn y's left subtree into x's right subtree.
1184
>
if (y.left !== SENTINEL) {
1186
>
}
1188
>
if (x.parent === SENTINEL) {
1194
>
}
1196
>
y.left = x; // put x on y's left.
1197
>
x.parent = y;
1198
>
1199
>
recomputeMaxEnd(x);
1200
>
recomputeMaxEnd(y);
1201
>
}
1204
>
const x = y.left;
1205
>
1206
>
y.delta -= x.delta;
1207
>
if (y.delta < Constants.MIN_SAFE_DELTA || y.delta > Constants.MAX_SAFE_DELTA) {
1208
T.requestNormalizeDelta = true;
1209
}
1211
>
y.end -= x.delta;
1212
>
1213
>
y.left = x.right;
1214
>
if (x.right !== SENTINEL) {
1216
>
}
1218
>
if (y.parent === SENTINEL) {
1222
>
} else {
1224
>
}
1226
>
x.right = y;
1227
>
y.parent = x;
1228
>
1229
>
recomputeMaxEnd(y);
1230
>
recomputeMaxEnd(x);
1231
>
}
1233
>
1234
>
//#region max end computation
1235
>
1237
>
let maxEnd = node.end;
1238
>
if (node.left !== SENTINEL) {
1240
>
if (leftMaxEnd > maxEnd) {
1242
>
}
1246
>
if (rightMaxEnd > maxEnd) {
1248
>
}
1251
>
}
1253
>
export function recomputeMaxEnd(node: IntervalNode): void {
1255
>
}
1258
>
while (node !== SENTINEL) {
1259
>
1260
>
const maxEnd = computeMaxEnd(node);
1261
>
1262
>
if (node.maxEnd === maxEnd) {
1264
>
return;
1265
>
}
1267
>
node.maxEnd = maxEnd;
1268
>
node = node.parent;
1269
>
}
1272
>
//#endregion
1273
>
1274
>
//#region utils
1275
>
export function intervalCompare(aStart: number, aEnd: number, bStart: number, bEnd: number): number {
1278
>
}
1280
>
}