/* SibTreePosition.java */

package tree;

/**
 * A SibTreePosition object refers to a specific position (node) within a
 * SibTree (sibling-based general tree), and allows operations on the tree
 * to be performed at that position.
 * @author Jonathan Shewchuk
 */

public class SibTreePosition implements TreePosition {

  /**
   * ADT implementation invariants:
   * 1) if theNode != null and theNode.live == true, then theNode is a node
   *    in theTree.
   * 2) theTree != null.
   * 3) theTree satisfies all the invariants of a SibTree.
   */

  /**
   * IMPORTANT:  It is okay for a SibTreePosition to have theNode set to null;
   *             this is one way to represent an "invalid position" which can
   *             be tested for by the isValidPosition() method.
   */

  private SibTree theTree;            // The tree in which this position occurs
  private SibTreeNode theNode;                       // Which node in the tree?

  /**
   * Constructs a position that is at the root of the Tree.
   */
  public SibTreePosition(SibTree tree) {
    theTree = tree;
    theNode = tree.root;
  }

  /**
   * Constructs a position at a given SibTreeNode.
   */
  SibTreePosition(SibTree tree, SibTreeNode node) {
    theTree = tree;
    theNode = node;
  }

  /**
   * children() returns the number of children of the node at this position.
   * WARNING:  Does not run in constant time.  Actually counts the kids.
   */
  public int children() {
    if (isValidPosition()) {
      int count = 0;
      SibTreeNode countNode = theNode.firstChild;
      while (countNode != null) {
        count++;
        countNode = countNode.nextSibling;
      }
      return count;
    } else {
      return 0;
    }
  }

  /**
   * parent() constructs a new TreePosition representing the parent of this
   * TreePosition.  Throws an exception if `this' is not a valid position.
   * Returns an invalid TreePosition if this position is at the root.
   */
  public TreePosition parent() throws NoSuchTreePosition {
    // FILL IN PART 1 HERE, REPLACING THE FOLLOWING LINE
    return null;
  }

  /**
   * child() constructs a new TreePosition representing the cth child of this
   * TreePosition.  Throws an exception if `this' is not a valid position.
   * Returns an invalid TreePosition if there is no cth child.
   */
  public TreePosition child(int c) throws NoSuchTreePosition {
    if (isValidPosition()) {
      if (c < 1) {
        return new SibTreePosition(theTree, null);
      }
      SibTreeNode kid = theNode.firstChild;
      while ((kid != null) && (c > 1)) {
        kid = kid.nextSibling;
        c--;
      }
      return new SibTreePosition(theTree, kid);
    } else {
      throw new NoSuchTreePosition();
    }
  }

  /**
   * nextSibling() constructs a new TreePosition representing the next sibling
   * to the right from this TreePosition.  Throws an exception if `this' is
   * not a valid position.  Returns an invalid TreePosition if there is no
   * sibling to the right of this position.
   */
  public TreePosition nextSibling() throws NoSuchTreePosition {
    if (isValidPosition()) {
      return new SibTreePosition(theTree, theNode.nextSibling);
    } else {
      throw new NoSuchTreePosition();
    }
  }

  /**
   * elementAt() returns the item at the current position.
   */
  public Object elementAt() throws NoSuchTreePosition {
    if (isValidPosition()) {
      return theNode.item;
    } else {
      throw new NoSuchTreePosition();
    }
  }

  /**
   * setElementAt() sets the item at the current position.
   */
  public void setElementAt(Object value) throws NoSuchTreePosition {
    if (isValidPosition()) {
      theNode.item = value;
    } else {
      throw new NoSuchTreePosition();
    }
  }

  /**
   * insertChild() inserts an item as the cth child of the current position.
   * Existing children numbered c or higher are shifted one place to the right
   * to accommodate.  If the current position has fewer than c children,
   * the new item is inserted as the last child.  If c < 1, it is treated as
   * if it were 1.
   */
  public void insertChild(Object item, int c) throws NoSuchTreePosition {
    // FILL IN PART 2 HERE
  }

  /**
   * removeLeaf() removes the node at the current position from the tree if
   * it is a leaf.  Throws a BadOperation exception if `this' has one or more
   * children.  Throws a NoSuchTreePosition exception if `this' is not a valid
   * position. If 'this' has siblings to its right, those siblings are all
   * shifted left by one.
   */
  public void removeLeaf() throws NoSuchTreePosition, BadOperation {
    // FILL IN PART 3 HERE
  }

  /**
   * isValidPosition() determines whether the current position is valid;
   * i.e., whether it refers to an existing node of the tree.
   */
  public boolean isValidPosition() {
    return (theNode != null) && theNode.live;
  }

  /**
   * equals() determines whether two TreePositions refer to the same node.
   */
  public boolean equals(Object other) {
    if (other instanceof SibTreePosition) {
      return theNode == ((SibTreePosition) other).theNode;
    } else {
      return false;
    }
  }

}