/**
 * A cursor for a binary tree.  Cursors are the primary mechanism by which
 * we traverse and modify binary trees.
 *
 * @author Samuel A. Rebelsky
 * @version 1.0 of April 1999
 */
public interface BinaryTreeCursor {
  // +-----------+-----------------------------------------------
  // | Accessors |
  // +-----------+

  /**
   * Get the value associated with the cursor.
   * Pre: The cursor is initialized.
   * Pre: The cursor is on the tree.
   * Pre: The tree is initialized and nonempty.
   * Post: Returns the value associated with the cursor.
   */
  public Object getValue();

  /**
   * Determine whether there is a left child below the current
   * cursor.
   * Pre: Cursor is initialized and on the tree.
   * Pre: Tree is initialized and nonempty.
   * Post: Returns true if there is a left child and false otherwise.
   */
  public boolean hasLeftChild();

  /**
   * Determine whether there is a right child below the current
   * cursor.
   * Pre: Cursor is initialized and on the tree.
   * Pre: Tree is initialized and nonempty.
   * Post: Returns true if there is a right child and false otherwise.
   */
  public boolean hasRightChild();

  /**
   * Determine if the cursor is on a leaf.
   * Pre: Cursor is initialized and on the tree.
   * Pre: Tree is initialized and nonempty.
   * Post: Returns true if its on a leaf and false otherwise.
   */
  public boolean onLeaf();

  /**
   * Determine whether the cursor is on the tree.  Included because
   * it serves as a precondition for many methods.  (You don't need
   * to test it explicitly, but you might want to.)
   * Pre: Cursor is initialized.
   * Pre: Tree is initialized.
   * Post: Returns true if the cursor is on the tree and false otherwise.
   */
  public boolean onTree();

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

  /**
   * Make a copy of the current cursor.  Note that the return type
   * is Object rather than BinaryTreeNode to satisfy the Java compiler.
   * You are, nonetheless, expected to return a cursor.
   * Pre: Cursor is initialized and on the tree.
   * Pre: Tree is initialized and nonempty.
   * Post: Returns a new cursor that refers to the same node.  The two
   *   cursors will move independently.
   */
  public Object clone();

  /**
   * Create a new cursor at the left child.
   * Pre: Cursor is initialized and on the tree.
   * Pre: Tree is initialized and nonempty.
   * Pre: There is a left child below the current cursor.
   * Post: Returns a cursor such that the cursor is at the same place
   *   that the current cursor would be after a downLeft operation.
   */
  public BinaryTreeCursor getLeftChild();

  /**
   * Create a new cursor at the right child.
   * Pre: Cursor is initialized and on the tree.
   * Pre: Tree is initialized and nonempty.
   * Pre: There is a right child below the current cursor.
   * Post: Returns a cursor such that the cursor is at the same place
   *   that the current cursor would be after a downRight operation.
   */
  public BinaryTreeCursor getRightChild();

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

  /**
   * Move the cursor down to a left child.
   * Pre: Cursor is initialized and on the tree.
   * Pre: Tree is initialized and nonempty.
   * Pre: There is a left child below the current cursor.
   * Post: The cursor is now at the left child of its previous node.
   */
  public void downLeft();

  /**
   * Move the cursor down to a right child.
   * Pre: Cursor is initialized and on the tree.
   * Pre: Tree is initialized and nonempty.
   * Pre: There is a right child below the current cursor.
   * Post: The cursor is now at the right child of its previous node.
   */
  public void downRight();

  /**
   * Move the cursor up one level.
   * Pre: Cursor is initialized and on the tree.
   * Pre: Tree is initialized and nonempty.
   * Pre: The cursor is not at the root.
   * Post: The cursor is now at the parent of its previous node.
   */
  public void up();
  
  // +-----------------+-----------------------------------------
  // | Other Modifiers |
  // +-----------------+

  /**
   * Delete the node referenced by the cursor.
   * Pre: Cursor is initialized and on the tree.
   * Pre: The tree is nonempty.
   * Post: The node referenced by the cursor, and all parts of the subtree
   *   rooted at that node, are no longer in the tree.
   * Post: The tree decreases in size by at least 1.
   */
  public void delete();

  /**
   * Set the value in the node associated with this cursor.
   * Pre: Cursor is initialized and on the tree.
   * Pre: Tree is initialized and nonempty.
   * Post: The value returned by getValue will be newValue.
   */
  public void setValue(Object newValue);

  /**
   * Set the left child of the node associated with the cursor.
   * Pre: Cursor is initialized and on the tree.
   * Pre: Tree is initialized and nonempty.
   * Pre: Node currently has no left child.
   * Post: The left child now exists and has the given value.
   */
  public void setLeft(Object newValue);

  /**
   * Set the right child of the node associated with the cursor.
   * Pre: Cursor is initialized and on the tree.
   * Pre: Tree is initialized and nonempty.
   * Pre: Node currently has no right child.
   * Post: The right child now exists and has the given value.
   */
  public void setRight(Object newValue);

} // interface BinaryTreeCursor