/*************************************************************** * CarQueue.java -- CS100m-fa05 Project 6 * * An array implementation of a queue, which allows insertion of element * at the rear of the queue, and access and removal remove at the * front of the queue. Moreover, the relative order between elements in * the queue should should never be changed. It it always first-in-first out * (FIFO) -- That is why it is called a queue. * * This data structure holds objects of type Car. * * * @ TO STUDENTS: * * Implementation specifications/hints: * * A key feature of queues (and double-ended queues, * which you will implement later) is constant access/update time, * i.e. all public methods have 'amortized' running time that is independent of * the size of the queue. (The exception is the time for doubling the queue size * when a queue is full, the time for doubling the queue size * is proportional to the queue size n, but it happens only after at least n/2 * operations (since previous resizing), making the time per operation * constant on average.) * For this reason, the queue needs to be implemented in * a circular fashion (i.e. wrap-around). More specifically, when * adding/removing elements to/from the queue, one should update the * appropriate rear or front position pointer instead of shifting elements * in the whole array to make the front element align with position zero. * The former approach has contant running time per * operation, whilst the latter is proportional to the queue size. One MUST * implement the double-ended queue with the former approach; an implementation * using the latter (inappropriate) approach will receive NO CREDIT. * * * Instructions: * * - Complete methods with comments "### Implement this method ###" and write * your code in the specified place. Do not modify any other part of the * program unless instructed to do so. * * - You may add methods, i.e. write helper methods for taking care of certain * subroutines that you may want to use at more than one place. * * - You may NOT import any additional classes other than those already * included in the set of skeleton code . * * - When needed, errors should be raised by calling the raiseError method * with the appropriate argument. * * - Be sure to test your code. Some code for testing is provided, but you * are strongly encouraged to test you program more thoroughly by writing your * own testing routines. For example, you can hand-code a sequence of operations * and print out the queue content after each step. Then your can compare * the output against what you expect, i.e. what you have worked out * on paper or in your mind. * * * @ TO GRADERS: Specific way of implementing each method is not unique. Any * implementation that conforms to the queue specification is acceptable. * * @ INTERNAL COMMENTS: As a good practice, we should declare methods that * throw exceptions as ... throws ...Exception. But here we take this out * to avoid confusion to beginners. * * @ Yunpeng Li, Nov. 12, 2005 */ public class CarQueue { // --- Constants --- public final static int DEF_INIT_CAPACITY = 50; // default init capacity // --- Variables --- /* These variables should always be updated appropriately after each operation throughout the program. */ protected Car[] data; // the array holding data protected int f; // position of the first (front) element protected int r; // position of the spot right after the last (rear) element protected int capacity; // the capacity of the queue. /* You may add and use additional variables of you own choice if you wish to. */ // --- Additional Variables (Optional) --- //--------- YOUR CODE BELOW --------- //--------- YOUR CODE ABOVE --------- // --- Constructors --- /* Construct a queue with specified initial capacity. * When the queue size reaches the capacity, resizing will occur. (i.e. you will need to double the capacity of the queue.) The queue should be initially empty. You do not yet need to be concerned with how exception works -- just think of it as some type of error, which terminates the execution of the program. (You will get to know more of it in a higher level class.) */ public CarQueue(int _capacity) { if(_capacity <= 0) // Capacity should be positive throw new IllegalArgumentException( "Capacity must be greater than zero!"); // ### Implement this method ### //--------- YOUR CODE BELOW --------- capacity = _capacity; f = 0; r = 0; data = new Car[capacity + 1]; /* Keep one empty cell to distinguish a full queue from an empty one. The implementation is not unique. For instance, one may also keep a 'size' instance variable instead of the rear pointer r and hence not needing the extra blank. */ //--------- YOUR CODE ABOVE --------- } /* Construct a queue of default initial capacity DEF_INIT_CAPACITY. (queue is initially empty) You must implement this constructor in ONE LINE (i.e. one statement). Hint: use keyword 'this'. */ public CarQueue() { // ### Implement this method ### //--------- YOUR CODE BELOW --------- this(DEF_INIT_CAPACITY); //--------- YOUR CODE ABOVE --------- } /* Error signaling - this method with terminate the execution in this program by raising an error. - Call this method wherever appropriate, pass the name of the caller method as the parameter (a String). */ protected void raiseError(String callerMethodName) { throw new DataEmptyException("In " + callerMethodName + ": Data array is empty"); /* Ideally, queues, DE-queues, and stacks should all have their own (different) exception class, but here we make them share the same one just to keep things simple. */ } // --- Standard Queue Methods --- /* =Return the number of elements in the queue. */ public int size() { // ### Implement this method ### //--------- YOUR CODE BELOW --------- // @ for HW release: return 0; // Replace this dummy line with your code return (capacity + 1 + r - f) % (capacity + 1); //--------- YOUR CODE ABOVE --------- } /* ={This queue is empty}, true or false */ public boolean isEmpty() { // ### Implement this method ### //--------- YOUR CODE BELOW --------- // @ for HW release: return true; // Replace this dummy line with your code return size() == 0; //--------- YOUR CODE ABOVE --------- } /* Insert an element into the rear of the queue. e.g. (a, b, c) -- insertLast(d) --> (a, b, c, d) - Need to double the capacity of the queue when necessary. */ public void insertLast(Car obj) { // ### Implement this method ### //--------- YOUR CODE BELOW --------- if(size() == capacity) // capacity has been reached doubleSize(); data[r] = obj; // insert the new object to the rear r = (r + 1) % (capacity + 1); // update rear pointer //--------- YOUR CODE ABOVE --------- } /* =Return the first (front) element. - You'll need to check whether the queue is empty. An appropriate error message should be raised if it is. */ public Car first() { // ### Implement this method ### if(isEmpty()) raiseError("first"); //--------- YOUR CODE BELOW --------- // @ for HW release: return null; // Replace this dummy line with your code return data[f]; //--------- YOUR CODE ABOVE --------- } /* =Remove the first (front) element from the queue and return it. - Queue is non-empty or error should be raised. */ public Car removeFirst() { // ### Implement this method ### if(isEmpty()) raiseError("removeFirst"); //--------- YOUR CODE BELOW --------- // @ for HW release: return null; // Replace this dummy line with your code Car result = data[f]; data[f] = null; // setting it to null helps garbage collection f = (f + 1) % (capacity + 1); // update front pointer return result; //--------- YOUR CODE ABOVE --------- } // --- Additional methods (Optional, your choice) --- //--------- YOUR CODE BELOW --------- /* Double the capacity of the queue. */ protected void doubleSize() { // get hold of the the original data Car[] oldData = data; int oldCapacity = capacity; // instantiate new array twice as large capacity = 2 * capacity; data = new Car[capacity + 1]; // copy the data from the old array to the new array if(f <= r) { // no wrap-around, so straight copying for(int i=f; i