/*  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 linked list to store the queue. 
  
    Note:  The handling of errors should be improved.

    H. Conrad Cunningham, 1 November 1996 
                          4 November 1996
*/

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

  // Constructor

    public QueueList(int maxElements)
    /*  Pre:   0 < maxElements
        Post:  initialized new queue instance to have 'maxElements' positions
               and to be empty
    */
    {   if (maxElements <= 0)
        {   System.out.println
	        ("ERROR.  Invalid Queue capacity given: " + maxElements);
	    return;
        }
        capacityQ = maxElements;
    }

  // Mutators

    public void enqueue(Object item)
    /*  Pre:   this queue instance is not full
        Post:  'item' is appended to back of queue
    */
    {   if (full())
        {   System.out.println("ERROR.  Queue full.  Cannot enqueue: " + item);
	    return;
        }
        Node newEl = new Node(item);
        if (empty())
            frontQ = newEl;
	else
            backQ.setNext(newEl);
	backQ = newEl;
	countQ++;
    }

    public void dequeue()
    /*  Pre:   this queue instance is not empty
        Post:  the front element is removed from this queue 
    */
    {   if (empty())
	{    System.out.println("ERROR.  Queue empty.  Cannot dequeue.");
	     return;
	}
        frontQ = frontQ.getNext();
        countQ--;
    }

  // Accessors

    public Object front()
    /*  Pre:   this queue instance is not empty
        Post:  returns the front element of the queue
    */
    {   if (empty())
	{   System.out.println("ERROR.  Queue empty.  Cannot return front.");
            return null;
	}
        return frontQ.getData();
    }

    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
    */
    {   if (empty())
        {   System.out.println("ERROR.  Queue empty.  Cannot return back.");
	    return null;
        }
        return backQ.getData();
    }

    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);
        if (frontQ != null)
            System.out.println("Queue front    = " + frontQ.getData());
        if (backQ != null)
            System.out.println("Queue back     = " + backQ.getData());
        System.out.println("Queue count    = " + countQ);
	System.out.println("Queue beginning at front is below.");

	for (Node next = frontQ; next != null; next = next.getNext())
	    System.out.println(next.getData());

	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);
        QueueList tq = new QueueList(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,
	    frontQ == front element on this queue instance
	        (null if the queue is empty)
	    backQ == back element on this queue instance
	        (null if the queue is empty)
	    0 < capacityQ == maximum number of elements in this queue instance 
	    countQ == number of elements in this queue instance
    */

    private Node frontQ   = null;
    private Node backQ    = null;
    private int capacityQ = 0;
    private int countQ    = 0;
}


/*  
    Class Node holds one link on a linked list.
*/
class Node
{
    /*  Interface invariant:  This instance holds a non-null data item that
	    is not allowed to change after initialization.  The instance
	    also holds the current next node in a linked list of instances.
    */

  //  Constructors
    public Node(Object item)
    /*  Pre:   true
        Post:  this instance holds object "item"
    */
    {   data = item;
    }

  //  Mutators
    public final void setNext(Node nxt)
    /*  Pre:   true
	Post:  this instance gives node "nxt" as the next node of the list
    */
    {   next = nxt;
    }

  //  Accessors
    public final Object getData()
    /*  Pre:   true
        Post:  returns the data held at this node
    */
    {   return data;
    }

    public final Node getNext()
    /*  Pre:   true
        Post:  returns current next node of the list (null if none)
    */
    {   return next;
    }

  //  Instance variables
    /*  Implementation invariant:  Once intialized correctly,
            data is the object held at this node, not null, does not change.
	    next is the next node of the list.
    */

    private Object data = null;
    private Node next   = null;
}