Introduction to Data Structures and Algorithms
Assignment 3 Part A: Using Collections

  • Due 24 May , 7pm

What To Hand In

  • and (for the completion)
  • and any files that was modified for the Challenge, need to be renamed by appending Chall to the name of the class.

Do not rename these files.

Remember to submit all of these files. When you have submitted them, check that you can read the files listed on the submission page, and complete the submission process.

Hospital ER (Weight: 2/3)

Hint: The specification of this problem is quite long and detailed. Read it carefully! You cannot do this assignment just based on comments in the template code.

The HospitalER program is a tick-based simulation of patients arriving at the emergency room of a hospital. Patients arrive, wait for treatment, get treated, then are discharged.
  • For the core version, there is just one waiting room and one treatment room, and patients only need one treatment.
  • For the completion version, patients move through a series of treatments in different departments - ER, X-ray, MRI, Operating Theatre, etc. Each department has its own waiting room and treatment room. When patients have finished all their treatments, they are discharged.

A treatment room only has facilities to treat a fixed number of patients at any one time; if the treatment room is full, any new patients arrive for that treatment have to wait in the waiting room until there is a space.

Patients can have different priorities (from 1 (the highest priority) to 3), which are assigned when they arrive at the emergency room.

(Note, this program is related to the MedicalCenter program in the lectures, but is more complex.

The Core version of the program has three classes:
  • Patient which contains information about an individual patient. This includes the treatment plan: the sequence of treatments they need and how long each treatment will take. Note that the core version of the simulation ignores everything beyond the first treatment.
    The Patient object keeps track of which treatment in the treatment plan the Patient is currently undergoing (or waiting for), and the remaining time for that treatment.
    It has a constructor that requires the arrival time and a priority (1-3),
    It has methods for accessing fields, comparing Patients, and drawing Patients
    It has methods for moving the Patient through the simulation:
    • waitForATick(): makes patient wait for one tick.
    • advanceTreatmentByTick(): removes one time tick from the remaining time for the current treatment.
    • completedCurrentTreatment(): whether the Patient has completed their current treatment.
    • incrementTreatmentNumber(): [completion] Sets the Patient to their next treatment.
    • getCurrentTreatment(): [completion] gets the name of the department for the current (or about-to-start) treatment.
    • noMoreTreatments(): [completion] whether the Patient has completed all their treatments.

  • HospitalERCore which contains
    • fields to hold collections of Patients for the waiting room and the treatment room, fields to hold the statistics, and fields with parameters for the simulation.
    • a reset(...) method [incomplete] which will reset the simulation, the waiting room, the treatment room, and all the fields for the statistics.
    • the run() method [incomplete] for the simulation
    • several helper methods, including a redraw() method that visualises the state of the simulation for you.

  • HospitalERGUI which contains
    • fields to hold which simulation is run: HospitalERCore or HospitalERCompl)
    • a constructor (completed for you)
    • a main(...) and setupGUI() methods (completed for you).

The Completion version of the program has four classes
  • Patient, just as in the core

  • HospitalERCompl which contains
    • a field containing a collection of Department objects, representing the different treatment centers in the hospital.
    • The same methods as the core version, but the reset(...) and run() methods will be more complicated.

  • Department which contains information about one department of the hospital. It will need
    • Fields to hold
      • The set of patients currently being treated (and the maximum size of this set)
      • The queue of patients waiting to be treated.
    • Methods to
      • Add a patient to the department
      • Return the collection of waiting patients and current patients
      • Move patients from the waiting room to the treatment area (if there is space)
      • Remove a patient from the treatment area department
      • Draw a graphical representation of the patients in the department

  • HospitalERGUI, just as in the core, but you will need to modify the declaration of the variable er, to HospitalERCompl er = new HospitalERCompl();

Note that the interface of HospitalERGUI has four buttons for resetting, running, and pausing the simulation. It also has sliders to control some of the parameters of the simulation, such as the speed of the simulation, how often new patients arrive, and the relative frequency of the different priority patients.


Complete the HospitalERCore and Patient classes so that it simulates patients coming to the emergency room, and reports on basic statistics.

  1. Complete the reset method to set up waitingRoom to have a queue of patients and treatmentRoom to have a set of Patients.
  2. Complete the run method. Each loop of the run() method represents one tick of time. The method should, in that order:
    • Advance the time by one "tick"
    • Find all patients in the treatment room who have completed their current treatment and discharge them (remove them from the treatment room).
      You must call the reportDischargePatient() method to print a message for each patient when they are discharged.
    • Process one-time tick for each patient currently being treated, or waiting in the waiting room.
    • Move patients from the waiting room to the treatment room if there is space.
    • Get any new patient that has arrived and adds them to the waiting room (done for you already).
    • Display the state of the waiting room and treatment room (done for you already).
  3. Add fields to record basic statistics, extend the run() method to update the statistics when a patient is discharged, and complete the reportStatistics() method by calling the reportLine() method to report:
    • The total number of patients treated
    • The average waiting time of the patients
  4. Make the waiting room act as a priority queue taking into account the priority of the patients.
    • Extend the reset method to use a priority queue if the argument to the method is true, and a regular queue if the argument is false.
    • Complete the compareTo method in the Patient class so that a Patient with a higher priority is ordered before a Patient with lower priority. Patients with equal priority should be ordered by their time of arrival.
    • Add fields, and modify the run() and reportStatistics methods to also report
      • The total number of priority 1 patients treated,
      • The average waiting time of the priority 1 patients
        Hint: You MUST call reportLine() method twice. Once for all patients, and once for just patients with priority 1.

Run some tests to see whether using the priority queue improves the waiting time for priority 1 patients.

It is very important that you do not rename these methods


The Core version of the simulation is not realistic, since patients often need a sequence of treatments, including Surgery, X-rays, MRI, or ultrasound, in addition to treatment in the emergency room itself. The simulation should have a collection of departments, where each department provides a different kind of treatment. When a patient finishes one treatment, they then need to move on to their next treatment, until they finally finish all the required treatments and can be discharged. When a Patient object is created, the sequence of treatments (and how long they will take) is worked out by the constructor.

Each department will have limited facilities so each department will have its own waiting room and treatment room.

Extend your program to handle the more realistic simulation.

  1. In the HospitalERGUI class, modify the declaration of the variable er, to HospitalERCompl er = new HospitalERCompl();
  2. Copy the field for statistics from into Extend them by adding a field with a collection of Departments.
    Hint: Your collection must be a map, with the key being the name of the department and the value being the department object.
  3. Complete the reset method to initialise the statistics fileds (copy this part from the reset method in
    Note that the departments collection have been initialised for you. Do not modify this code.
  4. Complete the Department class, in accordance with the description above. Note that the constructor will need at least three parameters: the name of the department, the maximum number of Patients in its treatment room, and whether the waiting room is run as an ordinary queue or a priority queue.
    Note: The template for Department is almost empty. You sill have to do some program design for this class, working out the fields and method headers it needs, as well as writing the method bodies!
  5. Extend the run() method in your HospitalERCompl class so that each cycle in the loop does in that order:
    • Advances the time by one "tick"
    • Runs through all the departments to find all patients who have completed their current treatment, remove them from their current department, and increment their treatment number. A patient who has completed all their treatments should be discharged; other patients should be moved to the next department according to their treatment plan.
    • Process one time tick for each patient currently being treated in each department or waiting in the waiting room.
    • For each department, move patients from the waiting room into the treatment room, if there are any spaces.
    • Gets any new patient that has arrived and adds them to the appropriate department for their first treatment.
    • Copy the reportStatistics() method from Eg, you MUST call the reportLine() method.

It is very important that you do not rename these methods


You need to write a HospitalERChall class and not modify the HospitalERCore and HospitalERCompl classes, as this would affect the marking of the core and completion. Also, make sure you create Challenge version of any files you modify for the Challenge.

The goal of a simulation like this is to be able to evaluate and/or design a real system. For the EmergencyRoom, we might want to find out how well it is performing (How long do patients have to wait? Are critical patients at risk because of having to wait too long? Which departments get overloaded and need more facilities? etc), or we might want to find out what kinds of situations (arrival rates, distributions of priorities, kinds of injuries) would stress the emergency room.

Add more record keeping and more reporting to the system to allow a user to evaluate how well the emergency room functions under various different situations. You will need to make the Patient class print more useful information, and possibly record more information. You will also need to complete the reportStatistics method to produce a useful report, preferably with graphical information as well as text, of the performance of the emergency room.

You may need to modify the makeRandomTreatments method in Patient to allow the user to vary the kinds of patients. But, in order for us to mark your core and completion part, you MUST create a PatientChall class, if you want to modify the Patient class.

The challenge is essentially a Data Science task, of writing code that generates data and presents/visualises in a way that is useful to a human analyst. This is a very common purpose of simulation programs.