"Computing's core challenge is how not to make a mess of it. ... All unmastered complexity is of our own making; there is no one else to blame and so we had better learn how not to introduce the complexity in the first place."
This library provides an immutable tree model (data structure) implementation and a pluggable tree behavior for hierarchical data. It maintains zero internal state, does not alter your data, and does not trample on the global scope (unless you tell it to).
_tree
supports AMD (RequireJs), Node, and global-script loading
scenarios.
'use strict';
var patronage, familyTree, charlie, chuckFamilyTree, printLineage;
patronage = {'name': 'Jake', 'children': [
{'name': 'Jake Jr.'},
{'name': 'T.V.'},
{'name': 'Charlie'},
{'name': 'Viola'}
]};
familyTree = _tree.inflate(patronage);
// add a child, and save the new tree.
familyTree = familyTree.root().parseAndAddChild({'name': 'Kim Kil Wam'});
// Prints the tree with everyone's name and their father's name
printLineage = function(node) {
var origin = ', origin unknown';
if (node.parent()) {
origin = 'is the child of ' + node.parent().data().name;
}
console.log(node.data().name, origin);
};
familyTree.walk(printLineage);
// Charlie goes by Chuck now
charlie = familyTree.findNodeByData({name: 'Charlie'});
chuckFamilyTree = charlie.data({'name': 'Chuck'});
// Make sure Chuck's name is changed in the new tree ...
chuckFamilyTree.walk(printLineage);
// ... and *not* in the old tree
familyTree.walk(printLineage);
To get a feel for the library, check out the tests and run them in your browser. The annotated source code is also available.
Tests: All tests pass for:
- Chrome: >= 12
- Firefox: >= 4
- NodeJS >= 0.8
- Internet Explorer: >= 9note
- Safari 6
- iPhone 5, 4S (6.0)
- Kindle Fire 2
- iPad mini
- Samsung Galaxy Nexus
- Epiphany: >= 3.6.1
The following environments do not support immutability, whether via
Object.freeze
or Object.defineProperty
. _tree
is fully usable,
but object immutability tests are skipped, and mutability is asserted
instead (to make the environment's behavior clear).
- Opera: 11., 12.
- Safari: 5.0.6, 5.1
- PhantomJS
- iPad: 2, 3rd
- iPhone 4S (5.1)
- Rekonq >= 0.9.2
IE7 and below are currently untested and unsupported. The test framework doesn't currently support IE8.
You can run tests at the command line via PhantonJS with grunt phantom_test
, or via Node with grunt test
Keep in mind that IE9 doesn't support strict mode. Trying to alter an
immutable object will fail silently. Altering a _tree
in a modern
browser under strict mode
throws an error.
Performance: On an Intel Core 2 CPU T5600 @ 1.83GHz, 3GB Memory, using Chrome 30 on Debian Wheezy:
- 1024 node trees can be inflated at ~15/sec
- 30 node trees can be inflated at ~600/sec
- 11 node trees can be inflated at ~1,500/sec
- empty trees can be created at ~12,000/sec
You can run the benchmarks with grunt benchmark:all
Coverage: Current PhantomJS coverage is at 95% statements, 96% branches, 100% functions, and 95% lines.
Test coverage is currently measured for PhantomJS. Branches for Node
and global script definitions aren't executed, nor are the
Object.defineProperty
fallbacks.
Coverage is analyzed by running grunt phantom_cover
. You can view the
coverage report locally at coverage/index.html
.
The _tree
library exposes the following functions:
-
create
: creates an emptyTree
-
inflate
: parses your data into aTree
-
fromNode
: creates a new tree using aNode
from another tree
All of the _tree
methods return a Tree
object, which has the
following methods:
-
root
: returns the rootNode
-
walk
: traverses theTree
, executing a callback for each node in the order you specify -
equals
: determines if twoTree
s are related clones. -
findNode
: finds the equivalentNode
in a tree (works across clones) -
findNodeByData
: finds the firstNode
containing matching data -
containsNode
: returnsboolean
whether theNode
exists in theTree
-
containsData
: returnsboolean
whether the data exists in anyNode
in theTree
-
moveNode
: move aNode
and its descendants from one point in the tree to another.
The Tree
consists of Node
s, which have the following API:
-
data
: gets or sets the data on a node. Setting data generates a newTree
. -
children
: returns the childNode
s of a node -
parent
: returns theNode
's parent -
tree
: returns theNode
's tree -
id
: returns the tree-unique internal id of theNode
-
parseAndAddChild
: parses an object (much like inflate) and adds it as a child of theNode
. Returns a newTree
. -
addChildNode
: adds aNode
as a child. Errors are thrown if theNode
already exists in the tree. Returns a newTree
. -
equals
: returnsboolean
that representse the clone-agnostic equality of nodes. -
remove
: removes aNode
from the tree, returning a newTree
.
Requirements: Node
and grunt
git clone https://github.com/drfloob/_tree.git
cd _tree
npm install
grunt --force
_tree
does not maintain any internal state, which has a number of
benefits:
- all state can be managed directly by your application
- all functions are referentially transparent
- all operations are idempotent
- tests can be implemented easily
- the library should perform identically in parallel environments
It is also unobtrusive, in that _tree
does not alter your input
objects in any way, or trample on the global scope by default.
- Referential transparency
- Immutable data structures
- Zero internal state
- Zero side effects in the public API
- All logical operations have pluggable behaviors
- All operations have sane defaults
- Performance isn't impractically bad
- AMD, Node, and global-script compatible
Please do.