import java.util.LinkedList;
import java.util.ListIterator;

/**
 *  The CircularLLIterator class provides an iterator through
 *  a linear LinkedList object that makes it appear to be
 *  circular.  The element after the last element in the list,
 *  as returned by <code>next</code>, is the first element in
 *  the list.  The element before the first element in the list,
 *  as returned by <code>previous</code>, is the last element
 *  in the list.
 *
 *  <p>
 *  In a circular iteration, the methods <code>hasNext</code>
 *  and <code>hasPrevious</code> will always return
 *  <code>true</code> unless the list is empty.  This means
 *  that the usual iteration pattern of
 *  <pre>
 *     while (iterator.hasNext())
 *         <em>&lt;do something&gt;</em></pre>
 *  will result in an infinite loop.  To iterate once through
 *  the elements of the list, use the list iterator returned by
 *  the linked list's <code>listIterator</code> method or get
 *  the size of the list and iterate through that many times.
 *  (The latter technique will not work if you are adding or
 *  removing elements as you iterate.)
 *
 *  @author Alyce Brady, Nathan Sprague (Changed to use generics)
 *  @version 7 October 2009
 *  @see LinkedList
 **/
public class CircularLLIterator<E> implements ListIterator<E>
{
    private LinkedList<E> list;
    private ListIterator<E> internalIterator;

    /** Constructs a circular iterator for the specified list.
     *      @param list the linked list through which to iterate
     **/
    public CircularLLIterator(LinkedList<E> list)
    {
        this.list = list;
        internalIterator = list.listIterator(0);
    }

    /** Returns <code>true</code> if this list iterator has more elements 
     *  when traversing the list in the forward direction. (In other words, 
     *  returns <code>true</code> if <code>next</code> would return an 
     *  element rather than throwing an exception.)  Since this is a
     *  circular iterator, returns <code>true</code> unless the list is
     *  empty.
     *      @return <code>true</code> if the list iterator has more elements
     *              when traversing the list in the forward direction
     **/
    public boolean hasNext()
    {
        return list.size() != 0; 
    }

    /** Returns <code>true</code> if this list iterator has more elements 
     *  when traversing the list in the reverse direction. (In other words, 
     *  returns <code>true</code> if <code>previous</code> would return an 
     *  element rather than throwing an exception.)  Since this is a
     *  circular iterator, returns <code>true</code> unless the list is
     *  empty.
     *      @return <code>true</code> if the list iterator has more elements
     *              when traversing the list in the reverse direction
     **/
    public boolean hasPrevious()
    {
        return list.size() != 0; 
    }

    /** Returns the index of the element that would be returned by a
     *  subsequent call to <code>next</code>. (Returns list size if the 
     *  list is empty.)
     **/
    public int nextIndex()
    {
        if ( internalIterator.hasNext() )
            return internalIterator.nextIndex();
        else
            return 0;
    }

    /** Returns the index of the element that would be returned by a
     *  subsequent call to <code>previous</code>. (Returns -1 if the 
     *  list is empty.)
     **/
    public int previousIndex()
    {
        if ( list.size() == 0 )
            return -1;

        if ( internalIterator.hasPrevious() )
            return internalIterator.previousIndex();
        else
            return list.size() - 1;
    }

    /** Returns the next element in the list. This method may be called 
     *  repeatedly to iterate through the list, or intermixed with calls
     *  to <code>previous</code> to go back and forth. (Note that 
     *  alternating calls to <code>next</code> and <code>previous</code> 
     *  will return the same element repeatedly.)
     *      @return the next element in the list
     *      @throws NoSuchElementException if the list is empty
     **/
    public E next()
    {
        if ( list.size() == 0 )
            return null;

        if ( internalIterator.hasNext() )
            return internalIterator.next();
        else
        {
            internalIterator = list.listIterator(0);
            return internalIterator.next();
        }
    }

    /** Returns the previous element in the list. This method may be called 
     *  repeatedly to iterate through the list backwards, or intermixed with
     *  calls to <code>next</code> to go back and forth. (Note that 
     *  alternating calls to <code>next</code> and <code>previous</code> 
     *  will return the same element repeatedly.)
     *      @return the previous element in the list
     *      @throws NoSuchElementException if the list is empty
     **/
    public E previous()
    {
        if ( list.size() == 0 )
            return null;

        if ( internalIterator.hasPrevious() )
            return internalIterator.previous();
        else
        {
            internalIterator = list.listIterator(list.size());
            E obj = internalIterator.previous();
            return obj;
        }
    }

    /** Inserts the specified element into the list. The element is inserted
     *  immediately before the next element that would be returned by 
     *  <code>next</code>, if any, and after the next element that would be 
     *  returned by <code>previous</code>, if any. (If the list contains no 
     *  elements, the new element becomes the sole element on the list.)
     *  The new element is inserted before the implicit cursor: a subsequent
     *  call to <code>next</code> would be unaffected, and a subsequent call
     *  to <code>previous</code> would return the new element. (This call
     *  increases by one the value that would be returned by a call to
     *  <code>nextIndex</code> or <code>previousIndex</code>.)
     *      @param obj the element to insert
     **/
    public void add(E obj)
    {
        internalIterator.add(obj);
    }

    /** Removes from the list the last element that was returned by
     *  <code>next</code> or <code>previous</code>. This call can only
     *  be made once per call to <code>next</code> or <code>previous</code>.
     *  It can be made only if <code>ListIterator.add</code> has not been
     *  called after the last call to <code>next</code> or
     *  <code>previous</code>.
     *      @throws IllegalStateException neither <code>next</code> nor 
     *              <code>previous</code> have been called, or
     *              <code>remove</code> or <code>add</code> have been called
     *              after the last call to <code>next</code> or
     *              <code>previous</code>
     **/
    public void remove()
    {
        internalIterator.remove();
    }

    /** Replaces the last element returned by <code>next</code> or
     *  <code>previous</code> with the specified element. This call
     *  can be made only if neither <code>ListIterator.remove</code>
     *  nor <code>ListIterator.add</code> have been called after the
     *  last call to <code>next</code> or <code>previous</code>.
     *      @param obj the element with which to replace the last element
     *                 returned by <code>next</code> or <code>previous</code>
     **/
    public void set(E obj)
    {
        internalIterator.set(obj);
    }

//    /** Runs test suite for the <code>CircularLLIterator</code> class.
//     *      @param args  standard parameter; not used
//     **/
//    public static void main(String[] args)
//    {
//        int val;
//
//        // Test cases for an empty list.
//        LinkedList emptyList = new LinkedList();
//        CircularLLIterator emptyIt = new CircularLLIterator(emptyList);
//        executeTest("emptyIt.hasNext()", emptyIt.hasNext(), false);
//        executeTest("emptyIt.hasPrevious()", emptyIt.hasNext(), false);
//
//        // Test cases for a list with one element.
//        LinkedList singleEltList = new LinkedList();
//        singleEltList.add(new Integer(1));
//        CircularLLIterator singleEltIt = new CircularLLIterator(singleEltList);
//        // test calls to hasNext, next from beginning of list
//        executeTest("1st call to singleEltIt.hasNext()", singleEltIt.hasNext(), true);
//        executeTest("1st call to singleEltIt.nextIndex()", singleEltIt.nextIndex(), 0);
//        val = ((Integer)singleEltIt.next()).intValue();
//        executeTest("first call to singleEltIt.next()", val, 1);
//        // test calls to hasNext, next from end of list; should wrap around
//        executeTest("call to hasNext from end of list", singleEltIt.hasNext(), true);
//        executeTest("call to nextIndex from end of list", singleEltIt.nextIndex(), 0);
//        val = ((Integer)singleEltIt.next()).intValue();
//        executeTest("call to next from end of list should wrap to 1st element", val, 1);
//        // test calls to hasPrevious, previous from beginning of list; should wrap
//        singleEltIt = new CircularLLIterator(singleEltList);
//        executeTest("call to hasPrevious from beginning of list", singleEltIt.hasPrevious(), true);
//        executeTest("call to previousIndex from beginning of list", singleEltIt.previousIndex(), 0);
//        val = ((Integer)singleEltIt.previous()).intValue();
//        executeTest("first call to singleEltIt.previous() should wrap", val, 1);
//        // second calls to hasPrevious, previous are also from beginning of list; should wrap
//        executeTest("2nd call to singleEltIt.hasPrevious()", singleEltIt.hasPrevious(), true);
//        executeTest("2nd call to singleEltIt.previousIndex()", singleEltIt.previousIndex(), 0);
//        val = ((Integer)singleEltIt.previous()).intValue();
//        executeTest("second call to singleEltIt.previous() should wrap", val, 1);
//        // test calls to hasPrevious, previous from end of list, via next
//        singleEltIt = new CircularLLIterator(singleEltList);
//        val = ((Integer)singleEltIt.next()).intValue();
//        executeTest("call to hasPrevious from end of list", singleEltIt.hasPrevious(), true);
//        executeTest("call to previousIndex from end of list", singleEltIt.previousIndex(), 0);
//        val = ((Integer)singleEltIt.previous()).intValue();
//        executeTest("call to previous from end of list, last element", val, 1);
//        // test calls to hasNext, next from beginning of list, via previous
//        singleEltIt = new CircularLLIterator(singleEltList);
//        val = ((Integer)singleEltIt.previous()).intValue();
//        executeTest("call to singleEltIt.hasNext() after previous", singleEltIt.hasNext(), true);
//        executeTest("call to singleEltIt.nextIndex() after previous", singleEltIt.nextIndex(), 0);
//        val = ((Integer)singleEltIt.next()).intValue();
//        executeTest("call to singleEltIt.next() after previous", val, 1);
//
//        // Test cases for a list with two elements.  Note: calls to next will
//        // never leave us at the beginning of the list, and calls to previous
//        // will never leave us at the end.
//        LinkedList twoEltList = new LinkedList();
//        twoEltList.add(new Integer(1));
//        twoEltList.add(new Integer(2));
//        // test calls to hasNext, next from beginning of list
//        CircularLLIterator twoEltIt = new CircularLLIterator(twoEltList);
//        executeTest("1st call to twoEltIt.hasNext()", twoEltIt.hasNext(), true);
//        executeTest("1st call to twoEltIt.nextIndex()", twoEltIt.nextIndex(), 0);
//        val = ((Integer)twoEltIt.next()).intValue();
//        executeTest("first call to twoEltIt.next()", val, 1);
//        // test calls to hasNext, next from middle of list
//        executeTest("2nd call to twoEltIt.hasNext()", twoEltIt.hasNext(), true);
//        executeTest("2nd call to twoEltIt.nextIndex()", twoEltIt.nextIndex(), 1);
//        val = ((Integer)twoEltIt.next()).intValue();
//        executeTest("second call to twoEltIt.next()", val, 2);
//        // test calls to hasNext, next from end of list; should wrap around
//        executeTest("3rd call to twoEltIt.hasNext()", twoEltIt.hasNext(), true);
//        executeTest("3rd call to twoEltIt.nextIndex()", twoEltIt.nextIndex(), 0);
//        val = ((Integer)twoEltIt.next()).intValue();
//        executeTest("third call to twoEltIt.next() should wrap", val, 1);
//        // test calls to hasPrevious, previous from beginning of list; should wrap
//        twoEltIt = new CircularLLIterator(twoEltList);
//        executeTest("1st call to twoEltIt.hasPrevious()", twoEltIt.hasPrevious(), true);
//        executeTest("1st call to twoEltIt.previousIndex()", twoEltIt.previousIndex(), 1);
//        val = ((Integer)twoEltIt.previous()).intValue();
//        executeTest("first call to twoEltIt.previous() should wrap", val, 2);
//        // test calls to hasPrevious, previous from middle of list
//        executeTest("2nd call to twoEltIt.hasPrevious()", twoEltIt.hasPrevious(), true);
//        executeTest("2nd call to twoEltIt.previousIndex()", twoEltIt.previousIndex(), 0);
//        val = ((Integer)twoEltIt.previous()).intValue();
//        executeTest("second call to twoEltIt.previous()", val, 1);
//        // third calls to hasPrevious, previous are also from beginning of list; should wrap
//        executeTest("3rd call to twoEltIt.hasPrevious()", twoEltIt.hasPrevious(), true);
//        executeTest("3rd call to twoEltIt.previousIndex()", twoEltIt.previousIndex(), 1);
//        val = ((Integer)twoEltIt.previous()).intValue();
//        executeTest("third call to twoEltIt.previous() should wrap", val, 2);
//        // test calls to hasPrevious, previous from middle of list, via next
//        twoEltIt = new CircularLLIterator(twoEltList);
//        val = ((Integer)twoEltIt.next()).intValue();
//        executeTest("twoElt: next, hasPrevious", twoEltIt.hasPrevious(), true);
//        executeTest("twoElt: next, previousIndex", twoEltIt.previousIndex(), 0);
//        val = ((Integer)twoEltIt.previous()).intValue();
//        executeTest("twoElt: next, previous", val, 1);
//        // test calls to hasNext, next from beginning of list, via previous
//        val = ((Integer)twoEltIt.next()).intValue();
//        executeTest("twoElt: next, previous, next", val, 1);
//        // test calls to hasPrevious, previous from end of list, via next
//        twoEltIt = new CircularLLIterator(twoEltList);
//        val = ((Integer)twoEltIt.next()).intValue();
//        val = ((Integer)twoEltIt.next()).intValue();
//        executeTest("twoElt: next, next, hasPrevious", twoEltIt.hasPrevious(), true);
//        executeTest("twoElt: next, next, previousIndex", twoEltIt.previousIndex(), 1);
//        val = ((Integer)twoEltIt.previous()).intValue();
//        executeTest("twoElt: next, next, previous", val, 2);
//        // test calls to hasNext, next from middle of list, via previous
//        val = ((Integer)twoEltIt.next()).intValue();
//        executeTest("twoElt: next, next, previous, next", val, 2);
//
//        // Test adding objects.
//        LinkedList listToModify = (LinkedList) twoEltList.clone();
//        CircularLLIterator addingIt = new CircularLLIterator(listToModify);
//        LinkedList goal = new LinkedList();
//        goal.add(new Integer(4));
//        goal.add(new Integer(0));
//        goal.add(new Integer(1));
//        goal.add(new Integer(12));
//        goal.add(new Integer(2));
//        goal.add(new Integer(3));
//        // add at the beginning, middle, and end of the list
//        addingIt.add(new Integer(0));
//        executeTest("adding elt to index 0", addingIt.previous(), new Integer(0));
//        addingIt.add(new Integer(4));
//        executeTest("adding elt to beginning via previous", addingIt.previous(), new Integer(4));
//        addingIt.next(); // get the 4
//        addingIt.next(); // get the 0
//        addingIt.next(); // get the 1
//        addingIt.add(new Integer(12));
//        executeTest("adding elt to middle via next", addingIt.previous(), new Integer(12));
//        addingIt.next(); // get the 12
//        addingIt.next(); // get the 2
//        addingIt.add(new Integer(3));
//        executeTest("adding elt to end via next", addingIt.previous(), new Integer(3));
//        addingIt.next(); // get the 3
//        executeTest("element after last added elt should be 1st elt", addingIt.next(), new Integer(4));
//        executeTest("after all adds", listToModify, goal);
//
//        // Test setting objects.
//        // set from beginning, middle, and end of the list
//        ListIterator goalIt = goal.listIterator();
//        goalIt.next();
//        goalIt.set(new Integer(-4));
//        goalIt = goal.listIterator(goal.size());
//        goalIt.previous(); // gets the 3
//        goalIt.set(new Integer(-3));
//        // addingIt has most recently gotten the 4 from next
//        addingIt.set(new Integer(-4));
//        addingIt.previous(); // gets the -4
//        addingIt.previous(); // gets the 3
//        addingIt.set(new Integer(-3));
//        executeTest("after all sets", listToModify, goal);
//
//        // Test removing objects.
//        // remove from beginning, middle, and end of the list
//        addingIt.remove(); // removes -3
//        addingIt.next(); // get the -4
//        addingIt.remove();
//        addingIt.previous(); // get the 2
//        addingIt.previous(); // get the 12
//        addingIt.remove();
//        addingIt.previous(); // get the 1
//        addingIt.previous(); // get the 0
//        addingIt.remove();
//        executeTest("after all removes", listToModify, twoEltList);
//    }
//
//    private static void executeTest(String testDescription, 
//        boolean actualValue, boolean expectedValue)
//    {
//        System.out.print("Testing: " + testDescription + ";");
//        System.out.print("  expected value = " + expectedValue);
//        System.out.print("; actual = " + actualValue + "; ");
//        if ( actualValue == expectedValue )
//            System.out.println("OK");
//        else
//            System.out.println("ERROR !!!");
//    }
//
//    private static void executeTest(String testDescription, 
//        int actualValue, int expectedValue)
//    {
//        System.out.print("Testing: " + testDescription + ";");
//        System.out.print("  expected value = " + expectedValue);
//        System.out.print("; actual = " + actualValue + "; ");
//        if ( actualValue == expectedValue )
//            System.out.println("OK");
//        else
//            System.out.println("ERROR !!!");
//    }
//
//    private static void executeTest(String testDescription, 
//        Object actualValue, Object expectedValue)
//    {
//        System.out.print("Testing: " + testDescription + ";");
//        System.out.print("  expected value = " + expectedValue);
//        System.out.print("; actual = " + actualValue + "; ");
//        if ( actualValue.equals(expectedValue) )
//            System.out.println("OK");
//        else
//            System.out.println("ERROR !!!");
//    }
}