Class comb.collections.Tree

Extends comb.collections.Collection, comb.collections.Iterable.

Defined in: Tree.js.

Methods borrowed from class comb.collections.Collection:: concat, indexOf, join, lastIndexOf, slice, toString

Class Detail

comb.collections.Tree(options)

Base Class for all tree implementations

Parameters:

{Object} options

options to initialize the tree

{Function} options.compare

function used to compare items in a tree must return an integer

-1 for less than 0 for equal 1 for greater than

options = options || {};
this.compare = options.compare || compare;
this.__root = null;

Field Detail

<static> comb.collections.Tree.IN_ORDER

In Order

<static> comb.collections.Tree.POST_ORDER

Post Order

<static> comb.collections.Tree.PRE_ORDER

Pre Order

<static> comb.collections.Tree.REVERSE_ORDER

Reverse Order

Method Detail

clear()

Clear all items from a tree

this.__root = null;

{Boolean} contains(value)

Determines if a value is contained in the tree

Parameters:
{*} value: the value to find

Returns:: {Boolean} true if the tree contains the item false otherwise.

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;

{Boolean} every(cb, scope, order)

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

Parameters:
{Function} cb: called for each item in the tree
{Object} scope Optional, Default: this: scope to call the function in
{Tree.PRE_ORDER|Tree.POST_ORDER|Tree.IN_ORDER|Tree.REVERSE_ORDER} order Optional, Default: Tree.IN_ORDER: the traversal scheme

Returns:: {Boolean} True if every item passed false otherwise

if (typeof cb !== "function")
    throw new TypeError();

order = order || Tree.IN_ORDER;
scope = scope || this;
var ret = false;
this.traverseWithCondition(this.__root, order, function(node) {
    return (ret = cb.call(scope, node, this));
});
return ret;

{comb.collections.Tree} filter(cb, scope, order)

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

Parameters:
{Function} cb: called for each item in the tree
{Object} scope Optional, Default: this: scope to call the function in
{Tree.PRE_ORDER|Tree.POST_ORDER|Tree.IN_ORDER|Tree.REVERSE_ORDER} order Optional, Default: Tree.IN_ORDER: the traversal scheme

Returns:: {comb.collections.Tree} the tree with items that resulted in true being returned from the callback

if (typeof cb !== "function")
    throw new TypeError();

order = order || Tree.IN_ORDER;
scope = scope || this;
var construct = this.constructor;
var ret = new construct();
this.traverse(this.__root, order, function(node) {
    var include = cb.call(scope, node, this);
    include && ret.insert(node);
});
return ret;

find(value)

Finds a value in the tree

Parameters:
{*} value: the value to find

Returns:: the value of the node that matched

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;

{Array} findGreaterThan(value, exclusive)

Find all greater than a value

Parameters:
{*} value: the value to find nodes greater than
{Boolean} exclusive Optional, Default: false: if true the value will NOT be included in the return array

Returns:: {Array} the array containing all values greater than


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;

{Array} findLessThan(value, exclusive)

Find all values less than a value

Parameters:
{*} value: the value to find nodes less than
{Boolean} exclusive Optional, Default: false: if true the value will NOT be included in the return array

Returns:: {Array} the array containing all values less than


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(cb, scope, order)

Loop through each item in the tree

Parameters:
{Function} cb: called for each item in the tree
{Object} scope Optional, Default: this: scope to call the function in
{Tree.PRE_ORDER|Tree.POST_ORDER|Tree.IN_ORDER|Tree.REVERSE_ORDER} order Optional, Default: Tree.IN_ORDER: the traversal scheme

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

insert(data)

Inserts an item into the tree

Parameters:
{Anything} data: the item to insert

throw new Error("Not Implemented");

{Boolean} isEmpty()

Test if a tree is empty

Returns:: {Boolean} true if empty false otherwise

return this.__root == null;

{comb.collections.Tree} map(cb, scope, order)

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

Parameters:
{Function} cb: called for each item in the tree. Whatever the function returns is inserted into the return tree
{Object} scope Optional, Default: this: scope to call the function in
{Tree.PRE_ORDER|Tree.POST_ORDER|Tree.IN_ORDER|Tree.REVERSE_ORDER} order Optional, Default: Tree.IN_ORDER: the traversal scheme

Returns:: {comb.collections.Tree} the tree with the mapped items

if (typeof cb !== "function")
    throw new TypeError();

order = order || Tree.IN_ORDER;
scope = scope || this;
var construct = this.constructor;
var ret = new construct();
this.traverse(this.__root, order, function(node) {
    ret.insert(cb.call(scope, node, this));
});
return ret;

print()

Prints a tree to the console.

this.__printNode(this.__root, 0);

reduce(fun, accumulator, order)

Reduces a tree

Parameters:
{Function} fun: called for each item in the tree
accumulator Optional, Default: First item in tree(Order dependant): scope to call the function in
{Tree.PRE_ORDER|Tree.POST_ORDER|Tree.IN_ORDER|Tree.REVERSE_ORDER} order Optional, Default: Tree.IN_ORDER: the traversal scheme

Returns:: the result of the reduce function

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

reduceRight(fun, accumulator, order)

Reduces from right to left

Parameters:
{Function} fun: called for each item in the tree
accumulator Optional, Default: First item in tree(Order dependant): scope to call the function in
{Tree.PRE_ORDER|Tree.POST_ORDER|Tree.IN_ORDER|Tree.REVERSE_ORDER} order Optional, Default: Tree.IN_ORDER: the traversal scheme

Returns:: the result of the reduce function

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

remove(data)

Removes an item from the tree

Parameters:
{Anything} data: the item to insert

throw new Error("Not Implemented");

{Boolean} some(cb, scope, order)

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

Parameters:
{Function} cb: called for each item in the tree
{Object} scope Optional, Default: this: scope to call the function in
{Tree.PRE_ORDER|Tree.POST_ORDER|Tree.IN_ORDER|Tree.REVERSE_ORDER} order Optional, Default: Tree.IN_ORDER: the traversal scheme

Returns:: {Boolean} True if every item passed false otherwise

if (typeof cb !== "function")
    throw new TypeError();

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;

{Array} toArray(order)

Converts a tree into an array based on the specified order

Parameters:
{Tree.PRE_ORDER|Tree.POST_ORDER|Tree.IN_ORDER|Tree.REVERSE_ORDER} order Optional, Default: Tree.IN_ORDER: the traversal scheme

Returns:: {Array} array of all items in the order specified.

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

traverse(node, order, callback)

Traverse a tree

Not typically used directly

Parameters:
{Object} node: the node to start at
{Tree.PRE_ORDER|Tree.POST_ORDER|Tree.IN_ORDER|Tree.REVERSE_ORDER} order Optional, Default: Tree.IN_ORDER: the traversal scheme
{Function} callback: called for each item

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(node, order, callback)

Traverse a tree until the callback function returns false

Not typically used directly

Parameters:
{Object} node: the node to start at
{Tree.PRE_ORDER|Tree.POST_ORDER|Tree.IN_ORDER|Tree.REVERSE_ORDER} order Optional, Default: Tree.IN_ORDER: the traversal scheme
{Function} callback: called for each item, traversal continues until the function returns false

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;

Documentation generated by JsDoc Toolkit 2.4.0 on Tue Jan 31 2012 16:14:12 GMT-0600 (CST)