/**
 * Collections of elements not supporting iteration.  The technique used
 * for implementation is to put the elements in an array, adding new elements
 * at the end of the array.  When we run off the end of the array, we wrap
 * around to the beginning of the array (assuming, of course, that there is
 * room at the beginning).
 */
public class ArrayBasedQueue
  implements Queue
{
  // +--------+--------------------------------------------------
  // | Fields |
  // +--------+
  
  /** The elements of the queue. */
  protected Object[] elements;
  
  /** The number of elements in the queue. */
  protected int size;
  
  /** The index of the front element. */
  protected int front;
  
  // +--------------+--------------------------------------------
  // | Constructors |
  // +--------------+
  
  /**
   * Build a new queue with a specified capacity.
   */
  public ArrayBasedQueue(int capacity) {
    elements = new Object[capacity];
    size = 0;
    front = 0;
  } // ArrayBasedQueue(int)
  
  /**
   * Build a new queue of default capacity.  (Not generally a good idea
   * unless your queue won't be very large.)
   */
  public ArrayBasedQueue() {
    elements = new Object[10];
    size = 0;
    front = 0;
  } // ArrayBasedQueue()
  
  // +-----------+-----------------------------------------------
  // | Accessors |
  // +-----------+
  
  /**
   * Determine if the queue is full (in which case no more
   * elements can be added).
   * Precondition: The queue is initialized.
   */
  public boolean isFull() {
    return size == elements.length;
  } // isFull()
  
  /**
   * Determine if the queue is empty (in which case no elements
   * can be deleted).
   * Precondition: The queue is initialized.
   * Postcondition: Returns true if the queue is empty, and
   *  false otherwise.
   */
  public boolean isEmpty() {
    return size == 0;
  } // isEmpty()
  
  /**
   * Get the element at the front of the queue.
   * Precondition: The queue is initialized and nonempty.
   * Postcondition: Returns the front of the queue.
   */
  public Object next() {
    return elements[front];
  } // next()
  
  // +-----------+-----------------------------------------------
  // | Modifiers |
  // +-----------+
  
  /**
   * Add an element to the end of the queue.
   * Precondition: The queue is initialized and is not full.
   * Postcondition: The element is added to the end of the queue.
   * Postcondition: The queue grows by one element.
   */
   public void add(Object elt) {
     // If we know where the front is, and we know how many elements
     // are in the queue, we know where the back is.  We move forward
     // size steps from front, we reach the end.  We can use the mod
     // operator (%) to wrap around.
     elements[(front+size)%elements.length] = elt;
     size = size + 1;
   } // add(Object)
   
   /**
    * Delete the first element from the queue.
    * Precondition: The queue is initialized and nonempty.
    * Postcondition: The first element is deleted from the queue.
    * Postcondition: Returns the element deleted.
    * Postcondition: The queue shrinks by one element.
    */
   public Object delete() {
     // Get the front element.
     Object tmp = elements[front];
     // Advance the front, wrapping around when we reach the end.
     front = (front + 1) % elements.length;
     // Decrease the size.
     size = size - 1;
     // Get the front element.
     return tmp;
   } // delete()
   
} // class ArrayBasedQueue