import java.util.Arrays;
import java.util.Iterator;
import java.util.ListIterator;
import java.util.NoSuchElementException;
/**
   A class that implements the ADT list by using a resizable array.
   The list has entries that are numbered beginning at 1.
   The list has an iterator that implements the interface ListIterator.
   Iterator positions (indexes) are numbered beginning at 0.
   
   @author Frank M. Carrano
   @author Timothy M. Henry
   @version 4.0
*/
public class ArrayListWithListIterator<T>
             implements ListWithListIteratorInterface<T>
{
   private T[] list;  // Array of list entries; ignore list[0]
   private int numberOfEntries; 
   private boolean initialized = false;
   private static final int DEFAULT_CAPACITY = 25;
	private static final int MAX_CAPACITY = 10000;

   public ArrayListWithListIterator()
   {
      this(DEFAULT_CAPACITY);
   } // end default constructor

   public ArrayListWithListIterator(int initialCapacity)
   {
      // Is initialCapacity too small?
      if (initialCapacity < DEFAULT_CAPACITY)
         initialCapacity = DEFAULT_CAPACITY;
      else // Is initialCapacity too big?
         checkCapacity(initialCapacity);
      
      // The cast is safe because the new array contains null entries
      @SuppressWarnings("unchecked")
      T[] tempList = (T[])new Object[initialCapacity + 1];
      list = tempList;
      numberOfEntries = 0;
      initialized = true;
   } // end constructor
  
   /* < Implementations of the methods of the ADT list go here;
        you can see them in Chapter 13, beginning at Segment 13.5. */
   
   public ListIterator<T> getIterator()
   {
      return new ListIteratorForArrayList();
   } // end getIterator
   
   public Iterator<T> iterator()
   {
      return getIterator();
   } // end iterator
   
   // 15.24
   private enum Move {NEXT, PREVIOUS}
   // 15.24
   private class ListIteratorForArrayList implements ListIterator<T>
   {
      private int     nextIndex;   // Index of next entry in the iteration
      private boolean isRemoveOrSetLegal;
      private Move    lastMove;
      
      private ListIteratorForArrayList()
      {
         nextIndex = 1;            // Iteration begins at list's first entry
         isRemoveOrSetLegal = false;
         lastMove = null;
      } // end default constructor
      
      // 15.25
      public boolean hasNext()
      {
         return nextIndex <= numberOfEntries;
      } // end hasNext
      
      // 15.26
      public T next()
		{
         if (hasNext())
         {
            lastMove = Move.NEXT;
            isRemoveOrSetLegal = true;

            T nextEntry = list[nextIndex];
            nextIndex++; // Advance iterator

            return nextEntry;
         }
         else
            throw new NoSuchElementException("Illegal call to next(); " +
                                             "iterator is after end of list.");
		} // end next
		
      // 15.27
		public boolean hasPrevious()
		{
		   return (nextIndex > 1) && (nextIndex <= numberOfEntries + 1);
		} // end hasPrevious
		
      // 15.27
		public T previous()
		{
         if (hasPrevious())
         {
            lastMove = Move.PREVIOUS;
            isRemoveOrSetLegal = true;
          
            T previousEntry = list[nextIndex - 1];
            nextIndex--; // Move iterator back
            return previousEntry;
         }
         else
            throw new NoSuchElementException("Illegal call to previous(); " +
                                             "iterator is before beginning of list.");
		} // end previous
      
      // 15.28
		public int nextIndex()
		{
         int result;

         if (hasNext())
            result = nextIndex - 1;   // Change to zero-based numbering of iterator
         else
            result = numberOfEntries; // End-of-list flag

         return result;
		} // end nextIndex
      
      // 15.28
		public int previousIndex()
		{
         int result;

         if (hasPrevious())
            result = nextIndex - 2; // Change to zero-based numbering of iterator
         else
            result = -1;            // Beginning-of-list flag
          
         return result;
		} // end previousIndex
		
      // 15.29
		public void add(T newEntry)
		{
		   isRemoveOrSetLegal = false;
         
         // Insert newEntry immediately before the the iterator's current position
		   ArrayListWithListIterator.this.add(nextIndex, newEntry);
		   nextIndex++;
		} // end add
		
      // 15.30
		public void remove()
		{
			if (isRemoveOrSetLegal)
			{
				isRemoveOrSetLegal = false;
				
            if (lastMove.equals(Move.NEXT))
            { 
               // next() called, but neither add() nor remove() has been 
               // called since.
               
               // Remove entry last returned by next().

               // nextIndex is 1 more than the index of the entry
               // returned by next()
               ArrayListWithListIterator.this.remove(nextIndex - 1);
               nextIndex--; // Move iterator back
            }
            else 
            { 
               // previous() called, but neither add() nor remove() has been 
               // called since
               assert lastMove.equals(Move.PREVIOUS);

               // Remove entry last returned by previous().
               
               // nextIndex is the index of the entry returned by previous().
               ArrayListWithListIterator.this.remove(nextIndex);
			  } // end if
			}
		   else
    		   throw new IllegalStateException("Illegal call to remove(); " +
                                            "next() or previous() not called, OR " +
                                            "add() or remove() called since then.");
		} // end remove
      // 15.31
		public void set(T newEntry)
		{
         if (isRemoveOrSetLegal)
         {
            if (lastMove.equals(Move.NEXT))
            {
               list[nextIndex - 1] = newEntry; // Replace entry last returned by next()
            }
            else 
            {
               assert lastMove.equals(Move.PREVIOUS);
               list[nextIndex] = newEntry; // Replace entry last returned by previous()
            } // end if
         }
         else
            throw new IllegalStateException("Illegal call to set(); " +
                                            "next() or previous() not called, OR " +
                                            "add() or remove() called since then.");
      } // end set		
   } // end ListIteratorForArrayList
} // end ArrayListWithListIterator