/**
 * Array-based implementation of the queue.
 * @author Mark Allen Weiss
 **/
public class QueueAr
{

  /*@ spec_public */ private Object [ ] theArray;
  /*@ invariant theArray.owner == this; */
  /*@ invariant \typeof(theArray) == \type(java.lang.Object[]); */
  /*@ spec_public */ private int        currentSize;
  /*@ spec_public */ private int        front;
  /*@ spec_public */ private int        back;
  
  /**
   * Construct the queue.
   **/
  public QueueAr( int capacity )
  {
    theArray = new Object[ capacity ];
    currentSize = 0;
    front = 0;
    back = theArray.length - 1;
    /*@ set theArray.owner = this; */
  }

  /**
   * Test if the queue is logically empty.
   * @return true if empty, false otherwise.
   **/
  public boolean isEmpty( )
  {
    return currentSize == 0;
  }

  /**
   * Test if the queue is logically full.
   * @return true if full, false otherwise.
   **/
  public boolean isFull( )
  {
    return currentSize == theArray.length;
  }

  /**
   * Make the queue logically empty.
   **/
  public void makeEmpty( )
  {
    currentSize = 0;
    front = 0;
    back = theArray.length - 1;
    for (int i = 0; i < theArray.length; i++){
      theArray[i] = null;
    }
  }

  /**
   * Get the least recently inserted item in the queue.
   * Does not alter the queue.
   * @return the least recently inserted item in the queue, or null, if empty.
   **/
  public Object getFront( )
  {
    if( isEmpty( ) )
      return null;
    return theArray[ front ];
  }

  /**
   * Return and remove the least recently inserted item from the queue.
   * @return the least recently inserted item in the queue, or null, if empty.
   **/
  public Object dequeue( )
  {
    if( isEmpty( ) )
      return null;
    currentSize--;

    Object frontItem = theArray[ front ];
    theArray[ front ] = null;
    if ( ++front == theArray.length )
      front = 0;
    return frontItem;
  }

  /**
   * Insert a new item into the queue.
   * @param x the item to insert.
   * @exception Overflow if queue is full.
   **/
  public void enqueue( Object x ) throws RuntimeException
  {
    if( isFull( ) )
      throw new RuntimeException( "Overflow" );
    if ( ++back == theArray.length )
      back = 0;
    theArray[ back ] = x;
    currentSize++;
  }

}