Wondering what’s next for npm?Check out our public roadmap! »

    symbol-tree
    DefinitelyTyped icon, indicating that this package has TypeScript declarations provided by the separate @types/symbol-tree package

    3.2.4 • Public • Published

    symbol-tree

    Travis CI Build Status Coverage Status

    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,); // 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 joris@jorisvanderwel.com

    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

    Install

    npm i symbol-tree

    DownloadsWeekly Downloads

    11,740,173

    Version

    3.2.4

    License

    MIT

    Unpacked Size

    57.1 kB

    Total Files

    7

    Last publish

    Collaborators

    • avatar