/*
Research Project:   Graphical Database for Category Theory
                    J. Bradbury, Dr. R. Rosebrugh, I. Rutherford
                    Mount Allison University 2001
File:               HomTree.java
                    (written by: Ian Rutherford)
Description:
*/

public class HomTree
{
	public IniSettings ini = new IniSettings();
	public HomNode root = new HomNode();
	public HomNode prev; // 
	public HomNode pos; // used for traversing paths, remembers last path position
	protected int len = -1;

	public HomTree()
	{
		root.data = -1;
		root.across = root;
		prev = root;
		pos = root;
	}

	public boolean addNode(HomNode currentnode, int data)
	/*
	Parameters:
		currentnode: a node to which we wish to add a child with contents `info'.
		data:				the data we wish to put in the new node.
	Purpose:
		To insert a node into a tree with an alphabetical ordering.
	Design:
		Make a new node which we insert as the first child of the node
		by currentnode.	Then sort the children of currentnode in alphabetical
		order and return true.	Returns false if the node already exists.
		This method will also point prev to the new inserted node.
	*/
	{
		HomNode insert = new HomNode();
		HomNode temp;

		insert.data = data;

		if (currentnode.down == null)
		{
			currentnode.down = insert;
			insert.across = currentnode;
			insert.last = true;
		}
		else if (currentnode.down.data > data)
		{
			insert.across = currentnode.down;
			currentnode.down = insert;
			insert.last = false;
		}
		else
		{
			temp = currentnode.down;
			while (!temp.last && data >= temp.across.data)
				temp = temp.across;
			if (data != temp.data)
			{
				insert.across = temp.across;
				temp.across = insert;
				insert.last = temp.last;
				temp.last = false;
			}
			else
			{
				prev = temp;
				return false;
			}
		}

		prev = insert;
		return true;
	}

	public boolean containsNode(HomNode currentnode, int data)
	/*
	Parameters:
		currentnode: a node to which we wish to add a child with contents `info'.
		data:				the data we wish to put in the new node.
	Purpose:
		To insert a node into a tree with an alphabetical ordering.
	Design:
		Make a new node which we insert as the first child of the node
		by currentnode.	Then sort the children of currentnode in alphabetical
		order and return true.	Returns false if the node already exists.
		This method will also point prev to the new inserted node.
	*/
	{
		HomNode temp;

		if (currentnode.down == null || currentnode.down.data > data)
		{
			return false;
		}
		else
		{
			temp = currentnode.down;
			while (!temp.last && data >= temp.across.data)
				temp = temp.across;
			if (data == temp.data)
			{
				prev = temp;
				return true;
			}
			return false;
		}
	}

	public boolean addPath(int path[])
	/*
	Parameters:
		path[]:			 an array of arrows
	Purpose:
		To search a tree and determine if path is in the tree,
		if it is not then path is added to the tree.
	Design:
		Returns false if path is already in the tree, otherwise
		adds path to the tree and returns true.
	*/
	{
		int i, j = 0;
		prev = root;

		// Reverse the path before storing it in the tree
		// paths are normally stored in reverse order, and
		// this tree structure is greatly simplified if
		// they are stored here in non-reverse order
		while (path[j] != -1)
			j++;
		int newpath[] = new int[j+1];
		for (i=0; i<j; i++)
		{
			newpath[i] = path[j-i-1];
		}
		newpath[j] = -1;

		// Continue trying to add new nodes until we find that one
		// isn't already in the tree
		i = 0;
		while (i < j && !addNode(prev, newpath[i]))
			i++;
		if (i >= j)
		{
			if (prev.ispath)
				return false;
			else
			{
				prev.ispath = true;
				return true;
			}
		}
		i++;

		if (i >= j)
		{
			prev.ispath = true;
			return true;
		}

		// If there are still more nodes to add, add them
		// After this point, we have added at least one new
		// node, so the path wasn't already in the tree
		while (i < j && newpath[i] != -1)
		{
			addNode(prev, newpath[i]);
			i++;
		}

		prev.ispath = true;
		return true;
	}

	public boolean containsPath(int path[])
	/*
	Parameters:
		path[]:			 an array of arrows
	Purpose:
		To search a tree and determine if path is in the tree,
		if it is not then path is added to the tree.
	Design:
		Returns false if path is already in the tree, otherwise
		adds path to the tree and returns true.
	*/
	{
		int i, j = 0;
		prev = root;

		// Reverse the path before storing it in the tree
		// paths are normally stored in reverse order, and
		// this tree structure is greatly simplified if
		// they are stored here in non-reverse order
		while (path[j] != -1)
			j++;
		int newpath[] = new int[j+1];
		for (i=0; i<j; i++)
		{
			newpath[i] = path[j-i-1];
		}
		newpath[j] = -1;

		// Continue trying to add new nodes until we find that one
		// isn't already in the tree
		i = 0;
		while (i < j && containsNode(prev, newpath[i]))
			i++;
		if (i >= j)
		{
			return prev.ispath;
		}
		return false;
	}

	public boolean isEqual(HomTree tree)
	/*
	Parameters:
		tree :	the two tree to be tested for equality against this one
	Purpose:
		To compare a tree to this one and return whether or not they are equal
	Design:
		Calls the recursive equalSubtree() method
	*/
	{
		return equalSubtree(root, tree.root);
	}

	public boolean equalSubtree(HomNode node1, HomNode node2)
	/*
	Parameters:
		node1, node2 :	the root of each subtree to be tested
	Purpose:
		To compare two subtrees and return whether or not they are equal
	Design:
		Traverses both subtrees recursively and compares each node to see if they are equal
	*/
	{
		if (node1.down == null && node2.down == null)
			return true;
		if (node1.down == null || node2.down == null)
			return false;

		HomNode temp1 = node1.down;
		HomNode temp2 = node2.down;

		while (!temp1.last && !temp2.last)
		{
			if (temp1.ispath != temp2.ispath || temp1.data != temp2.data || temp1.last != temp2.last || !equalSubtree(temp1, temp2))
				return false;
			temp1 = temp1.across;
			temp2 = temp2.across;
		}
		if (temp1.ispath != temp2.ispath || temp1.data != temp2.data || temp1.last != temp2.last || !equalSubtree(temp1, temp2))
			return false;
		return true;
	}

	public String printTree(Category A)
	{
		String ret = new String();
		HomNode temp = root;
		if (temp.down == null)
			return ret;
		int depth = 0;

		do
		{
			while (temp.down != null)
			{
				temp = temp.down;
				depth++;
				if (temp.ispath)
					ret += "P";
				if (temp.data == -2)
					ret += "D ident	";
				else if (temp.data != -1)
					ret += "D" + A.arrow[temp.data] + "	";
				if (temp.tree != null)
					ret += "(" + temp.tree.printTree(A) + ")	";
			}
			while (temp.last)
			{
				temp = temp.across;
				ret += "U";
				depth--;
			}
			temp = temp.across;
			if (temp.ispath)
				ret += "P";
			if (temp.data == -2)
				ret += "A ident	";
			else if (temp.data != -1)
				ret += "A" + A.arrow[temp.data] + "	";
			if (temp.tree != null)
				ret += "(" + temp.tree.printTree(A) + ")	";
		} while (depth > 0 && temp.data != -1);
		return ret;
	}

	public int[] getFirstPath()
	{
		int[] path = new int[ini.getMAXWORD()];
		len = 0;
		pos = root;
		if (pos.down == null)
		{
			len = -1;
			path[0] = -1;
			return path;
		}
		
		while (pos.down != null)
		{
			path[len] = pos.data;
			len++;
			pos = pos.down;
		}
		path[len] = pos.data;
		len++;
		while (!pos.ispath)
		{
			while (!pos.ispath && pos.last)
			{
				pos = pos.across;
				len--;
			}
			if (!pos.ispath)
			{
				pos = pos.across;
				while (pos.down != null)
				{
					pos = pos.down;
					len++;
				}
			}
		}

		// Now we're at the end of the path, so figure out the rest of it and return
		int i = 0;
		HomNode tmp = pos;
		while (tmp != root)
		{
			path[i] = tmp.data;
			i++;
			while (!tmp.last)
				tmp = tmp.across;
			tmp = tmp.across;
		}
		path[i] = -1;
		return path;
	}

	public int[] getNextPath()
	{
		if (len == -1) return getFirstPath();
		int[] path = new int[ini.getMAXWORD()];

		if (pos.last)
		{
			len--;
			pos = pos.across;
		}
		else
		{
			pos = pos.across;
			while (pos.down != null)
				pos = pos.down;
		}

		while (!pos.ispath)
		{
			while (!pos.ispath && pos.last)
			{
				len--;
				pos = pos.across;
			}
			if (!pos.ispath)
			{
				pos = pos.across;
				while (!pos.ispath && pos.down != null)
				{
					len++;
					pos = pos.down;
				}
			}
		}

		// Now we're at the end of the path, so figure out the rest of it and return
		int i = 0;
		HomNode tmp = pos;
		while (tmp != root)
		{
			path[i] = tmp.data;
			i++;
			while (!tmp.last)
				tmp = tmp.across;
			tmp = tmp.across;
		}
		path[i] = -1;
		return path;
	}
	
	public int getLength()
	{
		return len;
	}
}