diff options
Diffstat (limited to 'school/node_modules/symbol-tree/lib/SymbolTree.js')
| -rw-r--r-- | school/node_modules/symbol-tree/lib/SymbolTree.js | 838 |
1 files changed, 838 insertions, 0 deletions
diff --git a/school/node_modules/symbol-tree/lib/SymbolTree.js b/school/node_modules/symbol-tree/lib/SymbolTree.js new file mode 100644 index 0000000..b2b8f2e --- /dev/null +++ b/school/node_modules/symbol-tree/lib/SymbolTree.js @@ -0,0 +1,838 @@ +'use strict'; + +/** + * @module symbol-tree + * @author Joris van der Wel <joris@jorisvanderwel.com> + */ + +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]; // no need to check `index >= 0` +} + +class SymbolTree { + + /** + * @constructor + * @alias module:symbol-tree + * @param {string} [description='SymbolTree data'] Description used for the Symbol + */ + constructor(description) { + this.symbol = Symbol(description || 'SymbolTree data'); + } + + /** + * You can use this function to (optionally) initialize an object right after its creation, + * to take advantage of V8's fast properties. Also useful if you would like to + * freeze your object. + * + * `O(1)` + * + * @method + * @alias module:symbol-tree#initialize + * @param {Object} object + * @return {Object} object + */ + 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()); + } + + /** + * Returns `true` if the object has any children. Otherwise it returns `false`. + * + * * `O(1)` + * + * @method hasChildren + * @memberOf module:symbol-tree# + * @param {Object} object + * @return {Boolean} + */ + hasChildren(object) { + return this._node(object).hasChildren; + } + + /** + * Returns the first child of the given object. + * + * * `O(1)` + * + * @method firstChild + * @memberOf module:symbol-tree# + * @param {Object} object + * @return {Object} + */ + firstChild(object) { + return this._node(object).firstChild; + } + + /** + * Returns the last child of the given object. + * + * * `O(1)` + * + * @method lastChild + * @memberOf module:symbol-tree# + * @param {Object} object + * @return {Object} + */ + lastChild(object) { + return this._node(object).lastChild; + } + + /** + * Returns the previous sibling of the given object. + * + * * `O(1)` + * + * @method previousSibling + * @memberOf module:symbol-tree# + * @param {Object} object + * @return {Object} + */ + previousSibling(object) { + return this._node(object).previousSibling; + } + + /** + * Returns the next sibling of the given object. + * + * * `O(1)` + * + * @method nextSibling + * @memberOf module:symbol-tree# + * @param {Object} object + * @return {Object} + */ + nextSibling(object) { + return this._node(object).nextSibling; + } + + /** + * Return the parent of the given object. + * + * * `O(1)` + * + * @method parent + * @memberOf module:symbol-tree# + * @param {Object} object + * @return {Object} + */ + parent(object) { + return this._node(object).parent; + } + + /** + * Find the inclusive descendant that is last in tree order of the given object. + * + * * `O(n)` (worst case) where `n` is the depth of the subtree of `object` + * + * @method lastInclusiveDescendant + * @memberOf module:symbol-tree# + * @param {Object} object + * @return {Object} + */ + lastInclusiveDescendant(object) { + let lastChild; + let current = object; + + while ((lastChild = this._node(current).lastChild)) { + current = lastChild; + } + + return current; + } + + /** + * Find the preceding object (A) of the given object (B). + * An object A is preceding an object B if A and B are in the same tree + * and A comes before B in tree order. + * + * * `O(n)` (worst case) + * * `O(1)` (amortized when walking the entire tree) + * + * @method preceding + * @memberOf module:symbol-tree# + * @param {Object} object + * @param {Object} [options] + * @param {Object} [options.root] If set, `root` must be an inclusive ancestor + * of the return value (or else null is returned). This check _assumes_ + * that `root` is also an inclusive ancestor of the given `object` + * @return {?Object} + */ + 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); + } + + // if there is no previous sibling return the parent (might be null) + return this._node(object).parent; + } + + /** + * Find the following object (A) of the given object (B). + * An object A is following an object B if A and B are in the same tree + * and A comes after B in tree order. + * + * * `O(n)` (worst case) where `n` is the amount of objects in the entire tree + * * `O(1)` (amortized when walking the entire tree) + * + * @method following + * @memberOf module:symbol-tree# + * @param {!Object} object + * @param {Object} [options] + * @param {Object} [options.root] If set, `root` must be an inclusive ancestor + * of the return value (or else null is returned). This check _assumes_ + * that `root` is also an inclusive ancestor of the given `object` + * @param {Boolean} [options.skipChildren=false] If set, ignore the children of `object` + * @return {?Object} + */ + 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; + } + + /** + * Append all children of the given object to an array. + * + * * `O(n)` where `n` is the amount of children of the given `parent` + * + * @method childrenToArray + * @memberOf module:symbol-tree# + * @param {Object} parent + * @param {Object} [options] + * @param {Object[]} [options.array=[]] + * @param {Function} [options.filter] Function to test each object before it is added to the array. + * Invoked with arguments (object). Should return `true` if an object + * is to be included. + * @param {*} [options.thisArg] Value to use as `this` when executing `filter`. + * @return {Object[]} + */ + 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; + } + + /** + * Append all inclusive ancestors of the given object to an array. + * + * * `O(n)` where `n` is the amount of ancestors of the given `object` + * + * @method ancestorsToArray + * @memberOf module:symbol-tree# + * @param {Object} object + * @param {Object} [options] + * @param {Object[]} [options.array=[]] + * @param {Function} [options.filter] Function to test each object before it is added to the array. + * Invoked with arguments (object). Should return `true` if an object + * is to be included. + * @param {*} [options.thisArg] Value to use as `this` when executing `filter`. + * @return {Object[]} + */ + 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; + } + + /** + * Append all descendants of the given object to an array (in tree order). + * + * * `O(n)` where `n` is the amount of objects in the sub-tree of the given `object` + * + * @method treeToArray + * @memberOf module:symbol-tree# + * @param {Object} root + * @param {Object} [options] + * @param {Object[]} [options.array=[]] + * @param {Function} [options.filter] Function to test each object before it is added to the array. + * Invoked with arguments (object). Should return `true` if an object + * is to be included. + * @param {*} [options.thisArg] Value to use as `this` when executing `filter`. + * @return {Object[]} + */ + 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; + } + + /** + * Iterate over all children of the given object + * + * * `O(1)` for a single iteration + * + * @method childrenIterator + * @memberOf module:symbol-tree# + * @param {Object} parent + * @param {Object} [options] + * @param {Boolean} [options.reverse=false] + * @return {Object} An iterable iterator (ES6) + */ + 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 + ); + } + + /** + * Iterate over all the previous siblings of the given object. (in reverse tree order) + * + * * `O(1)` for a single iteration + * + * @method previousSiblingsIterator + * @memberOf module:symbol-tree# + * @param {Object} object + * @return {Object} An iterable iterator (ES6) + */ + previousSiblingsIterator(object) { + return new TreeIterator( + this, + object, + this._node(object).previousSibling, + TreeIterator.PREV + ); + } + + /** + * Iterate over all the next siblings of the given object. (in tree order) + * + * * `O(1)` for a single iteration + * + * @method nextSiblingsIterator + * @memberOf module:symbol-tree# + * @param {Object} object + * @return {Object} An iterable iterator (ES6) + */ + nextSiblingsIterator(object) { + return new TreeIterator( + this, + object, + this._node(object).nextSibling, + TreeIterator.NEXT + ); + } + + /** + * Iterate over all inclusive ancestors of the given object + * + * * `O(1)` for a single iteration + * + * @method ancestorsIterator + * @memberOf module:symbol-tree# + * @param {Object} object + * @return {Object} An iterable iterator (ES6) + */ + ancestorsIterator(object) { + return new TreeIterator( + this, + object, + object, + TreeIterator.PARENT + ); + } + + /** + * Iterate over all descendants of the given object (in tree order). + * + * Where `n` is the amount of objects in the sub-tree of the given `root`: + * + * * `O(n)` (worst case for a single iteration) + * * `O(n)` (amortized, when completing the iterator) + * + * @method treeIterator + * @memberOf module:symbol-tree# + * @param {Object} root + * @param {Object} options + * @param {Boolean} [options.reverse=false] + * @return {Object} An iterable iterator (ES6) + */ + treeIterator(root, options) { + const reverse = options && options.reverse; + + return new TreeIterator( + this, + root, + reverse ? this.lastInclusiveDescendant(root) : root, + reverse ? TreeIterator.PRECEDING : TreeIterator.FOLLOWING + ); + } + + /** + * Find the index of the given object (the number of preceding siblings). + * + * * `O(n)` where `n` is the amount of preceding siblings + * * `O(1)` (amortized, if the tree is not modified) + * + * @method index + * @memberOf module:symbol-tree# + * @param {Object} child + * @return {Number} The number of preceding siblings, or -1 if the object has no parent + */ + index(child) { + const childNode = this._node(child); + const parentNode = this._node(childNode.parent); + + if (!parentNode) { + // In principal, you could also find out the number of preceding siblings + // for objects that do not have a parent. This method limits itself only to + // objects that have a parent because that lets us optimize more. + 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; + } + + /** + * Calculate the number of children. + * + * * `O(n)` where `n` is the amount of children + * * `O(1)` (amortized, if the tree is not modified) + * + * @method childrenCount + * @memberOf module:symbol-tree# + * @param {Object} parent + * @return {Number} + */ + childrenCount(parent) { + const parentNode = this._node(parent); + + if (!parentNode.lastChild) { + return 0; + } + + return this.index(parentNode.lastChild) + 1; + } + + /** + * Compare the position of an object relative to another object. A bit set is returned: + * + * <ul> + * <li>DISCONNECTED : 1</li> + * <li>PRECEDING : 2</li> + * <li>FOLLOWING : 4</li> + * <li>CONTAINS : 8</li> + * <li>CONTAINED_BY : 16</li> + * </ul> + * + * The semantics are the same as compareDocumentPosition in DOM, with the exception that + * DISCONNECTED never occurs with any other bit. + * + * where `n` and `m` are the amount of ancestors of `left` and `right`; + * where `o` is the amount of children of the lowest common ancestor of `left` and `right`: + * + * * `O(n + m + o)` (worst case) + * * `O(n + m)` (amortized, if the tree is not modified) + * + * @method compareTreePosition + * @memberOf module:symbol-tree# + * @param {Object} left + * @param {Object} right + * @return {Number} + */ + compareTreePosition(left, right) { + // In DOM terms: + // left = reference / context object + // right = other + + if (left === right) { + return 0; + } + + /* jshint -W016 */ + + const leftAncestors = []; { // inclusive + let leftAncestor = left; + + while (leftAncestor) { + if (leftAncestor === right) { + return TreePosition.CONTAINS | TreePosition.PRECEDING; + // other is ancestor of reference + } + + 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)) { + // note: unlike DOM, preceding / following is not set here + return TreePosition.DISCONNECTED; + } + + // find the lowest common ancestor + 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; + } + + // indexes within the common ancestor + const leftIndex = this.index(reverseArrayIndex(leftAncestors, commonAncestorIndex + 1)); + const rightIndex = this.index(reverseArrayIndex(rightAncestors, commonAncestorIndex + 1)); + + return rightIndex < leftIndex + ? TreePosition.PRECEDING + : TreePosition.FOLLOWING; + } + + /** + * Remove the object from this tree. + * Has no effect if already removed. + * + * * `O(1)` + * + * @method remove + * @memberOf module:symbol-tree# + * @param {Object} removeObject + * @return {Object} removeObject + */ + 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; + } + + /** + * Insert the given object before the reference object. + * `newObject` is now the previous sibling of `referenceObject`. + * + * * `O(1)` + * + * @method insertBefore + * @memberOf module:symbol-tree# + * @param {Object} referenceObject + * @param {Object} newObject + * @throws {Error} If the newObject is already present in this SymbolTree + * @return {Object} newObject + */ + 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; + } + + /** + * Insert the given object after the reference object. + * `newObject` is now the next sibling of `referenceObject`. + * + * * `O(1)` + * + * @method insertAfter + * @memberOf module:symbol-tree# + * @param {Object} referenceObject + * @param {Object} newObject + * @throws {Error} If the newObject is already present in this SymbolTree + * @return {Object} 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; + } + + /** + * Insert the given object as the first child of the given reference object. + * `newObject` is now the first child of `referenceObject`. + * + * * `O(1)` + * + * @method prependChild + * @memberOf module:symbol-tree# + * @param {Object} referenceObject + * @param {Object} newObject + * @throws {Error} If the newObject is already present in this SymbolTree + * @return {Object} 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; + } + + /** + * Insert the given object as the last child of the given reference object. + * `newObject` is now the last child of `referenceObject`. + * + * * `O(1)` + * + * @method appendChild + * @memberOf module:symbol-tree# + * @param {Object} referenceObject + * @param {Object} newObject + * @throws {Error} If the newObject is already present in this SymbolTree + * @return {Object} 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; |