import java.util.Iterator;
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
 *  @version 13 October 2002
 *  @see LinkedList
 **/
public class CircularLLIterator implements ListIterator
{
    private LinkedList list;
    private ListIterator internalIterator;

    /** Constructs a circular iterator for the specified list.
     *      @param list the linked list through which to iterate
     **/
    public CircularLLIterator(LinkedList 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 Object 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 Object previous()
    {
        if ( list.size() == 0 )
            return null;

        if ( internalIterator.hasPrevious() )
            return internalIterator.previous();
        else
        {
            internalIterator = list.listIterator(list.size());
            Object 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(Object 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(Object 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 !!!");
    }
}