Created
April 7, 2016 23:46
-
-
Save Pomax/9c3ea3d9b990afa7c723393989d1e406 to your computer and use it in GitHub Desktop.
A silly but effective JS tree datastructure
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* Basic tree implementation. | |
*/ | |
function Tree(value) { | |
this.value = value || false; | |
this.parent = false; | |
this.children = []; | |
}; | |
Tree.prototype = { | |
// add a child tree to this tree | |
add: function(value) { | |
var n = new Tree(value); | |
this.children.push(n); | |
n.parent = this; | |
return n; | |
}, | |
// the value of a tree is the tree itself | |
valueOf: function() { | |
return this; | |
}, | |
// list-style string representation of this tree | |
toString: function() { | |
var blocks = []; | |
if (this.value) { blocks.push(this.value); } | |
var cblocks = this.children.map(c => c.toString()); | |
if (cblocks.length > 0) { blocks = blocks.concat(cblocks); } | |
if (blocks.length > 0) { blocks = ["("].concat(blocks).concat([")"]); } | |
return blocks.join(''); | |
}, | |
// generate all paths from the root to each of the leaves. | |
getDistinctPaths: function(sofar, seen) { | |
seen = seen || []; | |
var base = sofar? sofar.slice() : []; | |
if(this.value) { base.push(this.value); } | |
if (this.children.length===0) { seen.push(base); } | |
this.children.map(c => { c.getDistinctPaths(base, seen); }); | |
return seen; | |
} | |
}; | |
module.exports = Tree; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment