<!--  // Hide this just in case this file is read as HTML

// *****************************************************************
// TREE.JS
// *****************************************************************
// TreeNode(value, child1, child2, ...): A generic tree structure
// nodeEqual(node1, node2): Compare two nodes
// treeEqual(tree1, tree2): Compare two trees recursively
// ***************************************************************** 

function TreeNode(value)
{
	// first argument is the value of this node
	// any additional arguments should be TreeNodes
	// and will be added as the initial children of this node
	// this just makes it more convenient to program in places

	this.value = value;
	this.parent = null;
	this.childNum = -1;
	this.children = new Array();

	this.addChild = treeNodeAddChild;
    this.setChild = treeNodeSetChild;
	this.toString = treeNodeToString;
	this.clone = treeNodeCopy;
	this.traverse = preorderTraverse;
	this.getTreeTop = getTreeTop;
	this.replaceWith = treeNodeReplace;
	this.find = treeNodeFind;
	this.getNodePosition = getTreeNodePosition;
	this.getNode = getTreeNode;

	var i;

	for (i = 1; i < arguments.length; i++)
	{
		this.addChild(arguments[i]);
	}
}

function treeNodeSetChild(childNum, childNode)
{
        // sets the childNum child of this node to childNode
        childNode.parent = this;
        childNode.childNum = childNum;
        this.children[childNum] = childNode;
}

function treeNodeAddChild(childNode)
{
        // adds a child node to the end of this node's list of children
        this.setChild(this.children.length, childNode);
}

function treeNodeToString()
{
	// returns the value of this node if it exists
	return ("TreeNode: " + (!this.value ? null : this.value));
}

function treeNodeFind(value)
{
	// searches the tree depth first for a node that has a value equal to value
	// returns a found node or null
	if (this.value == value)
		return (this);

	var found;
	for (var i = 0; i < this.children.length; i++)
	{
		found = this.children[i].find(value);

		if (found)
			return (found);
	}

	return (null);
}

function treeNodeCopy()
{
	// perform a deep copy of the tree
	var copy = new TreeNode(this.value);
	var i;

	for (i = 0; i < this.children.length; i++)
	{
		copy.addChild(this.children[i].clone());
	}

	return (copy);
}

function preorderTraverse(func, param)
{
	// traverses the tree in preorder and calls func(node, param) at every node
	func(this, param);

	var i;
	for (i = 0; i < this.children.length; i++)
	{
		this.children[i].traverse(func, param);
	}
}

function getTreeTop()
{
	// goes up to find the parent with no parent (top of the tree)
	var top = this;

	while (top.parent != null)
		top = top.parent;

	return (top);
}

function treeNodeReplace(node)
{
	// replace this by node
	// that is import node's value and tree structure
	// but keep my parent

	if (this == node)
		return;

	this.value = node.value;

	this.children = new Array();
	for (var i = 0; i < node.children.length; i++)
		this.addChild(node.children[i]);
}

function getTreeNodePosition()
{
	// returns this node's position from the top of the tree
	// so getTop().getNode(getNodePosition()) == this
	// returns an array of child numbers leading to the node

	var position = new Array();
	var node = this;

	// create array of childNums leading to the top
	while (node.parent != null)
	{
		position[position.length] = node.childNum;
		node = node.parent;
	}

	return (position);
}


function getTreeNode(position)
{
	// given an array like that returned by getTreeNodePosition(), return
	// the node at that position or null if none

	// travel down to find the node
	var node = this;
	for (var i = position.length - 1; i >= 0; i--)
	{
		node = node.children[position[i]];

		if (!node)
			return (null);
	}

	return (node);
}

// *****************************************************************
// Tree helpers
// *****************************************************************

function nodeEqual(node1, node2)
{
	// compares the two nodes' values
	// returns true if they are equal
	// either the two node values are the same (with ==)
	// or they have an equals() method defined
	// and equals() returns true

	if (node1.value == node2.value)
		return (true);
	else if (node1.value.equals && (node1.value.equals(node2.value)))
		return (true);
	else
		return (false);
}

function treeEqual(tree1, tree2)
{
	// basically the same as nodesEqual but recurses through children also

	var i;

        if (!tree1)
        {
                if (!tree2)
                        return (true);
                else
                        return (false);
        }

        if (!tree1.children || !tree2.children)
                return (false);         // not trees

	if (tree1.children.length != tree2.children.length)
		return (false);		// must have same number of children

	if (!nodeEqual(tree1, tree2))
		return (false);

	// check all children
	for (i = 0; i < tree1.children.length; i++)
	{
		if (!treeEqual(tree1.children[i], tree2.children[i]))
			return (false);
	}

	return (true);
}

// Stop hiding -->