source: frontend/node_modules/symbol-tree/lib/SymbolTree.js

Last change on this file was 9af201e, checked in by MBK <marija.karapandzova@…>, 12 days ago

Fix frontend appearance
  • Property mode set to 100644
File size: 28.8 KB
Line 
1'use strict';
2
3/**
4 * @module symbol-tree
5 * @author Joris van der Wel <joris@jorisvanderwel.com>
6 */
7
8const SymbolTreeNode = require('./SymbolTreeNode');
9const TreePosition = require('./TreePosition');
10const TreeIterator = require('./TreeIterator');
11
12function returnTrue() {
13 return true;
14}
15
16function reverseArrayIndex(array, reverseIndex) {
17 return array[array.length - 1 - reverseIndex]; // no need to check `index >= 0`
18}
19
20class SymbolTree {
21
22 /**
23 * @constructor
24 * @alias module:symbol-tree
25 * @param {string} [description='SymbolTree data'] Description used for the Symbol
26 */
27 constructor(description) {
28 this.symbol = Symbol(description || 'SymbolTree data');
29 }
30
31 /**
32 * You can use this function to (optionally) initialize an object right after its creation,
33 * to take advantage of V8's fast properties. Also useful if you would like to
34 * freeze your object.
35 *
36 * `O(1)`
37 *
38 * @method
39 * @alias module:symbol-tree#initialize
40 * @param {Object} object
41 * @return {Object} object
42 */
43 initialize(object) {
44 this._node(object);
45
46 return object;
47 }
48
49 _node(object) {
50 if (!object) {
51 return null;
52 }
53
54 const node = object[this.symbol];
55
56 if (node) {
57 return node;
58 }
59
60 return (object[this.symbol] = new SymbolTreeNode());
61 }
62
63 /**
64 * Returns `true` if the object has any children. Otherwise it returns `false`.
65 *
66 * * `O(1)`
67 *
68 * @method hasChildren
69 * @memberOf module:symbol-tree#
70 * @param {Object} object
71 * @return {Boolean}
72 */
73 hasChildren(object) {
74 return this._node(object).hasChildren;
75 }
76
77 /**
78 * Returns the first child of the given object.
79 *
80 * * `O(1)`
81 *
82 * @method firstChild
83 * @memberOf module:symbol-tree#
84 * @param {Object} object
85 * @return {Object}
86 */
87 firstChild(object) {
88 return this._node(object).firstChild;
89 }
90
91 /**
92 * Returns the last child of the given object.
93 *
94 * * `O(1)`
95 *
96 * @method lastChild
97 * @memberOf module:symbol-tree#
98 * @param {Object} object
99 * @return {Object}
100 */
101 lastChild(object) {
102 return this._node(object).lastChild;
103 }
104
105 /**
106 * Returns the previous sibling of the given object.
107 *
108 * * `O(1)`
109 *
110 * @method previousSibling
111 * @memberOf module:symbol-tree#
112 * @param {Object} object
113 * @return {Object}
114 */
115 previousSibling(object) {
116 return this._node(object).previousSibling;
117 }
118
119 /**
120 * Returns the next sibling of the given object.
121 *
122 * * `O(1)`
123 *
124 * @method nextSibling
125 * @memberOf module:symbol-tree#
126 * @param {Object} object
127 * @return {Object}
128 */
129 nextSibling(object) {
130 return this._node(object).nextSibling;
131 }
132
133 /**
134 * Return the parent of the given object.
135 *
136 * * `O(1)`
137 *
138 * @method parent
139 * @memberOf module:symbol-tree#
140 * @param {Object} object
141 * @return {Object}
142 */
143 parent(object) {
144 return this._node(object).parent;
145 }
146
147 /**
148 * Find the inclusive descendant that is last in tree order of the given object.
149 *
150 * * `O(n)` (worst case) where `n` is the depth of the subtree of `object`
151 *
152 * @method lastInclusiveDescendant
153 * @memberOf module:symbol-tree#
154 * @param {Object} object
155 * @return {Object}
156 */
157 lastInclusiveDescendant(object) {
158 let lastChild;
159 let current = object;
160
161 while ((lastChild = this._node(current).lastChild)) {
162 current = lastChild;
163 }
164
165 return current;
166 }
167
168 /**
169 * Find the preceding object (A) of the given object (B).
170 * An object A is preceding an object B if A and B are in the same tree
171 * and A comes before B in tree order.
172 *
173 * * `O(n)` (worst case)
174 * * `O(1)` (amortized when walking the entire tree)
175 *
176 * @method preceding
177 * @memberOf module:symbol-tree#
178 * @param {Object} object
179 * @param {Object} [options]
180 * @param {Object} [options.root] If set, `root` must be an inclusive ancestor
181 * of the return value (or else null is returned). This check _assumes_
182 * that `root` is also an inclusive ancestor of the given `object`
183 * @return {?Object}
184 */
185 preceding(object, options) {
186 const treeRoot = options && options.root;
187
188 if (object === treeRoot) {
189 return null;
190 }
191
192 const previousSibling = this._node(object).previousSibling;
193
194 if (previousSibling) {
195 return this.lastInclusiveDescendant(previousSibling);
196 }
197
198 // if there is no previous sibling return the parent (might be null)
199 return this._node(object).parent;
200 }
201
202 /**
203 * Find the following object (A) of the given object (B).
204 * An object A is following an object B if A and B are in the same tree
205 * and A comes after B in tree order.
206 *
207 * * `O(n)` (worst case) where `n` is the amount of objects in the entire tree
208 * * `O(1)` (amortized when walking the entire tree)
209 *
210 * @method following
211 * @memberOf module:symbol-tree#
212 * @param {!Object} object
213 * @param {Object} [options]
214 * @param {Object} [options.root] If set, `root` must be an inclusive ancestor
215 * of the return value (or else null is returned). This check _assumes_
216 * that `root` is also an inclusive ancestor of the given `object`
217 * @param {Boolean} [options.skipChildren=false] If set, ignore the children of `object`
218 * @return {?Object}
219 */
220 following(object, options) {
221 const treeRoot = options && options.root;
222 const skipChildren = options && options.skipChildren;
223
224 const firstChild = !skipChildren && this._node(object).firstChild;
225
226 if (firstChild) {
227 return firstChild;
228 }
229
230 let current = object;
231
232 do {
233 if (current === treeRoot) {
234 return null;
235 }
236
237 const nextSibling = this._node(current).nextSibling;
238
239 if (nextSibling) {
240 return nextSibling;
241 }
242
243 current = this._node(current).parent;
244 } while (current);
245
246 return null;
247 }
248
249 /**
250 * Append all children of the given object to an array.
251 *
252 * * `O(n)` where `n` is the amount of children of the given `parent`
253 *
254 * @method childrenToArray
255 * @memberOf module:symbol-tree#
256 * @param {Object} parent
257 * @param {Object} [options]
258 * @param {Object[]} [options.array=[]]
259 * @param {Function} [options.filter] Function to test each object before it is added to the array.
260 * Invoked with arguments (object). Should return `true` if an object
261 * is to be included.
262 * @param {*} [options.thisArg] Value to use as `this` when executing `filter`.
263 * @return {Object[]}
264 */
265 childrenToArray(parent, options) {
266 const array = (options && options.array) || [];
267 const filter = (options && options.filter) || returnTrue;
268 const thisArg = (options && options.thisArg) || undefined;
269
270 const parentNode = this._node(parent);
271 let object = parentNode.firstChild;
272 let index = 0;
273
274 while (object) {
275 const node = this._node(object);
276 node.setCachedIndex(parentNode, index);
277
278 if (filter.call(thisArg, object)) {
279 array.push(object);
280 }
281
282 object = node.nextSibling;
283 ++index;
284 }
285
286 return array;
287 }
288
289 /**
290 * Append all inclusive ancestors of the given object to an array.
291 *
292 * * `O(n)` where `n` is the amount of ancestors of the given `object`
293 *
294 * @method ancestorsToArray
295 * @memberOf module:symbol-tree#
296 * @param {Object} object
297 * @param {Object} [options]
298 * @param {Object[]} [options.array=[]]
299 * @param {Function} [options.filter] Function to test each object before it is added to the array.
300 * Invoked with arguments (object). Should return `true` if an object
301 * is to be included.
302 * @param {*} [options.thisArg] Value to use as `this` when executing `filter`.
303 * @return {Object[]}
304 */
305 ancestorsToArray(object, options) {
306 const array = (options && options.array) || [];
307 const filter = (options && options.filter) || returnTrue;
308 const thisArg = (options && options.thisArg) || undefined;
309
310 let ancestor = object;
311
312 while (ancestor) {
313 if (filter.call(thisArg, ancestor)) {
314 array.push(ancestor);
315 }
316 ancestor = this._node(ancestor).parent;
317 }
318
319 return array;
320 }
321
322 /**
323 * Append all descendants of the given object to an array (in tree order).
324 *
325 * * `O(n)` where `n` is the amount of objects in the sub-tree of the given `object`
326 *
327 * @method treeToArray
328 * @memberOf module:symbol-tree#
329 * @param {Object} root
330 * @param {Object} [options]
331 * @param {Object[]} [options.array=[]]
332 * @param {Function} [options.filter] Function to test each object before it is added to the array.
333 * Invoked with arguments (object). Should return `true` if an object
334 * is to be included.
335 * @param {*} [options.thisArg] Value to use as `this` when executing `filter`.
336 * @return {Object[]}
337 */
338 treeToArray(root, options) {
339 const array = (options && options.array) || [];
340 const filter = (options && options.filter) || returnTrue;
341 const thisArg = (options && options.thisArg) || undefined;
342
343 let object = root;
344
345 while (object) {
346 if (filter.call(thisArg, object)) {
347 array.push(object);
348 }
349 object = this.following(object, {root: root});
350 }
351
352 return array;
353 }
354
355 /**
356 * Iterate over all children of the given object
357 *
358 * * `O(1)` for a single iteration
359 *
360 * @method childrenIterator
361 * @memberOf module:symbol-tree#
362 * @param {Object} parent
363 * @param {Object} [options]
364 * @param {Boolean} [options.reverse=false]
365 * @return {Object} An iterable iterator (ES6)
366 */
367 childrenIterator(parent, options) {
368 const reverse = options && options.reverse;
369 const parentNode = this._node(parent);
370
371 return new TreeIterator(
372 this,
373 parent,
374 reverse ? parentNode.lastChild : parentNode.firstChild,
375 reverse ? TreeIterator.PREV : TreeIterator.NEXT
376 );
377 }
378
379 /**
380 * Iterate over all the previous siblings of the given object. (in reverse tree order)
381 *
382 * * `O(1)` for a single iteration
383 *
384 * @method previousSiblingsIterator
385 * @memberOf module:symbol-tree#
386 * @param {Object} object
387 * @return {Object} An iterable iterator (ES6)
388 */
389 previousSiblingsIterator(object) {
390 return new TreeIterator(
391 this,
392 object,
393 this._node(object).previousSibling,
394 TreeIterator.PREV
395 );
396 }
397
398 /**
399 * Iterate over all the next siblings of the given object. (in tree order)
400 *
401 * * `O(1)` for a single iteration
402 *
403 * @method nextSiblingsIterator
404 * @memberOf module:symbol-tree#
405 * @param {Object} object
406 * @return {Object} An iterable iterator (ES6)
407 */
408 nextSiblingsIterator(object) {
409 return new TreeIterator(
410 this,
411 object,
412 this._node(object).nextSibling,
413 TreeIterator.NEXT
414 );
415 }
416
417 /**
418 * Iterate over all inclusive ancestors of the given object
419 *
420 * * `O(1)` for a single iteration
421 *
422 * @method ancestorsIterator
423 * @memberOf module:symbol-tree#
424 * @param {Object} object
425 * @return {Object} An iterable iterator (ES6)
426 */
427 ancestorsIterator(object) {
428 return new TreeIterator(
429 this,
430 object,
431 object,
432 TreeIterator.PARENT
433 );
434 }
435
436 /**
437 * Iterate over all descendants of the given object (in tree order).
438 *
439 * Where `n` is the amount of objects in the sub-tree of the given `root`:
440 *
441 * * `O(n)` (worst case for a single iteration)
442 * * `O(n)` (amortized, when completing the iterator)
443 *
444 * @method treeIterator
445 * @memberOf module:symbol-tree#
446 * @param {Object} root
447 * @param {Object} options
448 * @param {Boolean} [options.reverse=false]
449 * @return {Object} An iterable iterator (ES6)
450 */
451 treeIterator(root, options) {
452 const reverse = options && options.reverse;
453
454 return new TreeIterator(
455 this,
456 root,
457 reverse ? this.lastInclusiveDescendant(root) : root,
458 reverse ? TreeIterator.PRECEDING : TreeIterator.FOLLOWING
459 );
460 }
461
462 /**
463 * Find the index of the given object (the number of preceding siblings).
464 *
465 * * `O(n)` where `n` is the amount of preceding siblings
466 * * `O(1)` (amortized, if the tree is not modified)
467 *
468 * @method index
469 * @memberOf module:symbol-tree#
470 * @param {Object} child
471 * @return {Number} The number of preceding siblings, or -1 if the object has no parent
472 */
473 index(child) {
474 const childNode = this._node(child);
475 const parentNode = this._node(childNode.parent);
476
477 if (!parentNode) {
478 // In principal, you could also find out the number of preceding siblings
479 // for objects that do not have a parent. This method limits itself only to
480 // objects that have a parent because that lets us optimize more.
481 return -1;
482 }
483
484 let currentIndex = childNode.getCachedIndex(parentNode);
485
486 if (currentIndex >= 0) {
487 return currentIndex;
488 }
489
490 currentIndex = 0;
491 let object = parentNode.firstChild;
492
493 if (parentNode.childIndexCachedUpTo) {
494 const cachedUpToNode = this._node(parentNode.childIndexCachedUpTo);
495 object = cachedUpToNode.nextSibling;
496 currentIndex = cachedUpToNode.getCachedIndex(parentNode) + 1;
497 }
498
499 while (object) {
500 const node = this._node(object);
501 node.setCachedIndex(parentNode, currentIndex);
502
503 if (object === child) {
504 break;
505 }
506
507 ++currentIndex;
508 object = node.nextSibling;
509 }
510
511 parentNode.childIndexCachedUpTo = child;
512
513 return currentIndex;
514 }
515
516 /**
517 * Calculate the number of children.
518 *
519 * * `O(n)` where `n` is the amount of children
520 * * `O(1)` (amortized, if the tree is not modified)
521 *
522 * @method childrenCount
523 * @memberOf module:symbol-tree#
524 * @param {Object} parent
525 * @return {Number}
526 */
527 childrenCount(parent) {
528 const parentNode = this._node(parent);
529
530 if (!parentNode.lastChild) {
531 return 0;
532 }
533
534 return this.index(parentNode.lastChild) + 1;
535 }
536
537 /**
538 * Compare the position of an object relative to another object. A bit set is returned:
539 *
540 * <ul>
541 * <li>DISCONNECTED : 1</li>
542 * <li>PRECEDING : 2</li>
543 * <li>FOLLOWING : 4</li>
544 * <li>CONTAINS : 8</li>
545 * <li>CONTAINED_BY : 16</li>
546 * </ul>
547 *
548 * The semantics are the same as compareDocumentPosition in DOM, with the exception that
549 * DISCONNECTED never occurs with any other bit.
550 *
551 * where `n` and `m` are the amount of ancestors of `left` and `right`;
552 * where `o` is the amount of children of the lowest common ancestor of `left` and `right`:
553 *
554 * * `O(n + m + o)` (worst case)
555 * * `O(n + m)` (amortized, if the tree is not modified)
556 *
557 * @method compareTreePosition
558 * @memberOf module:symbol-tree#
559 * @param {Object} left
560 * @param {Object} right
561 * @return {Number}
562 */
563 compareTreePosition(left, right) {
564 // In DOM terms:
565 // left = reference / context object
566 // right = other
567
568 if (left === right) {
569 return 0;
570 }
571
572 /* jshint -W016 */
573
574 const leftAncestors = []; { // inclusive
575 let leftAncestor = left;
576
577 while (leftAncestor) {
578 if (leftAncestor === right) {
579 return TreePosition.CONTAINS | TreePosition.PRECEDING;
580 // other is ancestor of reference
581 }
582
583 leftAncestors.push(leftAncestor);
584 leftAncestor = this.parent(leftAncestor);
585 }
586 }
587
588
589 const rightAncestors = []; {
590 let rightAncestor = right;
591
592 while (rightAncestor) {
593 if (rightAncestor === left) {
594 return TreePosition.CONTAINED_BY | TreePosition.FOLLOWING;
595 }
596
597 rightAncestors.push(rightAncestor);
598 rightAncestor = this.parent(rightAncestor);
599 }
600 }
601
602
603 const root = reverseArrayIndex(leftAncestors, 0);
604
605 if (!root || root !== reverseArrayIndex(rightAncestors, 0)) {
606 // note: unlike DOM, preceding / following is not set here
607 return TreePosition.DISCONNECTED;
608 }
609
610 // find the lowest common ancestor
611 let commonAncestorIndex = 0;
612 const ancestorsMinLength = Math.min(leftAncestors.length, rightAncestors.length);
613
614 for (let i = 0; i < ancestorsMinLength; ++i) {
615 const leftAncestor = reverseArrayIndex(leftAncestors, i);
616 const rightAncestor = reverseArrayIndex(rightAncestors, i);
617
618 if (leftAncestor !== rightAncestor) {
619 break;
620 }
621
622 commonAncestorIndex = i;
623 }
624
625 // indexes within the common ancestor
626 const leftIndex = this.index(reverseArrayIndex(leftAncestors, commonAncestorIndex + 1));
627 const rightIndex = this.index(reverseArrayIndex(rightAncestors, commonAncestorIndex + 1));
628
629 return rightIndex < leftIndex
630 ? TreePosition.PRECEDING
631 : TreePosition.FOLLOWING;
632 }
633
634 /**
635 * Remove the object from this tree.
636 * Has no effect if already removed.
637 *
638 * * `O(1)`
639 *
640 * @method remove
641 * @memberOf module:symbol-tree#
642 * @param {Object} removeObject
643 * @return {Object} removeObject
644 */
645 remove(removeObject) {
646 const removeNode = this._node(removeObject);
647 const parentNode = this._node(removeNode.parent);
648 const prevNode = this._node(removeNode.previousSibling);
649 const nextNode = this._node(removeNode.nextSibling);
650
651 if (parentNode) {
652 if (parentNode.firstChild === removeObject) {
653 parentNode.firstChild = removeNode.nextSibling;
654 }
655
656 if (parentNode.lastChild === removeObject) {
657 parentNode.lastChild = removeNode.previousSibling;
658 }
659 }
660
661 if (prevNode) {
662 prevNode.nextSibling = removeNode.nextSibling;
663 }
664
665 if (nextNode) {
666 nextNode.previousSibling = removeNode.previousSibling;
667 }
668
669 removeNode.parent = null;
670 removeNode.previousSibling = null;
671 removeNode.nextSibling = null;
672 removeNode.cachedIndex = -1;
673 removeNode.cachedIndexVersion = NaN;
674
675 if (parentNode) {
676 parentNode.childrenChanged();
677 }
678
679 return removeObject;
680 }
681
682 /**
683 * Insert the given object before the reference object.
684 * `newObject` is now the previous sibling of `referenceObject`.
685 *
686 * * `O(1)`
687 *
688 * @method insertBefore
689 * @memberOf module:symbol-tree#
690 * @param {Object} referenceObject
691 * @param {Object} newObject
692 * @throws {Error} If the newObject is already present in this SymbolTree
693 * @return {Object} newObject
694 */
695 insertBefore(referenceObject, newObject) {
696 const referenceNode = this._node(referenceObject);
697 const prevNode = this._node(referenceNode.previousSibling);
698 const newNode = this._node(newObject);
699 const parentNode = this._node(referenceNode.parent);
700
701 if (newNode.isAttached) {
702 throw Error('Given object is already present in this SymbolTree, remove it first');
703 }
704
705 newNode.parent = referenceNode.parent;
706 newNode.previousSibling = referenceNode.previousSibling;
707 newNode.nextSibling = referenceObject;
708 referenceNode.previousSibling = newObject;
709
710 if (prevNode) {
711 prevNode.nextSibling = newObject;
712 }
713
714 if (parentNode && parentNode.firstChild === referenceObject) {
715 parentNode.firstChild = newObject;
716 }
717
718 if (parentNode) {
719 parentNode.childrenChanged();
720 }
721
722 return newObject;
723 }
724
725 /**
726 * Insert the given object after the reference object.
727 * `newObject` is now the next sibling of `referenceObject`.
728 *
729 * * `O(1)`
730 *
731 * @method insertAfter
732 * @memberOf module:symbol-tree#
733 * @param {Object} referenceObject
734 * @param {Object} newObject
735 * @throws {Error} If the newObject is already present in this SymbolTree
736 * @return {Object} newObject
737 */
738 insertAfter(referenceObject, newObject) {
739 const referenceNode = this._node(referenceObject);
740 const nextNode = this._node(referenceNode.nextSibling);
741 const newNode = this._node(newObject);
742 const parentNode = this._node(referenceNode.parent);
743
744 if (newNode.isAttached) {
745 throw Error('Given object is already present in this SymbolTree, remove it first');
746 }
747
748 newNode.parent = referenceNode.parent;
749 newNode.previousSibling = referenceObject;
750 newNode.nextSibling = referenceNode.nextSibling;
751 referenceNode.nextSibling = newObject;
752
753 if (nextNode) {
754 nextNode.previousSibling = newObject;
755 }
756
757 if (parentNode && parentNode.lastChild === referenceObject) {
758 parentNode.lastChild = newObject;
759 }
760
761 if (parentNode) {
762 parentNode.childrenChanged();
763 }
764
765 return newObject;
766 }
767
768 /**
769 * Insert the given object as the first child of the given reference object.
770 * `newObject` is now the first child of `referenceObject`.
771 *
772 * * `O(1)`
773 *
774 * @method prependChild
775 * @memberOf module:symbol-tree#
776 * @param {Object} referenceObject
777 * @param {Object} newObject
778 * @throws {Error} If the newObject is already present in this SymbolTree
779 * @return {Object} newObject
780 */
781 prependChild(referenceObject, newObject) {
782 const referenceNode = this._node(referenceObject);
783 const newNode = this._node(newObject);
784
785 if (newNode.isAttached) {
786 throw Error('Given object is already present in this SymbolTree, remove it first');
787 }
788
789 if (referenceNode.hasChildren) {
790 this.insertBefore(referenceNode.firstChild, newObject);
791 }
792 else {
793 newNode.parent = referenceObject;
794 referenceNode.firstChild = newObject;
795 referenceNode.lastChild = newObject;
796 referenceNode.childrenChanged();
797 }
798
799 return newObject;
800 }
801
802 /**
803 * Insert the given object as the last child of the given reference object.
804 * `newObject` is now the last child of `referenceObject`.
805 *
806 * * `O(1)`
807 *
808 * @method appendChild
809 * @memberOf module:symbol-tree#
810 * @param {Object} referenceObject
811 * @param {Object} newObject
812 * @throws {Error} If the newObject is already present in this SymbolTree
813 * @return {Object} newObject
814 */
815 appendChild(referenceObject, newObject) {
816 const referenceNode = this._node(referenceObject);
817 const newNode = this._node(newObject);
818
819 if (newNode.isAttached) {
820 throw Error('Given object is already present in this SymbolTree, remove it first');
821 }
822
823 if (referenceNode.hasChildren) {
824 this.insertAfter(referenceNode.lastChild, newObject);
825 }
826 else {
827 newNode.parent = referenceObject;
828 referenceNode.firstChild = newObject;
829 referenceNode.lastChild = newObject;
830 referenceNode.childrenChanged();
831 }
832
833 return newObject;
834 }
835}
836
837module.exports = SymbolTree;
838SymbolTree.TreePosition = TreePosition;
Note: See TracBrowser for help on using the repository browser.