Restaurant Waiting List System

For this lab, write a C program that will implement a customerwaiting list that might be used by a restaurant. Use the base codeto finish the project. When people want to be seated in therestaurant, they give their name and group size to the host/hostessand then wait until those in front of them have been seated. Theprogram must use a linked list to implement the queue-like datastructure.

The linked list is to maintain the following information foreach group that is waiting:

? name (we assume a maximum name length of 30 characters)

? group size

? in-restaurant status: whether the group has called ahead or iswaiting in the restaurant

The system does not take reservations for a specific time anddate (i.e. table of 4 for 7pm on Saturday), but it will allow for agroup to call ahead and get their name on the waiting list beforethey arrive. Note: these call-ahead groups will still need to checkin when they arrive so the host/hostess knows they are waiting inthe restaurant.

Groups are added to the wait list when they call-ahead or whenthey arrive at the restaurant. Groups are always added to the endof the wait list. The system will require that each name used beunique. So when a group is added to the wait list, the system mustmake sure that no other group is already using that name.

When a table with N seats becomes available in the restaurant,the system returns the name of the first group that is in therestaurant and can sit at a table with N seats (i.e. the number ofseats at the table is greater than or equal to the number of peoplein that group). Note that the group selected may not be the first(or even the second or third) group on the wait list.

This program will NOT keep track of how many tables therestaurant actually has, nor how many people can sit at each table.The host/hostess is expected to know that information and willenter the appropriate values when needed.

The commands used by this system are listed below and are tocome from standard input. Your program is to prompt the user forinput and display error messages for unknown commands or improperlyformatted commands. Note that the name of the group when given willbe given as the last item on the input line. The name of the groupmay contain white space characters in the middle of the name butnot at the beginning or end of the name. Each command given mustdisplay some information about the command being performed. Code toimplement this interface is provided in the programproj4base.c.

Command	Description
q	Quit the program.
?	List the commands used by this program and a brief descriptionof how to use each one.

CS 211 – Programming Practicum Fall 2015

a	Add the group to the wait list using the given group size andname specifying the group is waiting in the restaurant. The group’sinformation is added to the end of the list. If the name alreadyexists in the wait list, give an error message and do not add theinformation.
c	Add the group to the wait list using the given group size andname specifying the group as a call ahead group. The group’sinformation is added to the end of the list. If the name alreadyexists in the wait list, give an error message and do not add theinformation.
w	Mark the call ahead group using the given name as waiting in therestaurant. If the name does not exist is the wait list or is not acall ahead group, give an error message.
r	Retrieve and remove the first group on the wait list that iswaiting in the restaurant and is less than or equal to the tablesize. Note that “first” is the group that has been in the wait listthe longest.
l	List total number of groups that are in the wait list in frontof the group specified by the given name. Also list the size ofeach group that are in the wait list ahead of the group specifiedby the given name. If the name does not exist, give an errormessage.
d	Display the total number of groups in the wait list. Alsodisplay the names, group size and in-restaurant status of allgroups in the wait list in order from first to last.

Note that and are to be integervalues and is a list of characters. The < and >symbols are NOT part of the input but being used to describe theinput.

Use of C struct and C functions

When writing your code, you MUST create a C struct for the nodesin the linked list of the wait list. These data items must includethe following (and may include others if needed).

? the name of the group

? the integer variable specifying the size of the group (numberof people in the group)

? the in-restaurant status (5 extra points for using anenum!)

? a pointer to the next node in the list

The pointer for the head of the linked list MUST be declared asa local variable in main() or some other function. It may NOT beglobal. If you wish to have the head of the list enclosed in astructure with some other information, that is OK (but certainlynot required). The variable used to access this structure; however,may not be global. Each operation performed on the linked list MUSTbe done in its own function. These function must take the head ofthe linked list as its FIRST parameter.

Linked List Operations/Functions

You must write C functions for the following 7 operations. Thesefunctions must be called when the specified commands are given asinput.

addToList ( ) – This operation is to add a new node to the endof the linked list. This is to be used when the a and c commandsare given as input.

doesNameExist ( ) – This operation is to return a Boolean valueindicating whether a name already exists in the linked list. Thisis to be used when the a, c, w and l commands are given asinput.

updateStatus ( ) – This operation is to change the in-restaurantstatus when a call-ahead group arrives at the restaurant. Thisoperation will return a FALSE value if that group is already markedas being in the restaurant. This is to be used when the w commandis given as input.

retrieveAndRemove ( ) – This operation is to find the firstin-restaurant group that can fit at a given table. This operationis to return the name of group. This group is to be removed fromthe linked list. This is to be used when the r command is given asinput.

countGroupsAhead ( ) – This operation is to return the number ofgroups waiting ahead of a group with a specific name. This is to beused when the l command is given as input.

displayGroupSizeAhead ( ) – This operation traverses down thelist until a specific group name is encountered. As each node istraversed, print out that node’s group size. This command is to beused when the l command is given.

displayListInformation ( ) – This operation to traverse down theentire list from beginning to end. As each node is traversed, printout that node’s group name, group size and in-restaurant status.This command is to be used when the d command is given asinput.

Note that there may be a many-to-many relationship between thecommands in the user interface and the required functions. Forexample, the l command relies on the following functions:doesNameExist(), countGroupsAhead() anddisplayGroupSizeAhead().

Command Line Argument: Debug Mode

Your program is to be able to take one optional command lineargument, the -d flag. When this flag is given, your program is torun in "debug" mode. When in this mode, your program is to displayeach group’s information as you traverse through the linked list ofthe wait list. Note that for the w, r and l commands, the entirelist may not be traversed, so you only display the part of the listthat is needed to be traversed to complete the command.

When the flag is not given, this debugging information shouldnot be displayed. One simple way to set up a "debugging" mode is touse a boolean variable which is set to true when debugging mode isturned on but false otherwise. This variable may be a globalvariable. Then using a simple if statement controls whetherinformation should be output or not.

if ( debugMode == TRUE )
printf (" Debugging Information ");

Provided Code for the User Inteface

The code given in proj3s15.c should properly provide for theuser interface for this program including all command errorchecking. This program has no code for the linked list. It is yourjob to write the functions for the specified operations and makethe appropriate calls. Most of

the changes to the existing proj4base.c program need to be madein each of the doXXXX ( ) functions. Look for the comments of:

     // add code to perform this operation here

Note: the head of the linked list is required to be a localvariable in main and you are required to pass the head of thelinked to the operation functions. All of the doXXXX ( ) functionscurrently have no parameters. It will then be expected that youwill modify the function signatures of the doXXXX() functions toallow for this information to be passed as required.

MULTIPLE SOURCE CODE FILES

Your program is to be written using at least three source codefiles. It must also have a makefile and a header file to help withthe compilation of the program. All of the storage structure code(the linked list code) is to be in one source code file. The codein proj4base.c is to be separated into two different source codefiles.

The following functions from proj4base.c are to be in one sourcecode file (these are the user interface functions):

? main()
? clearToEoln()
? getNextNWSChar() ? getPosInt()
? getName()
? printCommands()

The following functions from proj4base.c are to be in anothersource code file (these are the functions that interact with thelinked list functions):

? doAdd()
? doCallAhead() ? doWaiting()
? doRetrieve()
? doList()
? doDisplay()

The third source code file is to have the code that you arewriting that will perform the linked list implementation: Thefunctions in this source code file will include the followingfunctions plus any other you write to handle the linked list:

? addToList()
? doesNameExist()
? updateStatus()
? retrieveAndRemove()
? countGroupsAhead()
? displayGroupSizeAhead() ? displayListInformation()

You must also create a header file. The job of the header fileis to contain the information so the source code files can talk toeach other. The header file (.h file) should contain the functionprototypes and any struct and/or typedef statements. Please reviewthe .h file in the example below.

The makefile MUST seperately compile each source code file intoa ".o" file and separately link the ".o" files together into anexecutable file. Review the makefile in the example below to seehow this is done. The command to create the .o file is:

gcc –c program1.c
The command to link the files program1.o, program2.o and program3.ointo an executable file is:

gcc program1.o program2.o program3.o
The above command will just name the executable file using thedefault name of a.out, most often the –o option is given to providea specific name for the executable file.

gcc program1.o program2.o program3.o –o program.exe

Example of Multiple Source Code Files

Consider the program contained in the following files:

? max3a.c

? max3b.c

? max3.h

? makefile

This example shows how to set up this simplest of multiplesource code file program. Note that max3a.c and max3b.c justcontain functions and a #include of max3.h. The file max3.hcontains the prototypes (or forward declarations) for all of thefunctions that are called from outside its source code file and any"globally" needed information.

The makefile is a special file that helps in the compilation ofthe source code into the object files into the executable file. Amakefile is executed by the use of the make command. The syntax ofa makefile can be strange. I have always found that it is easiestto modify an existing makefile rather than trying to create onefrom scratch. The makefile will contain multiple rules. Each rulehas the following syntax:

target: dependencyList commandLine

The multiple rules in the make file are separated by a blankline. Also note (this is VERY IMPORTANT) the commandLine must use aTAB for its indentation! An example of a rule is:

      max3a.o: max3a.c max3.h            gcc -c max3a.c

The commandLine is gcc -c max3a.c, which will compile the sourcecode file of max3a.c into the object code file of max3a.o.

The target in the above example is the file max3a.o, which isalso the name of the file created when the commandLine is executed.This relationship is what causes makefiles to work.

The dependencyList in the above example is the two files:max3a.c and max3.h, which are the files needed for the commandLineto properly run. Again, this relationship is what causes makefilesto work.

The make command uses the timestamps of the files in the targetand the dependencyList. If any file in the dependencyList has amore recent timestamp than the target file, the commandLine isexecuted. The idea is that if the user has recently changed eithermax3a.c or max3.h, then the object file max3a.o needs to bere-compiled. Make is designed to help the programmer keep track ofwhat needs to be compiled next.

Make and makefile tutorials can be found at:

? http://mrbook.org/tutorials/make/

? http://www.gnu.org/software/make/manual/make.html

? http://www.opussoftware.com/tutorial/TutMakefile.htm

/Base Code for Project/#include #include #include typedef enum {FALSE = 0, TRUE, NO = 0, YES} boolean;/* forward definition of functions */void clearToEoln();/* Read in until the first Non-White-Space character is Read *//* The white space characters are: *      space, tab t, newline , vertical tab v,  *      form feed f, and carriage return r */ int getNextNWSChar (){ int ch; ch = getc(stdin); if (ch == EOF)   return ch; while (isspace (ch))   {    ch = getc(stdin);    if (ch == EOF)      return ch;   } return ch;}/* read in the next Positive Integer or error:    *//* This is based on the Mathematical definition of a Postive Integer *//*    zero is not counted as a positive number */ int getPosInt (){ int value = 0; /* clear white space characters */ int ch; ch = getc(stdin); while (!isdigit(ch))   {    if ('' == ch)  /* error  ==> no integer given */       return 0;    if (!isspace(ch)) /* error non white space ==> integer not given next */      {       clearToEoln();       return 0;      }    ch = getc(stdin);   } value = ch - '0'; ch = getc(stdin); while (isdigit(ch))   {    value = value * 10 + ch - '0';    ch = getc(stdin);   } ungetc (ch, stdin);  /* put the last read character back in input stream */ /* Integer value of 0 is an error in this program */ if (0 == value)    clearToEoln();    return value;}/* read in the name until the end of the input */char *getName(){ /* skip over the white space characters */ int ch; ch = getc(stdin); while (isspace(ch))   {    if ('' == ch)  /* error  ==> no integer given */       return NULL;    ch = getc(stdin);   } char *word; int size; size = 10; word = (char *) malloc (sizeof(char) * size);   // read in character-by-character until the newline is encountered int count = 0; while (ch != '')   {    if (count+1 >= size)      {       // to grow an array to make it "dynamically sized" using malloc       char* temp;       int i;       size = size * 2;       temp = (char *) malloc (sizeof(char) * size);              // printf ("Growing array from size %d to size %d", count, size);       // copy the characters to the new array       for (i = 0 ; i < count ; i++)           temp[i] = word[i];       free (word);       word = temp;      }    word[count] = ch;    count++;    word[count] = '0';    // read next character    ch = getc(stdin);   } if (count > 30)   {    count = 30;    word[count] = '0';   }  /* clear ending white space characters */ while (isspace (word[count-1]))   {    count--;    word[count] = '0';   } return word;}/* Clear input until next End of Line Character -  */void clearToEoln(){ int ch;  do {     ch = getc(stdin);    } while ((ch != '') && (ch != EOF));}/* Print out a list of the commands for this program */void printCommands(){ printf ("The commands for this program are:"); printf ("q - to quit the program"); printf ("? - to list the accepted commands"); printf ("a   - to add a group to the wait list"); printf ("c   - to add a call-ahead group to the wait list"); printf ("w  - to specify a call-ahead group is now waiting in the restaurant"); printf ("r  - to retrieve the first waiting group that can fit at the available table size"); printf ("l  - list how many groups are ahead of the named group"); printf ("d - display the wait list information");        /* clear input to End of Line */ clearToEoln();}void doAdd (){ /* get group size from input */ int size = getPosInt(); if (size < 1)   {    printf ("Error: Add command requires an integer value of at least 1");    printf ("Add command is of form: a  ");    printf ("  where:  is the size of the group making the reservation");    printf ("          is the name of the group making the reservation");    return;   } /* get group name from input */ char *name = getName(); if (NULL == name)   {    printf ("Error: Add command requires a name to be given");    printf ("Add command is of form: a  ");    printf ("  where:  is the size of the group making the reservation");    printf ("          is the name of the group making the reservation");    return;   } printf ("Adding group "%s" of size %d", name, size); // add code to perform this operation here}void doCallAhead (){ /* get group size from input */ int size = getPosInt(); if (size < 1)   {    printf ("Error: Call-ahead command requires an integer value of at least 1");    printf ("Call-ahead command is of form: c  ");    printf ("  where:  is the size of the group making the reservation");    printf ("          is the name of the group making the reservation");    return;   } /* get group name from input */ char *name = getName(); if (NULL == name)   {    printf ("Error: Call-ahead command requires a name to be given");    printf ("Call-ahead command is of form: c  ");    printf ("  where:  is the size of the group making the reservation");    printf ("          is the name of the group making the reservation");    return;   } printf ("Call-ahead group "%s" of size %d", name, size); // add code to perform this operation here}void doWaiting (){ /* get group name from input */ char *name = getName(); if (NULL == name)   {    printf ("Error: Waiting command requires a name to be given");    printf ("Waiting command is of form: w ");    printf ("  where:  is the name of the group that is now waiting");    return;   } printf ("Waiting group "%s" is now in the restaurant", name); // add code to perform this operation here}void doRetrieve (){ /* get table size from input */ int size = getPosInt(); if (size < 1)   {    printf ("Error: Retrieve command requires an integer value of at least 1");    printf ("Retrieve command is of form: r ");    printf ("  where:  is the size of the group making the reservation");    return;   } clearToEoln(); printf ("Retrieve (and remove) the first group that can fit at a tabel of size %d", size); // add code to perform this operation here}void doList (){ /* get group name from input */ char *name = getName(); if (NULL == name)   {    printf ("Error: List command requires a name to be given");    printf ("List command is of form: l ");    printf ("  where:  is the name of the group to inquire about");    return;   } printf ("Group "%s" is behind the following groups", name); // add code to perform this operation here} void doDisplay (){ clearToEoln(); printf ("Display information about all groups"); // add code to perform this operation here}int main (int argc, char **argv){ char *input; int ch; printf ("Starting Restaurant Wait List Program"); printf ("Enter command: "); while ((ch = getNextNWSChar ()) != EOF)   {    /* check for the various commands */    if ('q' == ch)      {       printf ("Quitting Program");       return (0);      }    else if ('?' == ch)      {       printCommands();      }    else if('a' == ch)      {       doAdd();      }     else if('c' == ch)      {       doCallAhead();      }     else if('w' == ch)      {       doWaiting();      }     else if('r' == ch)      {       doRetrieve();      }     else if('l' == ch)      {       doList();      }     else if('d' == ch)      {       doDisplay();      }     else      {       printf ("%c - in not a valid command", ch);       printf ("For a list of valid commands, type ?");       clearToEoln();      }    printf ("Enter command: ");   } printf ("Quiting Program - EOF reached"); return 1;}