import TreeNode;
import TreeVertex;
import Tree;

/**
 * Generic trees.
 *
 * @author Samuel A. Rebelsky
 * @version 1.0 of April 2000
 */
public class NodeBasedTree
  implements Tree 
{

    // +--------+----------------------------------------
    // | Fields |
    // +--------+

    /**
     * The root of the tree.  Set to null when the
     * tree is empty.
     */
    protected TreeNode root;

    // +------------+------------------------------------
    // | Extractors |
    // +------------+

    /**
     * Get the vertex at the root of the tree.
     */
    public TreeVertex getRoot() {
      return this.root;
    } // getRoot()

    /**
     * Determine if the tree is empty.
     */
    public boolean isEmpty() {
      return (this.root == null);
    } // isEmpty()

    // +-----------+-------------------------------------
    // | Modifiers |
    // +-----------+

    /**
     * Add a vertex to the tree as a child of a particular vertex.
     */
    public void addChild(TreeVertex parent, Object child)
        throws Exception
    {
      ((TreeNode) parent).addChild(child);
    } // addChild(TreeVertex, Object)

    /**
     * Add a root to an empty tree.
     * Pre: The tree is empty.
     * Post: The tree contains one vertex which contains the
     *       specified value.
     */
    public void makeRoot(Object rootValue) {
      this.root = new TreeNode(rootValue);
    } // makeRoot(Object)

    /**
     * Delete a vertex from the tree.  An unpleasant operation,
     * at best.  Also deletes everything below the vertex.
     */
    public void delete(TreeVertex target) {
        // Special case: It's the root.
        if (target.isRoot()) {
            this.root = null;
        }
        // Normal case
        else {
            TreeNode parent = (TreeNode) target.getParent();
            for (int i = 1; i <= parent.numChildren(); i++) {
                if (target.equals(parent.getChild(i))) {
                  parent.deleteChild(i);
                  return;
                } // If we've found the child
            } // for each child
        } // not the root
    } // delete
} // class NodeBasedTree