under_tree v0.2.5
_tree
"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.
Example
'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.
Quality Metrics
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
.
API
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 specifyequals
: determines if twoTree
s are related clones.findNode
: finds the equivalentNode
in a tree (works across clones)findNodeByData
: finds the firstNode
containing matching datacontainsNode
: 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 nodeparent
: returns theNode
's parenttree
: returns theNode
's treeid
: 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
.
Building
Requirements: Node
and grunt
git clone https://github.com/drfloob/_tree.git
cd _tree
npm install
grunt --force
Development Stuff
_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.
Core development principles:
- Referential transparency
- Immutable data structures
- Zero internal state
- Zero side effects in the public API
Secondary design goals:
- All logical operations have pluggable behaviors
- All operations have sane defaults
- Performance isn't impractically bad
- AMD, Node, and global-script compatible
Contributing
Please do.
10 years ago