Assignment 6, due Thursday March 23 at noon.

You must submit your program electronically via gsubmit on csa.

Under no circumstances will late assignments be accepted.

The code you submit must conform with the programming guidelines. 

Program Description

Write and submit three files: list.cpp, list.h, main.cpp.

In this assignment you will use the list ADT to model a real-world simulation. You will first develop the list ADT, and then use it in your simulation program.

The assignment consists of three files.  The first file list.cpp should contain member functions for the list ADT. The second file list.h should contain the class definitions and function prototypes used in your program. The file main.cpp contains the main program.

Third Harbor Tunnel Toll Booth Simulation

Suppose that Boston's Ted William's tunnel has only three toll booths, and we would like to simulate the traffic jams caused by toll-taking. For each car in this simulation we are given:
  1. an arrival time t1
  2. the time needed to process the toll t2
If at time t1 a toll booth is free, then the arriving car can be processed immediately, and the car leaves the toll booth at time t1+t2. The total time spent waiting at the toll booths is t2.

However, it is possible that none of the toll booths is free; they are all servicing cars that have arrived previously. In that case there is a line of one or more cars at each toll booth. The new car proceeds to the shortest line and waits until all cars preceding it in line have paid their tolls. At that time the new car can pay its toll and pass through the tunnel. The customer leaves the toll at t2 time units after reaching the front of a toll booth line. In this case the time spent in the toll is t2 plus the time spent waiting on line.

Part 1: List ADT and Car class

Implement the list ADT class as described in the Main and Savitch text, Chapter 3. Keep in mind that you will need to maintain lists of cars, so you will also need to define a Car class.  The car class will need to contain the arrival time t1 and time needed to process toll t2.

Part 2: Toll booth simulator

Write a  simulator to find the average waiting time at the toll booths. Use an array of three lists to model the cars waiting at the toll booths. As each car arrives, two facts are known: the car's arrival time t1 and the amount of time needed to process the car's toll t2.

Arrival and processing time will be expressed in integer units. Thus your simulator's main loop should probably increment a integer time counter by one tick each pass.

Your program should print out the average waiting time (floating point number) to cout.

The data pairs are stored in an input file ordered by increasing arrival time. The simulation input file will be read from standard input. Here is an example simulation input file. Each line in the input file consists of two positive integer values: arrival time t1 and processing time t2.

To start you in testing your simulator, here is a simple example where the average waiting time is easy to compute. Here is another simple example where the average waiting time is easy to compute.

Grading Criteria

Refer to the grading criteria file: p6.criteria

Academic Honesty and Collaboration

Cooperation is recommended in understanding various concepts and system features. But the actual
solution of the assignments, the programming and debugging must be your individual work, except for
what you specifically credit to other sources. (Your grade will be based on your own contribution.) For
example, copying without attribution any part of someone else's program is plagiarism, even if you
modify it and even if the source is a textbook. The University takes acts of cheating and plagiarism
very seriously: first time violators are routinely suspended for a semester.