University of Toronto
CSC148--Introduction to Computer Science, Spring 1997
C++ Assignment 3:
Object-Oriented Simulation

 
Due:    Thursday April 10th, 6:00 p.m.
Weight: 13% of your mark in this course

Students often complain that assignments seem unrelated to the real world. Guess what: this one is related.

The purpose of this assignment is to teach you about object-oriented programming, to give you some more practise writing recursive code, and to give you experience working on a ``real'' program. We will provide a very large program that already runs; your assignment will be to modify it in various ways. On assignment 1 you had the experience of working with someone else's code. This time, the code is quite a lot larger - over 2,500 lines long. Some of you won't like working with such a large program, particularly one written by someone else. In industry, however, maintaining, extending, and rewriting someone else's code is much more common than writing a program from scratch, and it is something that you need to be able to do.

As you start to look at the code, you will inevitably notice shortcomings, particularly in the comments. Documenting a program this large and complex so that it will be easy to read is very difficult. And keeping comments up to date in a changing program is notoriously difficult.

You will find it virtually impossible to understand the assignment 3 code by thinking of all the details at once. Luckily, you are all now wonderfully well-versed in abstraction, and will have little trouble working only with the interfaces to the classes whenever possible.

We have designed this assignment carefully, so that it will be doable despite the size of the program. The code you will start with already runs, and so provides a good starting point. The tasks which we have laid out for you are all quite modest, and they do not rely on each other. They can therefore be done in any order. Getting stuck on one should not prevent you from completing the others. Part 1 of this assignment can be done without knowing very much about object-oriented programming, and before digesting much of our code, so it is a good place to start.

A note about C++: The King textbook and my lectures will give an overview of some of the key object-oriented features of the language, as well as the more mundane aspects of how it differs from C. However, you may find some bits of code that use C++ features we haven't discussed. If so, please bring it to my attention and I'll give an explanation in class and/or on the web.  

Introduction

Have you ever stood waiting for an elevator and tried to figure out how it decides where to go next? (And why it hasn't come to get you yet!) If it has nothing to do for a while, where should an elevator wait? At the ground floor? Near the middle of the building? If a bunch of people on lower floors and just one person above have requested an elevator, should the elevator go up to get that one person while it's in the vicinity, and keep all the others waiting? One way to figure out what algorithms make the most sense is to run a simulation and take some measures of performance -- average time waited by passengers, for example.

We are providing you with a large program that does exactly that. The program is event-driven, meaning that we keep track of events that we know are going to happen in the future, and the simulated clock moves ahead in leaps according to the time of the next event. The events are kept in a priority queue, so that events are sorted according to their time-stamp and events with the same time-stamp are in first-in-first-out order. This means that whenever we dequeue an event, it is the one that should occur next.

Note that we don't all at once queue up every single event that will happen in the future. We don't have to, because some events will themselves cause other events to be created and added to the queue.

The program's input and output

The program requires no input. However, optional ``flags'' can be used to select various settings for the program. For example, the default number of floors for the simulation is 5, but you can use a flag to select a different number. The flags you are most likely to use are -t and -i. The -t flag chooses text mode rather than graphics. This will be helpful when testing because it provides more detailed feedback on exactly what is happening. You can also use this mode for producing test runs on paper, and for running at home, where you don't have the required graphics library. The -i flag is used with a number (for example, -i 5). In graphics mode, it will change the interval at which the image is redrawn. Choosing a higher interval time will make the animation a bit more jerky, but it will run faster. If you run the program with an unrecognized flag, the list of accepted flags will be displayed. (Or you can look at function display_help in file main.C to find out what the accepted flags are.)

Output is a graphical animation of the elevators and people going up and down, as well as some simple performance statistics. If you run the program in text mode (using the -t flag), output is a running commentary on what is happening.

Pick up the code from the course web site and run it. (See the web site for instructions.) When working at home, you will have to run the program in text mode. Neat, eh?  

Architecture of the program

The program is broken up into the following classes, each of which is quite small:

class Person:

Keeps track of a single person. There is also an Impatient Person class, which is derived from Person. In part 3 of this assignment, you will add some additional types of people.

class List:

A general class for keeping lists of people. Used by the Floor and Elevator classes.

class Floor:

Uses the List class to keeps track of the people waiting on that floor for an elevator.

class Elevator:

Uses the List class to keep track of the people on that elevator. Also keeps track of info about where it is going, at what rate of acceleration, and so on.

class Controller:

Is in control of all of the elevators. Keeps track of all requests for an elevator in the building, where all the elevators are, which direction they're going in, and what floors they're going to. Also decides where the elevators will go. The elevator algorithm is embodied by this class.

class EventPQ:

A priority queue of events that we know are going to happen in the future.

class Event:

The general class called Event defines those things all events have in common: a time-stamp, a way of printing information about themselves, and a way of ``handling'' themselves -- instructions for what to do when their turn comes up. The specific kinds of events (like ElevatorArrival) are all classes derived from Event. Your extensions in Part 3 may lead you to add a new type of event.

class Scheduler:

This class keeps the event queue, and is called by any code that needs to add events to the queue, remove events from it, or handle events.

class Stats:

Keeps some performance statistics and is capable of reporting on them.

main program:

The main program. It declares and initializes things. Then it runs a main loop that, on each iteration, takes the next scheduled event from the event queue and handles it.

classes Graphics and OpenGL:

These take care of graphics. For the purposes of this assignment, you can probably ignore these classes completely. (Of course, out of curiosity, you may want to see how things are done.)

Your assignment

Your assignment consists of 4 parts. As stated above, these are not dependent on each other, and can thus be done in any order.

Get the program from the web site and run it a few times to see what it does.

Then read the rest of this handout. You will probably not understand everything that we say the first time through, so expect to go over it a few times, and to have lots of questions for us.

Hand in:

• The amount of time you spent on this part of the assignment.

This step involves only the List class, and can be done before you know much about the rest of the program or about object-oriented programming.

Re-implement the given List class using a binary search tree ordered by person index, rather than the current structure (an unsorted, doubly-linked list with sentinel). Be sure not to change the interface to this class at all; your new version should be capable of running in the context of the simulation.

Before starting this re-implementation, you may find it helpful to work through the comments and questions from Part 2 of the assignment that pertain to the List class.

To test your new implementation, write a small driver program. It is your job, in your testing, to provide evidence that will thoroughly convince the grader that your revised List class works. If you hand in no test runs, or poor testing, you will get few or no marks for correctness of your class. (Note that you will not be required to hand in thorough testing for the code you write in the other parts of this assignment.)

The List class is not large, so there is not much code to re-write. However, at least one of the functions will require some clever recursion.

Hand in:

• a printout of your revised List class
• a printout of your driver program
• a written description of your testing strategy
• annotated test runs that show how you applied your testing strategy
• a short sample run of the simulation (in text mode) with your revised List class, to show that your revised List class does run in the context of the simulation.
• The amount of time you spent on this part of the assignment.

The purpose of this step is to help you get familiar with this very large program. It takes you through some of the code, pointing out interesting things and asking a lot of questions. You are to hand in answers to only those that are labelled Hand-in questions. The questions do not require elaborate answers.

First, print out the code. (It is long, so print double-sided if you can, and don't print it more than once. You won't need to look a the Graphics or OpenGL classes, so there is no need to print them.) Highlight the interface of each class. As you begin to look at the code, try at first to focus as much as possible on these interfaces. Although the program is very long, the class interfaces are not.

Look at the interface for the Person class. Public member functions for a person allow one to signal a person to let them know an elevator has arrived (which will cause them to get on or off that elevator, if appropriate); to handle a person's initial appearance at the elevator (which will cause them to be added to the list of people waiting on that floor, among other things); to find out the person's number (also called their ``index'' in the program); to draw them graphically; and to print info about them. There is also a ``constructor'' function. What does it do? Notice that signal_arrival and most of the other public member functions for Person are ``virtual'' functions. This means that a class derived from Person may complete the function (if it was only declared but not defined in Person) or override it (if it was actually defined in Person). Hand-in question: Why is it that signal_arrival is a virtual function, but index is not?

Look at the data members for Person. They keep track of things like the person's number (for identifying them), when they started to wait for an elevator (useful for later determining how long they had to wait for an elevator); what floor they started on and what floor they were going to. These data members are ``protected'' rather than ``private''. This means that other classes cannot look at them directly, but derived classes (like ImpatientPerson) do inherit them. Notice that the Statistics class is declared to be a ``friend'' of the Person class. This allows Statistics to have direct access to these data members.

Now look at the interface to class ImpatientPerson. Notice that it has an additional data member for keeping track of information that is only relevant to impatient people. So this class extends the Person class. This class also overrides the Person class by redefining function signal_arrival. Hand-in question: In what way is an ImpatientPerson's behaviour different from a Person?

Now look at the List class. It makes use of a LNode class for creating individual nodes. Every LNode has next and previous pointers (so it can be part of a doubly-linked list), and a data field that points to an instance of Person. This means that it can be used to make linked lists of people only. It would be nicer to have a List class that could make lists of anything, and this can be done in C++ using templates.

The public member functions of class List allow one to empty a list, get out the next element after any particular one, print the list, or add or remove a given person. There are also constructors and destructors. There are no operations for adding or removing by position in the list. In fact, this class resembles a set ADT more than a list.

A List has one private data member: a ``sentinal'' node. This is a sort of dummy node. Look at the implementation of the List class to see how the sentinel works. Draw a diagram showing how an empty List is represented. Hand-in question: Draw a diagram showing how a List would look if it had 3 nodes in it (plus the sentinel).

Look at the Floor class. It has a private data member for its own floor number, and an instance of the List class for keeping track of all the people waiting on that floor. It also has some private data members for storing information used by the graphics code; you can ignore that. Look at the implementation of signal_arrival_to_attendees. See how it uses the List class's getNext XXX function to loop through the people waiting. For each person, it calls their own signal_arrival function so that they can the decide what to do about the fact that an elevator has arrived. Look at function schedule_next_appearance. When called, it will figure out at what time the next person should arrive on this floor (using a given statistical distribution and a random number generator). It then creates a PersonAppearance event and adds it to the event queue. The main program is responsible for scheduling the very first appearance. Look at the main program. Hand-in question: How many appearances does the main program create initially? After such things are set up, the main program has a loop that dequeues and handles events until there are no more. Find that loop.

When a PersonAppearance event comes out of the queue, its own PersonAppearance::handle_event function creates a new Person (randomly chosen to be either a regular Person or an ImpatientPerson). Look at the code to see how this is done. Notice that the last thing this function does is schedule the next PersonAppearance event. This ensures that people will continue to appear.

Take a close look at the Event class, and the specific subclasses derived from it (PersonAppearance etc.) Every event must have a time, so this is declared in the Event class. But each subclass of Event has its own additional data members for keeping track of other information it must know. For instance, a PersonAppearance must know the floor the person is appearing on and the floor they want to go to. The constructors for each of these subclasses just set these data members. The code is very simple, so it is written ``inline''. Each subclass of Event also has its own handle_event function. Obviously, these functions have to be different from each other. Take a look at what the various handlers do. After handling the event, some of them schedule the next time this sort of event should occur. All of the handlers for elevator-related events call another class to actually handle the event. Hand-in question: What class do they call? Think about why they do not handle elevator-related events themselves. This is a design issue.

Look at the EventPQ class and figure out the data structure it uses. Draw a picture of it. The dequeue function deletes something from memory. Hand-in question: How can it delete, given that it has to return the dequeued item?

Look at the interface to the Elevator class to see what kind of operations it provides. Each instance of Elevator can tell you its index; these numbers are used as array indices by the Controller class (see below). Look at function add_person, which is called when a person gets on the elevator. It calls add_data. What class is that function from? Function remove_person is to be called when a person gets off the elevator. Trace what happens. There is a ``memory leak'' -- some data that should be deleted from memory is not. Hand-in question: Identify the memory leak.

Notice how the Elevator's handle_arrival_at_floor function calls signal_arrival_to_occupants, which loops through the people on the elevator so that they can decide whether or not to get off. This is analogous to what Floor's signal_arrival_to_attendees function does.

The Controller class directs the behaviour of all of the Elevators. Look at the four small data structures that it uses to keep track of things. Draw a diagram of these structures, and make sure you understand what they mean. What are the initial values of each of these data structures? What function will tell you this? Function update_destinations is called when an elevator gets to a floor, so that it can decide what floors that elevator should head to next. Look at the code to see how it does this. Write a better comment for the first for-loop under the first case labelled ``UP''.

Hand in:

• written answers to the hand-in questions above.
• The amount of time you spent on this part of the assignment.

Currently, there are two types of people in the simulation: ordinary people and impatient people. Here, your job is to add more types of people to the simulation.

First, add a Claustrophobic class. Claustrophobics are just like other people, except that they won't get on the elevator if there are too many people on it. You may choose some arbitrary comfort threshold for your claustrophobics. Declare a global variable for this in the main program, where other simulation variables are set.

Then make up two other subclasses of Person, each with significantly different behaviour. This is a chance for you to be creative and have fun.

To add a new type of person you must:

• Define a new class that is derived from Person. Add new data members, add new functions, or override existing functions as appropriate.
• There is an enumerated type called PersonType in the header file for class Person. It is a list of the kinds of people (currently just. NORMAL and IMPATIENT). Add a new one to this list.
• The class for PersonAppearance events (a class derived from the general Event class) takes care of creating a random new Person or ImpatientPerson. Modify this function so that it can create a person of your new type.
• Depending on what kind of people you choose to add, you may need to create additional kinds of Event.

For each of your new person types, add its class into the existing file that already contains the Person and ImpatientPerson classes. If you add any new event types, add them into the file that already contains the other event types.

Hand in:

• printouts of your new classes. Your comments on each new class should clearly explain how it is different from the other types of people.
• a sample run (in text mode). You needn't do thorough testing. Just give an example that shows your code for your new types of people does run, and that these people do behave differently.
• a written description of any bugs or other flaws in your new classes that you have not been able to fix. If there are none, say so.
• The amount of time you spent on this part of the assignment.

You may have noticed that the elevators don't operate in a very efficient manner. Your task here is to improve on this. To do so, you will have to modify the Controller class, since it controls the movement of elevators. In order to see if your improvement really did improve things, you can look at how the average trip time changes.

There are many ways you might improve the elevator control. We are not looking for any one particular change, or any particular level of improvement in the performance statistics.

Hand in:

• A short written description of why the current controller algorithm is poor.
• A short written description of your idea for improving it.
• A printout of your modified Controller class. Hightlight the exact lines of code that were changed.
• A sample run (in text mode) Again, you needn't do thorough testing. Just give an example that shows your modified controller code does run, and that the elevators do behave differently.
• The amount of time you spent on this part of the assignment.

Some Advice

Here a a few tips to help you avoid problems with C++:

• The relationships among all of the files have been carefully arranged through include statements, and the Borland project file. Do not add any files to the program, or you may interfere with these relationships. All of your code can be added to existing files.
• Also, do not change any of the include statements.
• As you go through the stages of the assignment, keep a history of previous working versions of the code, in separate project directories. If you run into problems, you can back up to a working version and add back your most recent changes one at a time. This will help you find the problem.

How to submit your assignment

This assignment is to be handed in completely on paper. Do not hand in a diskette.

To help the marker identify the parts of your assignment, staple each part, and include a front page that identifies which part it is.

As always, put everything into an 8.5 by 11 inch envelope. The cover sheet provided here (or a photocopy or facsimile of it) must be filled out, signed, and taped to the envelope containing your assignment.  

Draft grading scheme

Below is the grading scheme that we currently expect to use. It may be changed somewhat as the assignment unfolds, but should give you an idea of where to focus your efforts.

 
Part 1: Revised List class
	Does it work? 		 			20
	Testing strategy and annotated test runs 	10
Part 2: Answers to hand-in questions 			10
Part 3: Extended class hierarchy 			30
Part 4: Improve the elevator control 			15
Programming style 		 			5
Comments 		 		 		5
Overall quality of writing   		 		5
TOTAL                        		 		100

Credits
Thanks to Professor James Stewart for allowing us to use his simulation code for this assignment.