CISC181, Project 2, Fall 2004

Introduction

This project is about four major ideas:

using object-oriented design (solving problems with classes)
separating large tasks into smaller, more manageable functions (functional decomposition);
using arrays to keep track of various kinds of data that need to be "indexed", i.e. associated with a number;
passing variables and arrays to functions both by value and reference.

This project is based on lab07 and lab10

In lab07, you started with a program tables.cpp and made some modifications to it. The tables.cpp program was a menu-driven program that was designed to help a manager or Maitre D' in a restaurant manage the assignment of guests to tables in the restaurant.

You then revisited this application in lab10, working with an object-oriented approach. You worked with a Restaurant class and a Table class.

In both of these labs, you started with code provided by your instructor, and then added two new features to that program, an "S" option to allow guests to "select" a particular table, and a "T" option to provide the manager with a "total" of how many guests are in the restaurant at a particular moment in time.

In this project you will develop this program further. This project is divided into three stages. Only stage three involves adding new menu options to the program. The following table shows the complete list of options, and at which stage in the development of the program each new option is added.

Option	Explanation	Stage
R	Reserve first avail table	1
C	Clear a table	1
P	Print status of all tables	1
T	Total guests in restaurant	1
S	Select a particular table	1
Q	Quit the program	1
M	Merge tables	3
U	Unmerge tables	3

Reminders about academic honesty

Work independently on this programming project.
Do not work with another student in the class. If you need help, see your instructor or TA during office hours, or make an appointment if those hours are not convenient.
You are expected to be familiar with and comply with the University's policies on academic honesty. Sharing source code with another student, or submitting source code that is not your own (without attribution) is form of academic dishonesty, and will be treated as such.
Submitting someone else's code even with attribution, while not "plagiarism", is nevertheless also inappropriate, and may result in severe deductions or a faling grade, unless you have specific permission from your instructor to use borrowed code.

For example, your instructor might tell you that it is ok to use a function supplied by the TA, code provided by the instructor in lecture, or to borrow some code from your textbook, and use that code as a building block in a larger program. However, if you are not sure, ask. Above all, when you include code in one of your submissions that you didn't write yourself, include a comment indicating the source.

Develop your program in stages

The project is described in three stages. At each stage, you should have a working complete project that you could script and turn in for partial credit. The percentage of partial credit is listed after each stage. (Note: these percentages are cumulative.)

I strongly encourage you to complete one stage at a time, get each stage perfect, and then make a "backup" of your proj2 directory in a tar files before moving on to the next stage. That is, when you complete, for example, stage 1, do the following:

make clean
cd ..
tar cvf proj2s1.tar proj2
cd proj2

And when you complete stage 2 and it is working perfectly, do the commands:

make clean
cd ..
tar cvf proj2s2.tar proj2
cd proj2

That way, if you are in the middle of some stage and find that you have made a mess of things, you can "roll back" to a previous working program and try again. You'd do that by renaming your proj2 to proj2.mess, and untar'ing the backup, for example:

cd ..
mv proj proj2.mess
tar xvf proj2s2
cd proj2

In the end you should only turn in only two files: your proj2.tar file, and a proj2.txt script file showing a script that tests as many of the feature as you've been able to get working at the stage where you stop.

Pace yourself

This assignment is designed so you can pace yourself over several days. You are given fourteen days to complete the project, so starting on the day it is assigned, try to complete at least one stage every two days.

That will leave you several extra days of "slack time" to take a vacation from the project (e.g. over Thanksgiving break!) plus some extra time for any of the stages that take extra time.

Above all, don't wait until the day before the assignment is due to start working. If you wait until then, you'll have no time to go in for help if you get stuck.

A note about the final stage.

Stages 1 and 2 are challenging, but relatively straight-forward. If you understand how classes, member functions, arrays, for loops and while loops work, and follow the directions, you should be able to complete all of these stages with a bit of hard work.

Stage three is different. It is designed to provide an extra challenge for those students that really want to stretch themselves and "go for the A". It is only worth 10% of the project, but is significantly more challenging than the rest.

So, there is no dishonor is stopping after stage four and settling for an A- as the maximum possible grade. However, all students should at least plan to complete through stage two.

Assignment Description

Stage 1: Preliminaries (50%)

Create a proj2 directory, and copy your lab10 code into this directory. These files are your starting point for project 2.

If you were not able to get a satisfactory lab10 working by the lab10 deadline, copy your files over to your proj2 directory, and keep working! Completing the requirements of lab10 in a satisfactory manner gets you half-way through project 2, and is worth 50% partial credit towards project 2.

Stage 2: Adding capacities for tables (90%)

In the code for lab10, every table was assumed to have the same "capacity". The "maxGuestsPerTable" attribute was an attribute of the restaurant class, rather than the table class.

This "fixed table capacity" is a real limitation on the usefulness of this program for a real restaurant. Most restaurants that have waiters and waitresses also have tables of different sizes for different size parties.

For example, suppose that the restaurant named "Harvey's Diner" has 8 tables total: three tables that can hold four guests, and 5 tables that can hold two guests. We might write a data file to represent this called HarveysDiner.dat (shown below).

Listing of HarveysDiner.dat:

Harvey's Diner
8
3 4
5 2

The file consists of one line with the name of the restaurant, followed by a line with the total number of tables, followed by lines that contain count/capacity pairs. For example, this file indicates that Harvey's Diner has 8 tables total: 3 of the tables can seat 4 guests, and 5 other tables can seat 2 guests each.

In this stage, you will modify your software to allow table capacities to be read from a file on the disk. The individual capacities will be an attribute of each table, rather than an attribute of the restaurant object. However, the tables objects are created inside the restaurant object. Therefore, the job of reading this data file belongs to the restaurant object.

The design we'll use is to add a single command line parameter that specifies an input file containing table capacities. After the modifications in this stage, you'll be able to run the program one of the following ways:

> ./proj2 HarveysDiner.dat 3

> ./proj2 ChezPhillipe.dat 4

The first parameter is the name of a data file, containing the definitions of the tables in the restaurant. The second parameter is the number of servers in the restaurant. For this stage, just assume that you always have these two parameters.

You'll pass in this file name and this number of servers to a redefined constructor for the Restaurant class that has the prototype:

Restaurant(const char * const filename);

or the prototype:

Restaurant(const char * const filename, const int howManyServers);

You'll use that prototype in the main by passing in argv[1] or argv[1] and atoi(argv[2]) as follows:

Restaurant r(argv[1]);
OR:
Restaurant r(argv[1],atoi(argv[2]));

What you do in the new Restaurant constructor

Inside the new version of the Restaurant constructor, if you are defining servers in your version of project 2, you'll first set an attribute of the restaurant called numServers to the value howManyServers passed in in the constructor. (If you aren't including support for servers, don't worry about this part.) You'll then declare a local ifstream variable, passing in the filename parameter (which was argv[1] back in the main). You'll make sure the file opened ok, and if not, print an error message and exit the program.

You'll then read data from the file into the objects.

The file will start with one line of text containing the name of the restaurant, and another line with the total number of tables. Each additional line will contain two items: count and capacity:

To read from the file, you'll first use getline to read the restaurant name into a chararcter array, for example:

char restaurantName[40]; /* space for 39 chars and null terminator */

...

infile.getline(restaurantName,40);

The restaurantName variable should be added as a private data member of the Restaurant class. Also note: better style would be to use a "const int" for the size of the restaurant name in the code above, avoiding repeating the number 40 twice. This could be a private data member, for example:

const int restaurantNameLen = 40; char restaurantName[restaurantNameLen];

You can use the restaurantName when printing out the information for the P option.

You can then read the total number of tables into the data member numberOfTables:

infile >> numberOfTables;

Once you have numberOfTables, you can allocate the tables array. You'll then use a loop to read until end-of-file. Each input line contains two integer values, representing count and capacity.

With count and capacity, you'll need to use a for loop to intialize tables in the tables array, calling a new member function of the table class called "setCapacity" on the appropriate tables. For example, inside the loop, to set the capacity of table i to cap, you might do:

tables[i].setCapacity(cap);

As this illustrates, to support this new constructor, several changes are needed as well, as explained below.

Several other change you'll need to support varying table capacities:

This is not necessarily a complete list, but a list to get you started

Add "int capacity;" as a private attribute of the Table class.
Add public methods to your Table class to get and set the capacity. Use "int getCapacity() const;" and "void setCapacity(int cap);" as your function prototypes. Remember that you need to add the prototype in your table.h file, and the definition of these functions into your table.cpp file.
Add another constructor to your Table class with the prototype "Table(int cap);". This constructor should call the "setCapacity(cap);" member function to set the capacity of the object.

Change your Restaurant constructor to have one of the following function prototypes:


Restaurant(const char * const filename); // OR
Restaurant(const char * const filename, const int howManyServers);

Remove "int maxGuestsPerTable;" as an attribute (data member) of the Restaurant class.
Change all the member functions of Restaurant that access the maxGuestsPerTable member. This is a bit more involved, so it gets its own section below called "changing the code to enforce the table capacities".

Put "last chance validation" into your set functions

With the setCapacity function, you could just use:

void Table::setCapacity(int cap) 
{ 
  capacity = cap;
}

However, this misses one of the points of having classes and member functions in the first place. One of the reasons we make capacity a private data member is so that we can protect the value from being set to something wacky such as -17. If we protect the data value right at the point where it is set, then we can "depend" on that data value being valid (in this case, valid means greater than or equal to zero) later on.

So, the set function should enforce the rules on table capacities. The programmer should validate the table capacity data passed into the setCapacity member function and ensure that it is always positive (zero or negative table capacities don't make any sense.) However, it is good style to add a "last chance validation" into your set function, as follows:

void Table::setCapacity(int cap)
{ 
  if (cap <= 0) 
    { 
      cerr << "Fatal Error: " << __FILE__ << ":" << __LINE__ << endl 
           << "Illegal capacity: " << cap << endl; 
      exit(-1); 
    } 
  else 
    capacity = cap; 
}

I call this "last chance validation", because it is the last chance to prevent a bad assignment from messing up our data values.

Note that if the programmer wants to give the user some opportunity to type in a valid number for the table capacity, that kind of error checking (e.g. a loop on "cin" until the capacity value is valid) does NOT belong in a set function, but rather in the code that would call the set function.

Therefore, this code makes entering a bad data value a "fatal error". It uses the pre-defined symbols __FILE__ and __LINE__ (those are two underscores before and after the word FILE and LINE) to print out the name of the source code file and the line number in that file so that in case of an error, the programmer can track down the line of code that produced the error.

Be sure to add similar code into all of your set functions.

Changing the code to enforce the table capacities

As an example of what must change, consider the reserveTable function. Inside this function, there is a loop as follows:
// find first open table for (i=0; i<numberOfTables && table[i].getNumberOfGuests()>0; i++) ; // for loop has empty body;

This code looks for the index of the lowest numbered table where it is NOT true that the number of guests is greater then zero. That is the first "available table". The code then asks for the number of guests.

However, you'll have to turn that around and ask for the number of guests first. Do you see why? The problem is that the first "open table" might be one that doesn't have enough room for the number of guests that are looking for a table.

Instead, you'll need to look through the array for the lowest numbered table where the number of guests is less than or equal to the table capacity. This is known in Computer Science as the "first fit" algorithm.

"Best fit" vs. "First Fit": 5 points are at stake

An even better approach (and one that will earn 5 more points) is to find the table with the smallest capacity that will still have sufficient capacity to satisfy the request. This is known in Computer Science as the "best fit" algorithm. (For "best fit', if there is more than one such table, it doesn't matter which one you choose; for example, it could always be the highest numbered such table, or the lowest numbered such table.)

Some thoughts on the reserve() member function

Note that you have a choice: you can implement the first fit algorithm (which is easier) and give up 5 points, or you can implement the (more difficult) best fit algorithm and earn 5 more points.

Either way is acceptable: as in the real world, there are tradeoffs to be made. Sometimes making your program simpler (albeit less capable) means you can get it to market faster, and make it less likely to contain bugs. The analogous tradeoff in school is that you may need the time to spend on some other subject (or on your personal life, or whatever.)

Now change the other options as needed

After making this update to the reserve() function that supports the R option, you need to think about the member functions that support every other option in the program: C, T, S, etc., to see which ones need to change, and which ones don't need to change. For example, it definitely make sense to add printing out the capacity for each table into the P option. Is there any change that makes sense on the S option or the T option?

Change each option that does need to change, changing the function prototypes and parameters as needed.

A question to ponder about the S option

In the S option, which question should you ask first: "which table", or "how many guests"?

Does it make any difference?

In terms of earning a grade, either order is acceptable, but your choice will definitely impact how you write your code. Which way you ask the questions might make the code easier or harder to write. It would be a good idea to reason out the consquences of both choices on paper before you start typing in your code.

This is just one example of what you need to think about. If you reason each option through before starting to code, and write some "pseudocode", your programming will go more smoothly.

Stage 3: Merging and Unmerging tables (options M and U) (100%)

A reminder: this stage is a real challenge. There is no dishonor is skipping it and taking the A- (90%) as the maximum possible grade (additional deductions may apply for style, etc.). We are deliberately providing less guidance on this option, because we want you to really think about how to implement it. So you might find your instructors and TAs a bit more stingy with help on this stage.

On the other hand, if you come to your instructor or TA with clear ideas about how you plan to implement the option, and just need help gettting your code to work, we'll be happy to help you as usual.

In this stage, you will add two final options, "M" and "U", to support merging and unmerging of tables.

Option M merges two tables together so that more people can sit together. To implement this, you will want to modify your other code as little as possible. (This is good practice, in part because it reduces the chance of breaking something that already works!)

Option U will separate ("un-merge") merged tables and restore them to their capacity before merging.

Here are some considerations for the M and U options:

Any two tables can be merged. When two tables are merged, the new capacity is the sum of the tables' capacity minus one. The new capacity is stored as the capacity of the lowest numbered table. For example, if table 2, capacity 2, and table 3, capacity 4 are merged, then the new capacity is stored as capacity 5 under table 2.
What new attributes and/or member functions need to be added to support this new feature?
After merging, your program should only present the lower numbered table as a viable seating option, with the new merged capacity.
The U ("un-merge") option has to restore tables to their original capacity before merging. This is hard. How will you determine what the capacity of each table used to be? You need to make sure that whatever technique you use to merge doesn't "lose" this information!

Submission Instructions

Scripting your project: make a test plan

You need to create a script called "proj2.txt" showing that all of the features of your program work correctly. In labs 7 and 10, you had practice with thinking about a "test plan" for a program. For this project you are not required to "turn in" a formal test plan, however you should think through a test plan before you script your project, and most likely, you should write this test plan down before you start your script.

Your testing needs to be as complete as possible, covering both legal and illegal inputs. If your program is capable of performing an action, your test plan should cover that action. if your program is capable of detecting an error condition and printing an appropriate message, your test plan should include that case as well.

For example, in addition to testing with the built in "default" table capacities, and the ChezPhillipe.dat and HarveysDiner.dat files (found in the proj2 directory), you should also create at least one data file that would cause the restaurant to have "too many tables" (i.e. more than will fit in your arrays), so that you can show that your code is capable of handing this error condition.

As always, your script should include a listing of your program, a listing of each input file that you use, followed by a clean compile, and your sample runs. Putting the items in that specificorder will make it easier for your TA to grade your project. Making things easier for your TA tends to result in higher marks.

What to submit

Do a make clean, cd to the directory above your proj2 directory, and make a tar file with the command:
tar -cvf proj2.tar proj2
Then do the command "ls -lh" (l as in long, h as in human) to check the size of your tar file in KB; it should be no larger than about 200KB if you did it right (probably a lot less.)
Submit your proj2.tar and proj2.txt files on WebCT
Print your proj2.txt file and give it to your TA.

Grading

The following table indicates, in general, the amount of credit assigned to each portion of the assignment. Your TA might (at his/her discretion, and under supervision of the instructor) further refine each of these items into a more detailed grading rubric. Consult with your TA for more details.

Also note that while 20 points are assigned "overall" to "following instructions" and "coding style", the TAs have the discretion to deduct additional points from the individual portions of the assignment for these issues as appropriate. Deductions may also be made from individual portions of the assignment for "incomplete testing".

Stage	Explanation	Percent	Cumulative Total
All	Following submission instructions	20	20
All	Overall coding style	20	40
1	Lab10 functions (adding S and T to object oriented version of the program)	10	50
2	Adding table capacities	40	90
2	Note: 5 out of the 40 points are reserved for making your R option pick the "best fit" and not the "first fit".		90
3	The M and U options	10	100

Credits: Professors Terry Harvey, Phill Conrad and James Atlas contributed text to the description above, and collaborated on the source code provided. Some of the ideas for features were contribted by CISC105 students from Fall 2004 as part of their lab06 submissions.

*** end of project 2 description ***