t

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
objects
- config:
you can define the name of the children property with
config.childrenName (shoutout to @GianlucaGuarini)
- callback (last argument):
function to be executed at each node. the arguments are:
- node: the current node
- par: the current node's parent
- ctrl: 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
objects
- config:
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 the callback has access to the return values of its
child nodes. you can define the name of the children property with
config.childrenName
- callback (last argument):
function to be executed at each node. the arguments are:
- node: the current node
- par: the current node's parent
- ctrl: control object. setting the stop property of this will end
the search, setting the cutoff property of this will not visit any
children of this node
- ret: return values of child nodes. this is only set if dfs() is
called with the order property set to post.

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
objects
- config:
you can define the name of the children property with
config.childrenName
- callback (last argument):
function to be executed at each node. this must return an object. the
map function takes care of setting children. the arguments are:
- node: the current node
- par: 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
objects
- config:
you can define the name of the children property with
config.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. the filter function takes care of setting children. the
arguments are:
- node: the current node
- par: 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 traversal
- node2:
the second tree of the traversal
- config:
you can define the name of the children property with
config.childrenName
- callback (last argument):
function to be executed at each node. the arguments are:
- node1: the node from the first tree
- node2: 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 node
- config:
you can define the name of the children property with
config.childrenName
- callback (last argument):
function to be executed at each node. if this function returns a truthy
value, the traversal will stop and find will return the current node.
the arguments are:
- node: the current node
- par: 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.