intervalTree.js 33 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972
  1. /*---------------------------------------------------------------------------------------------
  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. export function getNodeColor(node) {
  6. return ((node.metadata & 1 /* ColorMask */) >>> 0 /* ColorOffset */);
  7. }
  8. function setNodeColor(node, color) {
  9. node.metadata = ((node.metadata & 254 /* ColorMaskInverse */) | (color << 0 /* ColorOffset */));
  10. }
  11. function getNodeIsVisited(node) {
  12. return ((node.metadata & 2 /* IsVisitedMask */) >>> 1 /* IsVisitedOffset */) === 1;
  13. }
  14. function setNodeIsVisited(node, value) {
  15. node.metadata = ((node.metadata & 253 /* IsVisitedMaskInverse */) | ((value ? 1 : 0) << 1 /* IsVisitedOffset */));
  16. }
  17. function getNodeIsForValidation(node) {
  18. return ((node.metadata & 4 /* IsForValidationMask */) >>> 2 /* IsForValidationOffset */) === 1;
  19. }
  20. function setNodeIsForValidation(node, value) {
  21. node.metadata = ((node.metadata & 251 /* IsForValidationMaskInverse */) | ((value ? 1 : 0) << 2 /* IsForValidationOffset */));
  22. }
  23. function getNodeStickiness(node) {
  24. return ((node.metadata & 24 /* StickinessMask */) >>> 3 /* StickinessOffset */);
  25. }
  26. function _setNodeStickiness(node, stickiness) {
  27. node.metadata = ((node.metadata & 231 /* StickinessMaskInverse */) | (stickiness << 3 /* StickinessOffset */));
  28. }
  29. function getCollapseOnReplaceEdit(node) {
  30. return ((node.metadata & 32 /* CollapseOnReplaceEditMask */) >>> 5 /* CollapseOnReplaceEditOffset */) === 1;
  31. }
  32. function setCollapseOnReplaceEdit(node, value) {
  33. node.metadata = ((node.metadata & 223 /* CollapseOnReplaceEditMaskInverse */) | ((value ? 1 : 0) << 5 /* CollapseOnReplaceEditOffset */));
  34. }
  35. export class IntervalNode {
  36. constructor(id, start, end) {
  37. this.metadata = 0;
  38. this.parent = this;
  39. this.left = this;
  40. this.right = this;
  41. setNodeColor(this, 1 /* Red */);
  42. this.start = start;
  43. this.end = end;
  44. // FORCE_OVERFLOWING_TEST: this.delta = start;
  45. this.delta = 0;
  46. this.maxEnd = end;
  47. this.id = id;
  48. this.ownerId = 0;
  49. this.options = null;
  50. setNodeIsForValidation(this, false);
  51. _setNodeStickiness(this, 1 /* NeverGrowsWhenTypingAtEdges */);
  52. setCollapseOnReplaceEdit(this, false);
  53. this.cachedVersionId = 0;
  54. this.cachedAbsoluteStart = start;
  55. this.cachedAbsoluteEnd = end;
  56. this.range = null;
  57. setNodeIsVisited(this, false);
  58. }
  59. reset(versionId, start, end, range) {
  60. this.start = start;
  61. this.end = end;
  62. this.maxEnd = end;
  63. this.cachedVersionId = versionId;
  64. this.cachedAbsoluteStart = start;
  65. this.cachedAbsoluteEnd = end;
  66. this.range = range;
  67. }
  68. setOptions(options) {
  69. this.options = options;
  70. let className = this.options.className;
  71. setNodeIsForValidation(this, (className === "squiggly-error" /* EditorErrorDecoration */
  72. || className === "squiggly-warning" /* EditorWarningDecoration */
  73. || className === "squiggly-info" /* EditorInfoDecoration */));
  74. _setNodeStickiness(this, this.options.stickiness);
  75. setCollapseOnReplaceEdit(this, this.options.collapseOnReplaceEdit);
  76. }
  77. setCachedOffsets(absoluteStart, absoluteEnd, cachedVersionId) {
  78. if (this.cachedVersionId !== cachedVersionId) {
  79. this.range = null;
  80. }
  81. this.cachedVersionId = cachedVersionId;
  82. this.cachedAbsoluteStart = absoluteStart;
  83. this.cachedAbsoluteEnd = absoluteEnd;
  84. }
  85. detach() {
  86. this.parent = null;
  87. this.left = null;
  88. this.right = null;
  89. }
  90. }
  91. export const SENTINEL = new IntervalNode(null, 0, 0);
  92. SENTINEL.parent = SENTINEL;
  93. SENTINEL.left = SENTINEL;
  94. SENTINEL.right = SENTINEL;
  95. setNodeColor(SENTINEL, 0 /* Black */);
  96. export class IntervalTree {
  97. constructor() {
  98. this.root = SENTINEL;
  99. this.requestNormalizeDelta = false;
  100. }
  101. intervalSearch(start, end, filterOwnerId, filterOutValidation, cachedVersionId) {
  102. if (this.root === SENTINEL) {
  103. return [];
  104. }
  105. return intervalSearch(this, start, end, filterOwnerId, filterOutValidation, cachedVersionId);
  106. }
  107. search(filterOwnerId, filterOutValidation, cachedVersionId) {
  108. if (this.root === SENTINEL) {
  109. return [];
  110. }
  111. return search(this, filterOwnerId, filterOutValidation, cachedVersionId);
  112. }
  113. /**
  114. * Will not set `cachedAbsoluteStart` nor `cachedAbsoluteEnd` on the returned nodes!
  115. */
  116. collectNodesFromOwner(ownerId) {
  117. return collectNodesFromOwner(this, ownerId);
  118. }
  119. /**
  120. * Will not set `cachedAbsoluteStart` nor `cachedAbsoluteEnd` on the returned nodes!
  121. */
  122. collectNodesPostOrder() {
  123. return collectNodesPostOrder(this);
  124. }
  125. insert(node) {
  126. rbTreeInsert(this, node);
  127. this._normalizeDeltaIfNecessary();
  128. }
  129. delete(node) {
  130. rbTreeDelete(this, node);
  131. this._normalizeDeltaIfNecessary();
  132. }
  133. resolveNode(node, cachedVersionId) {
  134. const initialNode = node;
  135. let delta = 0;
  136. while (node !== this.root) {
  137. if (node === node.parent.right) {
  138. delta += node.parent.delta;
  139. }
  140. node = node.parent;
  141. }
  142. const nodeStart = initialNode.start + delta;
  143. const nodeEnd = initialNode.end + delta;
  144. initialNode.setCachedOffsets(nodeStart, nodeEnd, cachedVersionId);
  145. }
  146. acceptReplace(offset, length, textLength, forceMoveMarkers) {
  147. // Our strategy is to remove all directly impacted nodes, and then add them back to the tree.
  148. // (1) collect all nodes that are intersecting this edit as nodes of interest
  149. const nodesOfInterest = searchForEditing(this, offset, offset + length);
  150. // (2) remove all nodes that are intersecting this edit
  151. for (let i = 0, len = nodesOfInterest.length; i < len; i++) {
  152. const node = nodesOfInterest[i];
  153. rbTreeDelete(this, node);
  154. }
  155. this._normalizeDeltaIfNecessary();
  156. // (3) edit all tree nodes except the nodes of interest
  157. noOverlapReplace(this, offset, offset + length, textLength);
  158. this._normalizeDeltaIfNecessary();
  159. // (4) edit the nodes of interest and insert them back in the tree
  160. for (let i = 0, len = nodesOfInterest.length; i < len; i++) {
  161. const node = nodesOfInterest[i];
  162. node.start = node.cachedAbsoluteStart;
  163. node.end = node.cachedAbsoluteEnd;
  164. nodeAcceptEdit(node, offset, (offset + length), textLength, forceMoveMarkers);
  165. node.maxEnd = node.end;
  166. rbTreeInsert(this, node);
  167. }
  168. this._normalizeDeltaIfNecessary();
  169. }
  170. _normalizeDeltaIfNecessary() {
  171. if (!this.requestNormalizeDelta) {
  172. return;
  173. }
  174. this.requestNormalizeDelta = false;
  175. normalizeDelta(this);
  176. }
  177. }
  178. //#region Delta Normalization
  179. function normalizeDelta(T) {
  180. let node = T.root;
  181. let delta = 0;
  182. while (node !== SENTINEL) {
  183. if (node.left !== SENTINEL && !getNodeIsVisited(node.left)) {
  184. // go left
  185. node = node.left;
  186. continue;
  187. }
  188. if (node.right !== SENTINEL && !getNodeIsVisited(node.right)) {
  189. // go right
  190. delta += node.delta;
  191. node = node.right;
  192. continue;
  193. }
  194. // handle current node
  195. node.start = delta + node.start;
  196. node.end = delta + node.end;
  197. node.delta = 0;
  198. recomputeMaxEnd(node);
  199. setNodeIsVisited(node, true);
  200. // going up from this node
  201. setNodeIsVisited(node.left, false);
  202. setNodeIsVisited(node.right, false);
  203. if (node === node.parent.right) {
  204. delta -= node.parent.delta;
  205. }
  206. node = node.parent;
  207. }
  208. setNodeIsVisited(T.root, false);
  209. }
  210. function adjustMarkerBeforeColumn(markerOffset, markerStickToPreviousCharacter, checkOffset, moveSemantics) {
  211. if (markerOffset < checkOffset) {
  212. return true;
  213. }
  214. if (markerOffset > checkOffset) {
  215. return false;
  216. }
  217. if (moveSemantics === 1 /* ForceMove */) {
  218. return false;
  219. }
  220. if (moveSemantics === 2 /* ForceStay */) {
  221. return true;
  222. }
  223. return markerStickToPreviousCharacter;
  224. }
  225. /**
  226. * This is a lot more complicated than strictly necessary to maintain the same behaviour
  227. * as when decorations were implemented using two markers.
  228. */
  229. export function nodeAcceptEdit(node, start, end, textLength, forceMoveMarkers) {
  230. const nodeStickiness = getNodeStickiness(node);
  231. const startStickToPreviousCharacter = (nodeStickiness === 0 /* AlwaysGrowsWhenTypingAtEdges */
  232. || nodeStickiness === 2 /* GrowsOnlyWhenTypingBefore */);
  233. const endStickToPreviousCharacter = (nodeStickiness === 1 /* NeverGrowsWhenTypingAtEdges */
  234. || nodeStickiness === 2 /* GrowsOnlyWhenTypingBefore */);
  235. const deletingCnt = (end - start);
  236. const insertingCnt = textLength;
  237. const commonLength = Math.min(deletingCnt, insertingCnt);
  238. const nodeStart = node.start;
  239. let startDone = false;
  240. const nodeEnd = node.end;
  241. let endDone = false;
  242. if (start <= nodeStart && nodeEnd <= end && getCollapseOnReplaceEdit(node)) {
  243. // This edit encompasses the entire decoration range
  244. // and the decoration has asked to become collapsed
  245. node.start = start;
  246. startDone = true;
  247. node.end = start;
  248. endDone = true;
  249. }
  250. {
  251. const moveSemantics = forceMoveMarkers ? 1 /* ForceMove */ : (deletingCnt > 0 ? 2 /* ForceStay */ : 0 /* MarkerDefined */);
  252. if (!startDone && adjustMarkerBeforeColumn(nodeStart, startStickToPreviousCharacter, start, moveSemantics)) {
  253. startDone = true;
  254. }
  255. if (!endDone && adjustMarkerBeforeColumn(nodeEnd, endStickToPreviousCharacter, start, moveSemantics)) {
  256. endDone = true;
  257. }
  258. }
  259. if (commonLength > 0 && !forceMoveMarkers) {
  260. const moveSemantics = (deletingCnt > insertingCnt ? 2 /* ForceStay */ : 0 /* MarkerDefined */);
  261. if (!startDone && adjustMarkerBeforeColumn(nodeStart, startStickToPreviousCharacter, start + commonLength, moveSemantics)) {
  262. startDone = true;
  263. }
  264. if (!endDone && adjustMarkerBeforeColumn(nodeEnd, endStickToPreviousCharacter, start + commonLength, moveSemantics)) {
  265. endDone = true;
  266. }
  267. }
  268. {
  269. const moveSemantics = forceMoveMarkers ? 1 /* ForceMove */ : 0 /* MarkerDefined */;
  270. if (!startDone && adjustMarkerBeforeColumn(nodeStart, startStickToPreviousCharacter, end, moveSemantics)) {
  271. node.start = start + insertingCnt;
  272. startDone = true;
  273. }
  274. if (!endDone && adjustMarkerBeforeColumn(nodeEnd, endStickToPreviousCharacter, end, moveSemantics)) {
  275. node.end = start + insertingCnt;
  276. endDone = true;
  277. }
  278. }
  279. // Finish
  280. const deltaColumn = (insertingCnt - deletingCnt);
  281. if (!startDone) {
  282. node.start = Math.max(0, nodeStart + deltaColumn);
  283. }
  284. if (!endDone) {
  285. node.end = Math.max(0, nodeEnd + deltaColumn);
  286. }
  287. if (node.start > node.end) {
  288. node.end = node.start;
  289. }
  290. }
  291. function searchForEditing(T, start, end) {
  292. // https://en.wikipedia.org/wiki/Interval_tree#Augmented_tree
  293. // Now, it is known that two intervals A and B overlap only when both
  294. // A.low <= B.high and A.high >= B.low. When searching the trees for
  295. // nodes overlapping with a given interval, you can immediately skip:
  296. // a) all nodes to the right of nodes whose low value is past the end of the given interval.
  297. // b) all nodes that have their maximum 'high' value below the start of the given interval.
  298. let node = T.root;
  299. let delta = 0;
  300. let nodeMaxEnd = 0;
  301. let nodeStart = 0;
  302. let nodeEnd = 0;
  303. let result = [];
  304. let resultLen = 0;
  305. while (node !== SENTINEL) {
  306. if (getNodeIsVisited(node)) {
  307. // going up from this node
  308. setNodeIsVisited(node.left, false);
  309. setNodeIsVisited(node.right, false);
  310. if (node === node.parent.right) {
  311. delta -= node.parent.delta;
  312. }
  313. node = node.parent;
  314. continue;
  315. }
  316. if (!getNodeIsVisited(node.left)) {
  317. // first time seeing this node
  318. nodeMaxEnd = delta + node.maxEnd;
  319. if (nodeMaxEnd < start) {
  320. // cover case b) from above
  321. // there is no need to search this node or its children
  322. setNodeIsVisited(node, true);
  323. continue;
  324. }
  325. if (node.left !== SENTINEL) {
  326. // go left
  327. node = node.left;
  328. continue;
  329. }
  330. }
  331. // handle current node
  332. nodeStart = delta + node.start;
  333. if (nodeStart > end) {
  334. // cover case a) from above
  335. // there is no need to search this node or its right subtree
  336. setNodeIsVisited(node, true);
  337. continue;
  338. }
  339. nodeEnd = delta + node.end;
  340. if (nodeEnd >= start) {
  341. node.setCachedOffsets(nodeStart, nodeEnd, 0);
  342. result[resultLen++] = node;
  343. }
  344. setNodeIsVisited(node, true);
  345. if (node.right !== SENTINEL && !getNodeIsVisited(node.right)) {
  346. // go right
  347. delta += node.delta;
  348. node = node.right;
  349. continue;
  350. }
  351. }
  352. setNodeIsVisited(T.root, false);
  353. return result;
  354. }
  355. function noOverlapReplace(T, start, end, textLength) {
  356. // https://en.wikipedia.org/wiki/Interval_tree#Augmented_tree
  357. // Now, it is known that two intervals A and B overlap only when both
  358. // A.low <= B.high and A.high >= B.low. When searching the trees for
  359. // nodes overlapping with a given interval, you can immediately skip:
  360. // a) all nodes to the right of nodes whose low value is past the end of the given interval.
  361. // b) all nodes that have their maximum 'high' value below the start of the given interval.
  362. let node = T.root;
  363. let delta = 0;
  364. let nodeMaxEnd = 0;
  365. let nodeStart = 0;
  366. const editDelta = (textLength - (end - start));
  367. while (node !== SENTINEL) {
  368. if (getNodeIsVisited(node)) {
  369. // going up from this node
  370. setNodeIsVisited(node.left, false);
  371. setNodeIsVisited(node.right, false);
  372. if (node === node.parent.right) {
  373. delta -= node.parent.delta;
  374. }
  375. recomputeMaxEnd(node);
  376. node = node.parent;
  377. continue;
  378. }
  379. if (!getNodeIsVisited(node.left)) {
  380. // first time seeing this node
  381. nodeMaxEnd = delta + node.maxEnd;
  382. if (nodeMaxEnd < start) {
  383. // cover case b) from above
  384. // there is no need to search this node or its children
  385. setNodeIsVisited(node, true);
  386. continue;
  387. }
  388. if (node.left !== SENTINEL) {
  389. // go left
  390. node = node.left;
  391. continue;
  392. }
  393. }
  394. // handle current node
  395. nodeStart = delta + node.start;
  396. if (nodeStart > end) {
  397. node.start += editDelta;
  398. node.end += editDelta;
  399. node.delta += editDelta;
  400. if (node.delta < -1073741824 /* MIN_SAFE_DELTA */ || node.delta > 1073741824 /* MAX_SAFE_DELTA */) {
  401. T.requestNormalizeDelta = true;
  402. }
  403. // cover case a) from above
  404. // there is no need to search this node or its right subtree
  405. setNodeIsVisited(node, true);
  406. continue;
  407. }
  408. setNodeIsVisited(node, true);
  409. if (node.right !== SENTINEL && !getNodeIsVisited(node.right)) {
  410. // go right
  411. delta += node.delta;
  412. node = node.right;
  413. continue;
  414. }
  415. }
  416. setNodeIsVisited(T.root, false);
  417. }
  418. //#endregion
  419. //#region Searching
  420. function collectNodesFromOwner(T, ownerId) {
  421. let node = T.root;
  422. let result = [];
  423. let resultLen = 0;
  424. while (node !== SENTINEL) {
  425. if (getNodeIsVisited(node)) {
  426. // going up from this node
  427. setNodeIsVisited(node.left, false);
  428. setNodeIsVisited(node.right, false);
  429. node = node.parent;
  430. continue;
  431. }
  432. if (node.left !== SENTINEL && !getNodeIsVisited(node.left)) {
  433. // go left
  434. node = node.left;
  435. continue;
  436. }
  437. // handle current node
  438. if (node.ownerId === ownerId) {
  439. result[resultLen++] = node;
  440. }
  441. setNodeIsVisited(node, true);
  442. if (node.right !== SENTINEL && !getNodeIsVisited(node.right)) {
  443. // go right
  444. node = node.right;
  445. continue;
  446. }
  447. }
  448. setNodeIsVisited(T.root, false);
  449. return result;
  450. }
  451. function collectNodesPostOrder(T) {
  452. let node = T.root;
  453. let result = [];
  454. let resultLen = 0;
  455. while (node !== SENTINEL) {
  456. if (getNodeIsVisited(node)) {
  457. // going up from this node
  458. setNodeIsVisited(node.left, false);
  459. setNodeIsVisited(node.right, false);
  460. node = node.parent;
  461. continue;
  462. }
  463. if (node.left !== SENTINEL && !getNodeIsVisited(node.left)) {
  464. // go left
  465. node = node.left;
  466. continue;
  467. }
  468. if (node.right !== SENTINEL && !getNodeIsVisited(node.right)) {
  469. // go right
  470. node = node.right;
  471. continue;
  472. }
  473. // handle current node
  474. result[resultLen++] = node;
  475. setNodeIsVisited(node, true);
  476. }
  477. setNodeIsVisited(T.root, false);
  478. return result;
  479. }
  480. function search(T, filterOwnerId, filterOutValidation, cachedVersionId) {
  481. let node = T.root;
  482. let delta = 0;
  483. let nodeStart = 0;
  484. let nodeEnd = 0;
  485. let result = [];
  486. let resultLen = 0;
  487. while (node !== SENTINEL) {
  488. if (getNodeIsVisited(node)) {
  489. // going up from this node
  490. setNodeIsVisited(node.left, false);
  491. setNodeIsVisited(node.right, false);
  492. if (node === node.parent.right) {
  493. delta -= node.parent.delta;
  494. }
  495. node = node.parent;
  496. continue;
  497. }
  498. if (node.left !== SENTINEL && !getNodeIsVisited(node.left)) {
  499. // go left
  500. node = node.left;
  501. continue;
  502. }
  503. // handle current node
  504. nodeStart = delta + node.start;
  505. nodeEnd = delta + node.end;
  506. node.setCachedOffsets(nodeStart, nodeEnd, cachedVersionId);
  507. let include = true;
  508. if (filterOwnerId && node.ownerId && node.ownerId !== filterOwnerId) {
  509. include = false;
  510. }
  511. if (filterOutValidation && getNodeIsForValidation(node)) {
  512. include = false;
  513. }
  514. if (include) {
  515. result[resultLen++] = node;
  516. }
  517. setNodeIsVisited(node, true);
  518. if (node.right !== SENTINEL && !getNodeIsVisited(node.right)) {
  519. // go right
  520. delta += node.delta;
  521. node = node.right;
  522. continue;
  523. }
  524. }
  525. setNodeIsVisited(T.root, false);
  526. return result;
  527. }
  528. function intervalSearch(T, intervalStart, intervalEnd, filterOwnerId, filterOutValidation, cachedVersionId) {
  529. // https://en.wikipedia.org/wiki/Interval_tree#Augmented_tree
  530. // Now, it is known that two intervals A and B overlap only when both
  531. // A.low <= B.high and A.high >= B.low. When searching the trees for
  532. // nodes overlapping with a given interval, you can immediately skip:
  533. // a) all nodes to the right of nodes whose low value is past the end of the given interval.
  534. // b) all nodes that have their maximum 'high' value below the start of the given interval.
  535. let node = T.root;
  536. let delta = 0;
  537. let nodeMaxEnd = 0;
  538. let nodeStart = 0;
  539. let nodeEnd = 0;
  540. let result = [];
  541. let resultLen = 0;
  542. while (node !== SENTINEL) {
  543. if (getNodeIsVisited(node)) {
  544. // going up from this node
  545. setNodeIsVisited(node.left, false);
  546. setNodeIsVisited(node.right, false);
  547. if (node === node.parent.right) {
  548. delta -= node.parent.delta;
  549. }
  550. node = node.parent;
  551. continue;
  552. }
  553. if (!getNodeIsVisited(node.left)) {
  554. // first time seeing this node
  555. nodeMaxEnd = delta + node.maxEnd;
  556. if (nodeMaxEnd < intervalStart) {
  557. // cover case b) from above
  558. // there is no need to search this node or its children
  559. setNodeIsVisited(node, true);
  560. continue;
  561. }
  562. if (node.left !== SENTINEL) {
  563. // go left
  564. node = node.left;
  565. continue;
  566. }
  567. }
  568. // handle current node
  569. nodeStart = delta + node.start;
  570. if (nodeStart > intervalEnd) {
  571. // cover case a) from above
  572. // there is no need to search this node or its right subtree
  573. setNodeIsVisited(node, true);
  574. continue;
  575. }
  576. nodeEnd = delta + node.end;
  577. if (nodeEnd >= intervalStart) {
  578. // There is overlap
  579. node.setCachedOffsets(nodeStart, nodeEnd, cachedVersionId);
  580. let include = true;
  581. if (filterOwnerId && node.ownerId && node.ownerId !== filterOwnerId) {
  582. include = false;
  583. }
  584. if (filterOutValidation && getNodeIsForValidation(node)) {
  585. include = false;
  586. }
  587. if (include) {
  588. result[resultLen++] = node;
  589. }
  590. }
  591. setNodeIsVisited(node, true);
  592. if (node.right !== SENTINEL && !getNodeIsVisited(node.right)) {
  593. // go right
  594. delta += node.delta;
  595. node = node.right;
  596. continue;
  597. }
  598. }
  599. setNodeIsVisited(T.root, false);
  600. return result;
  601. }
  602. //#endregion
  603. //#region Insertion
  604. function rbTreeInsert(T, newNode) {
  605. if (T.root === SENTINEL) {
  606. newNode.parent = SENTINEL;
  607. newNode.left = SENTINEL;
  608. newNode.right = SENTINEL;
  609. setNodeColor(newNode, 0 /* Black */);
  610. T.root = newNode;
  611. return T.root;
  612. }
  613. treeInsert(T, newNode);
  614. recomputeMaxEndWalkToRoot(newNode.parent);
  615. // repair tree
  616. let x = newNode;
  617. while (x !== T.root && getNodeColor(x.parent) === 1 /* Red */) {
  618. if (x.parent === x.parent.parent.left) {
  619. const y = x.parent.parent.right;
  620. if (getNodeColor(y) === 1 /* Red */) {
  621. setNodeColor(x.parent, 0 /* Black */);
  622. setNodeColor(y, 0 /* Black */);
  623. setNodeColor(x.parent.parent, 1 /* Red */);
  624. x = x.parent.parent;
  625. }
  626. else {
  627. if (x === x.parent.right) {
  628. x = x.parent;
  629. leftRotate(T, x);
  630. }
  631. setNodeColor(x.parent, 0 /* Black */);
  632. setNodeColor(x.parent.parent, 1 /* Red */);
  633. rightRotate(T, x.parent.parent);
  634. }
  635. }
  636. else {
  637. const y = x.parent.parent.left;
  638. if (getNodeColor(y) === 1 /* Red */) {
  639. setNodeColor(x.parent, 0 /* Black */);
  640. setNodeColor(y, 0 /* Black */);
  641. setNodeColor(x.parent.parent, 1 /* Red */);
  642. x = x.parent.parent;
  643. }
  644. else {
  645. if (x === x.parent.left) {
  646. x = x.parent;
  647. rightRotate(T, x);
  648. }
  649. setNodeColor(x.parent, 0 /* Black */);
  650. setNodeColor(x.parent.parent, 1 /* Red */);
  651. leftRotate(T, x.parent.parent);
  652. }
  653. }
  654. }
  655. setNodeColor(T.root, 0 /* Black */);
  656. return newNode;
  657. }
  658. function treeInsert(T, z) {
  659. let delta = 0;
  660. let x = T.root;
  661. const zAbsoluteStart = z.start;
  662. const zAbsoluteEnd = z.end;
  663. while (true) {
  664. const cmp = intervalCompare(zAbsoluteStart, zAbsoluteEnd, x.start + delta, x.end + delta);
  665. if (cmp < 0) {
  666. // this node should be inserted to the left
  667. // => it is not affected by the node's delta
  668. if (x.left === SENTINEL) {
  669. z.start -= delta;
  670. z.end -= delta;
  671. z.maxEnd -= delta;
  672. x.left = z;
  673. break;
  674. }
  675. else {
  676. x = x.left;
  677. }
  678. }
  679. else {
  680. // this node should be inserted to the right
  681. // => it is not affected by the node's delta
  682. if (x.right === SENTINEL) {
  683. z.start -= (delta + x.delta);
  684. z.end -= (delta + x.delta);
  685. z.maxEnd -= (delta + x.delta);
  686. x.right = z;
  687. break;
  688. }
  689. else {
  690. delta += x.delta;
  691. x = x.right;
  692. }
  693. }
  694. }
  695. z.parent = x;
  696. z.left = SENTINEL;
  697. z.right = SENTINEL;
  698. setNodeColor(z, 1 /* Red */);
  699. }
  700. //#endregion
  701. //#region Deletion
  702. function rbTreeDelete(T, z) {
  703. let x;
  704. let y;
  705. // RB-DELETE except we don't swap z and y in case c)
  706. // i.e. we always delete what's pointed at by z.
  707. if (z.left === SENTINEL) {
  708. x = z.right;
  709. y = z;
  710. // x's delta is no longer influenced by z's delta
  711. x.delta += z.delta;
  712. if (x.delta < -1073741824 /* MIN_SAFE_DELTA */ || x.delta > 1073741824 /* MAX_SAFE_DELTA */) {
  713. T.requestNormalizeDelta = true;
  714. }
  715. x.start += z.delta;
  716. x.end += z.delta;
  717. }
  718. else if (z.right === SENTINEL) {
  719. x = z.left;
  720. y = z;
  721. }
  722. else {
  723. y = leftest(z.right);
  724. x = y.right;
  725. // y's delta is no longer influenced by z's delta,
  726. // but we don't want to walk the entire right-hand-side subtree of x.
  727. // we therefore maintain z's delta in y, and adjust only x
  728. x.start += y.delta;
  729. x.end += y.delta;
  730. x.delta += y.delta;
  731. if (x.delta < -1073741824 /* MIN_SAFE_DELTA */ || x.delta > 1073741824 /* MAX_SAFE_DELTA */) {
  732. T.requestNormalizeDelta = true;
  733. }
  734. y.start += z.delta;
  735. y.end += z.delta;
  736. y.delta = z.delta;
  737. if (y.delta < -1073741824 /* MIN_SAFE_DELTA */ || y.delta > 1073741824 /* MAX_SAFE_DELTA */) {
  738. T.requestNormalizeDelta = true;
  739. }
  740. }
  741. if (y === T.root) {
  742. T.root = x;
  743. setNodeColor(x, 0 /* Black */);
  744. z.detach();
  745. resetSentinel();
  746. recomputeMaxEnd(x);
  747. T.root.parent = SENTINEL;
  748. return;
  749. }
  750. let yWasRed = (getNodeColor(y) === 1 /* Red */);
  751. if (y === y.parent.left) {
  752. y.parent.left = x;
  753. }
  754. else {
  755. y.parent.right = x;
  756. }
  757. if (y === z) {
  758. x.parent = y.parent;
  759. }
  760. else {
  761. if (y.parent === z) {
  762. x.parent = y;
  763. }
  764. else {
  765. x.parent = y.parent;
  766. }
  767. y.left = z.left;
  768. y.right = z.right;
  769. y.parent = z.parent;
  770. setNodeColor(y, getNodeColor(z));
  771. if (z === T.root) {
  772. T.root = y;
  773. }
  774. else {
  775. if (z === z.parent.left) {
  776. z.parent.left = y;
  777. }
  778. else {
  779. z.parent.right = y;
  780. }
  781. }
  782. if (y.left !== SENTINEL) {
  783. y.left.parent = y;
  784. }
  785. if (y.right !== SENTINEL) {
  786. y.right.parent = y;
  787. }
  788. }
  789. z.detach();
  790. if (yWasRed) {
  791. recomputeMaxEndWalkToRoot(x.parent);
  792. if (y !== z) {
  793. recomputeMaxEndWalkToRoot(y);
  794. recomputeMaxEndWalkToRoot(y.parent);
  795. }
  796. resetSentinel();
  797. return;
  798. }
  799. recomputeMaxEndWalkToRoot(x);
  800. recomputeMaxEndWalkToRoot(x.parent);
  801. if (y !== z) {
  802. recomputeMaxEndWalkToRoot(y);
  803. recomputeMaxEndWalkToRoot(y.parent);
  804. }
  805. // RB-DELETE-FIXUP
  806. let w;
  807. while (x !== T.root && getNodeColor(x) === 0 /* Black */) {
  808. if (x === x.parent.left) {
  809. w = x.parent.right;
  810. if (getNodeColor(w) === 1 /* Red */) {
  811. setNodeColor(w, 0 /* Black */);
  812. setNodeColor(x.parent, 1 /* Red */);
  813. leftRotate(T, x.parent);
  814. w = x.parent.right;
  815. }
  816. if (getNodeColor(w.left) === 0 /* Black */ && getNodeColor(w.right) === 0 /* Black */) {
  817. setNodeColor(w, 1 /* Red */);
  818. x = x.parent;
  819. }
  820. else {
  821. if (getNodeColor(w.right) === 0 /* Black */) {
  822. setNodeColor(w.left, 0 /* Black */);
  823. setNodeColor(w, 1 /* Red */);
  824. rightRotate(T, w);
  825. w = x.parent.right;
  826. }
  827. setNodeColor(w, getNodeColor(x.parent));
  828. setNodeColor(x.parent, 0 /* Black */);
  829. setNodeColor(w.right, 0 /* Black */);
  830. leftRotate(T, x.parent);
  831. x = T.root;
  832. }
  833. }
  834. else {
  835. w = x.parent.left;
  836. if (getNodeColor(w) === 1 /* Red */) {
  837. setNodeColor(w, 0 /* Black */);
  838. setNodeColor(x.parent, 1 /* Red */);
  839. rightRotate(T, x.parent);
  840. w = x.parent.left;
  841. }
  842. if (getNodeColor(w.left) === 0 /* Black */ && getNodeColor(w.right) === 0 /* Black */) {
  843. setNodeColor(w, 1 /* Red */);
  844. x = x.parent;
  845. }
  846. else {
  847. if (getNodeColor(w.left) === 0 /* Black */) {
  848. setNodeColor(w.right, 0 /* Black */);
  849. setNodeColor(w, 1 /* Red */);
  850. leftRotate(T, w);
  851. w = x.parent.left;
  852. }
  853. setNodeColor(w, getNodeColor(x.parent));
  854. setNodeColor(x.parent, 0 /* Black */);
  855. setNodeColor(w.left, 0 /* Black */);
  856. rightRotate(T, x.parent);
  857. x = T.root;
  858. }
  859. }
  860. }
  861. setNodeColor(x, 0 /* Black */);
  862. resetSentinel();
  863. }
  864. function leftest(node) {
  865. while (node.left !== SENTINEL) {
  866. node = node.left;
  867. }
  868. return node;
  869. }
  870. function resetSentinel() {
  871. SENTINEL.parent = SENTINEL;
  872. SENTINEL.delta = 0; // optional
  873. SENTINEL.start = 0; // optional
  874. SENTINEL.end = 0; // optional
  875. }
  876. //#endregion
  877. //#region Rotations
  878. function leftRotate(T, x) {
  879. const y = x.right; // set y.
  880. y.delta += x.delta; // y's delta is no longer influenced by x's delta
  881. if (y.delta < -1073741824 /* MIN_SAFE_DELTA */ || y.delta > 1073741824 /* MAX_SAFE_DELTA */) {
  882. T.requestNormalizeDelta = true;
  883. }
  884. y.start += x.delta;
  885. y.end += x.delta;
  886. x.right = y.left; // turn y's left subtree into x's right subtree.
  887. if (y.left !== SENTINEL) {
  888. y.left.parent = x;
  889. }
  890. y.parent = x.parent; // link x's parent to y.
  891. if (x.parent === SENTINEL) {
  892. T.root = y;
  893. }
  894. else if (x === x.parent.left) {
  895. x.parent.left = y;
  896. }
  897. else {
  898. x.parent.right = y;
  899. }
  900. y.left = x; // put x on y's left.
  901. x.parent = y;
  902. recomputeMaxEnd(x);
  903. recomputeMaxEnd(y);
  904. }
  905. function rightRotate(T, y) {
  906. const x = y.left;
  907. y.delta -= x.delta;
  908. if (y.delta < -1073741824 /* MIN_SAFE_DELTA */ || y.delta > 1073741824 /* MAX_SAFE_DELTA */) {
  909. T.requestNormalizeDelta = true;
  910. }
  911. y.start -= x.delta;
  912. y.end -= x.delta;
  913. y.left = x.right;
  914. if (x.right !== SENTINEL) {
  915. x.right.parent = y;
  916. }
  917. x.parent = y.parent;
  918. if (y.parent === SENTINEL) {
  919. T.root = x;
  920. }
  921. else if (y === y.parent.right) {
  922. y.parent.right = x;
  923. }
  924. else {
  925. y.parent.left = x;
  926. }
  927. x.right = y;
  928. y.parent = x;
  929. recomputeMaxEnd(y);
  930. recomputeMaxEnd(x);
  931. }
  932. //#endregion
  933. //#region max end computation
  934. function computeMaxEnd(node) {
  935. let maxEnd = node.end;
  936. if (node.left !== SENTINEL) {
  937. const leftMaxEnd = node.left.maxEnd;
  938. if (leftMaxEnd > maxEnd) {
  939. maxEnd = leftMaxEnd;
  940. }
  941. }
  942. if (node.right !== SENTINEL) {
  943. const rightMaxEnd = node.right.maxEnd + node.delta;
  944. if (rightMaxEnd > maxEnd) {
  945. maxEnd = rightMaxEnd;
  946. }
  947. }
  948. return maxEnd;
  949. }
  950. export function recomputeMaxEnd(node) {
  951. node.maxEnd = computeMaxEnd(node);
  952. }
  953. function recomputeMaxEndWalkToRoot(node) {
  954. while (node !== SENTINEL) {
  955. const maxEnd = computeMaxEnd(node);
  956. if (node.maxEnd === maxEnd) {
  957. // no need to go further
  958. return;
  959. }
  960. node.maxEnd = maxEnd;
  961. node = node.parent;
  962. }
  963. }
  964. //#endregion
  965. //#region utils
  966. export function intervalCompare(aStart, aEnd, bStart, bEnd) {
  967. if (aStart === bStart) {
  968. return aEnd - bEnd;
  969. }
  970. return aStart - bStart;
  971. }
  972. //#endregion