123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838 |
- 'use strict';
- const SymbolTreeNode = require('./SymbolTreeNode');
- const TreePosition = require('./TreePosition');
- const TreeIterator = require('./TreeIterator');
- function returnTrue() {
- return true;
- }
- function reverseArrayIndex(array, reverseIndex) {
- return array[array.length - 1 - reverseIndex];
- }
- class SymbolTree {
-
- constructor(description) {
- this.symbol = Symbol(description || 'SymbolTree data');
- }
-
- initialize(object) {
- this._node(object);
- return object;
- }
- _node(object) {
- if (!object) {
- return null;
- }
- const node = object[this.symbol];
- if (node) {
- return node;
- }
- return (object[this.symbol] = new SymbolTreeNode());
- }
-
- hasChildren(object) {
- return this._node(object).hasChildren;
- }
-
- firstChild(object) {
- return this._node(object).firstChild;
- }
-
- lastChild(object) {
- return this._node(object).lastChild;
- }
-
- previousSibling(object) {
- return this._node(object).previousSibling;
- }
-
- nextSibling(object) {
- return this._node(object).nextSibling;
- }
-
- parent(object) {
- return this._node(object).parent;
- }
-
- lastInclusiveDescendant(object) {
- let lastChild;
- let current = object;
- while ((lastChild = this._node(current).lastChild)) {
- current = lastChild;
- }
- return current;
- }
-
- preceding(object, options) {
- const treeRoot = options && options.root;
- if (object === treeRoot) {
- return null;
- }
- const previousSibling = this._node(object).previousSibling;
- if (previousSibling) {
- return this.lastInclusiveDescendant(previousSibling);
- }
-
- return this._node(object).parent;
- }
-
- following(object, options) {
- const treeRoot = options && options.root;
- const skipChildren = options && options.skipChildren;
- const firstChild = !skipChildren && this._node(object).firstChild;
- if (firstChild) {
- return firstChild;
- }
- let current = object;
- do {
- if (current === treeRoot) {
- return null;
- }
- const nextSibling = this._node(current).nextSibling;
- if (nextSibling) {
- return nextSibling;
- }
- current = this._node(current).parent;
- } while (current);
- return null;
- }
-
- childrenToArray(parent, options) {
- const array = (options && options.array) || [];
- const filter = (options && options.filter) || returnTrue;
- const thisArg = (options && options.thisArg) || undefined;
- const parentNode = this._node(parent);
- let object = parentNode.firstChild;
- let index = 0;
- while (object) {
- const node = this._node(object);
- node.setCachedIndex(parentNode, index);
- if (filter.call(thisArg, object)) {
- array.push(object);
- }
- object = node.nextSibling;
- ++index;
- }
- return array;
- }
-
- ancestorsToArray(object, options) {
- const array = (options && options.array) || [];
- const filter = (options && options.filter) || returnTrue;
- const thisArg = (options && options.thisArg) || undefined;
- let ancestor = object;
- while (ancestor) {
- if (filter.call(thisArg, ancestor)) {
- array.push(ancestor);
- }
- ancestor = this._node(ancestor).parent;
- }
- return array;
- }
-
- treeToArray(root, options) {
- const array = (options && options.array) || [];
- const filter = (options && options.filter) || returnTrue;
- const thisArg = (options && options.thisArg) || undefined;
- let object = root;
- while (object) {
- if (filter.call(thisArg, object)) {
- array.push(object);
- }
- object = this.following(object, {root: root});
- }
- return array;
- }
-
- childrenIterator(parent, options) {
- const reverse = options && options.reverse;
- const parentNode = this._node(parent);
- return new TreeIterator(
- this,
- parent,
- reverse ? parentNode.lastChild : parentNode.firstChild,
- reverse ? TreeIterator.PREV : TreeIterator.NEXT
- );
- }
-
- previousSiblingsIterator(object) {
- return new TreeIterator(
- this,
- object,
- this._node(object).previousSibling,
- TreeIterator.PREV
- );
- }
-
- nextSiblingsIterator(object) {
- return new TreeIterator(
- this,
- object,
- this._node(object).nextSibling,
- TreeIterator.NEXT
- );
- }
-
- ancestorsIterator(object) {
- return new TreeIterator(
- this,
- object,
- object,
- TreeIterator.PARENT
- );
- }
-
- treeIterator(root, options) {
- const reverse = options && options.reverse;
- return new TreeIterator(
- this,
- root,
- reverse ? this.lastInclusiveDescendant(root) : root,
- reverse ? TreeIterator.PRECEDING : TreeIterator.FOLLOWING
- );
- }
-
- index(child) {
- const childNode = this._node(child);
- const parentNode = this._node(childNode.parent);
- if (!parentNode) {
-
-
-
- return -1;
- }
- let currentIndex = childNode.getCachedIndex(parentNode);
- if (currentIndex >= 0) {
- return currentIndex;
- }
- currentIndex = 0;
- let object = parentNode.firstChild;
- if (parentNode.childIndexCachedUpTo) {
- const cachedUpToNode = this._node(parentNode.childIndexCachedUpTo);
- object = cachedUpToNode.nextSibling;
- currentIndex = cachedUpToNode.getCachedIndex(parentNode) + 1;
- }
- while (object) {
- const node = this._node(object);
- node.setCachedIndex(parentNode, currentIndex);
- if (object === child) {
- break;
- }
- ++currentIndex;
- object = node.nextSibling;
- }
- parentNode.childIndexCachedUpTo = child;
- return currentIndex;
- }
-
- childrenCount(parent) {
- const parentNode = this._node(parent);
- if (!parentNode.lastChild) {
- return 0;
- }
- return this.index(parentNode.lastChild) + 1;
- }
-
- compareTreePosition(left, right) {
-
-
-
- if (left === right) {
- return 0;
- }
-
- const leftAncestors = []; {
- let leftAncestor = left;
- while (leftAncestor) {
- if (leftAncestor === right) {
- return TreePosition.CONTAINS | TreePosition.PRECEDING;
-
- }
- leftAncestors.push(leftAncestor);
- leftAncestor = this.parent(leftAncestor);
- }
- }
- const rightAncestors = []; {
- let rightAncestor = right;
- while (rightAncestor) {
- if (rightAncestor === left) {
- return TreePosition.CONTAINED_BY | TreePosition.FOLLOWING;
- }
- rightAncestors.push(rightAncestor);
- rightAncestor = this.parent(rightAncestor);
- }
- }
- const root = reverseArrayIndex(leftAncestors, 0);
- if (!root || root !== reverseArrayIndex(rightAncestors, 0)) {
-
- return TreePosition.DISCONNECTED;
- }
-
- let commonAncestorIndex = 0;
- const ancestorsMinLength = Math.min(leftAncestors.length, rightAncestors.length);
- for (let i = 0; i < ancestorsMinLength; ++i) {
- const leftAncestor = reverseArrayIndex(leftAncestors, i);
- const rightAncestor = reverseArrayIndex(rightAncestors, i);
- if (leftAncestor !== rightAncestor) {
- break;
- }
- commonAncestorIndex = i;
- }
-
- const leftIndex = this.index(reverseArrayIndex(leftAncestors, commonAncestorIndex + 1));
- const rightIndex = this.index(reverseArrayIndex(rightAncestors, commonAncestorIndex + 1));
- return rightIndex < leftIndex
- ? TreePosition.PRECEDING
- : TreePosition.FOLLOWING;
- }
-
- remove(removeObject) {
- const removeNode = this._node(removeObject);
- const parentNode = this._node(removeNode.parent);
- const prevNode = this._node(removeNode.previousSibling);
- const nextNode = this._node(removeNode.nextSibling);
- if (parentNode) {
- if (parentNode.firstChild === removeObject) {
- parentNode.firstChild = removeNode.nextSibling;
- }
- if (parentNode.lastChild === removeObject) {
- parentNode.lastChild = removeNode.previousSibling;
- }
- }
- if (prevNode) {
- prevNode.nextSibling = removeNode.nextSibling;
- }
- if (nextNode) {
- nextNode.previousSibling = removeNode.previousSibling;
- }
- removeNode.parent = null;
- removeNode.previousSibling = null;
- removeNode.nextSibling = null;
- removeNode.cachedIndex = -1;
- removeNode.cachedIndexVersion = NaN;
- if (parentNode) {
- parentNode.childrenChanged();
- }
- return removeObject;
- }
-
- insertBefore(referenceObject, newObject) {
- const referenceNode = this._node(referenceObject);
- const prevNode = this._node(referenceNode.previousSibling);
- const newNode = this._node(newObject);
- const parentNode = this._node(referenceNode.parent);
- if (newNode.isAttached) {
- throw Error('Given object is already present in this SymbolTree, remove it first');
- }
- newNode.parent = referenceNode.parent;
- newNode.previousSibling = referenceNode.previousSibling;
- newNode.nextSibling = referenceObject;
- referenceNode.previousSibling = newObject;
- if (prevNode) {
- prevNode.nextSibling = newObject;
- }
- if (parentNode && parentNode.firstChild === referenceObject) {
- parentNode.firstChild = newObject;
- }
- if (parentNode) {
- parentNode.childrenChanged();
- }
- return newObject;
- }
-
- insertAfter(referenceObject, newObject) {
- const referenceNode = this._node(referenceObject);
- const nextNode = this._node(referenceNode.nextSibling);
- const newNode = this._node(newObject);
- const parentNode = this._node(referenceNode.parent);
- if (newNode.isAttached) {
- throw Error('Given object is already present in this SymbolTree, remove it first');
- }
- newNode.parent = referenceNode.parent;
- newNode.previousSibling = referenceObject;
- newNode.nextSibling = referenceNode.nextSibling;
- referenceNode.nextSibling = newObject;
- if (nextNode) {
- nextNode.previousSibling = newObject;
- }
- if (parentNode && parentNode.lastChild === referenceObject) {
- parentNode.lastChild = newObject;
- }
- if (parentNode) {
- parentNode.childrenChanged();
- }
- return newObject;
- }
-
- prependChild(referenceObject, newObject) {
- const referenceNode = this._node(referenceObject);
- const newNode = this._node(newObject);
- if (newNode.isAttached) {
- throw Error('Given object is already present in this SymbolTree, remove it first');
- }
- if (referenceNode.hasChildren) {
- this.insertBefore(referenceNode.firstChild, newObject);
- }
- else {
- newNode.parent = referenceObject;
- referenceNode.firstChild = newObject;
- referenceNode.lastChild = newObject;
- referenceNode.childrenChanged();
- }
- return newObject;
- }
-
- appendChild(referenceObject, newObject) {
- const referenceNode = this._node(referenceObject);
- const newNode = this._node(newObject);
- if (newNode.isAttached) {
- throw Error('Given object is already present in this SymbolTree, remove it first');
- }
- if (referenceNode.hasChildren) {
- this.insertAfter(referenceNode.lastChild, newObject);
- }
- else {
- newNode.parent = referenceObject;
- referenceNode.firstChild = newObject;
- referenceNode.lastChild = newObject;
- referenceNode.childrenChanged();
- }
- return newObject;
- }
- }
- module.exports = SymbolTree;
- SymbolTree.TreePosition = TreePosition;
|