Exercise Sheet D

Exercise

You are getting quite proficient at writing Java programs by now. So, henceforth, you'll notice a change in the exercises. I'm no longer going to be telling you exactly what classes and methods you need. Instead, you will have to do more of the design work yourself.

This will certainly mean that, when you read these exercises, your first reaction will be one of utter bewilderment. You won't have a clue how to start. That's only natural. Do not expect to be able to launch straight into writing code. Begin by thinking about what classes there might be and what their interfaces might be.

Ask us for as much help as you need. Do not cog: there is nothing more obvious than a cogged design.

Your work for Exercise Sheet D will be automatically collected in (if you put it in the right place) at 5 p.m. on Friday 24th January. Do not delay starting this exercise. Be realistic. You know that your good intentions to work at CS2000 over the Christmas recess will come to nothing. And you know that you'll get little done in the last week of this term and the first week of next term.

Put your work into a subdirectory of your cs2000 directory called sheetD.

Make sure that, by the submission date, your sheetD directory contains only the files you want me to mark. Do not leave old versions of the program or versions of other programs in the directory.

First read through the whole exercise sheet. Then do some thinking! What classes of objects do you think you will need? What will their interfaces be? (Think about the client code.) Call us over to discuss your ideas. Speak to us regularly about your design. We will advise you. (We will try to help you towards a design that exhibits good procedural abstraction and good data abstraction. In particular, we will try to persuade you not to cram all the functionality into a single class definition!)

G'luck.

The Task

People often want to build computer simulations, e.g., in order to make business decisions. Simulations might tell us how many counters are needed in a post office for fast but cost-effective handling of customers; they might tell us how employment will be affected by changes in tax rates; or they might tell us how climate will change if there are changes in pollution emissions.

Object-oriented programming languages have long been thought to be ideal for implementing business simulations.

The goal of this exercise is to write an object-oriented Java program that simulates a face-lift clinic! Using your simulation, the owners of the clinic can observe patterns of operating theatre and recovery bed usage. It might help them to discover the optimal number of beds or how many patients they can comfortably admit.

I have written two class definitions that you can use in your own program. I shall explain these first.

CS2000Random.java is a class definition for generating random numbers according to certain statistical distributions. (The mathematics of this need not concern you nor scare you; just use this class definition as instructed below). I want you to use this class in your simulation instead of using Math.random().

The interface of this class definition has a zero-argument constructor and two methods:

public int nextNegExp(int theMean): This method returns a random integer according to a negative exponential distribution. The mean of the distribution must be supplied as a parameter.
public int nextPoisson(int theMean): This method returns a random integer according to a Poisson distribution. The mean of the distribution must be supplied as a parameter.

The second class definition is QueueOfPatients.java. This implements a queue as covered in CS2010. It has a zero-argument constructor, and the rest of its interface is as you would expect from the Abstract Data Type covered in CS2010:

public boolean isEmpty()
public int size()
public Patient front()
public void enqueue(Patient aPatient)
public Patient dequeue()

(For those of you who are interested, I have implemented the queue using a linked list with pointers to both head and tail.)

Now let's move on to a description of the Clinic.

The clinic maintains a waiting list of patients. It has three operating theatres and six recovery beds. Your task is to simulate a 900 minute (i.e. 15 hour) day in the life of the clinic. (Think of a for loop running from 0 up to 900. Each iteration represents one minute of the day. So the body of the loop will then send messages to make things happen in that minute.)

Patients initially are placed into the waiting list (which, of course, is a queue). Each patient will undergo an operation and will then spend a certain amount of time in a recovery bed. The duration of each patient's operation and the duration of their recovery are both random numbers.

Specifically, to work out how long a particular patient's operation will take, generate a random number using a negative exponential distribution, with a mean operation duration of 60 minutes.

You also use a negative exponential distribution when generating a random number to determine how long a particular patient will spend in a recovery bed. The mean recovery duration is 180 minutes.

Operating theatres can hold only one patient at a time. After a patient leaves the operating theatre, the theatre must be cleaned. This takes 20 minutes. Only after it has been cleaned is the theatre ready for the next patient, i.e. the person, if any, at the head of the waiting list.

Recovery beds similarly can hold only one patient at a time (!). Once a patient leaves a bed to go home, the bed takes 5 minutes to clean. Only after it has been cleaned is it ready for the next patient, i.e. a person, if any, who is in an operating theatre but whose operation is over.

Your design must include a class called Clinic.java. This should provide a zero-argument constructor and a zero-parameter method called simulate. Hence, I expect the following main method to be sufficient to run your program:

public static void main(String[] args)
{   Clinic c = new Clinic();
    c.simulate();
}

Here is some information about what the simulate method should do.

At the start of the day, create ten patients and put them into the waiting list. Then you need to simulate each minute of the day. (So this is the place for the for loop that goes from 0 to 900.) This is what your program will do at each point in time (i.e. each time around the loop). (Note, it should do these things in this order.)

If it's time for a new patient to arrive, add a new patient to the waiting list and calculate the time at which the next patient will arrive. (There is more information about this below.)
Look at each bed in turn. If it is occupied, see if the occupant's recovery is over. (If you know what time they got into the bed and you know their recovery duration, then you can work out whether their recovery is over). If so, kick them out of the bed. It's time for them to go home with their new face.
For each bed that is ready (i.e. vacant and cleaned), look through the operating theatres until you find a theatre that contains a patient whose operation is over. (If you know what time they went into theatre and you know the duration of their operation, then you can work out whether their surgery is over). Move that patient from his/her theatre to the recovery bed.
For each theatre that is ready (i.e. vacant and cleaned), move a patient from the waiting list (if there are any on the waiting list) into the theatre.

(If you look at the above, you should see that operating theatres and recovery beds are highly similar objects: a patient occupies them for a certain period of time; the patient leaves, the theatre/bed is cleaned; and then it is ready for the next patient. These can be identical class definitions, differing only in their name and the cleaning time.)

I'd like your simulation to print out one line per minute. On that line I'd like you to show the events that take place during that minute. The kind of output I want is extremely concise. Here's the sort of thing I'm looking for, which comes from a run of my own version of this program. (I've snipped some boring bits out of this. Obviously, you don't snip bits out of your output.)

Time: 0 WL->T0  WL->T1  WL->T2
Time: 1
Time: 2
Time: 3
Time: 4
Time: 5
Time: 6
Time: 7
Time: 8
Time: 9
Time: 10
Time: 11
Time: 12
Time: 13
Time: 14 T0->B0
Time: 15
<minutes 16-31 snipped out because nothing happened>
Time: 32
Time: 33 T2->B1
Time: 34
Time: 35 WL->T0
Time: 36
<minutes 37-52 snipped out because nothing happened>
Time: 53
Time: 54 WL->T2
Time: 55
Time: 56
Time: 57 LeaveB0
Time: 58
Time: 59
Time: 60
Time: 61
Time: 62
Time: 63 JoinWL T0->B0
Time: 64
<minutes 65-899 snipped out for brevity>

So what happened here? Well in time 0, three of the ten initial patients moved from the waiting list (WL) into the three operating theatres (T0, T1 and T2). By time 14, the patient in T0 had a new face and was moved to bed 0 (B0). By time 33, the patient in T2 was wrinkle-free and moved to B1. It takes 20 minutes to clean a theatre, so it wasn't until time 35 that the next patient at the head of the waiting list (WL) moved into T0 (vacated 20 minutes ago). At time 54, bits of the last patient had been scraped from the walls of T2 (taking 20 minutes from when s/he left the theatre), so the next patient now moves from WL to T2. At time 57, the patient who moved into B0 has recovered and so s/he leaves the clinic. This bed is ready again after 5 minutes of cleaning at time 63; and so the patient in T0 is allowed to move out of T0 to B0. Also during time 63, a new patient joins the WL. And so on!

The only thing I haven't explained so far is how we know when a new patient arrives.

The idea is that there is a gap between each arrival, and this is referred to as the inter-arrival time. You generate the inter-arrival time using a random number generator. Specifically, you use the Poisson distribution and the mean inter-arrival time is 60 minutes.

So suppose the time is 536 (536 minutes have elapsed since the start of the simulation). Suppose someone has just arrived and joined the queue. Now you use the random number generator to generate a new inter-arrival time. Suppose this is 48. This means that the next patient will join the queue 48 minutes from now. So when the time reaches 584 (i.e. 536 + 48), you add a new patient to the queue, and you generate the next inter-arrival time.

Challenge Exercise

Create a subdirectory of your cs2000/sheetD directory called challenge. Copy your program into this new directory, and make your changes to this copy.

Here are two alternative challenges.

A weakness of our simulation is that it advances the clock minute by minute. Often nothing happens in any particular minute. For more computationally expensive simulations, this is too wasteful. Instead, the clock should skip over minutes in which nothing happens. In other words, on each iteration, the clock should be advanced directly to the next event.
Change your program so that it works in this way.
An alternative to making the program faster is to make it more useful. Write a class definition called Histogram.java. Your class definition should have a constructor (e.g. for taking in the title), one or more setters to allow clients to update frequency values, and one or more getters which draw a histogram from the frequency values onto the screen, e.g.
```
===========
A histogram
===========
 0 |***
 1 |*
 2 |******
 3 |
 4 |***
 5 |*
 6 |**
 7 |
 8 |
 9 |****
```
There are numerous ways of making a groovy Histogram class. Maybe it has methods for plotting the histogram horizontally (as above) and others for plotting it vertically. Look at the kind of facilities provided within software such as Excel for other ideas.

Include a main method in Histogram.java that does a demo of the features you have implemented.

Then alter your simulation so that it collects some waiting time statistics (e.g. how long people wait on the waiting list, and how long people wait in theatre after the end of their operation until a bed becomes free). Show these statistics using histograms. (You may need to alter the number of theatres/beds to get more interesting results).