/**************************************************************************************
***************************************************************************************
				Übungsblatt 9, Aufgabe 5
		Gruppe: Madlen Frieseke, Carsten Kötter, Erik Streb

   28. Juni 2002
   class Deque von Erik Streb basierend auf der class Queue von H. Conrad
   Cunningham. Heruntergeladen auf:
   http://www.cs.olemiss.edu/~hcc/java_examples/Queue.java
   
   Ich denke es ist erlaubt einen vorhandenen Quelltext zu erweitern. Immerhin
   musste ich auch alles lesen und verstehen, um es zu erweitern. Ich habe mir
   dadurch lediglich einiges an Tipparbeit gespart. Falls das nicht erlaubt
   sein sollte, werde ich nächstes mal eben noch die englischen Kommentare
   entfernen/übersetzen und die Bennungen ändern, was aber im Prinzip keinen
   Unterschied machen würde, außer, dass man dann nicht mehr weiß, ob ich
   komplett alles selber geschrieben habe, oder nicht.   

   Kommentare leider gemischt deutsch und englisch. War mir zu viel Arbeit dies
   jetzt schön zu übersetzen. Ich hoffe es ist trotzdem verständlich. Außerdem
   sieht man dadurch einigermaßen, wer was geschrieben hat. Sprich: Alles, was
   deutsch kommentiert ist, ist neu.
   
   Nachfolgend der Originalkommentar von H. Conrad Cunningham:

      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 Deque
{   
  // Instance variables
   
    /*      0 < capacityQ == storeQ.size &&
	    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 putRear
    private int countQ      = 0;     // current number of elements in queue

  // Constructor

    public Deque(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 putFront(Object item)  // ist neu hinzu gekommen für class Deque
    /*  Pre:   this queue instance is not full
        Post:  'item' is appended to front of queue
	Error: if precondition not satisfied, queue left unchanged
    */
    {   if (isFull())
        {   System.out.println("ERROR.  Queue full.  Cannot putFront: " + item);
	    return;
        }
        storeQ[(frontQ+capacityQ-1)%capacityQ] = item;
	frontQ = (frontQ+capacityQ-1)%capacityQ;
	countQ++;
    }

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

    public void removeFront() // hieß vorher 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 (isEmpty())
	{    System.out.println("ERROR.  Queue empty.  Cannot removeFront.");
	     return;
	}
        storeQ[frontQ] = null;
	frontQ = (frontQ + 1) % capacityQ;
        countQ--;
    }

    public void removeRear() // ist neu hinzu gekommen für class Deque
    /*  Pre:   this queue instance is not empty
        Post:  the back element is removed from this queue 
	Error: if precondition not satisfied, queue left unchanged
    */
    {   if (isEmpty())
	{    System.out.println("ERROR.  Queue empty.  Cannot removeRear.");
	     return;
	}
        storeQ[(backQ+capacityQ-1)%capacityQ] = null;
	backQ = (backQ+capacityQ-1)%capacityQ;
        countQ--;
    }

  // Accessors

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

    public Object getRearElement()  // ist neu hinzu gekommen für class Deque
    /*  Pre:   this queue instance is not empty
        Post:  returns the back element of the queue
	Error: if precondition not satisfied, null returned
    */
    {   if (isEmpty())
	{   System.out.println("ERROR.  Queue empty.  Cannot return back.");
            return null;
	}
        return storeQ[(backQ+capacityQ-1)%capacityQ];
    }

    public boolean isFull()  // hieß vorher 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 isEmpty()
    /*  Pre:   true
        Post:  returns true if and only if there are no elements in this 
               queue instance
    */
    {   return (countQ == 0);
    }

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

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

  //  Methods for testing

    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)
    /*  Test verändert und erweitert, um die neuen Methoden der class Deque zu
        testen
    */
     
    /*  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);
        Deque tq = new Deque(qSize);

	tq.TEST_print();
	System.out.println("empty?  " + tq.isEmpty());
	System.out.println("full?  " + tq.isFull());
	System.out.println("capacity is " + tq.getCapacity());
	System.out.println("size is " + tq.size());

	System.out.println("\nremoveFront attempt (should fail)");
	tq.removeFront();
	System.out.println("empty?  " + tq.isEmpty());
	System.out.println("full?  " + tq.isFull());
	System.out.println("capacity is " + tq.getCapacity());
	System.out.println("size is " + tq.size());

	System.out.println("\nputRear \"First\"");
	tq.putRear("First");
	System.out.println("empty?  " + tq.isEmpty());
	System.out.println("full?  " + tq.isFull());
	System.out.println("capacity is " + tq.getCapacity());
	System.out.println("size is " + tq.size());
	System.out.println("back is \"" + tq.getRearElement() + "\"");
	System.out.println("front is \"" + tq.getFrontElement() + "\"");
	tq.TEST_print();

	System.out.println("\nputRear \"Second\"");
	tq.putRear("Second");
	System.out.println("empty?  " + tq.isEmpty());
	System.out.println("full?  " + tq.isFull());
	System.out.println("capacity is " + tq.getCapacity());
	System.out.println("size is " + tq.size());
	System.out.println("back is \"" + tq.getRearElement() + "\"");
	System.out.println("front is \"" + tq.getFrontElement() + "\"");

	System.out.println("\nputRear \"Third\"");
	tq.putRear("Third");
	System.out.println("empty?  " + tq.isEmpty());
	System.out.println("full?  " + tq.isFull());
	System.out.println("capacity is " + tq.getCapacity());
	System.out.println("size is " + tq.size());
	System.out.println("back is \"" + tq.getRearElement() + "\"");
	System.out.println("front is \"" + tq.getFrontElement() + "\"");
	tq.TEST_print();

	System.out.println("\nputRear \"Fourth\" (should fail)");
	tq.putRear("Fourth");
	System.out.println("empty?  " + tq.isEmpty());
	System.out.println("full?  " + tq.isFull());
	System.out.println("capacity is " + tq.getCapacity());
	System.out.println("size is " + tq.size());
	System.out.println("back is \"" + tq.getRearElement() + "\"");
	System.out.println("front is \"" + tq.getFrontElement() + "\"");
	tq.TEST_print();

	System.out.println("\nremoveFront \"" + tq.getFrontElement() + "\"");
	tq.removeFront();
	System.out.println("empty?  " + tq.isEmpty());
	System.out.println("full?  " + tq.isFull());
	System.out.println("capacity is " + tq.getCapacity());
	System.out.println("size is " + tq.size());
	System.out.println("back is \"" + tq.getRearElement() + "\"");
	System.out.println("front is \"" + tq.getFrontElement() + "\"");
	tq.TEST_print();

	System.out.println("\nputRear \"Fifth\"");
	tq.putRear("Fifth");
	System.out.println("empty?  " + tq.isEmpty());
	System.out.println("full?  " + tq.isFull());
	System.out.println("capacity is " + tq.getCapacity());
	System.out.println("size is " + tq.size());
	System.out.println("back is \"" + tq.getRearElement() + "\"");
	System.out.println("front is \"" + tq.getFrontElement() + "\"");

	System.out.println("\nremoveRear \"" + tq.getRearElement() + "\"");
	tq.removeRear();
	System.out.println("empty?  " + tq.isEmpty());
	System.out.println("full?  " + tq.isFull());
	System.out.println("capacity is " + tq.getCapacity());
	System.out.println("size is " + tq.size());
	System.out.println("back is \"" + tq.getRearElement() + "\"");
	System.out.println("front is \"" + tq.getFrontElement() + "\"");

	System.out.println("\nputRear \"Sixth\"");
	tq.putRear("Sixth");
	System.out.println("empty?  " + tq.isEmpty());
	System.out.println("full?  " + tq.isFull());
	System.out.println("capacity is " + tq.getCapacity());
	System.out.println("size is " + tq.size());
	System.out.println("back is \"" + tq.getRearElement() + "\"");
	System.out.println("front is \"" + tq.getFrontElement() + "\"");

	System.out.println("\nputFront \"Seventh\" (should fail)");
	tq.putFront("Seventh");
	System.out.println("empty?  " + tq.isEmpty());
	System.out.println("full?  " + tq.isFull());
	System.out.println("capacity is " + tq.getCapacity());
	System.out.println("size is " + tq.size());
	System.out.println("back is \"" + tq.getRearElement() + "\"");
	System.out.println("front is \"" + tq.getFrontElement() + "\"");
	tq.TEST_print();

	System.out.println("\nremoveFront \"" + tq.getFrontElement() + "\"");
	tq.removeFront();
	System.out.println("empty?  " + tq.isEmpty());
	System.out.println("full?  " + tq.isFull());
	System.out.println("capacity is " + tq.getCapacity());
	System.out.println("size is " + tq.size());
	System.out.println("back is \"" + tq.getRearElement() + "\"");
	System.out.println("front is \"" + tq.getFrontElement() + "\"");

	System.out.println("\nremoveRear \"" + tq.getRearElement() + "\"");
	tq.removeRear();
	System.out.println("empty?  " + tq.isEmpty());
	System.out.println("full?  " + tq.isFull());
	System.out.println("capacity is " + tq.getCapacity());
	System.out.println("size is " + tq.size());
	System.out.println("back is \"" + tq.getRearElement() + "\"");
	System.out.println("front is \"" + tq.getFrontElement() + "\"");

	System.out.println("\nremoveRear \"" + tq.getRearElement() + "\"");
	tq.removeRear();
	System.out.println("empty?  " + tq.isEmpty());
	System.out.println("full?  " + tq.isFull());
	System.out.println("capacity is " + tq.getCapacity());
	System.out.println("size is " + tq.size());
	tq.TEST_print();
    }
 
}