Agnostic tree traversal library.
> Agnostic tree traversal library.
[travis-image]: https://img.shields.io/travis/ngryman/tree-crawl.svg?style=flat
[travis-url]: https://travis-ci.org/ngryman/tree-crawl
[codecov-image]: https://img.shields.io/codecov/c/github/ngryman/tree-crawl.svg
[codecov-url]: https://codecov.io/github/ngryman/tree-crawl
[greenkeeper-image]: https://badges.greenkeeper.io/ngryman/tree-crawl.svg
[greenkeeper-url]: https://greenkeeper.io/
[size-image]: http://img.badgesize.io/https://unpkg.com/tree-crawl@1.0.0/dist/tree-crawl.min.js?compression=gzip
[size-url]: https://unpkg.com/tree-crawl@1.0.0/dist/tree-crawl.min.js
- Agnostic: Supports any kind of tree. You provide a way to access a node's children, that's it.
- Fast: Crafted to be optimizer-friendly. See performance for more details.
- Mutation friendly: Does not 💥 when you mutate the tree.
- Multiple orders: Supports DFS pre and post order and BFS traversals.
You can install tree-crawl with yarn:
``sh`
$ yarn add tree-crawl
Alternatively using npm:
`sh`
$ npm install --save tree-crawl
`js
import crawl from 'tree-crawl'
// traverse the tree in pre-order
crawl(tree, console.log)
crawl(tree, console.log, { order: 'pre' })
// traverse the tree in post-order
crawl(tree, console.log, { order: 'post' })
// traverse the tree using childNodes as the children key
crawl(tree, console.log, { getChildren: node => node.childNodes })
// skip a node and its children
crawl(tree, (node, context) => {
if ('foo' === node.type) {
context.skip()
}
})
// stop the walk
crawl(tree, (node, context) => {
if ('foo' === node.type) {
context.break()
}
})
// remove a node
crawl(tree, (node, context) => {
if ('foo' === node.type) {
context.parent.children.splice(context.index, 1)
context.remove()
}
})
// replace a node
crawl(tree, (node, context) => {
if ('foo' === node.type) {
const node = {
type: 'new node',
children: [
{ type: 'new leaf' }
]
}
context.parent.children[context.index] = node
context.replace(node)
}
})
`
tl;dr It's easy for DFS, less easy for BFS
If you are using DFS you can use the following utility function:
`javascript`
const getPath = context =>
context.cursor.stack.xs.reduce((path, item) => {
if (item.node) {
path.push(item.node)
}
return path
}, [])
If you are really concerned about performance, you could read items from the stack directly. Each item has a and index property that you can use. The first item in the stack can be discarded and will have a node set to null. Be aware that you should not mutate the stack, or it will break the traversal.
If you are using BFS, things gets more complex. A simple hacky way to do so is to traverse the tree using DFS first. You can ad a path property to your nodes using the method above. And then do your regular BFS traversal using that path property.
- See: Traversal context.
Called on each node of the tree.
Type: Function
Parameters
- node Object Node being visited.context
- Context Traversal context
Walk options.
Type: Object
Parameters
- node
Properties
- getChildren Function? Return a node's children.order
- ("pre" \| "post" \| "bfs")? Order of the walk either in DFS pre or post order, or
BFS.
Examples
_Traverse a DOM tree._
`javascript`
crawl(document.body, doSomeStuff, { getChildren: node => node.childNodes })
_BFS traversal_
`javascript`
crawl(root, doSomeStuff, { order: 'bfs' })
Walk a tree recursively.
By default getChildren will return the children property of a node.
Parameters
- root Object Root node of the tree to be walked.iteratee
- Iteratee Function invoked on each node.options
- Options? Options customizing the walk.
A traversal context.
Four operations are available. Note that depending on the traversal order, some operations have
no effects.
Parameters
- flags Flags cursor
- Cursor
#### skip
Skip current node, children won't be visited.
Examples
`javascript`
crawl(root, (node, context) => {
if ('foo' === node.type) {
context.skip()
}
})
#### break
Stop traversal now.
Examples
`javascript`
crawl(root, (node, context) => {
if ('foo' === node.type) {
context.break()
}
})
#### remove
Notifies that the current node has been removed, children won't be visited.
Because tree-crawl has no idea about the intrinsic structure of your tree, you have toContext#remove
remove the node yourself. only notifies the traversal code that the structure
of the tree has changed.
Examples
`javascript`
crawl(root, (node, context) => {
if ('foo' === node.type) {
context.parent.children.splice(context.index, 1)
context.remove()
}
})
#### replace
Notifies that the current node has been replaced, the new node's children will be visited
instead.
Because tree-crawl has no idea about the intrinsic structure of your tree, you have toContext#replace
replace the node yourself. notifies the traversal code that the structure of
the tree has changed.
Parameters
- node Object Replacement node.
Examples
`javascript`
crawl(root, (node, context) => {
if ('foo' === node.type) {
const node = {
type: 'new node',
children: [
{ type: 'new leaf' }
]
}
context.parent.children[context.index] = node
context.replace(node)
}
})
#### parent
Get the parent of the current node.
Returns Object Parent node.
#### depth
Get the depth of the current node. The depth is the number of ancestors the current node
has.
Returns Number Depth.
#### level
Get the level of current node. The level is the number of ancestors+1 the current node has.
Returns Number Level.
#### index
Get the index of the current node.
Returns Number Node's index.
tree-crawl` is built to be super fast and traverse potentially huge trees. It's possible because it implements its own stack and queue for traversal algorithms and makes sure the code is optimizable by the VM.
If you do need real good performance please consider reading this [checklist] first.
Your main objective is to keep the traversal code optimized and avoid de-optimizations and bailouts. To do so, your nodes should have the same [hidden class] and your code stay [monomorphic].
[checklist]: http://mrale.ph/blog/2011/12/18/v8-optimization-checklist.html
[hidden class]: http://mrale.ph/blog/2012/06/03/explaining-js-vms-in-js-inline-caches.html
[monomorphic]: http://mrale.ph/blog/2015/01/11/whats-up-with-monomorphism.html
- arbre Agnostic tree library.
- tree-mutate Agnostic tree mutation library.
- tree-morph Agnostic tree morphing library.
MIT © Nicolas Gryman