/*  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. 
  
    Note:  The handling of errors should be improved (e.g., throw exceptions).

    H. Conrad Cunningham, 30 October - 4 November 1996 
        29 September 1997, documentation corrections
*/

public class Queue
{   /*  Interface Invariant:  once created and intialized properly, 
                              this instance represents a valid queue
    */

  // Constructor

    public Queue(int maxElements)
    /*  Pre:   0 < maxElements
        Post:  initialized new queue instance to have 'maxElements' positions
               and to be empty
        Error: if precondition not satisfied, queue instance is both empty
	       and full.  
    */
    {   if (maxElements <= 0)
        {   System.out.println
	        ("ERROR.  Invalid Queue capacity given: " + maxElements);
	    return;
        }
        storeQ    = new Object[maxElements];
        capacityQ = maxElements;
    }

  // Mutators

    public void enqueue(Object item)
    /*  Pre:   this queue instance is not full
        Post:  'item' is appended to back of queue
	Error: if precondition not satisfied, queue left unchanged
    */
    {   if (full())
        {   System.out.println("ERROR.  Queue full.  Cannot enqueue: " + item);
	    return;
        }
        storeQ[backQ] = item;
	backQ = (backQ + 1) % capacityQ;
	countQ++;
    }

    public void dequeue()
    /*  Pre:   this queue instance is not empty
        Post:  the front element is removed from this queue 
	Error: if precondition not satisfied, queue left unchanged
    */
    {   if (empty())
	{    System.out.println("ERROR.  Queue empty.  Cannot dequeue.");
	     return;
	}
        storeQ[frontQ] = null;
	frontQ = (frontQ + 1) % capacityQ;
        countQ--;
    }

  // Accessors

    public Object front()
    /*  Pre:   this queue instance is not empty
        Post:  returns the front element of the queue
	Error: if precondition not satisfied, null returned
    */
    {   if (empty())
	{   System.out.println("ERROR.  Queue empty.  Cannot return front.");
            return null;
	}
        return storeQ[frontQ];
    }

    public boolean full()
    /*  Pre:   true
        Post:  returns true if and only if no more elements can be added
               to this queue instance
    */
    {   return (countQ == capacityQ);
    }

    public boolean empty()
    /*  Pre:   true
        Post:  returns true if and only if there are no elements in this 
               queue instance
    */
    {   return (countQ == 0);
    }

    public int capacity()
    /*  Pre:   true
        Post:  returns maximum number of elements possible in this queue
              instance
    */
    {   return capacityQ;
    }

    public int length()
    /*  Pre:   true
        Post:  returns the number of elements currently in this queue instance
    */
    {   return countQ;
    }

  //  Methods for testing

    private Object TEST_back()
    /*  Note:  for testing purposes only
        Pre:   this queue instance is not empty
        Post:  returns the back element of the queue
	Error: if precondition not satisfied, null returned
    */
    {   if (empty())
        {   System.out.println("ERROR.  Queue empty.  Cannot return back.");
	    return null;
        }
        return storeQ[(backQ+capacityQ-1)%capacityQ];
    }

    private void TEST_print()
    /*  Note:  for testing purposes only
        Pre:   true
        Post:  prints the internal data representation to standard output
    */
    {   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("-----------------------------------");
    }

    public static void main(String[] args)
    /*  Note:  for testing purposes only
        Pre:   true (command line arguments are not used)
        Post:  runs a sequence of tests on the Queue methods
    */
    {   
        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
   
    /*  Implementation invariant:  Once intialized correctly,
            0 < capacityQ == storeQ.length &&
	    0 <= frontQ < capacityQ && 
            0 <= backQ < capacityQ && 
	    0 <= countQ <= capacityQ &&
            backQ = (frontQ + countQ) % capacityQ &&
            (For all i: 0 <= i < countQ: storeQ[(frontQ+i)%capacityQ]
                is the element at offset i from the front of the queue)
        Error:  On failed initialization, queue is left both empty and full.
    */
    private Object[] storeQ = null;  // storage slots for queue elements
    private int capacityQ   = 0;     // maximum capacity of queue
    private int frontQ      = 0;     // slot holding front element
    private int backQ       = 0;     // slot for next enqueue
    private int countQ      = 0;     // current number of elements in queue
}