Reference no: EM133692775

Data Structures

Purpose: To measure the student's ability to implement and/or use one or more specialized containers (e.g., stacks and queues) to solve an underlying problem in C++.

Overview

This assignment will test your ability to implement a (linked) queue as well as usage of its functionality to simulate a queue of patients at a doctor's office. In summary, you will build a simulation of a queuing system where there are a set number of available doctors and patients that arrive are either allocated to a doctor or placed into a queue to be seen when a doctor becomes free.

We will model a system that primarily consists of a doctor's office (i.e., a collection of doctors) and a queue holding the patients waiting to be seen. Initially, all doctors are free and, hence, the first patient to arrive will immediately be seen by the first doctor. When the next patient arrives, they will immediately be seen if there is an available doctor. Otherwise, the patient is placed in a queue to wait. To appropriately model the queueing system of a doctor's office, we will need to know the number of doctors, the length of an appointment, and the average time between the arrivals of patients. For simplicity, the length of an appointment will be fixed for all patients.

The Supplied Files

This section gives an overview of the files that you are provided as part of this assignment. None of the provided files should be modified. In contrast to Assignment 1, you are not provided with (skeleton) implementation files - you will be expected to create these files from scratch.

You are recommended to take some time to understand the overall structure of the program before starting the implementation phase. Note: In some cases, there are methods implemented in the supplied header files - this is done so that you don't have to worry about implementing them. You will be expected to use these methods so be sure to check them out!

main.cpp - contains the main function, including the logic to parse the arguments, start the simulation, then display some statistics at completion.

empty_collection_exception.h - contains the definition of an exception that can be thrown when an operation is attempted on an empty queue. Note: there is no accompanying .cpp file - the .h file contains the complete definition and implementation of the exception.

lqueue.h - contains the header for the LQueue class, which includes the instance variables and behaviours that your queue should contain.

patient.h - contains the header for the patient class, which includes the instance variables and behaviours that a patient should contain.
doctor.h - contains the header for the doctor class, which includes the instance variables and behaviours that a doctor should contain.

doctors_office.h - contains the header for the doctors_office class, which includes the instance variables and behaviours that the doctor's office should contain.

simulation.h - contains the header for the simulation class, which includes the instance variables and behaviours that your simulation should contain.
makefile - the makefile for the project, which outlines the build recipe. The -g flag is set for you to make debugging and/or memory leak detection more convenient, should you wish to use these tools.

Running the Program
Of course, you will need to ensure the program is compiled prior to running it. You can use the supplied makefile for this - it will produce an executable called Simulation. The program should be executed using the command:
./Simulation <seed> <sim_time> <num_doctors> <appointment_time>
<time_between_arrivals>

This means, you need to supply various integer arguments to the program for it to run. For example, you can run it using:
./Simulation 0 10 1 4 3

To start a simulation with a random seed of 0, 10 units of time, 1 doctor, an appointment time of 4 units, and an average time between patients of 3 units. You are not responsible for parsing of the arguments, nor are you expected to make the program work with incorrect arguments - your program will only be tested with valid integer inputs.

The output of this simulation should look like the following:

If we increase the number of doctors to 2 by running the command:

./Simulation 0 10 2 4 3

we should see the average wait time is decreased significantly:

Note: the random seed will change the arrival time of patients. Running the simulation with the same seed (and all other parameters the same) will produce the same output, while running the simulation with a different seed (and all other parameters the same) will likely produce different output, though not always. For example, running the simulation above with 1 doctor, and a seed of 1120, leads to an average wait time of 2.33. This is because the seed controls the sequence of numbers that are generated as "random" - we use this to reproduce the output and make testing easier.

Note: the program will not compile as supplied, as you will not have the necessary implementation files. You are encouraged to write skeleton files, similar to those in Assignment 1, to allow compilation of an incomplete program - this will allow you to work incrementally.

The Tasks

The first task is to implement templated queue class using a linked list as the underlying data collection. As the purpose of this assignment is to focus on the behaviour of the queue data structure, you are expected to use std::list (std::list - cppreference.com) to provide the linked list behaviour. However, you are not permitted to use std::queue. This avoids being double penalised if your linked list did not work correctly in Assignment 1 and provides valuable experience working with an existing collection from the standard template library.
Next, you will implement the various data classes, namely patient, doctor, and doctors_office that support the simulation. Then, you will implement the simulation class, which executes the simulation. Further details about each class are given below.

LQueue

The LQueue class is a templated queue and should be implemented as discussed in lecture, noting that you are required to use (a pointer to) std::list as the underlying list. For a full list of methods required and some important details, you should examine the lqueue.h file and its associated documentation.

patient
Each patient has a number, arrival time, waiting time, appointment length, and departure time. If we know the arrival time, waiting time, and appointment length, we can determine their departure time by adding these together!

The basic operations that must be performed are as follows: set the patient number, arrival time, and waiting time; increment the waiting time by one time unit; return the waiting time; return the arrival time; return the appointment time; and return the patient number. For a full list of methods required and some important details, you should examine the patient.h file and its associated documentation.

doctor

At any given time, a doctor is either busy serving a patient or is free - we will use a Boolean variable to indicate their status. The doctor also records the information of the patient currently being seen, including an indication of the time remaining for the current appointment.

Some of the basic operations that must be performed by a doctor are as follows: check whether the doctor is free; set the doctor as free; set the doctor as busy; set the appointment time (that is, how long it takes to see the patient); return the remaining time in the current appointment (to determine whether the doctor should be set to free); if the doctor is busy after each time unit, decrement the remaining time in the current appointment by one time unit; etc.

For a full list of methods required and some important details, you should examine the doctor.h file and its associated documentation.

doctors_office
The doctors_office is a wrapper that represents a vector of doctor objects. For the patient at the front of the queue, we need to find a doctor in the list that is free. If all the doctors are busy, then the patient must wait until one of the doctors becomes free.

Some of the operations that must be performed are as follows: return the doctor number of a free doctor; set the doctor to busy when they are seeing a patient; return the number of busy doctors; update the doctor list - for each busy doctor, reduce the remaining time in their current appointment by one time unit. If the remaining appointment time of a doctor becomes zero, set the doctor as free - this should also display an appropriate message (using display_appointment_done(...)). For a full list of methods required and some important details, you should examine the doctors_office.h file and its associated documentation.

Simulation
The simulation is the driver of the simulation and handles the main queueing system logic. To run the simulation, we need to know the length of an appointment and the average time between patient arrivals. For simplicity, we will fix the length of an appointment, which we will supply as a program argument when running our simulation. For the patient arrivals, we will use a random number and Poisson distribution to determine whether a patient arrives at each time step - this adds some randomness to our simulation! Don't worry, the code to do this is already provided for you and you should use the function has_patient_arrived(...) to determine if a patient arrives at the current time step. Note: the argument passed to has_patient_arrived(...) function should be time_between_arrival, not the current time.
The bulk of the effort here will be in implementing the run_simulation(...) function. The general algorithm for this function is as follows:

for (int time = 0; time < sim_time; time++)
{
Update the doctors_office (using update_doctors(...)) to decrement the remaining appointment time of each busy doctor by one time unit.
If the patient queue is non-empty, increment the waiting time of each patient by one time unit. Note: you'll have to get clever here since you don't have access to the individual entries in the queue!
If a patient arrives (i.e., has_patient_arrived(...) returns true), display a message (using display_patient_arrived(...)), increment the number of patients by 1, add the new patient to the queue.
If there is a free doctor and the patient queue is non-empty, remove a patient from the front of the queue, increment the total waiting time, and send the patient to the free doctor. Display an appropriate message (using display_patient_seen(...)).
}

Lab Tasks
In this lab, you will use a Debian (Linux) virtual machine, Visual Studio Code (a text editor for code), and the GCC compiler to write, compile, and execute your first C++ programs.

For installation and usage guides for the virtual machine environment, please see the guide here: VM Installation and Usage.

Instructions for the lab tasks are found in the PDF file below. A ZIP archive is also provided, which contains a starter C++ file (hello. cpp), a ma kef le, and an empty C++ file (program. cpp) that you will use during the lab.

If you have trouble getting the VM to install or work, remember there is also a portable environment that can be downloaded and run from any Windows PC without installation. You may also download and run this environment from a flash drive for a completely portable development environment! See here for further details: Portable Windows Environment.