Project 3 - A Bank Simulator using Queues

Part 1 - Due - Tuesday, April 12, 2005

Part 2 - Due - Thursday, April 21, 2005

The goal of this project is to give you an opportunity to practice implementing and using queues and linked structures. You should also continue to use object-oriented concepts in your design and implementation.

For this project, you will implement a simulator that simulates customers entering and leaving a bank. You program will be given as input a configuration file that contains the number of tellers to simulate and the arrival time and service time of each customer. An example configuration file will look as follows:
numTellers 3
arrival 35 service 62
arrival 39 service 57
arrival 78 service 124
arrival 79 service 32
In this example, there are three tellers working at the bank. Customer 1 arrives at time 35. Since there are no other customers in the bank, all tellers are free and the customer can be serviced immediately. The cusomer's departure time is calculated as 97 (35+62). Customer 2 arrives at time 39, can be serviced immediately, and is scheduled for departure at time 96. Customer 3 arrives at time 78, can be serviced immediately, and is scheduled for departure at time 202. Customer 3 arrives at time 79. Unfortunately, all tellers are busy. At time 96, customer 2 leaves, freeing a teller and customer 4 can be serviced. Customer 4's departure time is scheduled as 128 (96+32).

The output of your program will be a list of the wait times and wait plus service times for all customers. You can output this information to a file or to standard output. For the previous example, the output would be the following:
wait 0 waitandservice 62
wait 0 waitandservice 57
wait 0 waitandservice 124
wait 17 waitandservice 49
Your program must implement a LinkedQueue class that provides a queue interface and stores a series of QueueItem objects in a linked structure. Your program must also implement a subclass of LinkedQueue called OrderedQueue. The OrderedQueue will inherit all of the LinkedQueue functions, but will override the enqueue function. The OrderedQueue enqueue function will insert items into the queue such that an item i has a departure time less than the departure times of all items after i in the queue.

Your program must declare two instances of the LinkedQueue class. The first will store information about each customer arrival that has not yet been processed. When your program starts, you should open the input configuration file and read in the customer arrival data. For each arrival, create a QueueItem object and insert it into the queue. You can assume that the data stored in the file will be sorted by arrival time.

The second instance of LinkedQueue will store information about customers waiting in line. In other words, if a customer arrives and cannot be serviced, that customer's arrival and service information is stored in the waiting queue.

Your program must also declare an instance of the OrderedQueue to store information about customers currently being serviced. When a teller is freed, the next customer in the waiting line is removed from the waiting line and put into the line of customers being serviced. If no customers are waiting, the teller remains unoccupied until another customer arrives.

Implementation Hints

You may look at the LinkedQueue code available from http://cpp.datastructures.net/source/ch04.html. However, you may not use structs in your code.

Part 1 - Due Tuesday, April 12, 2005

For part 1, you must submit the design of your program and algorithms for each piece of your design. You must also submit the code for the QueueItem, LinkedQueue, and OrderedQueue classes.

Part 2 - Due Thursday, April 21, 2005

  1. Complete and submit your working code.
  2. Make sure that each function is well documented. Your documentation should specify the type and function of the input paramaters and ouput.
  3. Run your program on a variety of inputs ensuring that all error conditions are handled correctly.
Reminder: No part of your code may be copied from any other source unless noted on this page. All other code submitted must be original code written by you.
Sami Rollins