/**
 * An implementation of binary trees using explicit nodes.  Fields are used 
 * to keep track of the depth and size.  The cursor is responsible for 
 * updating the fields.
 *
 * @author Samuel A. Rebelsky
 * @version 0.5 of April 1999
 */
public class NodeBasedBinaryTree 
  implements BinaryTree
{
  // +--------+--------------------------------------------------
  // | Fields |
  // +--------+

  /** The node at the root of the tree.  Set to null for empty trees. */
  protected BinaryTreeNode root;
  /** The depth of the tree.  Should only be modified by the cursor. */
  protected int depth;
  /** The size of the tree (number of nodes). */
  protected int size;

  // +--------------+--------------------------------------------
  // | Constructors |
  // +--------------+

  /**
   * Create a new, empty tree.
   */
  public NodeBasedBinaryTree() {
    this.root = null;
    this.depth = 0;
    this.size = 0;
  } // NodeBasedBinaryTree()

  // +---------+-------------------------------------------------
  // | Methods |
  // +---------+
 
  /**  Determine the number of elements in the tree. */
  public int size() {
    return this.size;
  } // size()

  /**  Determine the depth of the tree. */
  public int depth() {
    return this.depth;
  } // depth()

  /** Create a new cursor at the root of the tree. */
  public BinaryTreeCursor rootCursor() {
    return new NodeBasedBinaryTreeCursor(root, 0, this);
  } // rootCursor()

  /** Set the value at the root of an empty tree. */
  public void setRoot(Object newValue) {
    depth = 0;
    size = 1;
    root = new BinaryTreeNode(null, newValue);
  } // setRoot(Object)


  // +---------+-------------------------------------------------
  // | Helpers |
  // +---------+

  // These are only called by the other members of this package.
  
  /**
   * Recompute the depth of the tree.
   */
  protected void recomputeDepth() {
    depth = 0;
    recomputeDepth(root,0);
  } // recomputeDepth()

  /**
   * Recompute the depth of the tree, using knowledge that a particular node
   * is at a particular depth.
   */
  protected void recomputeDepth(BinaryTreeNode node, int depth) {
    if (node != null) {
      if (this.depth < depth) this.depth = depth;
      recomputeDepth(node.getLeft(), depth+1);
      recomputeDepth(node.getRight(), depth+1);
    }
  } // recomputeDepth(BinaryTreeNode, int)

} // class NodeBasedBinaryTree