jsdom/js-symbol-tree

Turn any collection of objects into its own efficient tree or linked list using Symbol

symbol-tree

Turn any collection of objects into its own efficient tree or linked list using Symbol.

This library has been designed to provide an efficient backing data structure for DOM trees. You can also use this library as an efficient linked list. Any meta data is stored on your objects directly, which ensures any kind of insertion or deletion is performed in constant time. Because an ES6 Symbol is used, the meta data does not interfere with your object in any way.

Node.js 4+, io.js and modern browsers are supported.

Example

A linked list:

const SymbolTree = require('symbol-tree');
const tree = new SymbolTree();

let a = {foo: 'bar'}; // or `new Whatever()`
let b = {foo: 'baz'};
let c = {foo: 'qux'};

tree.insertBefore(b, a); // insert a before b
tree.insertAfter(b, c); // insert c after b

console.log(tree.nextSibling(a) === b);
console.log(tree.nextSibling(b) === c);
console.log(tree.previousSibling(c) === b);

tree.remove(b);
console.log(tree.nextSibling(a) === c);

A tree:

const SymbolTree = require('symbol-tree');
const tree = new SymbolTree();

let parent = {};
let a = {};
let b = {};
let c = {};

tree.prependChild(parent, a); // insert a as the first child
tree.appendChild(parent,c ); // insert c as the last child
tree.insertAfter(a, b); // insert b after a, it now has the same parent as a

console.log(tree.firstChild(parent) === a);
console.log(tree.nextSibling(tree.firstChild(parent)) === b);
console.log(tree.lastChild(parent) === c);

let grandparent = {};
tree.prependChild(grandparent, parent);
console.log(tree.firstChild(tree.firstChild(grandparent)) === a);

See api.md for more documentation.

Testing

Make sure you install the dependencies first:

npm install

You can now run the unit tests by executing:

npm test

The line and branch coverage should be 100%.

API Documentation

symbol-tree

Author: Joris van der Wel [email protected]

• symbol-tree
  • SymbolTree ⏏
    • new SymbolTree([description])
    • .initialize(object) ⇒ Object
    • .hasChildren(object) ⇒ Boolean
    • .firstChild(object) ⇒ Object
    • .lastChild(object) ⇒ Object
    • .previousSibling(object) ⇒ Object
    • .nextSibling(object) ⇒ Object
    • .parent(object) ⇒ Object
    • .lastInclusiveDescendant(object) ⇒ Object
    • .preceding(object, [options]) ⇒ Object
    • .following(object, [options]) ⇒ Object
    • .childrenToArray(parent, [options]) ⇒ Array.<Object>
    • .ancestorsToArray(object, [options]) ⇒ Array.<Object>
    • .treeToArray(root, [options]) ⇒ Array.<Object>
    • .childrenIterator(parent, [options]) ⇒ Object
    • .previousSiblingsIterator(object) ⇒ Object
    • .nextSiblingsIterator(object) ⇒ Object
    • .ancestorsIterator(object) ⇒ Object
    • .treeIterator(root, [options]) ⇒ Object
    • .index(child) ⇒ Number
    • .childrenCount(parent) ⇒ Number
    • .compareTreePosition(left, right) ⇒ Number
    • .remove(removeObject) ⇒ Object
    • .insertBefore(referenceObject, newObject) ⇒ Object
    • .insertAfter(referenceObject, newObject) ⇒ Object
    • .prependChild(referenceObject, newObject) ⇒ Object
    • .appendChild(referenceObject, newObject) ⇒ Object

SymbolTree ⏏

Kind: Exported class

new SymbolTree([description])

Param	Type	Default	Description
[description]	string	"'SymbolTree data'"	Description used for the Symbol

symbolTree.initialize(object) ⇒ Object

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)

Kind: instance method of SymbolTree
Returns: Object - object

Param	Type
object	Object

symbolTree.hasChildren(object) ⇒ Boolean

Returns true if the object has any children. Otherwise it returns false.

• O(1)

Kind: instance method of SymbolTree

Param	Type
object	Object

symbolTree.firstChild(object) ⇒ Object

Returns the first child of the given object.

• O(1)

Kind: instance method of SymbolTree

Param	Type
object	Object

symbolTree.lastChild(object) ⇒ Object

Returns the last child of the given object.

• O(1)

Kind: instance method of SymbolTree

Param	Type
object	Object

symbolTree.previousSibling(object) ⇒ Object

Returns the previous sibling of the given object.

• O(1)

Kind: instance method of SymbolTree

Param	Type
object	Object

symbolTree.nextSibling(object) ⇒ Object

Returns the next sibling of the given object.

• O(1)

Kind: instance method of SymbolTree

Param	Type
object	Object

symbolTree.parent(object) ⇒ Object

Return the parent of the given object.

• O(1)

Kind: instance method of SymbolTree

Param	Type
object	Object

symbolTree.lastInclusiveDescendant(object) ⇒ Object

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

Kind: instance method of SymbolTree

Param	Type
object	Object

symbolTree.preceding(object, [options]) ⇒ Object

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)

Kind: instance method of SymbolTree

Param	Type	Description
object	Object
[options]	Object
[options.root]	Object	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

symbolTree.following(object, [options]) ⇒ Object

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)

Kind: instance method of SymbolTree

Param	Type	Default	Description
object	Object
[options]	Object
[options.root]	Object		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
[options.skipChildren]	Boolean	false	If set, ignore the children of object

symbolTree.childrenToArray(parent, [options]) ⇒ Array.<Object>

Append all children of the given object to an array.

• O(n) where n is the amount of children of the given parent

Kind: instance method of SymbolTree

Param	Type	Default	Description
parent	Object
[options]	Object
[options.array]	Array.<Object>	[]
[options.filter]	function		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.
[options.thisArg]	*		Value to use as this when executing filter.

symbolTree.ancestorsToArray(object, [options]) ⇒ Array.<Object>

Append all inclusive ancestors of the given object to an array.

• O(n) where n is the amount of ancestors of the given object

Kind: instance method of SymbolTree

Param	Type	Default	Description
object	Object
[options]	Object
[options.array]	Array.<Object>	[]
[options.filter]	function		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.
[options.thisArg]	*		Value to use as this when executing filter.

symbolTree.treeToArray(root, [options]) ⇒ Array.<Object>

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

Kind: instance method of SymbolTree

Param	Type	Default	Description
root	Object
[options]	Object
[options.array]	Array.<Object>	[]
[options.filter]	function		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.
[options.thisArg]	*		Value to use as this when executing filter.

symbolTree.childrenIterator(parent, [options]) ⇒ Object

Iterate over all children of the given object

• O(1) for a single iteration

Kind: instance method of SymbolTree
Returns: Object - An iterable iterator (ES6)

Param	Type	Default
parent	Object
[options]	Object
[options.reverse]	Boolean	false

symbolTree.previousSiblingsIterator(object) ⇒ Object

Iterate over all the previous siblings of the given object. (in reverse tree order)

• O(1) for a single iteration

Kind: instance method of SymbolTree
Returns: Object - An iterable iterator (ES6)

Param	Type
object	Object

symbolTree.nextSiblingsIterator(object) ⇒ Object

Iterate over all the next siblings of the given object. (in tree order)

• O(1) for a single iteration

Kind: instance method of SymbolTree
Returns: Object - An iterable iterator (ES6)

Param	Type
object	Object

symbolTree.ancestorsIterator(object) ⇒ Object

Iterate over all inclusive ancestors of the given object

• O(1) for a single iteration

Kind: instance method of SymbolTree
Returns: Object - An iterable iterator (ES6)

Param	Type
object	Object

symbolTree.treeIterator(root, [options]) ⇒ Object

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)

Kind: instance method of SymbolTree
Returns: Object - An iterable iterator (ES6)

Param	Type	Default
root	Object
[options]	Object
[options.reverse]	Boolean	false

symbolTree.index(child) ⇒ Number

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)

Kind: instance method of SymbolTree
Returns: Number - The number of preceding siblings, or -1 if the object has no parent

Param	Type
child	Object

symbolTree.childrenCount(parent) ⇒ Number

Calculate the number of children.

• O(n) where n is the amount of children
• O(1) (amortized, if the tree is not modified)

Kind: instance method of SymbolTree

Param	Type
parent	Object

symbolTree.compareTreePosition(left, right) ⇒ Number

Compare the position of an object relative to another object. A bit set is returned:

• DISCONNECTED : 1
• PRECEDING : 2
• FOLLOWING : 4
• CONTAINS : 8
• CONTAINED_BY : 16

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)

Kind: instance method of SymbolTree

Param	Type
left	Object
right	Object

symbolTree.remove(removeObject) ⇒ Object

Remove the object from this tree. Has no effect if already removed.

• O(1)

Kind: instance method of SymbolTree
Returns: Object - removeObject

Param	Type
removeObject	Object

symbolTree.insertBefore(referenceObject, newObject) ⇒ Object

Insert the given object before the reference object. newObject is now the previous sibling of referenceObject.

• O(1)

Kind: instance method of SymbolTree
Returns: Object - newObject
Throws:

• Error If the newObject is already present in this SymbolTree

Param	Type
referenceObject	Object
newObject	Object

symbolTree.insertAfter(referenceObject, newObject) ⇒ Object

Insert the given object after the reference object. newObject is now the next sibling of referenceObject.

• O(1)

Kind: instance method of SymbolTree
Returns: Object - newObject
Throws:

• Error If the newObject is already present in this SymbolTree

Param	Type
referenceObject	Object
newObject	Object

symbolTree.prependChild(referenceObject, newObject) ⇒ Object

Insert the given object as the first child of the given reference object. newObject is now the first child of referenceObject.

• O(1)

Kind: instance method of SymbolTree
Returns: Object - newObject
Throws:

• Error If the newObject is already present in this SymbolTree

Param	Type
referenceObject	Object
newObject	Object

symbolTree.appendChild(referenceObject, newObject) ⇒ Object

Insert the given object as the last child of the given reference object. newObject is now the last child of referenceObject.

• O(1)

Kind: instance method of SymbolTree
Returns: Object - newObject
Throws:

• Error If the newObject is already present in this SymbolTree

Param	Type
referenceObject	Object
newObject	Object

js-symbol-tree's Issues

Level (or depth) of a node

When I use the Iterator, I would want to know the level of a node.
Is there a (low complexity) way to have the level of a node?

Level: "The level of a node is defined as: 1 + the number of edges between the node and the root."
Depth: "The depth of a node is the number of edges from the tree's root node to the node."
(from Wikipedia)

Would be also interesting to have other characteristics about the tree:

• is Branch node (or is Internal node)
• Height of node
• Height of tree
• Depth

Braces on a new line, really?

I can understand strange preferences for 8-space indents. Even tabs. But newlines before braces? That is just crazy-sauce. (In part due to the return hazard, but also just because absolutely nobody does it.)

Feel free to close if you really want to keep this :P

Symbol not getting removed when item is removed from tree

When items are repeatedly added to and removed from new trees, the symbols stay and start clogging up the memory. Don't know if this is necessary by design or not.

My simple test:

const SymbolTree = require('symbol-tree');

const base = [];
for(let i=0; i<100; i++) {
	base.push({ content: i });
}

for(let i=0; i<1000; i++) {
	let tree = new SymbolTree();
	let root = { root: true };
	base.forEach(obj => {
		tree.appendChild(root, obj);
	});

	let it = tree.childrenIterator(root);
	for( child of it ){
		tree.remove(child);
	}
	console.log(JSON.stringify(process.memoryUsage()));

}

Babel balks when transpiling symbol-tree

This is due to a duplicate declaration in SymbolTree.js:

symbol-tree/lib/SymbolTree.js: Duplicate declaration "index"
  481 |                 }
  482 | 
> 483 |                 let index = childNode.getCachedIndex(parentNode);
      |                     ^
  484 | 
  485 |                 if (index >= 0) {
  486 |                         return index;

An in-range update of babel-eslint is breaking the build 🚨

Version 8.2.6 of babel-eslint was just published.

Branch	Build failing 🚨
Dependency	babel-eslint
Current Version	8.2.5
Type	devDependency

This version is covered by your current version range and after updating it in your project the build failed.

babel-eslint is a devDependency of this project. It might not break your production code or affect downstream projects, but probably breaks your build or test tools, which may prevent deploying or publishing.

Status Details

• ❌ continuous-integration/travis-ci/push The Travis CI build could not complete due to an error Details

---

Commits

The new version differs by 2 commits.

• b9067fa 8.2.6
• c797a36 pin to [email protected]

See the full diff

FAQ and help

There is a collection of frequently asked questions. If those don’t help, you can always ask the humans behind Greenkeeper.

---

Your Greenkeeper Bot 🌴

Want to move to the jsdom org?

Up to you, but if you do let me know. We've put a few things there.

api.md in readme is 404

api.md is 404

An in-range update of tape is breaking the build 🚨

The devDependency tape was updated from 4.12.0 to 4.12.1.

🚨 View failing branch.

This version is covered by your current version range and after updating it in your project the build failed.

tape is a devDependency of this project. It might not break your production code or affect downstream projects, but probably breaks your build or test tools, which may prevent deploying or publishing.

Status Details

• ❌ continuous-integration/travis-ci/push: The Travis CI build failed (Details).

---

Commits

The new version differs by 4 commits.

• 25bcbc6 v4.12.1
• 9094271 [Fix] error stack file path can contain parens/spaces
• b765bba [Deps] update resolve
• 949781f [Dev Deps] update eslint

See the full diff

FAQ and help

There is a collection of frequently asked questions. If those don’t help, you can always ask the humans behind Greenkeeper.

---

Your Greenkeeper Bot 🌴

Add a method to tell if a node is part of the symbol tree

I am running into some tricky initialization time issues in jsdom and need something like domSymbolTree.isInitialized(node), so I can bail out early if we're still in the pre-symbol-tree phase.

Use class syntax

Would be a lot more readable I think :)