import structure5.*;
import java.util.Iterator;

class ReverseIterator<E> extends AbstractIterator<E> {
  protected AbstractIterator<E> elems;

  /**
   * A ReverseIterator takes an existing Iterator
   * and when iterated, returns elements of type E
   * in reverse order.
   *
   * Note that this is not a particularly efficient
   * implementation!  It stores copies of all of the
   * values stored in the original data structure, so
   * it uses O(n) space.  See if you can find a
   * better way to implement this using less space.
   */
  public ReverseIterator(Iterator<E> iter) {
  // We iterate over iter and store each element
  // from the original collection in a new list.
  // Since we always call addFirst (aka "list prepend")
  // the last element we added will be the first
  // element in the list.
  SinglyLinkedList<E> list = new SinglyLinkedList<>();
  while (iter.hasNext()) {
    list.addFirst(iter.next());
  }
  // We do this unsafe cast because .iterator()
  // technically returns an Iterator<E>, not
  // an AbstractIterator<E>.  However, we also
  // know that SLL's .iterator() method happens to
  // return an Iterator<E> that is implemented as an
  // AbstractIterator<E>, thus the cast will not fail.
  // In general, casting is a bad idea, because
  // AbstractIterator<E> implements Iterator<E>,
  // not the other way around, meaning that for
  // an arbitrary data structure, not every Iterator<E>
  // is an AbstractIterator<E>.
    elems = (AbstractIterator<E>)list.iterator();
  }

  // here, we just rely on the SLL's built-in iterator
  public boolean hasNext() { return elems.hasNext(); }
  public void reset() { elems.reset(); }
  public E next() { return elems.next(); }
  public E get() { return elems.get(); }
}