import tester.Traversal;

/** Interface for classes that represent a recursively defined list of
 *  items of the type <code>T</code>... extends the
 *  <code>Traversal</code> interface.
 */
interface ILo<T> extends Traversal<T>{
    // Note that isEmpty(), getFirst() and getRest() 
    //   are also added to this interface by extending
    //   the 'implementation' of Traversal
}

/** Represents an empty list of items of the type <code>T</code>. */
class MtLo<T> implements ILo<T>{
    /** The constructor */
    public MtLo(){}

    /** Produce true if this {@link Traversal Traversal} represents an
     * empty dataset
     *
     * @return true if the dataset is empty
     */
    public boolean isEmpty(){
        return true;
    }

    /** Produce the first element in the dataset represented by this
     * {@link Traversal Traversal} Throws
     * <code>IllegalUseOfTraversalException</code> if the dataset is
     * empty.</p>
     * 
     * @return the first element if available -- otherwise throws
     * <code>IllegalUseOfTraversalException</code>
     */
    public T getFirst(){
        throw new IllegalUseOfTraversalException("No first element in an empty list");
    }

    /** Produce a {@link Traversal Traversal} for the rest of the
     *  dataset. Throws <code>IllegalUseOfTraversalException</code> if
     *  the dataset is empty.
     * 
     * @return the {@link Traversal Traversal}</code> for the rest of
     * this dataset if available - otherwise throws
     * <code>IllegalUseOfTraversalException</code>
     */
    public Traversal<T> getRest(){ 
        throw new IllegalUseOfTraversalException("No remaining elements in an empty list");
    }
}

/** Represents a nonempty list of items of the type <code>T</code>. */
class ConsLo<T> implements ILo<T>{
    /** the first item in this data set */
    private T first;

    /** the rest of this data set */
    private ILo<T> rest;

    /** The full constructor
     *
     * @param first the first item in this list
     * @param rest the rest of this list
     */
    public ConsLo(T first, ILo<T> rest){
        this.first = first;
        this.rest = rest;
    }


    /** Produce true if this {@link Traversal Traversal} represents an
     * empty dataset
     * 
     * @return true if the dataset is empty
     */
    public boolean isEmpty(){
        return false;
    }

    /** Produce the first element in the dataset represented by this
     * {@link Traversal Traversal}. Throws
     * <code>IllegalUseOfTraversalException</code> if the dataset is
     * empty.
     * 
     * @return the first element if available -- otherwise throws
     * <code>IllegalUseOfTraversalException</code>
     */
    public T getFirst(){ return this.first; }

    /** Produce a {@link Traversal Traversal} for the rest of the
     * dataset. Throws <code>IllegalUseOfTraversalException</code> if
     * the dataset is empty.
     * 
     * @return the {@link Traversal Traversal} for the rest of this
     * dataset if available - otherwise throws
     * <code>IllegalUseOfTraversalException</code>
     */
    public Traversal<T> getRest(){ return this.rest; }
}