package echopointng.tree;

/* 
 * This file is part of the Echo Point Project.  This project is a collection
 * of Components that have extended the Echo Web Application Framework.
 *
 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
 *
 * The contents of this file are subject to the Mozilla Public License Version
 * 1.1 (the "License"); you may not use this file except in compliance with
 * the License. You may obtain a copy of the License at
 * http://www.mozilla.org/MPL/
 *
 * Software distributed under the License is distributed on an "AS IS" basis,
 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
 * for the specific language governing rights and limitations under the
 * License.
 *
 * Alternatively, the contents of this file may be used under the terms of
 * either the GNU General Public License Version 2 or later (the "GPL"), or
 * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
 * in which case the provisions of the GPL or the LGPL are applicable instead
 * of those above. If you wish to allow use of your version of this file only
 * under the terms of either the GPL or the LGPL, and not to allow others to
 * use your version of this file under the terms of the MPL, indicate your
 * decision by deleting the provisions above and replace them with the notice
 * and other provisions required by the GPL or the LGPL. If you do not delete
 * the provisions above, a recipient may use your version of this file under
 * the terms of any one of the MPL, the GPL or the LGPL.
 */

/*
* The design paradigm and class name used within have been taken directly from
* the java.swing package has been retro-fitted to work with the NextApp Echo web framework.
*
* This file was made part of the EchoPoint project on the 25/07/2002.
*
*/

import java.io.Serializable;
import java.util.Vector;
import java.util.Stack;
import java.util.Enumeration;
import java.util.NoSuchElementException;
import java.util.EmptyStackException;

/**
 * A <code>DefaultMutableTreeNode</code> is a general-purpose node in a tree data
 * structure. A tree node may have at most one parent and 0 or more children.
 * <code>DefaultMutableTreeNode</code> provides operations for examining and modifying a
 * node's parent and children and also operations for examining the tree that
 * the node is a part of.  A node's tree is the set of all nodes that can be
 * reached by starting at the node and following all the possible links to
 * parents and children.  A node with no parent is the root of its tree; a
 * node with no children is a leaf.  A tree may consist of many subtrees,
 * each node acting as the root for its own subtree.
 * <p>
 * This class provides enumerations for efficiently traversing a tree or
 * subtree in various orders or for following the path between two nodes.
 * <p>
 * A <code>DefaultMutableTreeNode</code> may also hold a reference to a user object, the
 * use of which is left to the user.  Asking a <code>DefaultMutableTreeNode</code> for its
 * string representation with <code>toString()</code> returns the string
 * representation of its user object.
 * <p>
 * <b>This is not a thread safe class.</b>If you intend to use
 * a DefaultMutableTreeNode (or a tree of TreeNodes) in more than one thread, you
 * need to do your own synchronizing. A good convention to adopt is
 * synchronizing on the root node of a tree.
 * <p>
 * While DefaultMutableTreeNode implements the MutableTreeNode interface and
 * will allow you to add in any implementation of MutableTreeNode not all
 * of the methods in DefaultMutableTreeNode will be applicable to all
 * MutableTreeNodes implementations. Especially with some of the enumerations
 * that are provided, using some of these methods assumes the
 * DefaultMutableTreeNode contains only DefaultMutableNode instances. All
 * of the TreeNode/MutableTreeNode methods will behave as defined no
 * matter what implementations are added.
 * <p>
 *
 */
public class DefaultMutableTreeNode implements MutableTreeNode, Serializable {

	/** this node's action command */
	protected String actionCommand;

	/** this node's parent, or null if this node has no parent */
	protected MutableTreeNode parent;

	/** array of children, may be null if this node has no children */
	protected Vector children;

	/** optional user object */
	transient protected Object userObject;

	/** true if the node is able to have children */
	protected boolean allowsChildren;

	/**
	 * An enumeration that is always empty. This is used when an enumeration
	 * of a leaf node's children is requested.
	 */
	public static final Enumeration EMPTY_ENUMERATION = new Enumeration() {
		public boolean hasMoreElements() {
			return false;
		}
		public Object nextElement() {
			throw new NoSuchElementException("No more elements");
		}
	};

	public final class PreorderEnumeration implements Enumeration, Serializable {
		protected Stack stack;

		public PreorderEnumeration(TreeNode rootNode) {
			super();
			Vector v = new Vector(1);
			v.addElement(rootNode);
			stack = new Stack();
			stack.push(v.elements());
		}

		public boolean hasMoreElements() {
			return (!stack.empty() && ((Enumeration) stack.peek()).hasMoreElements());
		}

		public Object nextElement() {
			Enumeration enumer = (Enumeration) stack.peek();
			TreeNode node = (TreeNode) enumer.nextElement();
			Enumeration children = node.children();

			if (!enumer.hasMoreElements()) {
				stack.pop();
			}
			if (children.hasMoreElements()) {
				stack.push(children);
			}
			return node;
		}

	}

	public final class PostorderEnumeration implements Enumeration, Serializable {
		protected TreeNode root;
		protected Enumeration children;
		protected Enumeration subtree;

		public PostorderEnumeration(TreeNode rootNode) {
			super();
			root = rootNode;
			children = root.children();
			subtree = EMPTY_ENUMERATION;
		}

		public boolean hasMoreElements() {
			return root != null;
		}

		public Object nextElement() {
			Object retval;

			if (subtree.hasMoreElements()) {
				retval = subtree.nextElement();
			} else if (children.hasMoreElements()) {
				subtree = new PostorderEnumeration((TreeNode) children.nextElement());
				retval = subtree.nextElement();
			} else {
				retval = root;
				root = null;
			}

			return retval;
		}

	}

	public final class BreadthFirstEnumeration implements Enumeration, Serializable {
		protected Queue queue;

		public BreadthFirstEnumeration(TreeNode rootNode) {
			super();
			Vector v = new Vector(1);
			v.addElement(rootNode);
			queue = new Queue();
			queue.enqueue(v.elements());
		}

		public boolean hasMoreElements() {
			return (!queue.isEmpty() && ((Enumeration) queue.firstObject()).hasMoreElements());
		}

		public Object nextElement() {
			Enumeration enumer = (Enumeration) queue.firstObject();
			TreeNode node = (TreeNode) enumer.nextElement();
			Enumeration children = node.children();

			if (!enumer.hasMoreElements()) {
				queue.dequeue();
			}
			if (children.hasMoreElements()) {
				queue.enqueue(children);
			}
			return node;
		}

		// A simple queue with a linked list data structure.
		final class Queue {
			QNode head; // null if empty
			QNode tail;

			final class QNode {
				public Object object;
				public QNode next; // null if end
				public QNode(Object object, QNode next) {
					this.object = object;
					this.next = next;
				}
			}

			public void enqueue(Object anObject) {
				if (head == null) {
					head = tail = new QNode(anObject, null);
				} else {
					tail.next = new QNode(anObject, null);
					tail = tail.next;
				}
			}

			public Object dequeue() {
				if (head == null) {
					throw new NoSuchElementException("No more elements");
				}

				Object retval = head.object;
				QNode oldHead = head;
				head = head.next;
				if (head == null) {
					tail = null;
				} else {
					oldHead.next = null;
				}
				return retval;
			}

			public Object firstObject() {
				if (head == null) {
					throw new NoSuchElementException("No more elements");
				}

				return head.object;
			}

			public boolean isEmpty() {
				return head == null;
			}

		} // End of class Queue

	}

	public final class PathBetweenNodesEnumeration implements Enumeration, Serializable {
		protected Stack stack;

		public PathBetweenNodesEnumeration(TreeNode ancestor, TreeNode descendant) {
			super();

			if (ancestor == null || descendant == null) {
				throw new IllegalArgumentException("argument is null");
			}

			TreeNode current;

			stack = new Stack();
			stack.push(descendant);

			current = descendant;
			while (current != ancestor) {
				current = current.getParent();
				if (current == null && descendant != ancestor) {
					throw new IllegalArgumentException("node " + ancestor + " is not an ancestor of " + descendant);
				}
				stack.push(current);
			}
		}

		public boolean hasMoreElements() {
			return stack.size() > 0;
		}

		public Object nextElement() {
			try {
				return stack.pop();
			} catch (EmptyStackException e) {
				throw new NoSuchElementException("No more elements");
			}
		}

	}

	/**
	 * Creates a tree node that has no parent and no children, but which
	 * allows children.
	 */
	public DefaultMutableTreeNode() {
		super();
	}
	/**
	 * Creates a tree node with no parent, no children, but which allows 
	 * children, and initializes it with the specified user object.
	 * 
	 * @param userObject an Object provided by the user that constitutes
	 *                   the node's data
	 */
	public DefaultMutableTreeNode(Object userObject) {
		this(userObject, true);
	}
	/**
	 * Creates a tree node with no parent, no children, initialized with
	 * the specified user object, and that allows children only if
	 * specified.
	 * 
	 * @param userObject an Object provided by the user that constitutes
	 *        the node's data
	 * @param allowsChildren if true, the node is allowed to have child
	 *        nodes -- otherwise, it is always a leaf node
	 */
	public DefaultMutableTreeNode(Object userObject, boolean allowsChildren) {
		super();
		parent = null;
		this.allowsChildren = allowsChildren;
		this.userObject = userObject;
	}
	/**
	 * Removes <code>newChild</code> from its parent and makes it a child of
	 * this node by adding it to the end of this node's child array.
	 *
	 * @exception	IllegalArgumentException    if <code>newChild</code>
	 *						is null
	 * @exception	IllegalStateException	if this node does not allow
	 *						children
	 */
	public void add(MutableTreeNode newChild) {
		if (newChild != null && newChild.getParent() == this)
			insert(newChild, getChildCount() - 1);
		else
			insert(newChild, getChildCount());
	}
	/**
	 * Creates and returns an enumeration that traverses the subtree rooted at
	 * this node in breadth-first order.  The first node returned by the
	 * enumeration's <code>nextElement()</code> method is this node.<P>
	 *
	 * Modifying the tree by inserting, removing, or moving a node invalidates
	 * any enumerations created before the modification.
	 *
	 * @return	an enumeration for traversing the tree in breadth-first order
	 */
	public Enumeration breadthFirstEnumeration() {
		return new BreadthFirstEnumeration(this);
	}
	/**
	 * Creates and returns a forward-order enumeration of this node's
	 * children.  Modifying this node's child array invalidates any child
	 * enumerations created before the modification.
	 *
	 * @return	an Enumeration of this node's children
	 */
	public Enumeration children() {
		if (children == null) {
			return EMPTY_ENUMERATION;
		} else {
			return children.elements();
		}
	}
	/**
	 * Creates and returns an enumeration that traverses the subtree rooted at
	 * this node in depth-first order.  The first node returned by the
	 * enumeration's <code>nextElement()</code> method is the leftmost leaf.
	 * This is the same as a postorder traversal.<P>
	 *
	 * Modifying the tree by inserting, removing, or moving a node invalidates
	 * any enumerations created before the modification.
	 *
	 * @return	an enumeration for traversing the tree in depth-first order
	 */
	public Enumeration depthFirstEnumeration() {
		return postorderEnumeration();
	}
	/**
	 * Returns the Action command string associated with this node
	 */
	public String getActionCommand() {
		return actionCommand;
	}
	/**
	 * Returns true if this node is allowed to have children.
	 *
	 * @return	true if this node allows children, else false
	 */
	public boolean getAllowsChildren() {
		return allowsChildren;
	}
	/**
	 * Returns the child in this node's child array that immediately
	 * follows <code>aChild</code>, which must be a child of this node.  If
	 * <code>aChild</code> is the last child, returns null.  This method
	 * performs a linear search of this node's children for
	 * <code>aChild</code> and is O(n) where n is the number of children; to
	 * traverse the entire array of children, use an enumeration instead.
	 *
	 * @exception	IllegalArgumentException if <code>aChild</code> is
	 *					null or is not a child of this node
	 * @return	the child of this node that immediately follows
	 *		<code>aChild</code>
	 */
	public TreeNode getChildAfter(TreeNode aChild) {
		if (aChild == null) {
			throw new IllegalArgumentException("argument is null");
		}

		int index = getIndex(aChild); // linear search

		if (index == -1) {
			throw new IllegalArgumentException("node is not a child");
		}

		if (index < getChildCount() - 1) {
			return getChildAt(index + 1);
		} else {
			return null;
		}
	}
	/**
	 * Returns the child at the specified index in this node's child array.
	 *
	 * @param	index	an index into this node's child array
	 * @exception	ArrayIndexOutOfBoundsException	if <code>index</code>
	 *						is out of bounds
	 * @return	the TreeNode in this node's child array at  the specified index
	 */
	public TreeNode getChildAt(int index) {
		if (children == null) {
			throw new ArrayIndexOutOfBoundsException("node has no children");
		}
		return (TreeNode) children.elementAt(index);
	}
	/**
	 * Returns the child in this node's child array that immediately
	 * precedes <code>aChild</code>, which must be a child of this node.  If
	 * <code>aChild</code> is the first child, returns null.  This method
	 * performs a linear search of this node's children for <code>aChild</code>
	 * and is O(n) where n is the number of children.
	 *
	 * @exception	IllegalArgumentException if <code>aChild</code> is null
	 *						or is not a child of this node
	 * @return	the child of this node that immediately precedes
	 *		<code>aChild</code>
	 */
	public TreeNode getChildBefore(TreeNode aChild) {
		if (aChild == null) {
			throw new IllegalArgumentException("argument is null");
		}

		int index = getIndex(aChild); // linear search

		if (index == -1) {
			throw new IllegalArgumentException("argument is not a child");
		}

		if (index > 0) {
			return getChildAt(index - 1);
		} else {
			return null;
		}
	}
	/**
	 * Returns the number of children of this node.
	 *
	 * @return	an int giving the number of children of this node
	 */
	public int getChildCount() {
		if (children == null) {
			return 0;
		} else {
			return children.size();
		}
	}
	/**
	 * Returns the depth of the tree rooted at this node -- the longest
	 * distance from this node to a leaf.  If this node has no children,
	 * returns 0.  This operation is much more expensive than
	 * <code>getLevel()</code> because it must effectively traverse the entire
	 * tree rooted at this node.
	 *
	 * @return	the depth of the tree whose root is this node
	 */
	public int getDepth() {
		Object last = null;
		Enumeration enumeration = breadthFirstEnumeration();

		while (enumeration.hasMoreElements()) {
			last = enumeration.nextElement();
		}

		if (last == null) {
			throw new InternalError("nodes should be null");
		}

		return ((DefaultMutableTreeNode) last).getLevel() - getLevel();
	}
	/**
	 * Returns this node's first child.  If this node has no children,
	 * throws NoSuchElementException.
	 *
	 * @return	the first child of this node
	 * @exception	NoSuchElementException	if this node has no children
	 */
	public TreeNode getFirstChild() {
		if (getChildCount() == 0) {
			throw new NoSuchElementException("node has no children");
		}
		return getChildAt(0);
	}
	/**
	 * Finds and returns the first leaf that is a descendant of this node --
	 * either this node or its first child's first leaf.
	 * Returns this node if it is a leaf.
	 *
	 * @return	the first leaf in the subtree rooted at this node
	 */
	public DefaultMutableTreeNode getFirstLeaf() {
		DefaultMutableTreeNode node = this;

		while (!node.isLeaf()) {
			node = (DefaultMutableTreeNode) node.getFirstChild();
		}

		return node;
	}
	/**
	 * Returns the index of the specified child in this node's child array.
	 * If the specified node is not a child of this node, returns
	 * <code>-1</code>.  This method performs a linear search and is O(n)
	 * where n is the number of children.
	 *
	 * @param	aChild	the TreeNode to search for among this node's children
	 * @exception	IllegalArgumentException	if <code>aChild</code>
	 *							is null
	 * @return	an int giving the index of the node in this node's child 
	 *          array, or <code>-1</code> if the specified node is a not
	 *          a child of this node
	 */
	public int getIndex(TreeNode aChild) {
		if (aChild == null) {
			throw new IllegalArgumentException("argument is null");
		}

		if (!isNodeChild(aChild)) {
			return -1;
		}
		return children.indexOf(aChild); // linear search
	}
	/**
	 * Returns this node's last child.  If this node has no children,
	 * throws NoSuchElementException.
	 *
	 * @return	the last child of this node
	 * @exception	NoSuchElementException	if this node has no children
	 */
	public TreeNode getLastChild() {
		if (getChildCount() == 0) {
			throw new NoSuchElementException("node has no children");
		}
		return getChildAt(getChildCount() - 1);
	}
	/**
	 * Finds and returns the last leaf that is a descendant of this node --
	 * either this node or its last child's last leaf. 
	 * Returns this node if it is a leaf.
	 *
	 * @return	the last leaf in the subtree rooted at this node
	 */
	public DefaultMutableTreeNode getLastLeaf() {
		DefaultMutableTreeNode node = this;

		while (!node.isLeaf()) {
			node = (DefaultMutableTreeNode) node.getLastChild();
		}

		return node;
	}
	/**
	 * Returns the total number of leaves that are descendants of this node.
	 * If this node is a leaf, returns <code>1</code>.  This method is O(n)
	 * where n is the number of descendants of this node.
	 *
	 * @return	the number of leaves beneath this node
	 */
	public int getLeafCount() {
		int count = 0;

		TreeNode node;
		Enumeration enumeration = breadthFirstEnumeration(); // order matters not

		while (enumeration.hasMoreElements()) {
			node = (TreeNode) enumeration.nextElement();
			if (node.isLeaf()) {
				count++;
			}
		}

		if (count < 1) {
			throw new InternalError("tree has zero leaves");
		}

		return count;
	}
	/**
	 * Returns the number of levels above this node -- the distance from
	 * the root to this node.  If this node is the root, returns 0.
	 *
	 * @return	the number of levels above this node
	 */
	public int getLevel() {
		TreeNode ancestor;
		int levels = 0;

		ancestor = this;
		while ((ancestor = ancestor.getParent()) != null) {
			levels++;
		}

		return levels;
	}
	/**
	 * Returns the leaf after this node or null if this node is the
	 * last leaf in the tree.
	 * <p>
	 * In this implementation of the <code>MutableNode</code> interface,
	 * this operation is very inefficient. In order to determine the
	 * next node, this method first performs a linear search in the 
	 * parent's child-list in order to find the current node. 
	 * <p>
	 * That implementation makes the operation suitable for short
	 * traversals from a known position. But to traverse all of the 
	 * leaves in the tree, you should use <code>depthFirstEnumeration</code>
	 * to enumerate the nodes in the tree and use <code>isLeaf</code>
	 * on each node to determine which are leaves.
	 *
	 */
	public DefaultMutableTreeNode getNextLeaf() {
		DefaultMutableTreeNode nextSibling;
		DefaultMutableTreeNode myParent = (DefaultMutableTreeNode) getParent();

		if (myParent == null)
			return null;

		nextSibling = getNextSibling(); // linear search

		if (nextSibling != null)
			return nextSibling.getFirstLeaf();

		return myParent.getNextLeaf(); // tail recursion
	}
	/**
	 * Returns the node that follows this node in a preorder traversal of this
	 * node's tree.  Returns null if this node is the last node of the
	 * traversal.  This is an inefficient way to traverse the entire tree; use
	 * an enumeration, instead.
	 *
	 */
	public DefaultMutableTreeNode getNextNode() {
		if (getChildCount() == 0) {
			// No children, so look for nextSibling
			DefaultMutableTreeNode nextSibling = getNextSibling();

			if (nextSibling == null) {
				DefaultMutableTreeNode aNode = (DefaultMutableTreeNode) getParent();

				do {
					if (aNode == null) {
						return null;
					}

					nextSibling = aNode.getNextSibling();
					if (nextSibling != null) {
						return nextSibling;
					}

					aNode = (DefaultMutableTreeNode) aNode.getParent();
				} while (true);
			} else {
				return nextSibling;
			}
		} else {
			return (DefaultMutableTreeNode) getChildAt(0);
		}
	}
	/**
	 * Returns the next sibling of this node in the parent's children array.
	 * Returns null if this node has no parent or is the parent's last child.
	 * This method performs a linear search that is O(n) where n is the number
	 * of children; to traverse the entire array, use the parent's child
	 * enumeration instead.
	 *
	 */
	public DefaultMutableTreeNode getNextSibling() {
		DefaultMutableTreeNode retval;

		DefaultMutableTreeNode myParent = (DefaultMutableTreeNode) getParent();

		if (myParent == null) {
			retval = null;
		} else {
			retval = (DefaultMutableTreeNode) myParent.getChildAfter(this);
			// linear search
		}

		if (retval != null && !isNodeSibling(retval)) {
			throw new InternalError("child of parent is not a sibling");
		}

		return retval;
	}
	/**
	 * Returns this node's parent or null if this node has no parent.
	 *
	 * @return	this node's parent TreeNode, or null if this node has no parent
	 */
	public TreeNode getParent() {
		return parent;
	}
	/**
	  * Returns the path from the root, to get to this node.  The last
	  * element in the path is this node.
	  *
	  * @return an array of TreeNode objects giving the path, where the
	  *         first element in the path is the root and the last
	  *         element is this node.
	  */
	public TreeNode[] getPath() {
		return getPathToRoot(this, 0);
	}
	/**
	 * Builds the parents of node up to and including the root node,
	 * where the original node is the last element in the returned array.
	 * The length of the returned array gives the node's depth in the
	 * tree.
	 * 
	 * @param aNode  the TreeNode to get the path for
	 * @param depth  an int giving the number of steps already taken towards
	 *        the root (on recursive calls), used to size the returned array
	 * @return an array of TreeNodes giving the path from the root to the
	 *         specified node 
	 */
	protected TreeNode[] getPathToRoot(TreeNode aNode, int depth) {
		TreeNode[] retNodes;

		/* Check for null, in case someone passed in a null node, or
		   they passed in an element that isn't rooted at root. */
		if (aNode == null) {
			if (depth == 0)
				return null;
			else
				retNodes = new TreeNode[depth];
		} else {
			depth++;
			retNodes = getPathToRoot(aNode.getParent(), depth);
			retNodes[retNodes.length - depth] = aNode;
		}
		return retNodes;
	}
	/**
	 * Returns the leaf before this node or null if this node is the
	 * first leaf in the tree.
	 * <p>
	 * In this implementation of the <code>MutableNode</code> interface,
	 * this operation is very inefficient. In order to determine the
	 * previous node, this method first performs a linear search in the 
	 * parent's child-list in order to find the current node. 
	 * <p>
	 * That implementation makes the operation suitable for short
	 * traversals from a known position. But to traverse all of the 
	 * leaves in the tree, you should use <code>depthFirstEnumeration</code>
	 * to enumerate the nodes in the tree and use <code>isLeaf</code>
	 * on each node to determine which are leaves.
	 *
	 */
	public DefaultMutableTreeNode getPreviousLeaf() {
		DefaultMutableTreeNode previousSibling;
		DefaultMutableTreeNode myParent = (DefaultMutableTreeNode) getParent();

		if (myParent == null)
			return null;

		previousSibling = getPreviousSibling(); // linear search

		if (previousSibling != null)
			return previousSibling.getLastLeaf();

		return myParent.getPreviousLeaf(); // tail recursion
	}
	/**
	 * Returns the node that precedes this node in a preorder traversal of
	 * this node's tree.  Returns null if this node is the first node of the
	 * traveral -- the root of the tree.  This is an inefficient way to
	 * traverse the entire tree; use an enumeration, instead.
	 *
	 */
	public DefaultMutableTreeNode getPreviousNode() {
		DefaultMutableTreeNode previousSibling;
		DefaultMutableTreeNode myParent = (DefaultMutableTreeNode) getParent();

		if (myParent == null) {
			return null;
		}

		previousSibling = getPreviousSibling();

		if (previousSibling != null) {
			if (previousSibling.getChildCount() == 0)
				return previousSibling;
			else
				return previousSibling.getLastLeaf();
		} else {
			return myParent;
		}
	}
	/**
	 * Returns the previous sibling of this node in the parent's children
	 * array.  Returns null if this node has no parent or is the parent's
	 * first child.  This method performs a linear search that is O(n) where n
	 * is the number of children.
	 *
	 * @return	the sibling of this node that immediately precedes this node
	 */
	public DefaultMutableTreeNode getPreviousSibling() {
		DefaultMutableTreeNode retval;

		DefaultMutableTreeNode myParent = (DefaultMutableTreeNode) getParent();

		if (myParent == null) {
			retval = null;
		} else {
			retval = (DefaultMutableTreeNode) myParent.getChildBefore(this);
			// linear search
		}

		if (retval != null && !isNodeSibling(retval)) {
			throw new InternalError("child of parent is not a sibling");
		}

		return retval;
	}
	/**
	 * Returns the root of the tree that contains this node.  The root is
	 * the ancestor with a null parent.
	 *
	 */
	public TreeNode getRoot() {
		TreeNode ancestor = this;
		TreeNode previous;

		do {
			previous = ancestor;
			ancestor = ancestor.getParent();
		} while (ancestor != null);

		return previous;
	}
	/**
	 * Returns the nearest common ancestor to this node and <code>aNode</code>.
	 * Returns null, if no such ancestor exists -- if this node and
	 * <code>aNode</code> are in different trees or if <code>aNode</code> is
	 * null.  A node is considered an ancestor of itself.
	 *
	 */
	public TreeNode getSharedAncestor(DefaultMutableTreeNode aNode) {
		if (aNode == this) {
			return this;
		} else if (aNode == null) {
			return null;
		}

		int level1, level2, diff;
		TreeNode node1, node2;

		level1 = getLevel();
		level2 = aNode.getLevel();

		if (level2 > level1) {
			diff = level2 - level1;
			node1 = aNode;
			node2 = this;
		} else {
			diff = level1 - level2;
			node1 = this;
			node2 = aNode;
		}

		// Go up the tree until the nodes are at the same level
		while (diff > 0) {
			node1 = node1.getParent();
			diff--;
		}

		// Move up the tree until we find a common ancestor.  Since we know
		// that both nodes are at the same level, we won't cross paths
		// unknowingly (if there is a common ancestor, both nodes hit it in
		// the same iteration).

		do {
			if (node1 == node2) {
				return node1;
			}
			node1 = node1.getParent();
			node2 = node2.getParent();
		} while (node1 != null); // only need to check one -- they're at the
		// same level so if one is null, the other is

		if (node1 != null || node2 != null) {
			throw new InternalError("nodes should be null");
		}

		return null;
	}
	/**
	 * Returns the number of siblings of this node.  A node is its own sibling
	 * (if it has no parent or no siblings, this method returns
	 * <code>1</code>).
	 *
	 * @return	the number of siblings of this node
	 */
	public int getSiblingCount() {
		TreeNode myParent = getParent();

		if (myParent == null) {
			return 1;
		} else {
			return myParent.getChildCount();
		}
	}
	/**
	 * Returns this node's user object.
	 *
	 */
	public Object getUserObject() {
		return userObject;
	}
	/**
	  * Returns the user object path, from the root, to get to this node.
	  * If some of the TreeNodes in the path have null user objects, the
	  * returned path will contain nulls.
	  */
	public Object[] getUserObjectPath() {
		TreeNode[] realPath = getPath();
		Object[] retPath = new Object[realPath.length];

		for (int counter = 0; counter < realPath.length; counter++)
			retPath[counter] = ((DefaultMutableTreeNode) realPath[counter]).getUserObject();
		return retPath;
	}
	/**
	 * Removes <code>newChild</code> from its present parent (if it has a
	 * parent), sets the child's parent to this node, and then adds the child
	 * to this node's child array at index <code>childIndex</code>.
	 * <code>newChild</code> must not be null and must not be an ancestor of
	 * this node.
	 *
	 */
	public void insert(MutableTreeNode newChild, int childIndex) {
		if (!getAllowsChildren()) {
			throw new IllegalStateException("node does not allow children");
		} else if (newChild == null) {
			throw new IllegalArgumentException("new child is null");
		} else if (isNodeAncestor(newChild)) {
			throw new IllegalArgumentException("new child is an ancestor");
		}

		MutableTreeNode oldParent = (MutableTreeNode) newChild.getParent();

		if (oldParent != null) {
			oldParent.remove(newChild);
		}
		newChild.setParent(this);
		if (children == null) {
			children = new Vector();
		}
		children.insertElementAt(newChild, childIndex);
	}
	/**
	 * Returns true if this node has no children.  To distinguish between
	 * nodes that have no children and nodes that <i>cannot</i> have
	 * children (e.g. to distinguish files from empty directories), use this
	 * method in conjunction with <code>getAllowsChildren</code>
	 *
	 */
	public boolean isLeaf() {
		return (getChildCount() == 0);
	}
	/**
	 * Returns true if <code>anotherNode</code> is an ancestor of this node
	 * -- if it is this node, this node's parent, or an ancestor of this
	 * node's parent.  (Note that a node is considered an ancestor of itself.)
	 * If <code>anotherNode</code> is null, this method returns false.  This
	 * operation is at worst O(h) where h is the distance from the root to
	 * this node.
	 *
	 */
	public boolean isNodeAncestor(TreeNode anotherNode) {
		if (anotherNode == null) {
			return false;
		}

		TreeNode ancestor = this;

		do {
			if (ancestor == anotherNode) {
				return true;
			}
		} while ((ancestor = ancestor.getParent()) != null);

		return false;
	}
	/**
	 * Returns true if <code>aNode</code> is a child of this node.  If
	 * <code>aNode</code> is null, this method returns false.
	 *
	 * @return	true if <code>aNode</code> is a child of this node; false if 
	 *  		<code>aNode</code> is null
	 */
	public boolean isNodeChild(TreeNode aNode) {
		boolean retval;

		if (aNode == null) {
			retval = false;
		} else {
			if (getChildCount() == 0) {
				retval = false;
			} else {
				retval = (aNode.getParent() == this);
			}
		}

		return retval;
	}
	/**
	 * Returns true if <code>anotherNode</code> is a descendant of this node
	 * -- if it is this node, one of this node's children, or a descendant of
	 * one of this node's children.  Note that a node is considered a
	 * descendant of itself.  If <code>anotherNode</code> is null, returns
	 * false.  This operation is at worst O(h) where h is the distance from the
	 * root to <code>anotherNode</code>.
	 *
	 */
	public boolean isNodeDescendant(DefaultMutableTreeNode anotherNode) {
		if (anotherNode == null)
			return false;

		return anotherNode.isNodeAncestor(this);
	}
	/**
	 * Returns true if and only if <code>aNode</code> is in the same tree
	 * as this node.  Returns false if <code>aNode</code> is null.
	 *
	 */
	public boolean isNodeRelated(DefaultMutableTreeNode aNode) {
		return (aNode != null) && (getRoot() == aNode.getRoot());
	}
	/**
	 * Returns true if <code>anotherNode</code> is a sibling of (has the
	 * same parent as) this node.  A node is its own sibling.  If
	 * <code>anotherNode</code> is null, returns false.
	 *
	 * @param	anotherNode	node to test as sibling of this node
	 * @return	true if <code>anotherNode</code> is a sibling of this node
	 */
	public boolean isNodeSibling(TreeNode anotherNode) {
		boolean retval;

		if (anotherNode == null) {
			retval = false;
		} else if (anotherNode == this) {
			retval = true;
		} else {
			TreeNode myParent = getParent();
			retval = (myParent != null && myParent == anotherNode.getParent());

			if (retval && !((DefaultMutableTreeNode) getParent()).isNodeChild(anotherNode)) {
				throw new InternalError("sibling has different parent");
			}
		}

		return retval;
	}
	/**
	 * Returns true if this node is the root of the tree.  The root is
	 * the only node in the tree with a null parent; every tree has exactly
	 * one root.
	 *
	 * @return	true if this node is the root of its tree
	 */
	public boolean isRoot() {
		return getParent() == null;
	}
	/**
	 * Creates and returns an enumeration that follows the path from
	 * <code>ancestor</code> to this node.  The enumeration's
	 * <code>nextElement()</code> method first returns <code>ancestor</code>,
	 * then the child of <code>ancestor</code> that is an ancestor of this
	 * node, and so on, and finally returns this node.  Creation of the
	 * enumeration is O(m) where m is the number of nodes between this node
	 * and <code>ancestor</code>, inclusive.  Each <code>nextElement()</code>
	 * message is O(1).<P>
	 *
	 * Modifying the tree by inserting, removing, or moving a node invalidates
	 * any enumerations created before the modification.
	 *
	 */
	public Enumeration pathFromAncestorEnumeration(TreeNode ancestor) {
		return new PathBetweenNodesEnumeration(ancestor, this);
	}
	/**
	 * Creates and returns an enumeration that traverses the subtree rooted at
	 * this node in postorder.  The first node returned by the enumeration's
	 * <code>nextElement()</code> method is the leftmost leaf.  This is the
	 * same as a depth-first traversal.<P>
	 *
	 * Modifying the tree by inserting, removing, or moving a node invalidates
	 * any enumerations created before the modification.
	 *
	 */
	public Enumeration postorderEnumeration() {
		return new PostorderEnumeration(this);
	}
	/**
	 * Creates and returns an enumeration that traverses the subtree rooted at
	 * this node in preorder.  The first node returned by the enumeration's
	 * <code>nextElement()</code> method is this node.<P>
	 *
	 * Modifying the tree by inserting, removing, or moving a node invalidates
	 * any enumerations created before the modification.
	 *
	 */
	public Enumeration preorderEnumeration() {
		return new PreorderEnumeration(this);
	}
	/**
	 * Removes the child at the specified index from this node's children
	 * and sets that node's parent to null. The child node to remove
	 * must be a <code>MutableTreeNode</code>.
	 *
	 * @param	childIndex	the index in this node's child array
	 *				of the child to remove
	 * @exception	ArrayIndexOutOfBoundsException	if
	 *				<code>childIndex</code> is out of bounds
	 */
	public void remove(int childIndex) {
		MutableTreeNode child = (MutableTreeNode) getChildAt(childIndex);
		children.removeElementAt(childIndex);
		child.setParent(null);
	}
	/**
	 * Removes <code>aChild</code> from this node's child array, giving it a
	 * null parent.
	 *
	 * @param	aChild	a child of this node to remove
	 * @exception	IllegalArgumentException	if <code>aChild</code>
	 *					is null or is not a child of this node
	 */
	public void remove(MutableTreeNode aChild) {
		if (aChild == null) {
			throw new IllegalArgumentException("argument is null");
		}

		if (!isNodeChild(aChild)) {
			throw new IllegalArgumentException("argument is not a child");
		}
		remove(getIndex(aChild)); // linear search
	}
	/**
	 * Removes all of this node's children, setting their parents to null.
	 * If this node has no children, this method does nothing.
	 */
	public void removeAllChildren() {
		for (int i = getChildCount() - 1; i >= 0; i--) {
			remove(i);
		}
	}
	/**
	 * Removes the subtree rooted at this node from the tree, giving this
	 * node a null parent.  Does nothing if this node is the root of its
	 * tree.
	 */
	public void removeFromParent() {
		MutableTreeNode parent = (MutableTreeNode) getParent();
		if (parent != null) {
			parent.remove(this);
		}
	}
	/**
	 * Sets this node's action command to <code>newActionCommand</code> 
	 *
	 * @param	newActionCommand	this node's new action command
	 */
	public void setActionCommand(String newActionCommand) {
		actionCommand = newActionCommand;
	}
	/**
	 * Determines whether or not this node is allowed to have children. 
	 * If <code>allows</code> is false, all of this node's children are
	 * removed.
	 * <p>
	 * Note: By default, a node allows children.
	 *
	 * @param	allows	true if this node is allowed to have children
	 */
	public void setAllowsChildren(boolean allows) {
		if (allows != allowsChildren) {
			allowsChildren = allows;
			if (!allowsChildren) {
				removeAllChildren();
			}
		}
	}
	/**
	 * Sets this node's parent to <code>newParent</code> but does not 
	 * change the parent's child array.  This method is called from
	 * <code>insert()</code> and <code>remove()</code> to
	 * reassign a child's parent, it should not be messaged from anywhere
	 * else.
	 *
	 * @param	newParent	this node's new parent
	 */
	public void setParent(MutableTreeNode newParent) {
		parent = newParent;
	}
	/**
	 * Sets the user object for this node to <code>userObject</code>.
	 *
	 */
	public void setUserObject(Object userObject) {
		this.userObject = userObject;
	}
	/**
	 * Returns the result of sending <code>toString()</code> to this node's
	 * user object, or null if this node has no user object.
	 *
	 */
	public String toString() {
		if (userObject == null) {
			return null;
		} else {
			return userObject.toString();
		}
	}
}
