1tree

Functional API for traversing and manipulating tree structures

  • 1tree

Downloads in past

Stats

StarsIssuesVersionUpdatedCreatedSize
1tree
200.4.146 years ago6 years agoMinified + gzip package size for 1tree in KB

Readme

1tree
1tree
One tree to rule them all, one walk to find them,
One tree to bring them all and in the node graph bind them.

A functional API for traversing and manipulating tree structures

  • extensive traversal and manipulation API (comparable to DOM or jQuery)
  • provide an adapter to any other tree structure by implementing a few simple functions and get the rest of the API for free
  • supports plugins to extend or modify functionality
  • small footprint, no external dependencies, fast
  • optimised for large graphs, full test suite

Quick start

npm install 1tree --save Create a basic tree where each node is just a string: ```javascript const Tree = require( '1tree' ) const root = Tree.createRoot( 'Animalia' ) const chordata = Tree.createNode( 'Chordata' ) root.append( chordata ) root.walk( n => console.log( n.value() ) ) ```

API

Basics

Create a tree: ```javascript const root = Tree.createRoot( rootValue ) ``` Create a node: ```javascript const node = Tree.createNode( value ) ``` Get the node's underlying implementation: ```javascript const rawNode = node.get() ``` Get a node's value: ```javascript const value = node.value() ``` Set a node's value: ```javascript node.value( 'something' ) ``` Note that the value that you give a node can be anything, but I highly recommend that you use only JSON-serializable objects, it makes your resultant graph more useful as you can easily pass it over the wire, store it in a database etc. For most of the examples we just use a string as the node's value. A contrived example using object literals: ```javascript const root = Tree.createRoot({ fileType: 'folder' name: 'Photos' }) const selfie = Tree.createNode({ fileType: 'file', name: 'selfie.jpg' }) root.append( selfie ) ```

Traversal

The comment above each API method example is the function signature in rtype notation

getChildren

Get the child nodes of the current node ```javascript // getChildren() => Node const children = node.getChildren() ```

childAt

Gets the child at the specified index ```javascript // childAt( index: Integer ) => childNode: Node const second = node.childAt( 2 ) ```

index

Gets the index of the node relative to its siblings ```javascript // index() => childIndex: Integer const index = node.index() ```

firstChild

Get the first child of the current node ```javascript // firstChild() => childNode: Node const first = node.firstChild() ```

lastChild

Get the last child of the current node ```javascript // lastChild() => childNode: Node const last = node.lastChild() ```

walk

Do a depth-first traversal of the tree starting at the current node ```javascript // walk( callback: Function ) => Void node.walk( n => console.log( n.value() ) ) ``` The callback is passed the current node, the parent of the current node, and the depth relative to the inital node. You can halt the walk by returning a truthy value from your callback. ```javascript // callback( current: Node, parent: Node, depth: Integer ) => stop: Boolean node.walk( ( current, parent, depth ) => { console.log( current.value(), parent.value() ) if( depth > 5 ) return true }) ```

walkUp

Traverses the tree upwards from the current node, performing a callback on each parent until it reaches the root of the tree or the callback returns a truthy value. The traversal starts from the current node. ```javascript // walkUp( callback: Function ) => Void node.walkUp( n => console.log( n.value() ) ) ``` The callback is passed only the current node: ```javascript // callback( current: Node ) => stop: Boolean node.walkUp( n => { const value = n.value() console.log( value ) if( value === 'Some Value' ) return true }) ```

find

Traverses the tree from the current node and returns the first node matching a passed in predicate function. ```javascript // find( test: Predicate ) => Node const target = node.find( n => n.value() === 'Some Value' ) console.log( target.value() ) ```

findAll

Traverses the tree from the current node and returns all nodes matching a passed in predicate function. ```javascript // findAll( test: Predicate ) => Node const targets = node.findAll( n => n.value() === 'Some Value' ) targets.forEach( n => console.log( n.value() ) ) ```

getParent

Gets the parent of the current node ```javascript // getParent() => parentNode: Node const parent = node.getParent() ```

closest

Finds the first node matching the passed in predicate, traversing upwards from the current node ```javascript // closest( test: Predicate ) => Node const target = node.closest( n => n.value() === 'Some Value' ) console.log( target.value() ) ```

ancestors

Returns a list of all ancestors of the current node, where the head of the list is the current node's parent and the tail is the root node. ```javascript // ancestors() => Node const ancestors = node.ancestors() ancestors.forEach( n => console.log( n.value() ) ) ```

nextSibling

Returns the next sibling of the current node, or undefined if the current node is the last child. ```javascript // nextSibling() => siblingNode: Node const next = node.nextSibling() if( next ){ console.log( 'Next sibling value is', next.value() ) } else { console.log( 'Current node is last child' ) } ```

previousSibling

Returns the previous sibling of the current node, or undefined if the current node is the first child. ```javascript // previousSibling() => siblingNode: Node const prev = node.previousSibling() if( prev ){ console.log( 'Previous sibling value is', prev.value() ) } else { console.log( 'Current node is first child' ) } ```

siblings

Returns all siblings of the current node, excluding the current node. If the current node is the only child of its parent, an empty array is returned. ```javascript // siblings() => Node const siblings = node.siblings() siblings.forEach( n => console.log( n.value() ) ) ```

descendents

Returns all of a node's children, their children etc. as a flat array in depth first order. Returns an empty array if the node has no children. ```javascript // descendents() => Node const descendents = node.descendents() descendents.forEach( n => console.log( n.value() ) ) ```

contains

Returns a boolean indicating whether a node matching the predicate was found, searching from the current node downwards. ```javascript // contains( test: Predicate ) => Boolean const hasValue = node.contains( n => n.value() === 'Some Value' ) ```

hasChildren

Returns a boolean indicating whether or not the current node has any children, or false if it doesn't (is a leaf node). ```javascript // hasChildren() => Boolean const hasChildren = node.hasChildren() ```

isEmpty

Returns a boolean indicating whether or not the current node can have children - note, not the same as hasChildren, which is whether or not the node does have children. The default implementation always returns false, but you can override it to make leaf-only nodes. ```javascript // isEmpty() => Boolean const isEmpty = node.isEmpty() ```

accepts

Returns a boolean indicating whether or not the current node can accept another node. Also extends insertBefore (and by definition all of the other insertion methods, as they are all built on insertBefore) so that an error is thrown if you try to add a child that the parent cannot accept. The default implementation only checks that the node is not isEmpty but it can be extended for custom behavior. ```javascript // accepts( child: Node ) => Boolean const accepts = node.accepts( child ) ```

slug

Returns a string for a node which is unique amongst its siblings. The default implementation uses the node's index converted to a string. ```javascript // slug() => String const slug = node.slug() ```

getPath

Returns a string representing the path from the root to the node. The path is constructed of each node in the path's slug joined together with an optional separator string. The default separator string is /. None of the slugs may contain the separator string, or an error will be thrown. ```javascript // getPath( separator: String = "/" ) => String const path = node.getPath() const path2 = node.getPath( '' ) ```

atPath

Finds the node matching the specified path. The default separator string is /. If not using the default separator, the same separator must be used that was initially used to create the path. If the path is invalid or no node matched the path, undefined will be returned. ```javascript // atPath( path: String, separator: String = "/" ) => Node | Undefined const node = root.atPath( '/0/1/0/3/2' ) ```

Manipulation

append

Adds the new node to the tail end of the current node's child list. If the node already has a parent, it is removed from that parent's child list. Returns the node that was appended. ```javascript // append( newNode: Node ) => newNode: Node node.append( newNode ) ```

insertBefore

Inserts a new node into the current node's child list, before the node provided as a reference node. If the new node already has a parent, it is removed from that parent's child list. Returns the node that was inserted. ```javascript // insertBefore( newNode: Node, referenceNode: Node ) => Node node.insertBefore( newNode, referenceNode ) ```

remove

Removes the current node from its parent. Returns the current node. ```javascript // remove() => removedNode: Node const parent = node.getParent() console.log( parent.getChildren().length ) node.remove() console.log( parent.getChildren().length ) ```

replaceChild

Replaces the reference node in the parent's child list with the new node. If the new node already has a parent, it is removed from that parent's child list. Returns the node that was replaced. ```javascript // replaceChild( newNode: Node, referenceNode: Node ) => replacedNode: Node parentNode.replaceChild( newNode, referenceNode ) ```

insertAt

Inserts a new node into the current node's child list, at the index specified. If the new node already has a parent, it is removed from that parent's child list. Returns the node that was inserted. ```javascript // insertAt( newNode: Node, index: Integer ) => newNode: Node parentNode.insertAt( newNode, 2 ) ```

insertAfter

Inserts a new node into the current node's child list, after the node provided as a reference node. If the new node already has a parent, it is removed from that parent's child list. Returns the node that was inserted. ```javascript // insertAfter( newNode: Node, referenceNode: Node ) => newNode: Node node.insertAfter( newNode, referenceNode ) ```

removeAt

Removes the child of the current node at the specified index. Returns the removed node. ```javascript // removeAt( index: Integer ) => removedNode: Node const removedNode = node.removeAt( 2 ) ```

empty

Removes all of the current node's children. Returns an array of the removed children. ```javascript // empty() => removedNodes: Node
console.log( node.getChildren().length ) const removed = node.empty() console.log( node.getChildren().length ) ```

prepend

Adds the new node to the head of the current node's child list. Returns the new node. ```javascript // prepend( newNode: Node ) => newNode: Node node.prepend( newNode ) ```

unwrap

Replaces the parent of the current node with the current node and its siblings. Returns the removed parent node. ```javascript // unwrap() => removedParentNode: Node const oldParent = node.unwrap() ```

wrap

Replaces the current node with the new node, and then adds the current node to the new node's child list. Returns the new node. ```javascript // wrap( newParent: Node ) => newParent: Node node.wrap( newParentNode ) ```

Miscellaneous

get

Gets the node's underlying implementation - for example when using the DOM adapter it would probably refer to an HTMLElement or similar ```javascript // get() => Any const divElement = div.get() console.log( divElement.tagName ) // "div" ```

serialize

Returns a single object containing the current node and all of its children, where each node looks like: ```json { "value": ..., "children": ... } ``` Where possible you should ensure that the values you assign to nodes are JSON-serializable objects, it will make your life a lot easier. ```javascript // serialize() => Object const myTree = node.serialize() db.save( 'myTree', myTree ) ```

deserialize

Takes an object of the following form and returns a node: ```json { "value": ..., "children": ... } ``` ```javascript // deserialize( obj: Object ) => Node const obj = db.load( 'myTree' ) const node = Tree.deserialize( obj ) ```

clone

Clones a node - requires that value is JSON-serializable. Returns a new node with the same value and children as the original node, but the entire graph is a new instance. ```javascript // clone() => clonedNode: Node const cloned = node.clone() ```

meta

Store or retrieve metadata about a node that isn't persisted, eg doesn't change the underlying value of the node. Useful for storing temporary runtime information, like when you're visualising a tree in the browser and allow the user to collapse or expand nodes ```javascript // meta( name:string, value?:any ) => value:any //set node.meta( 'isCollapsed', true ) //get console.log( node.meta( 'isCollapsed' ) ) ```

adapters

```javascript const Dom = Tree.adapter( domAdapter ) const root = Dom.createRoot( 'My page title' ) ```

creating an adapter

You can create adapters that allow you to use the API over any tree-like backing structure. You need to provide between 1 and 5 functions for the adapter to work. If you only provide getChildren, you will get the whole traversal API, but the manipulation API requires insertBefore and remove. The serializer functions require value and createNode. You can also provide implementations of other functions normally provided by the API, for example your underlying data structure may already have a more efficient way of getting the parent of a node than the API does. These functions differ slightly from the consumer versions in the 1tree API in that they take more arguments (the API curries the extra arguments) - the signatures are shown here in rtype format: The fn argument will pass you in the tree API, so that you can call other API primitives from your adapter: ``` getChildren( node: Node ) => Node / children should be an array, even if the underlying implementation is not, for example the DOM returns a variety of array-like objects, you should convert these to an array / insertBefore( fn: ObjectFunction, rootNode: Node, currentNode: Node, newNode: Node, referenceNode: Node ) => newNode: Node / If referenceNode is not provided you should append the new node to the tail end of the current node's children instead. You should remove the new node from it's current parent if it already has one. (eg. fn.remove( fn, root, newNode ) ). / remove( fn: ObjectFunction, rootNode: Node, currentNode: Node ) => removedNode: Node / fn is provided in case you need to for example, find the parent via fn.getParent or etc. / value( currentNode: Node, value?: Any ) => value: Any / If called without the value parameter, it should return the "value" of the current node. If the value parameter is provided, it should set the "value" of the current node. It is best to have "value" be an abstraction of the underlying data stucture, and it is also wise to have that abstraction be JSON-serializable. For example, rather than returning an underlying DOM node directly, I would abstract it as: {
"nodeType": 1,
"tagName": "div",
"attributes": [
{
"name": "id",
"value": "myDiv"
}
]
}
/ ``` For an example, see the DOM adapter

plugins

A plugin is implemented as a function that takes the current tree API and adds to it, deletes from it, wraps an existing function etc.

using a plugin

```javascript const Tree = require( '1tree' ) const logPlugin = require( './log-plugin.js' ) Tree.plugin( logPlugin ) const root = Tree.createRoot( 'Animalia' ) root.log() ```

implementing a plugin

If your plugin attaches functions to the fn object, you should also attach a def object to each of those functions which provides some metadata so that your plugin can be used from a wrapped node. See the defs folder for examples of def in the built in functions. ```javascript const logPlugin = fn => { const log = node => {
console.log( fn.value( node ) )
return node
} log.def = {
argTypes: [ 'node' ],
returnType: 'node',
requires: [ 'value' ],
categories: [ 'log-plugin', 'plugin' ]
} fn.log = log return fn } ```

future

How to traverse when nodes may require async or events? Can an adapter or plugin be built that wraps all function calls to be async where necessary using similar technique to the wrap-nodes plugin?