# Queues

## Car Wash Project

#### Problem Description

The car wash machine at Squeaky Clean Car Wash requires exactly 3 minutes to complete the regular car wash (including rinse, wax, and dry). A car arrives at the car wash approximately every four minutes (cars don't arrive exactly four minutes apart: that would be easy to program!). The owners of the car wash are proposing to add another car wash bay, because they are suspicious that the average wait time for the cars is long enough that they are losing business. Construct a simulation of the car wash to determine the average waiting time for a car at the car wash during a typical day (9 am to 7 pm). Since the arrival time is an average, there is often a waiting line. This can be simulated using a queue.

Think about how you might go about simulating this problem. How could you simulate the arrivals, waiting, and washing of the cars at the car wash?

Perhaps it would be useful to think of what can happen in a given minute in the car wash (we'll assume that at most one car can arrive in any given minute, although this is not necessary). In a car wash, you can have cars arriving, cars waiting, and cars being washed. You also have cars changing from one state to another. If a car arrives and there is a car being washed, the arriving car becomes a waiting car. If there is at least one car waiting and the car wash bay becomes available, a waiting car becomes a car being washed.

How will you determine whether a car should arrive in the current minute? (In any given minute, there is a 1 in 4 chance that a car will arrive.) How will you decide whether a car is currently being washed? How will you decide when the machine is empty? How will you represent the waiting time of a car? How will you represent the total waiting time of all the cars for the day? How will you represent the total time that the car wash is open?

You may wish to develop your own design for this program, or you may wish to use the design below.

#### One Possible Design

First, let's look at the things in the problem description that might turn into objects in the implementation. The "things" (nouns) are:

 car wash machine Squeaky Clean Car Wash minutes car owners car wash bay average waiting time lost business simulation day arrival time waiting line (queue)
Several of these refer to the business as a whole: Squeaky Clean Car Wash and owners. The word simulation covers these, and is more relevant for our program. The possibility of lost business is the reason for the simulation, but not part of it. We are left with car wash machine and car wash bay (which seem to refer to the same thing), car, waiting line (queue), and several objects related to time: minutes, day, arrival time, and average waiting time.

Let's reconsider the problem in more detail. Our primary task is to create a simulation of the car wash for one day that calculates the average waiting time of all the cars. To do that we need to know the total waiting time for all the cars and the number of cars. To calculate the total waiting time we need the individual waiting time for each car, which we calculate from its arrival time (the current time when the car arrives) and the current time when the car leaves the waiting line and enters the car wash bay. Since the time a car spends in the wash bay is measured in minutes, we might as well measure waiting times and the time that the car wash is open (the length of the day) in minutes as well. As mentioned above, if a car arrives every four minutes, on average, then in any given minute there is a one in four chance of a car arriving.

This analysis has introduced several new "things" that did not appear explicitly in the original problem description: the total waiting time for all the cars, the number of cars, the waiting time for each individual car, and the current time. Our new list is:

 Integers: length of day current time arrival time individual waiting time total waiting time average waiting time number of cars Objects: simulation car waiting line (queue) car wash bay
Since the only reason we care about individual waiting times is to determine the total waiting time, we can avoid keeping track of them by adding them to the total waiting time as we go.

What do we know about the responsibilities of the objects listed in our table? In each minute the simulation is responsible for determining whether a car arrives, whether it has to wait on line, whether a car can leave the line, and, if so, how long it waited. To determine this it needs to know the car's arrival time and the current time. This constitutes a single step of the simulation. The simulation must run for as many minutes as the car wash is open. (Actually, the simulation should usually run longer -- what happens if there are cars waiting in line or in the wash bay when the car wash officially closes?) When done, the simulation must calculate the average waiting time.

The waiting line is easy. It is a first-in/first-out (FIFO) data structure of cars and, as mentioned in the problem description, can be modeled as a queue.

What do we care about for cars? We care about their arrival times and their waiting times. We also care about how long a car spends being washed, but we could argue that that is really a function of the car wash bay rather than of the car since all cars entering the bay will take the same amount of time to be washed. The waiting time can be calculated by the simulation, so the only thing the car really needs to keep track of is its arrival time. In fact, we could eliminate cars altogether in this simulation, and just keep a queue of arrival times. Providing a car abstraction more closely models the problem domain, however, and might be useful in the future if the problem is extended.

Finally, what are the responsibilities of a car wash bay? It should be able to tell the simulation whether it is empty or not, and, if it is not empty, it should keep track of the time until it becomes empty.

#### Implementation

A wash lasts three minutes, but your simulation should re-evaluate the state of the Squeaky Clean Car Wash every minute.

To solve this problem, use the Queue class and the other built-in classes that you find useful. Becoming familiar with the more common classes provided will be helpful to you, as they will often shorten your workload. Many classes in Java can be easily extended to make them useful for similar tasks. You can read the specifications for the built-in Java classes online: http://java.sun.com/j2se/1.4/docs/api/index.html. Become accustomed to using this website as a reference.

1. Consider the pseudo-code below, which shows all of the things that happen in one minute at the car wash. You will use this pseudo-code to write your Car Wash Simulation.
```   for each minute of the simulation

if a car arrives
note the arrival time of the car (store this with the car)
add the car to the queue

if the car wash bay is empty and there is a car waiting to be washed
dequeue a car for washing
determine how long that car was waiting and add to total wait time
start washing the car (bay will be occupied for next 2 minutes)

otherwise, if there is a car being washed
decrease the amount of time left before the car is done (bay empty)
```
Question: is there a case missing here that requires any action?

2. Implement the Car Wash Simulation program. If you wish, you may start with the template classes provided for three classes, `CarWashSimulation`, `Car`, and `Bay`, and a very simple class, `SimApplication`, that contains the `main` function. The locations where you will need to add code have been starred. If you do not wish to use the code provided, you may wish to become familiar with it anyway as a useful supplement to the problem description. (These classes are licensed under the Creative Commons GNU General Public License. )

Design usually proceeds from a high level of abstraction ("the big picture") down to low levels of abstraction (the details). Implementation often (although certainly not always) proceeds "bottom-up." The following suggested ordering is "bottom-up" and allows you to test your modifications incrementally.

1. The `Car` class is so trivial that it has been provided for you. Complete the implementation of the `Bay` class.

2. Implement `CarWashSimulation.reset` based on the comments provided. You should be able to test your partially completed program at this point, although it won't do much.

3. Implement `CarWashSimulation.step` based on the pseudo-code above. (Note that the code already contains one statement.) Implement a simplified version of `Simulation.run` that runs until closing time. (Don't worry yet about cars still waiting to be washed when the car wash closes.) Have the `main` function run the simulation for a small number of times (for example, 5 or 10 minutes) to test your `step` function. You may wish to use the Debug class. (The Debug class comes from the AP® Marine Biology Simulation case study and is available under the GNU General Public License.)

4. Once `CarWashSimulation.step` seems to be running correctly, update `CarWashSimulation.run` and `main` to meet the requirements of the problem description.

3. Run the simulation several times. What are the average waiting times over a ten hour day?
The owners of Squeaky Clean Car Wash don't want to make their customers wait more than ten minutes for a car wash. The car wash is open seven days a week. How often in those seven days is the average wait time over ten minutes?

Hint: Looking for the Random number generator? It's in `java.util`, and it's called `Random`.

Acknowledgements: The behavior of the car wash simulation in this lab is based on a project description by Todd Ollendyke (trollend@nb.net).

AP is a registered trademark of the College Entrance Examination Board. The Marine Biology Simulation case study was copyrighted in 2002 by the College Entrance Examination Board.  It is available on the web from the College Board web site (www.collegeboard.com and apcentral.collegeboard.com).