import java.util.Iterator;

public class Chain<T> implements Iterable<T>{

	/**
	 * How many specfields belong here?
	 *
	 * @specfield ______ : _______  ____________________________
	 *                              ____________________________
	 * @specfield ______ : _______  ____________________________
	 *                              ____________________________
	 * ...
	 *
	 * Represents an immutable sequence of elements, which can be
	 * extended from the "head" side.
	 */

	/*
	  Abstraction funciton:
	  











	 */


	/*
	  Representation invariant:









	 */
	private final int size;
	private final T head;
	private final Chain<T> rest;

	/**
	 * Constructs a new chain with one item, initial.
	 * @requires initial !=null
	 */
	public Chain(T initial){
		head = initial;
		rest = null;
		size = 1;
	}

	//Private constructor: remember this trick, it's useful.
	private Chain(T newHead, Chain<T> oldChain){
		head = newHead;
		rest = oldChain;
		size = oldChain.size + 1;
	}

	/**
	 * @returns the number of elements contained in this Chain
	 */
	public int size(){
		return size;
	}

	/**
	 * @returns ______________________________________________
	 *          ______________________________________________
	 *
	 * @modifies _____________________________________________
	 *          ______________________________________________
	 * 
	 * @requires _____________________________________________
	 *           _____________________________________________
	 *
	 * @effects ______________________________________________
	 *          ______________________________________________
	 */

	public Chain<T> extendAtFront(T next){
		return new Chain<T>(next, this);
	}


	/**
	 * 
	 *
	 *
	 *
	 *
	 *
	 *
	 */
	public Iterator<T> iterator(){
     return new ChainIterator();
	}

  
  class ChainIterator implements Iterator<T>{
    Chain<T> current = Chain.this;
    public boolean hasNext() {
      return current.rest != null;
    }
    public T next() {
      T toReturn = current.head;
      current = current.rest;
      return toReturn;
    }            
    public void remove() {
      throw new UnsupportedOperationException("Can't remove from a Chain iterator");
    }
  };

}