/*  This class provides an implementation of a bounded capacity queue
    abstract data type (ADT).  A queue is a first-in-first-out (FIFO)
    sequential data structure in which elements are added (enqueued)
    at one end (the back) and elements are removed (dequeued) at the
    other end (the front).

    This implementation uses a circular array buffer to store the queue. 
  
    Author:  H. Conrad Cunningham
    Dates:   version 1, Oct-Nov 1996
             version 2alpha with iContract annotations, 31 Mar 1998
    
*/

/**  
 * @invariant (0 < capacityQ) && (capacityQ == storeQ.length) &&
 *            (0 <= frontQ) && (frontQ < capacityQ) && 
 *            (0 <= backQ) && (backQ < capacityQ) && 
 *            (0 <= countQ) && (countQ <= capacityQ) &&
 *            (backQ == (frontQ + countQ) % capacityQ)
 * // buffer from frontQ to backQ-1 (modulo capacityQ) is actual queue
 */
class Queue
{  
  // Constructor

    /** 
     * @pre  0 < maxElements
     * @post (capacityQ == maxElements) && (storeQ.length == maxElements) &&
     *        empty() 
     */
    public Queue(int maxElements)
    {   storeQ    = new Object[maxElements];
        capacityQ = maxElements;
    }

  // Mutators

    /**
     * @pre !full()
     * @post TEST_back().equals(item)
     * // one item added at back, rest unchanged
     */
    public void enqueue(Object item)
    {   storeQ[backQ] = item;
	backQ = (backQ + 1) % capacityQ;
	countQ++;
    }

    /** 
     * @pre !empty()
     * @post (countQ == (countQ)@pre - 1) && (backQ == (backQ)@pre)
     * // one item removed from front, rest unchanged
     */
    public void dequeue()
    {   storeQ[frontQ] = null;
	frontQ = (frontQ + 1) % capacityQ;
        countQ--;
    }

  // Accessors

    /** 
     * @pre !empty()
     * @post return.equals(storeQ[frontQ])
     */
    public Object front()
    { return storeQ[frontQ];
    }

    /** 
     * @post return == (length() == capacityQ())
     */
    public boolean full()
    {   return (countQ == capacityQ);
    }

    /** 
     * @post  return == (length() == 0)
     */
    public boolean empty()
    {   return (countQ == 0);
    }

    /** 
     * @post  return == capacityQ
     */
    public int capacity()
    {   return capacityQ;
    }

    /** 
     * @post return == countQ
     */
    public int length()
    {   return countQ;
    }

  //  Methods for testing

    /** 
     * @pre !empty()
     * @post  return.equals(storeQ[backQ+capacityQ-1)%capacityQ])
     */ 
    public Object TEST_back()
    {   return storeQ[(backQ+capacityQ-1)%capacityQ];
    }

    /* 
     * prints the internal data representation to standard output
     */
    public void TEST_print()
    {   System.out.println("-----------------------------------");
        System.out.println("Queue capacity = " + capacityQ);
        System.out.println("Queue front    = " + frontQ);
        System.out.println("Queue back     = " + backQ);
        System.out.println("Queue count    = " + countQ);
	System.out.println("Queue beginning at front is below.");

	int i = frontQ;
	for (int j = 0; j != countQ; j++)
	{   System.out.println(i + ": " + storeQ[i]);
            i = (i + 1) % capacityQ;
	}

	System.out.println("Queue ending at back is above.");
        System.out.println("-----------------------------------");
    }

    /* 
       Note:  for testing purposes only
              runs a sequence of tests on the Queue methods
    */
    public static void main(String[] args)
    {   
        int qSize = 3;
        System.out.println("Begin test of Queue with capacity " + qSize);
        Queue tq = new Queue(qSize);

	tq.TEST_print();
	System.out.println("empty?  " + tq.empty());
	System.out.println("full?  " + tq.full());
	System.out.println("capacity is " + tq.capacity());
	System.out.println("length is " + tq.length());

	System.out.println("\nDequeue attempt (should fail)");
	tq.dequeue();
	System.out.println("empty?  " + tq.empty());
	System.out.println("full?  " + tq.full());
	System.out.println("capacity is " + tq.capacity());
	System.out.println("length is " + tq.length());

	System.out.println("\nEnqueue \"First\"");
	tq.enqueue("First");
	System.out.println("empty?  " + tq.empty());
	System.out.println("full?  " + tq.full());
	System.out.println("capacity is " + tq.capacity());
	System.out.println("length is " + tq.length());
	System.out.println("back is \"" + tq.TEST_back() + "\"");
	System.out.println("front is \"" + tq.front() + "\"");
	tq.TEST_print();

	System.out.println("\nEnqueue \"Second\"");
	tq.enqueue("Second");
	System.out.println("empty?  " + tq.empty());
	System.out.println("full?  " + tq.full());
	System.out.println("capacity is " + tq.capacity());
	System.out.println("length is " + tq.length());
	System.out.println("back is \"" + tq.TEST_back() + "\"");
	System.out.println("front is \"" + tq.front() + "\"");

	System.out.println("\nEnqueue \"Third\"");
	tq.enqueue("Third");
	System.out.println("empty?  " + tq.empty());
	System.out.println("full?  " + tq.full());
	System.out.println("capacity is " + tq.capacity());
	System.out.println("length is " + tq.length());
	System.out.println("back is \"" + tq.TEST_back() + "\"");
	System.out.println("front is \"" + tq.front() + "\"");
	tq.TEST_print();

	System.out.println("\nEnqueue \"Fourth\" (should fail)");
	tq.enqueue("Fourth");
	System.out.println("empty?  " + tq.empty());
	System.out.println("full?  " + tq.full());
	System.out.println("capacity is " + tq.capacity());
	System.out.println("length is " + tq.length());
	System.out.println("back is \"" + tq.TEST_back() + "\"");
	System.out.println("front is \"" + tq.front() + "\"");
	tq.TEST_print();

	System.out.println("\nDequeue \"" + tq.front() + "\"");
	tq.dequeue();
	System.out.println("empty?  " + tq.empty());
	System.out.println("full?  " + tq.full());
	System.out.println("capacity is " + tq.capacity());
	System.out.println("length is " + tq.length());
	System.out.println("back is \"" + tq.TEST_back() + "\"");
	System.out.println("front is \"" + tq.front() + "\"");
	tq.TEST_print();

	System.out.println("\nEnqueue \"Fifth\"");
	tq.enqueue("Fifth");
	System.out.println("empty?  " + tq.empty());
	System.out.println("full?  " + tq.full());
	System.out.println("capacity is " + tq.capacity());
	System.out.println("length is " + tq.length());
	System.out.println("back is \"" + tq.TEST_back() + "\"");
	System.out.println("front is \"" + tq.front() + "\"");

	System.out.println("\nDequeue \"" + tq.front() + "\"");
	tq.dequeue();
	System.out.println("empty?  " + tq.empty());
	System.out.println("full?  " + tq.full());
	System.out.println("capacity is " + tq.capacity());
	System.out.println("length is " + tq.length());
	System.out.println("back is \"" + tq.TEST_back() + "\"");
	System.out.println("front is \"" + tq.front() + "\"");


	System.out.println("\nDequeue \"" + tq.front() + "\"");
	tq.dequeue();
	System.out.println("empty?  " + tq.empty());
	System.out.println("full?  " + tq.full());
	System.out.println("capacity is " + tq.capacity());
	System.out.println("length is " + tq.length());
	System.out.println("back is \"" + tq.TEST_back() + "\"");
	System.out.println("front is \"" + tq.front() + "\"");

	System.out.println("\nDequeue \"" + tq.front() + "\"");
	tq.dequeue();
	System.out.println("empty?  " + tq.empty());
	System.out.println("full?  " + tq.full());
	System.out.println("capacity is " + tq.capacity());
	System.out.println("length is " + tq.length());
	tq.TEST_print();
    }
 
  // Instance variables
   
    private Object[] storeQ = null;
    private int capacityQ   = 0;
    private int frontQ      = 0;
    private int backQ       = 0;
    private int countQ      = 0;
}