/**
 * A cursor for node-based binary trees.
 *
 * @author Samuel A. Rebelsky
 * @version 0.5 of April 1999
 */
public class NodeBasedBinaryTreeCursor 
  implements BinaryTreeCursor
{
  // +--------+--------------------------------------------------
  // | Fields |
  // +--------+

  /** The node to which this cursor refers. */
  public BinaryTreeNode node;
  /** The tree which this node belongs to.  Cannot be changed.  */
  protected NodeBasedBinaryTree tree;
  /** 
   * The depth of this cursor. Cannot be changed explicitly, but changed
   * implicitly by up and down. 
   */
  protected int depth;
 
  // +--------------+--------------------------------------------
  // | Constructors |
  // +--------------+

  /**
   * Create a new cursor for a particular node at a particular depth in
   * a particular tree.
   */
  public NodeBasedBinaryTreeCursor(
    BinaryTreeNode node,
    int depth,
    NodeBasedBinaryTree tree)
  {
    this.node = node;
    this.depth = depth;
    this.tree = tree;
  } // NodeBasedBinaryTreeCursor(BinaryTreeNode, int, NodeBasedBinaryTree)

  // +-----------+-----------------------------------------------
  // | Accessors |
  // +-----------+

  /** Get the value associated with the cursor. */
  public Object getValue() {
    return node.getContents();
  } // getValue()

  /** Determine whether there is a left child below the current cursor. */
  public boolean hasLeftChild() {
    return node.getLeft() != null;
  } // hasLeftChild()

  /** Determine whether there is a right child below the current cursor. */
  public boolean hasRightChild() {
    return node.getRight() != null;
  } // hasRightChild()

  /** Determine if the cursor is on a leaf. */
  public boolean onLeaf() {
    return (node.getLeft() == null) && (node.getRight() == null);
  } // onLeaf()

  /** Determine whether the cursor is on the tree. */
  public boolean onTree() {
    // Either the tree or the node are set to null when a cursor is moved
    // off the tree.
    if ((tree == null) || (node == null)) return false;
    // When a node is "deleted" its parent is set to null.  If the node
    // has a null parent and is not the root of the tree, then the cursor
    // is not on the tree.  Because both this class and the tree class are
    // in the same package, we can access its fields directly.  (This is
    // a particular design strategy.)
    if ((node.getParent() == null) && (tree.root != node)) return false;
    // If the tree is empty, the cursor can't be on the tree.
    if (tree.root == null) return false;
    // If none of these conditions holds, then it seems to be on the tree.
    return true;
  } // onTree()

  // +-----------------+-----------------------------------------
  // | Cursor Creation |
  // +-----------------+

  /** Make a copy of the current cursor. */
  public Object clone() {
    return new NodeBasedBinaryTreeCursor(this.node, this.depth, this.tree);
  } // clone()

  /** Create a new cursor at the left child. */
  public BinaryTreeCursor getLeftChild() {
    return new NodeBasedBinaryTreeCursor(this.node.getLeft(), this.depth+1, this.tree);
  } // getLeftChild()

  /** Create a new cursor at the right child. */
  public BinaryTreeCursor getRightChild() {
    return new NodeBasedBinaryTreeCursor(this.node.getRight(), this.depth+1, this.tree);
  } // getRightChild()

  // +-----------------+-----------------------------------------
  // | Cursor Movement |
  // +-----------------+

  /** Move the cursor down to a left child. */
  public void downLeft() {
    node = node.getLeft();
    depth = depth+1;
  } // downLeft()

  /** Move the cursor down to a right child. */
  public void downRight() {
    node = node.getRight();
    depth = depth+1;
  } // downRight()

  /** Move the cursor up one level. */
  public void up() {
    node = node.getParent();
    depth = depth-1;
  } // up()
  
  // +-----------------+-----------------------------------------
  // | Other Modifiers |
  // +-----------------+

  /** Delete the node/subtree referenced by the cursor. */
  public void delete() {
    tree.size -= node.delete();
    tree.recomputeDepth();
    if (node == tree.root) tree.root = null;
    node = null;
    tree = null;
  } // delete()

  /** Set the value in the node associated with this cursor. */
  public void setValue(Object newValue) {
    node.setContents(newValue);
  } // setValue(Object)

  /** Set the left child of the node associated with the cursor. */
  public void setLeft(Object newValue) {
    node.setLeft(new BinaryTreeNode(node, newValue));
    if (depth+1 > tree.depth) tree.depth = depth;
    tree.size +=1;
  } // setLeft(Object)

  /** Set the right child of the node associated with the cursor. */
  public void setRight(Object newValue) {
    node.setRight(new BinaryTreeNode(node, newValue));
    if (depth+1 > tree.depth) tree.depth = depth;
    tree.size += 1;
  } // setRight(Object)

} // class NodeBasedBinaryTreeCursor