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

/* Iterates over the proper ancestors of a position in the tree,
   from bottom to top. */

public class TreeAncestorsIterator implements Iterator {
  protected TreeNode p;   // next position to return, or null if no more
  
  public TreeAncestorsIterator(TreeNode p) {
    this.p = p.parent();  // start with the parent of p
  }

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

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

  public TreeNode nextPosition() {
    if (!hasNext())
      throw new NoSuchElementException();

    TreeNode old = p;   // we will return old
    p = p.parent();
    return old;
  }

  /* 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();
  }
}