Description
Simulation is a good method for evaluating supermarket checkout strategies. Which is best: a single queue feeding all checkout counters, a single regular queue feeding each checkout counter (all of equal status) and a number of express checkout counters (for customers buying 12 or fewer items) and the rest being regular checkout queues. Using realistic assumptions about customer arrival time, mean number of item to purchase, etc. it is possible to simulate the checkout process to determine which setup provides the minimum average (weighted by number of items) waiting customer times. The important thing in the above brief description of simulation is that one or more queues must be used. This assignment focuses on manipulation of a single event queue for a supermarket counter setup. During simulation, we must be able to determine the next event that will occur. The problem is this event may not be the first event on the queue. One way to handle this problem is to use a priority queue. This strategy uses a heap to provide O(log(n)) enqueuing and dequeuing operations for queues of size n. There are Java classes that implement this but for this assignment we will use O(n) enqueueing and dequeueing operations implemented using our QueueADT class. Functional Specifications
You are provided with a zip file ass3Files.zip which contains a number of classes. I/O is done as on assignment 1, by using the InStringFile.java class. The standard class for queueing as presented in class, LinkedQueue, QueueADT, LinearNode are also provided. An Event class is provided that gives the definition of an event. Its has fields for time (double), type (String) and number of items (int). It has the appropriate getters and setters and a toString() method. This class uses the Service.java class for a method called doubleFormat used in Event’s toString() method (to perform minor pretty printing). Both of these classes are complete and do not need any modifications. A complete Main.java class is also provided. The static main method reads an event file ass3_events2015.txt. This is an unordered queue of events. Each event has an eventTime field (double) and an eventType field (String, one of ARRIVAL, IN_SERVICE, DEPART, SNAPSHOT and ALL_DONE). The ARRIVAL, IN_SERVICE and DEPART events represent a customer’s arrival at a checkout counter, the customer being served at the counter and the customer leaving the counter. Each has a 3rd field, eventNumItems (int) giving the number of items the customer has. The main method reads this file and prints out the data in unsorted order. It also computes the minimum eventTime value for all the ALL_DONE events (if there are more than one) in a local variable called minAllDoneTime. You are required to add two methods to the EventQueue. This class has a constructor (provided). You are required to write two methods: insertEvent() and deleteEvents().
2/26/2015 CS1027, Assignment 3
http://www.csd.uwo.ca/Courses/CS1027b/assignments/Asn3/asn3_description_2015.html 2/4
1. The insertEvent() method adds one event object to an eventQueue object. This queue can be assumed to be sorted by time. We insert an event by dequeueing events from eventQueue until we find the insertion place, add the new event and restore the eventQueue to its original state (plus one event for the newly inserted event). It will be necessary to use use a second queue to perform this operation. Because you may (potentially) have to look at each event in the queue, this operation is O(n) for an n event queue. We also can use the queue’s toString() method to print out the queue contents before and after insertion of the queue. A variable debug controls whether debugging printing occurs or not 2. The deleteEvents() method deletes all events with times = the lowest eventTime value for an ALL_DONE event. That means there may be more than one ALL_DONE event!!! If there are two or more ALL_DONE events with the minimum value, we keep the first occurrence in the output list. There may also be no ALL_DONE event, in which case a WARNING message should be printed. Again, the queue’s toString() method can be used to print the queue contents before and after insertion. As for insertEvent, a second queue may be needed to perform this O(n) operation. Lastly, the EmptyCollectionException.java exception class handles the possibility of trying to dequeue and empty queue. For a small event file (5 events), we read one line at a time in Main.java, and insert the event information into the eventQueue in the correct order. Then we delete all events in eventQueue with times greater than the smallest time for any ALL_DONE event from the sorted queue (but we do not delete the first ALL_DONE event at that time). For debugging purposes (debug=true in Main.java), we print the queue before and after each insert and delete operation. That code remains in the EventQueue.java file but the 2 places where insertion code and deletion code has been removed are indicated by comments. Put you code there. The debug output can be verbose, in that case set the debug variable to false (debug=false in Main.java) to reduce this output significantly. For our small event file we get:
1 Time: 9.90 Type: ARRIVAL Number of items: 33
INSERT EVENT: Event time: 9.90 Event type: ARRIVAL Event number of items: 33
Event Queue before new event enqueued ‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐Empty Queue
Event Queue after new event enqueued ‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐Time: 9.9 Type: ARRIVAL Number of items: 33
2 Time: 0.90 Type: ARRIVAL Number of items: 16
INSERT EVENT: Event time: 0.90 Event type: ARRIVAL Event number of items: 16
Event Queue before new event enqueued ‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐Time: 9.9 Type: ARRIVAL Number of items: 33
Event Queue after new event enqueued ‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐Time: 0.9 Type: ARRIVAL Number of items: 16 Time: 9.9 Type: ARRIVAL Number of items: 33
2/26/2015 CS1027, Assignment 3
http://www.csd.uwo.ca/Courses/CS1027b/assignments/Asn3/asn3_description_2015.html 3/4
3 Time: 9.00 Type: ALL_DONE
INSERT EVENT: Event time: 9.00 Event type: ALL_DONE
Event Queue before new event enqueued ‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐Time: 0.9 Type: ARRIVAL Number of items: 16 Time: 9.9 Type: ARRIVAL Number of items: 33
Event Queue after new event enqueued ‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐Time: 0.9 Type: ARRIVAL Number of items: 16 Time: 9.0 Type: ALL_DONE Number of items not specified Time: 9.9 Type: ARRIVAL Number of items: 33
4 Time: 0.10 Type: DEPART Number of items: 8
INSERT EVENT: Event time: 0.10 Event type: DEPART Event number of items: 8
Event Queue before new event enqueued ‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐Time: 0.9 Type: ARRIVAL Number of items: 16 Time: 9.0 Type: ALL_DONE Number of items not specified Time: 9.9 Type: ARRIVAL Number of items: 33
Event Queue after new event enqueued ‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐Time: 0.1 Type: DEPART Number of items: 8 Time: 0.9 Type: ARRIVAL Number of items: 16 Time: 9.0 Type: ALL_DONE Number of items not specified Time: 9.9 Type: ARRIVAL Number of items: 33
5 Time: 4.00 Type: ALL_DONE
INSERT EVENT: Event time: 4.00 Event type: ALL_DONE
Event Queue before new event enqueued ‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐Time: 0.1 Type: DEPART Number of items: 8 Time: 0.9 Type: ARRIVAL Number of items: 16 Time: 9.0 Type: ALL_DONE Number of items not specified Time: 9.9 Type: ARRIVAL Number of items: 33
Event Queue after new event enqueued ‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐Time: 0.1 Type: DEPART Number of items: 8 Time: 0.9 Type: ARRIVAL Number of items: 16 Time: 4.0 Type: ALL_DONE Number of items not specified Time: 9.0 Type: ALL_DONE Number of items not specified Time: 9.9 Type: ARRIVAL Number of items: 33
5 events read and inserted in order in the eventQueue
Event Queue before all events with eventTime<=4.0 deleted ‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐Time: 0.1 Type: DEPART Number of items: 8 Time: 0.9 Type: ARRIVAL Number of items: 16
2/26/2015 CS1027, Assignment 3
http://www.csd.uwo.ca/Courses/CS1027b/assignments/Asn3/asn3_description_2015.html 4/4
Time: 4.0 Type: ALL_DONE Number of items not specified Time: 9.0 Type: ALL_DONE Number of items not specified Time: 9.9 Type: ARRIVAL Number of items: 33
Event Queue after all events with eventTime<=4.0 deleted ‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐Time: 0.1 Type: DEPART Number of items: 8 Time: 0.9 Type: ARRIVAL Number of items: 16 Time: 4.0 Type: ALL_DONE Number of items not specified Nonfunctional Specifications
Your program has to be compilable under Eclipse. Use Javadoc comments for each class and method. All significant variables must be commented. Use Java conventions and good Java programming techniques (meaningful variable names, conventions for variable and constant names, etc). Indent your code properly. Remember that assignments are to be done individually and must be your own work