t
v0.5.1
Published
tree traversal and manipulation
Downloads
5,254
Readme
version 0.5.1 (source)
t-js is freely distributable under the MIT license
overview
t.js is a tree-traversal library. its only assumption is that the trees it traverses are made up of objects with 'children' arrays:
{
children: [
{ },
{
children: [
{ },
{ }
]
}
]
}
the actual property name is configurable. the traversals are entirely
non-recursive, including the post-order traversal and map()
functions,
and it works inside the browser or out.
testing
there's a bunch of tests in test/test.js
. you can run them along with the
linter with:
$ npm install && npm test
or view them on most any system with a modern browser by opening the
index.html
file.
documentation is generated with the grunt docs
target.
usage
the t
interface is exported in either the browser or node.js. the library
can be installed from npm:
$ npm install t
available functions
t.bfs()
perform a breadth-first search, executing the given callback at each node.
t.bfs(node, [config], function(node, par, ctrl) {
/* ... */
})
node
: object where the search will start. this could also be an array of objectsconfig
: you can define the name of the children property withconfig.childrenName
(shoutout to @GianlucaGuarini)callback
(last argument): function to be executed at each node. the arguments are:node
: the current nodepar
: the current node's parentctrl
: control object. this doesn't currently do anything.
returns: the first node
argument
t.dfs()
perform a depth-first search, executing the given callback at each node.
t.dfs(node, [config], function(node, par, ctrl) {
/* ... */
})
in the pre-order case, dfs()
doesn't process child nodes until after the
callback. so if you need to traverse an unknown tree, say a directory
structure, you can start with just the root, and add child nodes as you go
by appending them to this.children
in the callback function.
node
: object where the search will start. this could also be an array of objectsconfig
: if this is an object w/ the 'order' property set to 'post', a post-order traversal will be performed. this is generally worse performance, but thecallback
has access to the return values of its child nodes. you can define the name of the children property withconfig.childrenName
callback
(last argument): function to be executed at each node. the arguments are:node
: the current nodepar
: the current node's parentctrl
: control object. setting thestop
property of this will end the search, setting thecutoff
property of this will not visit any children of this noderet
: return values of child nodes. this is only set ifdfs()
is called with theorder
property set topost
.
returns: the first node
argument
t.map()
given a tree, return a tree of the same structure made up of the objects
returned by the callback which is executed at each node. think of the
underscore
's _.map()
function, or python's map()
t.map(node, [config], function(node, par) {
/* ... */
})
node
: object where the traversal will start. this could also be an array of objectsconfig
: you can define the name of the children property withconfig.childrenName
callback
(last argument): function to be executed at each node. this must return an object. themap
function takes care of setting children. the arguments are:node
: the current nodepar
: the current node's parent. note that this is the parent from the new tree that's being created.
returns: a new tree, mapped by the callback function
t.filter()
given a tree, return a tree of the same structure made up of the objects returned by the callback which is executed at each node. if, however, at a given node the callback returns a falsy value, then the current node and all of its descendents will be pruned from the output tree.
t.filter(node, [config], function(node, par) {
/* ... */
})
node
: object where the traversal will start. this could also be an array of objectsconfig
: you can define the name of the children property withconfig.childrenName
callback
(last argument): function to be executed at each node. this must return an object or a falsy value if the output tree should be pruned from the current node down. thefilter
function takes care of setting children. the arguments are:node
: the current nodepar
: the current node's parent. note that this is the parent from the new tree that's being created.
returns: a new tree, filtered by the callback function
t.stroll()
a walk through the trees...
given two trees of similar structure, traverse both trees at the same time, executing the given callback with the pair of corresponding nodes as arguments.
t.stroll(tree1, tree2, [config], function(node1, node2) {
/* ... */
})
tree1
: the first tree of the traversalnode2
: the second tree of the traversalconfig
: you can define the name of the children property withconfig.childrenName
callback
(last argument): function to be executed at each node. the arguments are:node1
: the node from the first treenode2
: the node from the second tree
t.find()
given a tree and a truth test, return the first node that responds with a truthy value
t.find(tree, [config], function(node, par) {
/* ... */
})
tree
: the tree in which to find the nodeconfig
: you can define the name of the children property withconfig.childrenName
callback
(last argument): function to be executed at each node. if this function returns a truthy value, the traversal will stop andfind
will return the current node. the arguments are:node
: the current nodepar
: the parent of the current node
returns: the found node
_dfsPostOrder()
this is a module-private function used by dfs()
license
Copyright (C) 2012 StoredIQ, Authored by Aaron Stacy
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.