/***************************************************************

 * CarDEQueue.java   -- CS100m-fa05 Project 6

 *

 * An array implementation of a double-ended queue, which is more generalised

 * than a standard queue. Apart from the standard queue operations,

 * it also allows insertion to the front as well as access and removal

 * from the rear.

 *

 *

 * @ TO STUDENTS:

 *

 * The specifications and instructions for the implementation of standard

 * queues also apply to double-ended queues.

 * The header comments in CarQueue.java contains all this information

 * (which you should already have read at this point).

 *

 * The double-ended queue class should have constructors, similar to the

 * two in the standard queue (CarQueue class)

 *

 *   public CarDEQueue(int _capacity)

 *     - Construct a double-ended queue with specified initial capacity.

 *       The queue is initially empty.

 *

 *   public CarDEQueue()

 *     - Construct a queue of default initial capacity DEF_INIT_CAPACITY

 *       (defined in CarQueue class). The queue is initially empty.

 *

 *   Hint: Don't forget the keyword 'super'.

 *

 * In addition to those methods supported by the standard queue,

 * the double-ended queue should support three more public methods:

 *

 *   insertFirst(Car obj)

 *     - Insert obj into the front of the double-ended queue.

 *       e.g. (a, b, c) -- insertFirst(d) --> (d, a, b, c).

 *       Need to double the capacity of the queue when necessary.

 *     - Has no return value.

 *

 *   last()

 *     - Return the last (rear) element, which is an instance of Car.

 *       Queue should be non-empty; otherwise error should be raised.

 *

 *   removeLast()

 *     - Remove the last (rear) element from the DEQueue and return it.

 *       Queue is non-empty or error should be raised. Return value is

 *       an instance of Car.

 *

 * Implement these three methods EXACTLY AS SPECIFIED ABOVE, i.e. same name,

 * parameter types, and return types.

 *

 * The remaining methods (i.e., those of standard queue) should also have exactly

 * the same functionality in double-ended queue, as specified in method

 * comments headers in CarQueue.java.

 * - Hint: You can have them completely for free--if you inherit them from

 *   the CarQueue class by extending it. Remember that every public/protected

 *   variable/method in a class is inherited by its sub-class.

 *

 *

 * Implement the double-ended queue. The name of your class should be

 * CarDEQueue. Yes, for this last project, you will have to

 * write this class by yourself without skeletal code -- something

 * everyone needs to have learnt by the end of this course.

 *

 * Your code should be clean and properly formatted and commented. Messy

 * code will receive a penalty.

 *

 *

 * @ TO GRADERS: Specific way of implementing each method is not unique. Any

 * implementation that conforms to the DEQueue specification is acceptable.

 *

 * @ Yunpeng Li, Nov. 12, 2005

 */





//--------- YOUR CODE BELOW ---------



public class CarDEQueue extends CarQueue {



    // --- Constructors ---



    /* Construct a queue with specified initial capacity.

     */

    public CarDEQueue(int _capacity) {

        super(_capacity);

    }



    /* Construct a queue of default initial capacity DEF_INIT_CAPACITY

     (defined in CarQueue class).

     */

    public CarDEQueue() {

        super();

    }





    // --- Double-ended Queue Methods ---



    /* Insert an element into the front of the double-ended queue.

     e.g. (a, b, c) -- insertFirst(d) --> (d, a, b, c)

      - Need to double the capacity of the queue when necessary.

     */

    public void insertFirst(Car obj) {

        if(size() == capacity) // capacity has been reached

            doubleSize();

        f = ((f - 1) + (capacity + 1)) % (capacity + 1); // update front pointer

        data[f] = obj;  // insert the new object to the front

    }



    /* Return the last (rear) element.

       - Again, queue should be non-empty; otherwise error should be raised

     */

    public Car last() {

        if(isEmpty())

            raiseError("last");

        return data[((r - 1) + (capacity + 1)) % (capacity + 1)];

            /* recall r points to the first empty cell after the last element */

    }



    /* Remove the last (rear) element from the DEQueue and return it.

       - Queue is non-empty or error should be raised.

     */

    public Car removeLast() {

        if(isEmpty())

            raiseError("removeLast");

        r = ((r - 1) + (capacity + 1)) % (capacity + 1);  // update rear pointer

        Car result = data[r];  // get the last element

        data[r] = null;  // setting it to null helps garbage collection

        return result;

    }

}



//--------- YOUR CODE ABOVE ---------