import java.util.Iterator;
import java.util.NoSuchElementException;

/* Iterates over a tree position's descendants in prefix order,
   starting with the position itself. */

public class TreePreorderIterator implements Iterator {
  protected TreeNode p;   // next position to return, or null if no more
  
  public TreePreorderIterator(TreeNode p) {
    this.p = p;
  }

  public boolean hasNext() {
    return (p != null);
  }

  public Object next() {
    return nextPosition().element();
  }

  /* The java.util.Iterator interface requires us to define a method
     for destructively removing an element from the list being
     iterated over, but we are allowed to just throw an
     UnsupportedOperationException if we don't want to implement this. */

  public void remove() {   
    throw new UnsupportedOperationException();
  }

  public TreeNode nextPosition() {
    if (!hasNext())
      throw new NoSuchElementException();

    TreeNode old = p;   // remember what to return

    // now advance p to the next thing to return

    if (p.isInternal()) 

      p = p.leftChild();

    else {

      // take the right sibling; 
      // or if there is none, take the parent's right sibling, and so on up.

      while (p.rightSibling() == null && p.parent() != null) 
	p = p.parent();

      // Now that the while loop is over, the while test must be
      // false.  That is, 
      //    p.rightSibling() != null || p.parent() == null
      // So either p finally has a right sibling, in which case we 
      // should use that next, or else p is parentless, in which case 
      // it is the root and we should use null next.

      p = p.rightSibling();    // works either way
    }
    
    // okay, return old position

    return old;
  }
}