CISC105, Project 2, Fall 2004

Introduction

This project is about three major ideas:

This project is based on the tables.c program from lab06

In lab06, you started with a program tables.c, and made some modifications to it. The tables.c 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 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 five stages. Only stage five 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 2
C Clear a table 2
P Print status of all tables 2
T Total guests in restaurant 2
S Select a particular table 2
Q Quit the program 2
M Merge tables 5
U Unmerge tables 5

Reminders about academic honesty

Develop your program in stages

The project is described in five 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.c file before moving on to the next stage. That is, when you complete, for example, stage 1, do the command:

cp proj2.c proj2s1.c

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

cp proj2.c proj2s2.c

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.

However, in the end you should only turn in only two files: your proj2.c 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 four extra days of "slack time" to take a vacation from the project, or in case you need extra time for one of the stages.

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 through 4 are challenging, but relatively straight-forward. If you understand how arrays, functions, 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 five 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 four.

Assignment Description

Stage 1: Preliminaries (0%)

Create a proj2 directory, and copy your lab06.c from lab06 into a file called proj2.c in this directory. This file is your starting point for project 2.

Stage 2: Factoring the existing options into functions (30%)

In the directory proj2 there are two files called tables1.c and tables2.c.

The tables1.c program was written by Prof. Conrad, who acknowledged in one of the comments that the program did not have "the best style"; in particular, a problem with tables1.c is that the main() function is too crowded. Each of the cases in the switch statement contains a long block of code. It would be better to factor these out into separate functions.

Prof. Harvey took on this challenge, and wrote an improved version of Prof. Conrad's program called tables2.c, illustrating this idea, which is known as functional decomposition. To arrive at the tables2.c program, Prof. Harvey decomposed a larger, complex program into several smaller functions. Each of these smaller functions is easier to understand when it is separated off by itself.

Sometimes this is called factoring; just as you might factor an equation such as f(x)=x2 - 2x -35 into the factors (x+5) and (x-7), you can talk about "factoring" a function like the main() in tables1.c into several smaller functions such as fillFirstOpenTable() and clearTable().

With that introduction, you should now compare the two files in detail.

What you are looking for is the differences between these files; in particular, the fact that each of the "options" in the switch statement of the main program is handled by a separate function. It may help to bring up two windows side by side, and in one window, type "emacs tables1.c" and in the other "emacs tables2.c". That way, you can see both files side-by-side, and compare them. Or, you might want to print out both files and look at the printouts side by side.

You are going to make the same changes in your own proj2.c file. Here's what you'll do:

When you are finished with this step, your proj2.c file should have all the same functions as your lab06 file, but the main will be more concise and easier to read.

Stage 3: Adding capacities for tables (40%)

In the original tables.c program, every table was assumed to have the same "capacity"; that is, the maximum number of guests which can sit at a single table. This maximum capacity which was controlled by a #define. Before you continue to read, look at your code for proj1.c, and locate this #define. Then, look through your code and find all the occurences of this #define, and see how it is used to enforce table capacities. Familiarizing yourself with this up front will make the rest of this stage easier to understand.

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. In this step, you will enhance the program to be able to support having tables with different capacities.

You will add a new array called tableCapacity, which has the same size as the tables array, with initial values as follows:

   /* the following line goes outside your main */
  #define NUM_TABLES 6
  ...
  /* the following line goes inside your main */
  int tableCapacity[NUM_TABLES] = {2, 2, 4, 4, 6, 6};

The idea is that table 0 has capacity 2, table 1 has capacity 2, table 2 has capacity 4, etc.

Adding this line of code is not difficult. What is challenging is figuring out now what else must change in the code as a result.

Changing the code to enforce the table capacities

As an example of what must change, consider the fillFirstOpenTable function. The way it was written in the code you were given is that there is either a while loop such as the following one from Prof. Harvey's version:

  while(tableNumber < NUM_TABLES && tables[tableNumber] > 0)
    tableNumber++;

or an empty for loop as in Prof. Conrad's version:

  for (i=0; i<NUM_TABLES && table[i]>0; i++)
        ; /* for loop has empty body; */

Regardless of which version you use, the idea is the same: look 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 (represented by "guests" or "numGuests", depending on which version of the code you used as a base) 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.)

Passing tableCapacity into the fillFirstOpenTable function

You'll also need now to pass the tableCapacity array in as a parameter to the function fillFirstOpenTable(). The new function prototype will look like this:

void fillFirstOpenTable(int tables[], int tableCapacities[]);

Please note that you are NOT permitted to "get around" this by making the tableCapacities array a global variable. (See "style issues" section near the end of this project description).

Some thoughts on the fillFirstOpenTable function

(Note: Profs. Harvey and Conrad might take some final exam questions from the discussion in this section)

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.)

However, if you do implement the best-fit algorithm: think about this: should the name of the function still be "fillFirstOpenTable"? If not, what would a better name be?

Suppose you changed the algorithm, but didn't change the name of the function. What kind of problem might result?

This happens all the time in the real world: a programmer changes what a function does, but doesn't change the name of the function or the comments to reflect this change. This creates major barriers for subsequent generations of programs that have to maintain the code.

Now change the other options as needed

After making this update to the fillFirstOpenTable() function, you need to think about 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 4: Reading capacities from a file (50%)

In stage three, you added capacities. However, these capacities are "hard coded"; that is, the number of tables is fixed at 6, and the capacities are established by the array intializer (i.e. {2, 2, 4, 4, 6, 6}; ).

Your program will be more flexible if you allow the table capacities to be read from a file on the disk. That way, you can define different files for different restaurants. You'll be able to use the same piece of software, and without changing the source code or recompiling, change the table capacities just by reading in a different input file.

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 using any of the following forms:

> ./proj2 HarveysDiner.dat

or

> ./proj2 ChezPhillipe.dat

or

> ./proj2

In the first case, the parameter HarveysDiner.dat specifies the name of a file containing capacity information for a restaurant called "Harvey's Diner". (We'll discuss the format of that file shortly, but in brief, that file indicates how many tables there are at Harvey's diner, and what the capacity of each table is.) In the second case, the parameter ChezPhillipe.dat specifies the name of a file containing capacity information for a different restaurant. Finally, the stand-alone form of the command specifies that the program should use the default capacities that you already defined in stage 3.

Explanation of the file format

The file will start with one line of text containing the name of the restaurant. Each additional line will contain three items: count, capacity and table_type, as shown below.

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

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

...

fgets(restaurantName, 40, infile);

(Note: Better style would be to use a #define for the size of the restaurant name, avoiding repeating the number 40 twice.)

You'll then use a loop to read until end-of-file. Each input line contains two integer values, representing count and capacity.

To understand how to interpret count and capacity, consider the example data file HarveysDiner.dat listed below.

Harvey's Diner
3 4
5 2

The first count/capacity pair is 3 and 4. This means that there are three tables, each of which can seat 4 guests. The second count/capacity pair is 5 and 2, meaning that there are 5 tables that can each seat only 2 guests.

Therefore, when you are finished with reading in this data file into the tableCapacity array, the contents of the array should be as follows:

tableCapacity[0] 4
tableCapacity[1] 4
tableCapacity[2] 4
tableCapacity[3] 2
tableCapacity[4] 2
tableCapacity[5] 2
tableCapacity[6] 2
tableCapacity[7] 2

Here's another example:

Chez Phillipe
2 6
2 4
3 2
2 4

This file would result in a tableCapacities array as follows:

tableCapacity[0] 6
tableCapacity[1] 6
tableCapacity[2] 4
tableCapacity[3] 4
tableCapacity[4] 2
tableCapacity[5] 2
tableCapacity[6] 2
tableCapacity[7] 4
tableCapacity[8] 4

Note that the number of tables is determine by the total of all the capacities. Therefore it can no longer be a #define. We will still use a #define to set the maximum number of tables that can be in the restaurant; this quantity, called TABLE_MAX, defines the size of arrays such as table, tableCapacities, etc. However, we will also need a variable, numTables, that can be set to the correct number of tables based on the input in the data file.

This creates an additional challenge: Just as you had to determine which functions to pass the tablesCapacities array to, you will now have to determine which functions you must pass the numTables variable to.

Step-by-step instructions for this stage

  1. Change #define NUM_TABLES 6 to #define TABLE_MAX 50
  2. Use TABLE_MAX instead of NUM_TABLES as the size of your table array. Consider which other array(s) need to change in a similar fashion, and change their definitions as well.

    Note: It will not always be the case that you will have 50 tables in the restaurant. However, the size of the array will always be 50. When there are fewer than 50 tables, the remaining spaces in the table array (and other arrays such as tableCapacity) will just be ignored.
  3. Add another variable in the main called "numTables". This variable will be set to 6 by default, to match the array initializer (i.e. {2, 2, 4, 4, 6, 6}; ). The idea is that if you don't specify an input file, the program will assume a default configuration of 6 tables with the capacities given in the array initalizer for tableCapacity. Specifying an input file on startup overrides these capacities.
  4. Set the main up to accept command line parameters by changing int main(void) to
    int main (int argc, char *argv[])
  5. Near the start of the program, check the argument count. If it is 1, then set numTable to 6, and proceed with the program under the default table capacities given in the array initializer. If it is 3 or more, then print an error message indicating that the proper usage of the program. If it is 2, then use the first parameter as the name of an input file. Put in code to open the file, and also to print an error message if the file can't be read.
  6. Add the code to read the values from the input file into tableCapacities. You should factor this stage out into a separate function. You should pass in the FILE * variable for the input file, and the tableCapacities array. You will also need to either (a) return an int value that you assign to numTables in the main, or (b) make this a void function, and pass the numTables variable "by reference." (your choice.)

    Note that as you read data from the file, you should check the error condition that the data file specifies more tables than you have room for in the array. Since TABLE_MAX is a #define you'll be able to access that inside your data reading function without having to pass it in (global constants are not a style problem, only global variables.)

    Assuming that you called the FILE * variable for your input file "infile", the following code will read the first line of that file into a variable called restaurantName. Actually, it will only read up to 39 characters into that variable (think: why 39 and not 40?)

    You can then use that variable along with the %s format specifier to print out the restaurant name throughout the program, as shown:

    7. char restaurantName[40];
    ...
    fgets(restaurantName, 40, infile);
    ...
    printf("Number of guests at %s is currently %d\n",
       restaurantName, numGuests);

    (Question to consider: why "up to 39" and not "up to 40"? )

  7. You'll need to change some of the references to NUM_TABLES to numTables, and possibly pass that variable into some of your functions.

Stage 5: 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:

  1. 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.
  2. What should be stored in the "table" array for table 3? In the "capacity" array? Do you need to add a new array to support the "merge" capability or are the current arrays sufficient?

    To answer, consider (a) when the program looks in the table and tableCapacity arrays, and (b) what you need the program to do when it looks in those arrays.
  3. After merging, your program should only present the lower numbered table as a viable seating option, with the new merged capacity.
  4. 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 lab06, 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, 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

Style Issues

In addition to the style rubrics made available by your instructor and/or TA, there are two style points that we want to emphasize in this project (and subsequent labs/projects in this course.)

You may not use programmer-defined global variables to avoid parameter passing.

As an example, consider the problem that the fillFirstOpenTable() function needs access to the tableCapacities array. There are two ways to accomplish this: (1) add tableCapacities as a parameter to fillFirstOpenTable(), or (2) make tableCapacities a global variable. However, option (2) is prohibited to you, even though it is legal C syntax, and it would "work". Why is this?

Admittedly, it is much more work to add tableCapacities as a parameter to the fillFirstOpenTable() function and all the other functions that require access to the tableCapacities array. Making it a global variable might seem "more efficient" in terms of programmer effort. However, this is a short-sighted view.

Global variables are a "short-cut" that can become a very bad habit. Programs that are built on global variables do not "scale well"—that means, that as they grow, they become harder and harder to manage. The problem is that global variables do not enforce the principle of least privledge, which is a very important concept in Computer Science, Computer Security, and in life in general. This principle says: don't give access when it is not needed.

An example of this principle is the "valet key" that comes with many cars. The "valet key" opens the car, and will start the car, but will not open the trunk. That way, a valet that parks your car is not "tempted" to investigate or (perhaps steal from) the contents of your trunk. By removing temptation, the valet key "keeps honest people honest". It also helps to remove suspicion from innocent people: if something turns up missing (perhaps because you just misplaced it), you don't have to suspect the valet if you know that he/she had no access to your trunk.

In the same way, suppose you follow our directions, and only pass the tableCapacities array as a parameter to the functions that need that access. Then, if at some point, the tableCapacities array is "messed up", the "suspects in the crime" are limited to only the main function (where tableCapacities should be defined), and the functions to which you pass tableCapacities as a parameter. If you choose the alternative, making tableCapacities a global variable, then every function in your program is a suspect in the crime. This makes debugging more difficult.

In this way, avoiding global variables enforces the "principle of least privledge" and makes large programs easier to maintain. Programs written in this way "scale better".

Our experience shows that in spite of this compelling teaching, many students are nevertheless unable to resist the temptation of the quick fix of global variables. The short term gain of writing the code more quickly is just too tempting. As a result, they get hooked on a bad habit that plagues them throughout their programming career. They usually wise up too late: after they have built a large project based on global variables, and found it impossible to debug. Too frequently, this happens sometime in the student's junior or senior year, or more tragically, when the student is a programmer in the "real world" with a paycheck and a mortgage at stake.

Therefore, to encourage you to follow the "right path", we are going to put a big disincentive in your way if you choose the "wrong path" of global variables. The TAs will be instructed to make severe deductions of 25% or more from any programs that use programmer-defined global variables to avoid passing parameters to functions.

You may not be lazy when defining function prototypes

Consider the following two examples of function prototypes: 

void findBestAvailableTable(int [], int, int );

versus:

 void findBestAvailableTable(int tables[], int numTables, int numGuests);

The second form of the function prototype is much more useful. Without the variables names, it is impossible to know from the prototype whether the function is written as 

void findBestAvailableTable(int tables[], int numTables, int numGuests);

versus:

void findBestAvailableTable(int tables[], int numGuests, int numTables);

(Note the fact that the numTables and numGuests variables are swapped between the two versions.)

There are two points to make here:

  1. It is true that from the standpoint of the compiler and the executable code, there is no difference between including the variables in the function prototype, and not including them. (Of course that is true of comments as well, and we all know that comments are absolutely necessary to a well-written program.)
  2. The same programmer who writes the function definition usually writes the function prototype as well. The function definition must contain variables names, so with a simple "cut and paste", a function prototype with variable names can be written with a few keystrokes.
  3. Programmers are notoriously lazy about writing documenation. Sometimes the function definitions are not available to the programmer using a function (only the object code is available). The function prototype must always be provided in such as case, for example, in a header file. If the function prototype provides at least some documentation about how to use the function, the programmer using the function has a much better chance of using the function correctly.

So, with very few keystrokes, a programmer can do something that is very helpful to programmers maintaining his/her code. To not include the variable names in a function prototype seems a most contemptible form of laziness.

Unfortunately, many textbook authors use the "short form" (lazy form) in order to save space in their examples. We are concerned that students will get the impression that this is an acceptable style in their own code.

Therefore, to re-enforce this style point, deductions will be taken as a penalty for anyone using the "lazy" form of function prototypes.

One final point: taking a function prototype such as:

void findBestAvailableTable(int [], int, int );

and rewriting it as

void findBestAvailableTable(int []a, int b, int c);

complies with the "letter of the law", but violates the "spirit of the law". To be in compliance with this style point, your variable names must actually convey useful information to the user of the function. Variable names "a,b,c" would be acceptable as coefficients in a quadratic equation, just as "x,y" would be acceptable for coordinates in a cartesian plane. In the case of findBestAvailableTable, (a,b,c) are just as useless as no variables names at all, and would be treated as such for grading purposes.

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
2 Factoring existing lab06 options into functions 10 50
3 Adding table capacities 20 70
Note: 5 out of the 20 points are reserved for making your R option pick the "best fit" and not the "first fit".
4 Reading table capacities from a file 20 90
5 The M and U options 10 100

Penalties (this penalty are like a "tax" applied to your grade after deductions taken above)

Credits: Professors Terry Harvey and Phill Conrad 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 ***