Question

Edit a C program based on the surface code(which is after the question's instruction.) that will implement a customer waiting list that might be used by a restaurant. Use the base code to finish the project. When people want to be seated in the restaurant, they give their name and group size to the host/hostess and then wait until those in front of them have been seated. The program must use a linked list to implement the queue-like data structure.

The linked list is to maintain the following information for each 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 is waiting in the restaurant

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

Groups are added to the wait list when they call-ahead or when they arrive at the restaurant. Groups are always added to the end of the wait list. The system will require that each name used be unique. So when a group is added to the wait list, the system must make 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 the restaurant and can sit at a table with N seats (i.e. the number of seats at the table is greater than or equal to the number of people in 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 the restaurant actually has, nor how many people can sit at each table. The host/hostess is expected to know that information and will enter the appropriate values when needed.

The commands used by this system are listed below and are to come from standard input. Your program is to prompt the user for input and display error messages for unknown commands or improperly formatted commands. Note that the name of the group when given will be given as the last item on the input line. The name of the group may contain white space characters in the middle of the name but not at the beginning or end of the name. Each command given must display some information about the command being performed. Code to implement this interface is provided in the program proj4base.c.

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

CS 211 – Programming Practicum Fall 2015

a	Add the group to the wait list using the given group size and name specifying the group is waiting in the restaurant. The group’s information is added to the end of the list. If the name already exists in the wait list, give an error message and do not add the information.
c	Add the group to the wait list using the given group size and name specifying the group as a call ahead group. The group’s information is added to the end of the list. If the name already exists in the wait list, give an error message and do not add the information.
w	Mark the call ahead group using the given name as waiting in the restaurant. If the name does not exist is the wait list or is not a call ahead group, give an error message.
r	Retrieve and remove the first group on the wait list that is waiting in the restaurant and is less than or equal to the table size. Note that “first” is the group that has been in the wait list the longest.
l	List total number of groups that are in the wait list in front of the group specified by the given name. Also list the size of each group that are in the wait list ahead of the group specified by the given name. If the name does not exist, give an error message.
d	Display the total number of groups in the wait list. Also display the names, group size and in-restaurant status of all groups in the wait list in order from first to last.

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

Use of C struct and C functions

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

 the name of the group

 the integer variable specifying the size of the group (number of people in the group)

 the in-restaurant status (5 extra points for using an enum!)

 a pointer to the next node in the list

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

Linked List Operations/Functions

You must write C functions for the following 7 operations. These functions must be called when the specified commands are given as input.

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

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

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

retrieveAndRemove ( ) – This operation is to find the first in-restaurant group that can fit at a given table. This operation is to return the name of group. This group is to be removed from the linked list. This is to be used when the r command is given as input.

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

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

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

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

Command Line Argument: Debug Mode

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

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

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

Provided Code for the User Inteface

The code given in proj3s15.c should properly provide for the user interface for this program including all command error checking. This program has no code for the linked list. It is your job to write the functions for the specified operations and make the appropriate calls. Most of

the changes to the existing proj4base.c program need to be made in 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 local variable in main and you are required to pass the head of the linked to the operation functions. All of the doXXXX ( ) functions currently have no parameters. It will then be expected that you will modify the function signatures of the doXXXX() functions to allow for this information to be passed as required.

MULTIPLE SOURCE CODE FILES

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

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

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

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

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

The third source code file is to have the code that you are writing that will perform the linked list implementation: The functions in this source code file will include the following functions 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 file is to contain the information so the source code files can talk to each other. The header file (.h file) should contain the function prototypes and any struct and/or typedef statements. Please review the .h file in the example below.

The makefile MUST seperately compile each source code file into a ".o" file and separately link the ".o" files together into an executable file. Review the makefile in the example below to see how 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.o into an executable file is:

gcc program1.o program2.o program3.o
The above command will just name the executable file using the default name of a.out, most often the –o option is given to provide a 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 multiple source code file program. Note that max3a.c and max3b.c just contain functions and a #include of max3.h. The file max3.h contains the prototypes (or forward declarations) for all of the functions 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 of the source code into the object files into the executable file. A makefile is executed by the use of the make command. The syntax of a makefile can be strange. I have always found that it is easiest to modify an existing makefile rather than trying to create one from scratch. The makefile will contain multiple rules. Each rule has the following syntax:

target: dependencyList commandLine

The multiple rules in the make file are separated by a blank line. Also note (this is VERY IMPORTANT) the commandLine must use a TAB 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 source code file of max3a.c into the object code file of max3a.o.

The target in the above example is the file max3a.o, which is also 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 commandLine to properly run. Again, this relationship is what causes makefiles to work.

The make command uses the timestamps of the files in the target and the dependencyList. If any file in the dependencyList has a more recent timestamp than the target file, the commandLine is executed. The idea is that if the user has recently changed either max3a.c or max3.h, then the object file max3a.o needs to be re-compiled. Make is designed to help the programmer keep track of what 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 \n, 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 ('\n' == ch)  /* error \n ==> 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 ('\n' == ch)  /* error \n ==> 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 != '\n')
   {
    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\n", 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 - \n */
void clearToEoln()
{
 int ch;
 
 do {
     ch = getc(stdin);
    }
 while ((ch != '\n') && (ch != EOF));
}

/* Print out a list of the commands for this program */
void printCommands()
{
 printf ("The commands for this program are:\n\n");
 printf ("q - to quit the program\n");
 printf ("? - to list the accepted commands\n");
 printf ("a   - to add a group to the wait list\n");
 printf ("c   - to add a call-ahead group to the wait list\n");
 printf ("w  - to specify a call-ahead group is now waiting in the restaurant\n");
 printf ("r  - to retrieve the first waiting group that can fit at the available table size\n");
 printf ("l  - list how many groups are ahead of the named group\n");
 printf ("d - display the wait list information\n");
       
 /* 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\n");
    printf ("Add command is of form: a  \n");
    printf ("  where:  is the size of the group making the reservation\n");
    printf ("          is the name of the group making the reservation\n");
    return;
   }

 /* get group name from input */
 char *name = getName();
 if (NULL == name)
   {
    printf ("Error: Add command requires a name to be given\n");
    printf ("Add command is of form: a  \n");
    printf ("  where:  is the size of the group making the reservation\n");
    printf ("          is the name of the group making the reservation\n");
    return;
   }

 printf ("Adding group \"%s\" of size %d\n", 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\n");
    printf ("Call-ahead command is of form: c  \n");
    printf ("  where:  is the size of the group making the reservation\n");
    printf ("          is the name of the group making the reservation\n");
    return;
   }

 /* get group name from input */
 char *name = getName();
 if (NULL == name)
   {
    printf ("Error: Call-ahead command requires a name to be given\n");
    printf ("Call-ahead command is of form: c  \n");
    printf ("  where:  is the size of the group making the reservation\n");
    printf ("          is the name of the group making the reservation\n");
    return;
   }

 printf ("Call-ahead group \"%s\" of size %d\n", 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\n");
    printf ("Waiting command is of form: w \n");
    printf ("  where:  is the name of the group that is now waiting\n");
    return;
   }

 printf ("Waiting group \"%s\" is now in the restaurant\n", 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\n");
    printf ("Retrieve command is of form: r \n");
    printf ("  where:  is the size of the group making the reservation\n");
    return;
   }
 clearToEoln();
 printf ("Retrieve (and remove) the first group that can fit at a tabel of size %d\n", 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\n");
    printf ("List command is of form: l \n");
    printf ("  where:  is the name of the group to inquire about\n");
    return;
   }

 printf ("Group \"%s\" is behind the following groups\n", name);

 // add code to perform this operation here
}
 
void doDisplay ()
{
 clearToEoln();
 printf ("Display information about all groups\n");

 // add code to perform this operation here
}


int main (int argc, char **argv)
{

 char *input;
 int ch;

 printf ("Starting Restaurant Wait List Program\n\n");
 printf ("Enter command: ");

 while ((ch = getNextNWSChar ()) != EOF)
   {
    /* check for the various commands */
    if ('q' == ch)
      {
       printf ("Quitting Program\n");
       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\n", ch);
       printf ("For a list of valid commands, type ?\n");
       clearToEoln();
      }

    printf ("\nEnter command: ");
   }

 printf ("Quiting Program - EOF reached\n");
 return 1;
}

Comment

Answer 1

CODE :

enum Status {call, wait};

typedef struct restaurant
{
    char name[30];
    int groupSize;
    enum Status status;
    struct restaurant *nextNode;
} list;