package prog06;

import java.util.*;

/**
 * Implements the Queue interface using a circular array.
 **/
public class ArrayQueue<E> extends AbstractQueue<E>
        implements Queue<E> {

    // Data Fields
    /** Index of the front of the queue. */
    private int front;
    /** Index of the rear of the queue. */
    private int rear;
    /** Current size of the queue. */
    private int size;
    /** Default capacity of the queue. */
    private static final int DEFAULT_CAPACITY = 10;
    /** Array to hold the items. */
    private E[] theItems;

    // Constructors
    /**
     * Construct a queue with the default initial capacity.
     */
    public ArrayQueue () {
        this(DEFAULT_CAPACITY);
    }

    /**
     * Construct a queue with the specified initial capacity.
     * @param initCapacity The initial capacity
     */
    @SuppressWarnings("unchecked")
    public ArrayQueue (int initCapacity) {
        theItems = (E[]) new Object[initCapacity];
        front = 0;
        rear = theItems.length - 1;
        size = 0;
    }

    // Public Methods
    /**
     * Inserts an item at the rear of the queue.
     * @post item is added to the rear of the queue.
     * @param item The element to add
     * @return true (always successful)
     */
    @Override
    public boolean offer (E item) {
        if (size == theItems.length)
            reallocate();
        size++;
        rear = (rear + 1) % theItems.length;
        theItems[rear] = item;
        return true;
    }

    /**
     * Returns the item at the front of the queue without removing it.
     * @return The item at the front of the queue if successful;
     * return null if the queue is empty
     */
    @Override
    public E peek () {
        if (size == 0)
            return null;
        return theItems[front];
    }

    /**
     * Removes the entry at the front of the queue and returns it
     * if the queue is not empty.
     * @post front references item that was second in the queue.
     * @return The item removed if successful or null if not
     */
    @Override
    public E poll() {
      // EXERCISE 3
    	if(size == 0)
    		return null;
    	else
    	{
    		size--;
    		E frontEntry = theItems[front];
    		front = (front+1)%theItems.length;
    		return frontEntry;
    	}
    }


/**
 * Return the size of the queue
 * @return The number of items in the queue
 */
    @Override
    public int size () {
      return size;
    }
    /**
     * Returns an iterator to the elements in the queue
     * @return an iterator to the elements in the queue
     */
    @Override
    public Iterator<E> iterator () {
      return new Iter();
    }

    // Private Methods
    /**
     * Double the capacity and reallocate the items.
     * @pre The array is filled to capacity.
     * @post The capacity is doubled and the first half of the
     *       expanded array is filled with items.
     */
    @SuppressWarnings("unchecked")
    private void reallocate () {
        int newCapacity = 2 * theItems.length;
        E[] newItems = (E[]) new Object[newCapacity];
        if(front > rear)
        {
        	System.arraycopy(theItems, front, newItems, 0, theItems.length-front);
        	System.arraycopy(theItems, 0, newItems, theItems.length-front, size-theItems.length+front);
        }
        else
        {
        	System.arraycopy(theItems, front, newItems, 0, size);
        }
        front = 0;
        rear = size - 1;
        theItems = newItems;
    }

    private boolean labSolution = false;


    /** Inner class to implement the Iterator<E> interface. */
    private class Iter implements Iterator<E> {
        // Data Fields

        // Index of next element */
        private int index;

        // Count of elements accessed so far */
        private int count = 0;


        // Methods
        // Constructor
        /**
         * Initializes the Iter object to reference the
         * first queue element.
         */
        public Iter ()
        {
        	if (labSolution) {
                index = front;
              }
              else
              {
            	  if(size == 0)
            		  index = -1;
            	  else
            		  index = front;
              }
        }

        /**
         * Returns true if there are more elements in the queue to access.
         * @return true if there are more elements in the queue to access.
         */
        @Override
        public boolean hasNext () {
            if (labSolution)
              return count < size;
            else {
              // EXERCISE
              return !(index == -1);
            }
          }
        /**
         * Returns the next element in the queue.
         * @pre index references the next element to access.
         * @post index and count are incremented.
         * @return The element with subscript index
         */
        @Override
        public E next () {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            E returnValue = theItems[index];
            if (labSolution) {
              index = (index + 1) % theItems.length;
              count++;
            }
            else {
              // EXERCISE
            	if(index == rear)
            		index = -1;
            	else
            	index++;
            }
            return returnValue;
        }

        /**
         * Remove the item accessed by the Iter object -- not implemented.
         * @throws UnsupportedOperationException when called
         */
        @Override
        public void remove () {
            throw new UnsupportedOperationException();
        }
    }
}







package prog06;
import java.util.*;

public class Main {
  public static void main (String[] args) {
    System.out.println("ArrayQueue");
    test(new ArrayQueue<Integer>());
   // System.out.println("LinkedQueue");
   // test(new LinkedQueue<Integer>());

   // WordGame game = new WordGame();
  }

  static void test (Queue<Integer> queue) {
    for (int i = 0; i < 5; i++)
      queue.offer(i);
    System.out.println(queue);
    for (int i = 5; i < 15; i++) {
      System.out.println(queue.poll());
      queue.offer(i);
      System.out.println(queue);
    }
    for (int i = 15; i < 25; i++)
      queue.offer(i);
    System.out.println(queue);
  }
}