Introduction
：
MyInteger.hpp MyInteger.cpp
IntegerSet.hpp IntegerSet.cpp
COMP 2150 Assignment 2 Winter 2018
Due:
February 28th, 2018, before 11:59 pm.
Notes
• Please follow both the “Programming Standards” for all work you submit. Programming standards 1-25
are in effect, but also follow all the specific requirements explained in this document. Marks will be
deducted for not following the programming standards and the guidelines described in this document.
• Any question about the assignment must be posted on the discussion forum on UMLearn, in the
“Assignment 2” thread. Questions sent by email to the instructors will not be answered. You are also
responsible for reading the answers and clarifications posted in the discussion forum.
• Hand-in will be via the D2L Dropbox facility. Make sure you leave enough time before the deadline to
ensure your hand-in works properly. The assignments are submitted using D2L’s time (not the time on
your computer). Assignments that are late will be marked according to the late policy in the ROASS.
• Official test data will be provided several days before the assignment due date. Until then, work with
your own test data.
• All assignments in this course carry an equal weight.
Assignment 2: Event-Driven Simulation (supermarket) in C++
Description
To begin working in C++, you will write a program that will use a discrete-event simulation to simulate
customers getting through the checkout lanes in a supermarket. You will implement two different types
of checkout systems:
(1) Express Lane Simulation: a supermarket that has 1 express checkout lane (for 12 items or less)
and one regular checkout lane each customer that has 12 items or less will always go to the
express lane and all the others will go to the regular lane;
(2) One Waiting Line Simulation: a supermarket that has two checkout lanes (both for any number
of items) and only one waiting line the next customer in the waiting line will go to the first
lane that is ready to serve a customer.
Your program must use two command-line arguments: the first argument will be a filename (the file
will contain a list of arrival events - described below) and the second argument will be a flag (either 1 or
2) which will determine which version of the supermarket to run (run like this for e.g.: a2.exe test.txt 1).
You should be making use of all the facilities for doing OO in C++ that we have covered, including
appropriate use of abstract classes and methods, and safe dynamic casting. For example, the two
different versions of the supermarket simulation should be subclasses of an abstract class which would
contain all the code that is shared between the two subclasses.
While you don’t have to completely follow OCCF standards, you must write destructors to properly free
any dynamically allocated memory that you use. You don’t need to worry about memory allocated in
linked structures that will exist until the end of the program, but anything that is unlinked or goes out of
scope during the course of the program’s run must be properly disposed of.
COMP 2150 Assignment 2 Winter 2018
Each class you define must separate the interface from the implementation. You do not need to
separately compile this program, but you can if you want to. You may also use the make utility if you are
familiar with it, but again, there’s nothing forcing you to do that here.
Details
A data file is used to drive the simulation and will contain only arrival events. The data file will be
ordered by time, so you must have only one event read from the data file in the event queue at any time
(you must not read the full file all at once). The processing of one arrival event must cause the next
event to be read from the file. Each Customer will get an ID number (start at 1) when she arrives, and
each new Customer will have an ID one higher than the one before. You must use a C++ static variable
to keep track of the next Customer number to be generated.
There are three events that can happen in this system:
An Arrival event occurs when a Customer arrives at the checkout lanes. This event will be handled
differently depending on the type of simulation (1 or 2):
(1) Express Lane Simulation: This Customer should be placed into the appropriate queue (regular or
express, depending on the number of items; use a strict FCFS queuing discipline). If no Customer
is currently ahead of this one in the queue, you should schedule a StartService event; otherwise
this Customer will have to wait her turn for service.
(2) One Waiting Line Simulation: If the waiting line is empty and one of the checkout lanes is also
empty, you should schedule a StartService event for the customer. Otherwise, this Customer
will have to wait her turn for service in the waiting line (once again, use a strict FCFS queuing
discipline).
Every time you process an Arrival event, you also must read the next event from the input file, if there is
another one, and add it to the event queue.
A StartService event means the Customer is being served. The length of time it takes to serve this
Customer depends on how many items are in the shopping cart and the types of the items. These
service times (corresponding to the time required to scan the items) are constant (see the table below),
so it is possible to calculate how long a Customer’s service will take, given what is in the shopping cart.
You must schedule a CompleteService event for that time (i.e., for the time the StartService began, plus
the time to complete the service).
A CompleteService event occurs when the Customer’s service has been completed. The Customer will
then leave the supermarket. At this time, you should display a summary of the Customer’s service:
which lane the Customer was in, the arrival time, the completion time, and how much time was spent
waiting in line. The checkout lane is now ready to serve the next customer: you must see if another
Customer is waiting for service, and schedule a StartService event for the next customer if there is one.
You will need to maintain a list of future events in order by time (event queue). During the simulation
process, at any point where the time unit is the same for two events, the Customer that arrived earlier
should be handled first. This means that as the simulation goes on you will be maintaining a list of
pending events that is ordered by primarily by time, but within time, ordered by Customer number.
As mentioned earlier, use a command-line argument to accept the name of the data file, and another
argument to determine which version of the simulation to run (either 1 or 2). Your program should then
COMP 2150 Assignment 2 Winter 2018
open that file and perform. the simulation. This method will allow the markers to easily run your program
on several different data files whose names you do not know ahead of time. Your program should write
to standard (console) output, not to an output file (again this makes things easy on the markers because
they can just read output in a terminal window).
Data file:
The data file contains information on Arrival events only. Each event is on one line of the file. Each line
begins with a positive integer, which is the time of the arrival event. Next is the keyword ARRIVE,
followed by one or more additional pairs of entries, representing this Customer’s shopping cart. Each pair
consists of a String (type of item) and a positive integer (how many are in the shopping cart). You can
assume that there will be a maximum of one pair for each type of item (e.g. you will not see twice SMALL
on one line), but the types of items will not always show up in the same order on the line (SMALL does
not always come first for example). If an item type does not show up on the line, it’s because there is no
item of this type in the cart.
This table lists the possible items that may be in the shopping cart, the amount of time needed to scan
one of that item, and whether or not this type of item will count towards the total number of items (to
determine if the customer can go to the express lane):
Item type Scan time (per item) Counts towards total nb of
items (for express lane)
SMALL 1 yes
BIG 2 yes
FORV (Fruit OR Vegetable) 4 yes
COUPON 5 no
Data Structures
Your data structures must be your own, and you cannot use the C++ standard template library: you must
make generic data structures (for example, a Queue and a PriorityQueue would be useful) using your
own linked structures and making use of C++’s object-orientation features. In particular, you should have
a polymorphic hierarchy of data items to go into generic data structures, and a polymorphic hierarchy of
Events. IF YOU USE C++ ARRAYS, TEMPLATES OR STL DATA STRUCTURES, YOU WILL LOSE MARKS.
Input and output example:
Here is a simple example of an input data file:
1 ARRIVE BIG 12
21 ARRIVE SMALL 2 BIG 3 COUPON 1
36 ARRIVE FORV 2 BIG 4
38 ARRIVE BIG 1 SMALL 14
53 ARRIVE BIG 55 SMALL 33 COUPON 3 FORV 11
75 ARRIVE COUPON 2 FORV 5 BIG 2 SMALL 4
124 ARRIVE BIG 3 SMALL 7 FORV 2 COUPON 10
You should use this simple example to test your program before the official test data is uploaded on
UMLearn (several days before the deadline).
COMP 2150 Assignment 2 Winter 2018
Your program should produce output that indicates the sequence of events processed and when they
occurred in order by time. At the end of the simulation you will produce a simple summary of the
service, waiting and service times. The output of the above example is shown below, for the two types
of simulations.
Output of Express Lane Simulation:
Simulation begins…
Time 1: Customer 1 arrives: BIG: 12 Service time: 24
Time 1: Customer 1 begins service in Express lane
Time 21: Customer 2 arrives: SMALL: 2 BIG: 3 COUPON: 1 Service time: 13
Time 25: Customer 1 completes service in Express lane. Arrival: 1 Complete: 25 Wait: 0
Time 25: Customer 2 begins service in Express lane
Time 36: Customer 3 arrives: BIG: 4 FORV: 2 Service time: 16
Time 38: Customer 2 completes service in Express lane. Arrival: 21 Complete: 38 Wait: 4
Time 38: Customer 3 begins service in Express lane
Time 38: Customer 4 arrives: SMALL: 14 BIG: 1 Service time: 16
Time 38: Customer 4 begins service in Regular lane
Time 53: Customer 5 arrives: SMALL: 33 BIG: 55 FORV: 11 COUPON: 3 Service time: 202
Time 54: Customer 3 completes service in Express lane. Arrival: 36 Complete: 54 Wait: 2
Time 54: Customer 4 completes service in Regular lane. Arrival: 38 Complete: 54 Wait: 0
Time 54: Customer 5 begins service in Regular lane
Time 75: Customer 6 arrives: SMALL: 4 BIG: 2 FORV: 5 COUPON: 2 Service time: 38
Time 75: Customer 6 begins service in Express lane
Time 113: Customer 6 completes service in Express lane. Arrival: 75 Complete: 113 Wait: 0
Time 124: Customer 7 arrives: SMALL: 7 BIG: 3 FORV: 2 COUPON: 10 Service time: 71
Time 124: Customer 7 begins service in Express lane
Time 195: Customer 7 completes service in Express lane. Arrival: 124 Complete: 195 Wait: 0
Time 256: Customer 5 completes service in Regular lane. Arrival: 53 Complete: 256 Wait: 1
… simulation ended.
###### Summary ######
- Total number of customers: 7
- Service time: total = 380, average = 54.2857
- Waiting time: total = 7, average = 1
Output of One Waiting Line Simulation:
Simulation begins…
Time 1: Customer 1 arrives: BIG: 12 Service time: 24
Time 1: Customer 1 begins service in 1st lane
Time 21: Customer 2 arrives: SMALL: 2 BIG: 3 COUPON: 1 Service time: 13
Time 21: Customer 2 begins service in 2nd lane
Time 25: Customer 1 completes service in 1st lane. Arrival: 1 Complete: 25 Wait: 0
Time 34: Customer 2 completes service in 2nd lane. Arrival: 21 Complete: 34 Wait: 0
Time 36: Customer 3 arrives: BIG: 4 FORV: 2 Service time: 16
Time 36: Customer 3 begins service in 1st lane
Time 38: Customer 4 arrives: SMALL: 14 BIG: 1 Service time: 16
Time 38: Customer 4 begins service in 2nd lane
Time 52: Customer 3 completes service in 1st lane. Arrival: 36 Complete: 52 Wait: 0
Time 53: Customer 5 arrives: SMALL: 33 BIG: 55 FORV: 11 COUPON: 3 Service time: 202
Time 53: Customer 5 begins service in 1st lane
Time 54: Customer 4 completes service in 2nd lane. Arrival: 38 Complete: 54 Wait: 0
Time 75: Customer 6 arrives: SMALL: 4 BIG: 2 FORV: 5 COUPON: 2 Service time: 38
Time 75: Customer 6 begins service in 2nd lane
Time 113: Customer 6 completes service in 2nd lane. Arrival: 75 Complete: 113 Wait: 0
Time 124: Customer 7 arrives: SMALL: 7 BIG: 3 FORV: 2 COUPON: 10 Service time: 71
Time 124: Customer 7 begins service in 2nd lane
Time 195: Customer 7 completes service in 2nd lane. Arrival: 124 Complete: 195 Wait: 0
Time 255: Customer 5 completes service in 1st lane. Arrival: 53 Complete: 255 Wait: 0
… simulation ended.
###### Summary ######
- Total number of customers: 7
- Service time: total = 380, average = 54.2857
- Waiting time: total = 0, average = 0
COMP 2150 Assignment 2 Winter 2018
Hand-in
Submit all your source code for all classes. You should also submit three text documents:
• The output of the official test data for the Express Lane Simulation.
• The output of the official test data for the One Waiting Line Simulation.
• Include a README.TXT file that describes exactly how to compile and run your code from the
command line. The markers will be using these instructions exactly and if your code does not compile
directly, you will lose marks.
You MUST submit all of your files in a zip file on UMLearn.
Remember: the easier it is to mark your assignment, the more marks you are likely to get. Do yourself a
favour.