import java.util.Iterator;

// Class: OrderedRecLL
//
// Author:  pcutter
//      with assistance from:  people who helped (including instructor/TAs)
//
// Created on Oct 14, 2008
// Modifications:
//    Date      Name     Reason
//    ----      ----     ------
//    Oct. 11, '07  Nathan Sprague  Updates for Fall 09
//

/**
 *  A one-sentence description of the role or purpose of objects
 *  of this class goes here.
 *
 *  A  more detailed description goes here, if necessary.
 *
 *  @author pcutter
 *  @author Your_Partner
 *  @version Oct 14, 2008
 */
public class OrderedRecLL<T> implements CS210OrderedListADT<T>
{
    // instance variables
    private T data;
    private OrderedRecLL<T> restOfList;

    // constructors
    public OrderedRecLL()
    {
        data = null;
        restOfList = null;
    }
    
    public OrderedRecLL(T newData, OrderedRecLL<T> list)
    {
        data = newData;
        restOfList = list;
    }
    
    /* (non-Javadoc)
     * @see CS210OrderedListADT#add(java.lang.Comparable)
     */
    public void add(T newData)
    {
        throw new UnsupportedOperationException();
    }

    /* (non-Javadoc)
     * @see CS210OrderedListADT#addAll(CS210OrderedListADT)
     */
    public void addAll(CS210OrderedListADT<? extends T> fromList)
    {
        for (T value : fromList)
            add(value);

    }

    /* (non-Javadoc)
     * @see CS210ListADT#clear()
     */
    public void clear()
    {
        data = null;
        restOfList = null;

    }

    /* (non-Javadoc)
     * @see CS210ListADT#contains(java.lang.Object)
     */
    public boolean contains(Object obj)
    {
       throw new UnsupportedOperationException();  
    }

    /* (non-Javadoc)
     * @see CS210ListADT#first()
     */
    public T first()
    {
        return data;
    }

    /** Gets the rest of the list (everything after the head).
     *      @return the rest of the list (which is, itself, a list)
     */
    public OrderedRecLL<T> rest()
    {
        return restOfList;
    }
    
    /* (non-Javadoc)
     * @see CS210ListADT#isEmpty()
     */
    public boolean isEmpty()
    {
        return data == null && restOfList == null;
    }

    /* (non-Javadoc)
     * @see CS210ListADT#iterator()
     */
    public Iterator<T> iterator()
    {
        return new RecLLIterator();
    }

    /* (non-Javadoc)
     * @see CS210ListADT#last()
     */
    public T last()
    {
        throw new UnsupportedOperationException();
    }

    /** Returns this  list -- useful within the nested RecLLIterator class.
     */
    public OrderedRecLL<T> list()
    {
        return this;
    }
   

    private void addLast(T newData)    // private helper method for adding elts to end of list
    {
        throw new UnsupportedOperationException();
    }
    /* (non-Javadoc)
     * @see CS210ListADT#remove(T)
     */
    public boolean remove(T obj)
    {
        throw new UnsupportedOperationException();
    }

    /* (non-Javadoc)
     * @see CS210ListADT#removeAll(CS210ListADT)
     */
    public void removeAll(CS210ListADT<? extends T> fromList)
    {
        throw new UnsupportedOperationException();
    }

    /* (non-Javadoc)
     * @see CS210ListADT#removeFirst()
     */
    public T removeFirst()
    {
        throw new UnsupportedOperationException();
    }

    /* (non-Javadoc)
     * @see CS210ListADT#removeLast()
     */
    public T removeLast()
    {
        throw new UnsupportedOperationException();
    }

    /* (non-Javadoc)
     * @see CS210ListADT#size()
     */
    public int size()
    {
        if (isEmpty())
            return 0;
        else
            return 1 + restOfList.size();
    }

    /* (non-Javadoc)
     * @see java.lang.Object#toString()
     */
    public String toString()
    {
        String internalRep = internalToString();
        if (internalRep == "")
            return "[ ]";
        else 
            return "[" + internalRep + "]";
    }
    
    /* Generates a space-separated string representation of the data 
     * values in this list without any delimiters at the beginning
     * or end.
     */
    protected String internalToString()
    {
        if (isEmpty())
            return "";
        else if (rest().isEmpty())
            return first().toString();
        else 
            return first().toString() + ", " + rest().internalToString();
    }
    
    /* (non-Javadoc)
     * @see java.lang.Object#equals(java.lang.Object)
     */
    public boolean equals(Object o)
    {
        // Make sure that we are comparing two OrderedRecLL lists.
        if ( ! (o instanceof OrderedRecLL) )
            return false;
        OrderedRecLL other = (OrderedRecLL) o;

        // If both lists are empty, they are equal.
        if ( isEmpty() && other.isEmpty() )
            return true;

        // At least one list is not empty;
        // if the other is empty, they are not equal.
        if ( isEmpty() || other.isEmpty() )
            return false;
        
        // Lists are equal they contain the same elements.
        if (!first().equals(other.first()))
            return false;
        else return rest().equals(other.rest());
    }

    /**
     *  A <code>RecLLIterator</code> object 
     *  steps through the elements in an OrderedRecLLSolution list.
     */
    private class RecLLIterator implements Iterator<T>
    {
        private OrderedRecLL<T> lastReturned;  // the last list/sublist returned
        private OrderedRecLL<T> oneBeforeLastReturned;  // the list pointing to lastReturned

      // RecLLIterator constructor

        RecLLIterator()
        {
            lastReturned = null;
            oneBeforeLastReturned = null;
        }

      // RecLLIterator methods

        protected OrderedRecLL<T> getNextSublist()
        {
            if ( lastReturned == null )
                return list();
            else
                return lastReturned.rest();
        }

        /* (non-Javadoc)
         * @see java.util.Iterator#hasNext()
         */
        public boolean hasNext()
        {
            OrderedRecLL<T> nextSublist = getNextSublist();
            return nextSublist != null && ! nextSublist.isEmpty();
        }

        /* (non-Javadoc)
         * @see java.util.Iterator#next()
         */
        public T next()
        {
            // Get the value to return.
            OrderedRecLL<T> nextSublist = getNextSublist();
            T valueToReturn = nextSublist.first();

            // Update the last one returned and the one before that
            // for possible future calls to remove.
            oneBeforeLastReturned = lastReturned;
            lastReturned = nextSublist;
            return valueToReturn;
        }

        /* (non-Javadoc)
         * @see java.util.Iterator#remove()
         */
        public void remove()
        {
            // Remove the last element to be returned by next.
            // Pre-condition: lastReturned != null

            // If last element to be returned was the first element in
            // the list, use deleteFirst to delete it.
            if ( lastReturned == list() )
                removeFirst();

            // Otherwise, if we know the list node that has a reference
            // to the element to delete, modify it to refer to the next
            // element instead.
            else if ( oneBeforeLastReturned != null )
            {
                oneBeforeLastReturned.restOfList = lastReturned.restOfList;
            }

            // Otherwise, we need to find element before one to remove,
            // probably because lastReturned element was removed.
            else
            {
                oneBeforeLastReturned = list();
                while ( oneBeforeLastReturned.rest() != lastReturned )
                {
                    oneBeforeLastReturned = oneBeforeLastReturned.rest();
                }
                oneBeforeLastReturned.restOfList = lastReturned.restOfList;
            }

            // Make sure method can only be called once per call to next.
            lastReturned = oneBeforeLastReturned = null;
        }
    }
}