Base Class for all tree implementations

Extends

• comb.collections.Collection
• comb.collections.Iterable

Static Properties

Property	Type	Default Value	Description
IN_ORDER	property	"in_order"	In Order
POST_ORDER	property	"post_order"	Post Order
PRE_ORDER	property	"pre_order"	Pre Order
REVERSE_ORDER	property	"reverse_order"	Reverse Order

Constructor

Defined collections/Tree.js Source

function (options){
   options = options || {};
   this.compare = options.compare || compare;
   this.__root = null;
           
}
            

__printNode Function Private

---

Defined collections/Tree.js

Prints a node

Arguments

• node :

  node to print

• level :

  the current level the node is at, Used for formatting

Source

function (node,level){
   //console.log(level);
   var str = [];
   if (node == null || node === undefined) {
       str.push(multiply('\t', level));
       str.push("~");
       console.log(str.join(""));
   } else {
       this.__printNode(node.right, level + 1);
       str.push(multiply('\t', level));
       str.push(node.data + "\n");
       console.log(str.join(""));
       this.__printNode(node.left, level + 1);
   }
           
}
    

clear Function Public

---

Defined collections/Tree.js

Clear all items from a tree

Source

function (){
   this.__root = null;
           
}
    

contains Function Public

---

Defined collections/Tree.js

Determines if a value is contained in the tree

Arguments

• value :

  the value to find

Returns

• Boolean

  true if the tree contains the item false otherwise.

Source

function (value){
   var ret = false;
   var root = this.__root;
   while (root != null) {
       var cmp = this.compare(value, root.data);
       if (cmp) {
           root = root[(cmp === -1) ? "left" : "right"];
       } else {
           ret = true;
           root = null;
       }
   }
   return ret;
           
}
    

every Function Public

---

Defined collections/Tree.js

Determines if every item meets the condition returned by the callback.

Arguments

• cb :

  called for each item in the tree

• [scope= this] :

  scope to call the function in

• [order= Tree.IN_ORDER] :

  the traversal scheme

Returns

• Boolean

  True if every item passed false otherwise

Source

function (cb,scope,order){
   if (typeof cb !== "function") {
       throw new TypeError("cb must be a function");
   }
   order = order || Tree.IN_ORDER;
   scope = scope || this;
   var ret = false;
   this.traverseWithCondition(this.__root, order, function (node) {
       ret = cb.call(scope, node, this);
       return ret;
   });
   return ret;
           
}
    

filter Function Public

---

Defined collections/Tree.js

Filters a tree, only returning items that result in true being returned from the callback

Arguments

• cb :

  called for each item in the tree

• [scope= this] :

  scope to call the function in

• [order= Tree.IN_ORDER] :

  the traversal scheme

Returns

• comb.collections.Tree

  the tree with items that resulted in true being returned from the callback

Source

function (cb,scope,order){
   if (typeof cb !== "function") {
       throw new TypeError("cb must be a function");
   }
   order = order || Tree.IN_ORDER;
   scope = scope || this;
   var ret = new this._static();
   this.traverse(this.__root, order, function (node) {
       var include = cb.call(scope, node, this);
       include && ret.insert(node);
   });
   return ret;
           
}
    

find Function Public

---

Defined collections/Tree.js

Finds a value in the tree

Arguments

• value :

  the value to find

Returns

• the value of the node that matched

Source

function (value){
   var ret;
   var root = this.__root;
   while (root != null) {
       var cmp = this.compare(value, root.data);
       if (cmp) {
           root = root[(cmp === -1) ? "left" : "right"];
       } else {
           ret = root.data;
           break;
       }
   }
   return ret;
           
}
    

findGreaterThan Function Public

---

Defined collections/Tree.js

Find all greater than a value

Arguments

• value :

  the value to find nodes greater than

• [exclusive= false] :

  if true the value will NOT be included in the return array

Returns

• Array

  the array containing all values greater than

Source

function (value,exclusive){
   //find a better way!!!!
   var ret = [], compare = this.compare;
   this.traverse(this.__root, exports.REVERSE_ORDER, function (v) {
       var cmp = compare(value, v);
       if ((!exclusive && cmp === 0) || cmp === -1) {
           ret.push(v);
           return true;
       } else {
           return false;
       }
   });
   return ret;
           
}
    

findLessThan Function Public

---

Defined collections/Tree.js

Find all values less than a value

Arguments

• value :

  the value to find nodes less than

• [exclusive= false] :

  if true the value will NOT be included in the return array

Returns

• Array

  the array containing all values less than

Source

function (value,exclusive){
   //find a better way!!!!
   var ret = [], compare = this.compare;
   this.traverseWithCondition(this.__root, exports.IN_ORDER, function (v) {
       var cmp = compare(value, v);
       if ((!exclusive && cmp === 0) || cmp === 1) {
           ret.push(v);
           return true;
       } else {
           return false;
       }
   });
   return ret;
           
}
    

forEach Function Public

---

Defined collections/Tree.js

Loop through each item in the tree

Arguments

• cb :

  called for each item in the tree

• [scope= this] :

  scope to call the function in

• [order= Tree.IN_ORDER] :

  the traversal scheme

Source

function (cb,scope,order){
   if (typeof cb !== "function") {
       throw new TypeError("cb must be a function");
   }
   order = order || Tree.IN_ORDER;
   scope = scope || this;
   this.traverse(this.__root, order, function (node) {
       cb.call(scope, node, this);
   });
           
}
    

insert Function Public

---

Defined collections/Tree.js

Inserts an item into the tree

Arguments

• data :

  the item to insert

Source

function (data){
   throw new Error("Not Implemented");
           
}
    

isEmpty Function Public

---

Defined collections/Tree.js

Test if a tree is empty

Returns

• Boolean

  true if empty false otherwise

Source

function (){
   return this.__root == null;
           
}
    

map Function Public

---

Defined collections/Tree.js

Loop through each item in the tree, collecting the value returned by the callback funciton.

Arguments

• cb :

  called for each item in the tree. Whatever the function returns is inserted into the return tree

• [scope= this] :

  scope to call the function in

• [order= Tree.IN_ORDER] :

  the traversal scheme

Returns

• comb.collections.Tree

  the tree with the mapped items

Source

function (cb,scope,order){
   if (typeof cb !== "function") {
       throw new TypeError("cb must be a function");
   }
   order = order || Tree.IN_ORDER;
   scope = scope || this;
   var ret = new this._static();
   this.traverse(this.__root, order, function (node) {
       ret.insert(cb.call(scope, node, this));
   });
   return ret;
           
}
    

print Function Public

---

Defined collections/Tree.js

Prints a tree to the console.

Source

function (){
   this.__printNode(this.__root, 0);
           
}
    

reduce Function Public

---

Defined collections/Tree.js

Reduces a tree

Arguments

• fun :

  called for each item in the tree

• [accumulator= First item in tree(Order dependant)] :

  scope to call the function in

• [order= Tree.IN_ORDER] :

  the traversal scheme

Returns

• the result of the reduce function

Source

function (fun,accumulator,order){
   var arr = this.toArray(order);
   var args = [fun];
   if (!base.isUndefinedOrNull(accumulator)) {
       args.push(accumulator);
   }
   return arr.reduce.apply(arr, args);
           
}
    

reduceRight Function Public

---

Defined collections/Tree.js

Reduces from right to left

Arguments

• fun :

  called for each item in the tree

• [accumulator= First item in tree(Order dependant)] :

  scope to call the function in

• [order= Tree.IN_ORDER] :

  the traversal scheme

Returns

• the result of the reduce function

Source

function (fun,accumulator,order){
   var arr = this.toArray(order);
   var args = [fun];
   if (!base.isUndefinedOrNull(accumulator)) {
       args.push(accumulator);
   }
   return arr.reduceRight.apply(arr, args);
           
}
    

remove Function Public

---

Defined collections/Tree.js

Removes an item from the tree

Arguments

• data :

  the item to insert

Source

function (data){
   throw new Error("Not Implemented");
           
}
    

some Function Public

---

Defined collections/Tree.js

Determines if some item meet the condition returned by the callback. Traversal ends the first time true is found.

Arguments

• cb :

  called for each item in the tree

• [scope= this] :

  scope to call the function in

• [order= Tree.IN_ORDER] :

  the traversal scheme

Returns

• Boolean

  True if every item passed false otherwise

Source

function (cb,scope,order){
   if (typeof cb !== "function") {
       throw new TypeError("cb must be a function");
   }
   order = order || Tree.IN_ORDER;
   scope = scope || this;
   var ret;
   this.traverseWithCondition(this.__root, order, function (node) {
       ret = cb.call(scope, node, this);
       return !ret;
   });
   return ret;
           
}
    

toArray Function Public

---

Defined collections/Tree.js

Converts a tree into an array based on the specified order

Arguments

• [order= Tree.IN_ORDER] :

  the traversal scheme

Returns

• Array

  array of all items in the order specified.

Source

function (order){
   order = order || Tree.IN_ORDER;
   var arr = [];
   this.traverse(this.__root, order, function (node) {
       arr.push(node);
   });
   return arr;
           
}
    

traverse Function Public

---

Defined collections/Tree.js

Traverse a tree

Not typically used directly

Arguments

• node :

  the node to start at

• [order= Tree.IN_ORDER] :

  the traversal scheme

• callback :

  called for each item

Source

function (node,order,callback){
   if (node) {
       order = order || Tree.PRE_ORDER;
       if (order === Tree.PRE_ORDER) {
           callback(node.data);
           this.traverse(node.left, order, callback);
           this.traverse(node.right, order, callback);
       } else if (order === Tree.IN_ORDER) {
           this.traverse(node.left, order, callback);
           callback(node.data);
           this.traverse(node.right, order, callback);
       } else if (order === Tree.POST_ORDER) {
           this.traverse(node.left, order, callback);
           this.traverse(node.right, order, callback);
           callback(node.data);
       } else if (order === Tree.REVERSE_ORDER) {
           this.traverseWithCondition(node.right, order, callback);
           callback(node.data);
           this.traverseWithCondition(node.left, order, callback);
       }
   }
           
}
    

traverseWithCondition Function Public

---

Defined collections/Tree.js

Traverse a tree until the callback function returns false

Not typically used directly

Arguments

• node :

  the node to start at

• [order= Tree.IN_ORDER] :

  the traversal scheme

• callback :

  called for each item, traversal continues until the function returns false

Source

function (node,order,callback){
   var cont = true;
   if (node) {
       order = order || Tree.PRE_ORDER;
       if (order === Tree.PRE_ORDER) {
           cont = callback(node.data);
           if (cont) {
               cont = this.traverseWithCondition(node.left, order, callback);
               cont && (cont = this.traverseWithCondition(node.right, order, callback));
           }
       } else if (order === Tree.IN_ORDER) {
           cont = this.traverseWithCondition(node.left, order, callback);
           if (cont) {
               cont = callback(node.data);
               cont && (cont = this.traverseWithCondition(node.right, order, callback));
           }
       } else if (order === Tree.POST_ORDER) {
           cont = this.traverseWithCondition(node.left, order, callback);
           if (cont) {
               cont && (cont = this.traverseWithCondition(node.right, order, callback));
               cont && (cont = callback(node.data));
           }
       } else if (order === Tree.REVERSE_ORDER) {
           cont = this.traverseWithCondition(node.right, order, callback);
           if (cont) {
               cont = callback(node.data);
               cont && (cont = this.traverseWithCondition(node.left, order, callback));
           }
       }
   }
   return cont;
           
}
    

---

License

MIT https://github.com/C2FO/comb/raw/master/LICENSE

Meta

• Code: git clone git://github.com/C2FO/comb.git
• Website: http://c2fo.com
• Twitter: http://twitter.com/c2fo - 877.465.4045