Assignment 4
Assignment 4 is worth 5% of your final mark, and is due by Saturday March 24 Sunday March 25 at 11:59 pm.
There are two Practical Lab sessions for this assignment (Tuesday March 13 and Tuesday March 20).
This assignment should be submitted via MarkUs.
Your assignments must follow the style guidelines discussed in the course style guide. Failure to do so may result in deductions. There are new requirements for this assignment.
You should not make any changes to the starter code, except where indicated.
Announcements and Updates
March 19: Updated information about the bonuses available for additional input validation.
March 17: Minor clarification to pseudocode in Step 12.
March 17: A Makefile is now available. For more information about Makefiles and make, see the documentation in the A3 handout. For A4, the program only consists of a single file, so make is not essential, but it still makes it easier to compile and run your program. You can compile your program by typing make. You can run your program (and recompile it if necessary) by typing make run. You can run the A4 tester (on ECF) by typing make test. Note that the Makefile must be saved under the filename Makefile for it to work; if your browser automatically renames it Makefile.txt, then make won't be able to use it.
March 17: The tester is now available. It can be run using the Makefile.
March 12: Note: If you're working on this Lab during the first Practical Lab session, we won't have covered all of malloc() yet (we will on Wednesday), so don't be alarmed if there are some parts of this lab that you aren't quite sure how to do. We'll talk about it soon, and there are several parts of the assignment that can be done without using malloc().
Overview
Your task for this assignment is to write guestList, a simple guest list manager that will help to manage a list of people who are invited to a party or event. The user can enter names into the system; this will place that individual on the "guest list", which is an unordered list of names. People can be deleted from the guest list if they cancel (or if they really annoy you, I suppose). People can be moved from the guest list to the "accepted list", which is an alphabetical list of names of people who have accepted the invitation. When someone is moved to the accepted list, the program asks whether or not the person will be bringing an additional guest, and then adds one or two people to the total number of attendees. For simplicity's sake, once someone is added to the accepted list, they cannot be removed.
Your program will be controlled by simple text commands. The user will type in a (very limited) set of commands to view the two lists, to add new names to the guest list, to delete someone from the guest list, to indicate that a person has accepted the invitation, or to quit the program.
It is worth noting that you are allowed to use subscripting on this assignment. The requirement of using pointer arithmetic that was in place for A3 does not apply to A4 or A5.
Limitations
Because we do not cover reading and writing files in this course, our guest list manager will not have the ability to save its list of names between sessions of the program. While this obviously makes guestList less useful (or, more accurately, not useful at all) as a practical program, it is still a useful learning exercise.
Dynamic Memory Allocation
You are required to use malloc() and free() to allocate and cleanup the memory associated with the string holding each name. In addition, you are required to free() all memory obtained from malloc(). Any submission that does not do so (i.e., that has a memory leak) will receive a deduction.
Commenting
You are expected to comment your code for this assignment. Commenting should follow the guidelines that we will be discussing in class.
Starter Code
guestList and acceptedList arrays
The first few lines of the starter code's main() set up two arrays to hold our two lists of names.
/* The current size of guestList. This is the size of the array, not the number of spaces currently in use. */
int guestListSize = GUEST_LIST_INITIAL_SIZE;
/* Our guest list, which is stored as an array of strings (i.e., array of char *). */
char **guestList = malloc(guestListSize * sizeof(char *));
/* The current size of acceptedList. This is the size of the array, not the number of spaces currently in use. */
int acceptedListSize = ACCEPTED_LIST_INITIAL_SIZE;
/* Our accepted list, which is stored as an array of strings (i.e., array of char *). */
char **acceptedList = malloc(acceptedListSize * sizeof(char *));
A brief note is in order about the two array declarations. char **guestList is a pointer to a pointer to a char. Because arrays and pointers are essentially synonymous in C, this is basically saying the same thing as char *guestList[], which as we've seen in class, is an array of pointers to char (i.e., a one-dimensional array of pointers, each of which points to a char array). Because of the way that malloc() works, we need to declare guestList as a char ** rather than as an array of pointers, but functionally it is the same thing. We will treat guestList as if it had been declared as char *guestList[].
So guestList is a dynamically allocated array of pointers to char. Each element either points to a char array (i.e., a string), or is NULL (if it's an empty slot). It's worth reiterating that each element is a pointer to a char array, not a char array itself.
Features
The following sections describe each of the features of the program.
A transcript of the program is available here.
"print" prints out the current contents of both lists, and is mostly intended for debugging purposes. If the lists are empty, the output of "print" looks like this:
Please enter a command: print
--- Guest List ---
0: [empty]
1: [empty]
2: [empty]
-------------------
-- Accepted List --
0: [empty]
1: [empty]
-------------------
Number of attendees: 0
Notice that the initial guest list has space for GUEST_LIST_INITIAL_SIZE names, and the initial accepted list has space for ACCEPTED_LIST_INITIAL_SIZE names.
After we add a name to the guest list, the output looks like this:
Please enter a command: print
--- Guest List ---
0: Homer
1: [empty]
2: [empty]
-------------------
-- Accepted List --
0: [empty]
1: [empty]
-------------------
Number of attendees: 0
Note that empty slots are still printed as [empty].
add
"add" adds a new name to the guest list. When selected, "add" first prompts the user for the name:
Please enter a command: add
Enter a name: Homer
"add" then creates a new string, and stores it in the guest list. Specifically, "add" starts at the beginning of guestList, and looks for the first available spot (i.e., the first pointer that is NULL). If it finds a spot, it updates that pointer to point at the new string, thereby adding it to the list. Note that this means that strings may eventually be added out of order, since as strings are deleted from the list they will leave gaps, and those gaps will later be filled in by a different string (e.g., the fifth name entered might be added at position 2 of the array). This is fine, since the list is unordered. Deleting names is discussed in more detail below.
If "add" doesn't find a spot (i.e., if there aren't any NULL pointers in the array), we grow the array by GUEST_LIST_INCREMENT_SIZE spaces. We grow the array by more than one space at a time because resizing arrays can be time-consuming, and it's better to do it less often if possible. So rather than frequently resizing the array by a single element, we occasionally add a larger number of elements. Note that we never shrink the array once we've grown it. Here is an example of growing the list:
Please enter a command: add
Enter a name: Homer
Please enter a command: add
Enter a name: Marge
Please enter a command: add
Enter a name: Bart
Please enter a command: print
--- Guest List ---
0: Homer
1: Marge
2: Bart
-------------------
-- Accepted List --
0: [empty]
1: [empty]
-------------------
Number of attendees: 0
Please enter a command: add
Enter a name: Lisa
Please enter a command: print
--- Guest List ---
0: Homer
1: Marge
2: Bart
3: Lisa
4: [empty]
5: [empty]
-------------------
-- Accepted List --
0: [empty]
1: [empty]
-------------------
Number of attendees: 0
In this example, we added three names, which filled up all of the available empty spaces in the guest list. When we add Lisa, the array is grown by GUEST_LIST_INCREMENT_SIZE (currently set to 3) spaces. One of those spaces is taken up by the newly added name, leaving two new empty spaces.
To resize it, we use realloc() (remember to use sizeof() with the appropriate type to figure out how many bytes you need to add to guestList), and then add the new string to the first newly available spot. Note: addToGuestList() returns a pointer to guestList, because the function can potentially realloc() the array, which can cause the array to move. In other words, after calling addToGuestList(), any existing pointer to guestList (including the one that was passed into the function) is no longer valid. This is the same result as a call to realloc(), which makes sense, since we are calling realloc() inside this function.
delete
"delete" first prints out the contents of the guest list, and then prompts the user to enter a row number. After the user enters a name to delete, the string at that position is free()ed, and the pointer is set to NULL, thereby freeing the space to be reused by another name.
Please enter a command: delete
0: Homer
1: [empty]
2: [empty]
Enter a row number between 0 and 2: 0
Please enter a command: print
--- Guest List ---
0: [empty]
1: [empty]
2: [empty]
-------------------
-- Accepted List --
0: [empty]
1: [empty]
-------------------
Number of attendees: 0
Please enter a command: add
Enter a name: Marge
Please enter a command: print
--- Guest List ---
0: Marge
1: [empty]
2: [empty]
-------------------
-- Accepted List --
0: [empty]
1: [empty]
-------------------
Number of attendees: 0
Notice that after we delete Homer from the list, all three spots are empty. When we add Marge, she gets added to position 0, which is the spot vacated when we deleted Homer.
You can assume that the user will never enter "delete" with an empty list. However, there is a bonus available if you choose to add this additional validation; see the section Bonus for more information.
accept
"accept" also prints out the contents of the guest list, and prompts the user to select a row. Once a row is selected, that name is removed from the guest list, and the user is prompted whether or not this individual is bringing an additional guest to the event. If the person is not, then the name is added to the accepted list, and the number of attendees is incremented by one. If they are, then a new string is created containing the original name and the text TEXT_PLUS_GUEST (which is currently set to " + guest"), and this string is added to the accepted list. (The original string should be destroyed, since it is not longer needed.) Finally, the number of attendees should be incremented by two.
In this example, we add two names to the guest list, and then accept them one at a time. Notice that the name that was entered was "Marge", but "Marge + guest" is the string that is added to the accepted list.
Please enter a command: add
Enter a name: Homer
Please enter a command: add
Enter a name: Marge
Please enter a command: print
--- Guest List ---
0: Homer
1: Marge
2: [empty]
-------------------
-- Accepted List --
0: [empty]
1: [empty]
-------------------
Number of attendees: 0
Please enter a command: accept
0: Homer
1: Marge
2: [empty]
Enter a row number between 0 and 2: 0
Is there an additional guest? [yes/no]: no
Please enter a command: print
--- Guest List ---
0: [empty]
1: Marge
2: [empty]
-------------------
-- Accepted List --
0: Homer
1: [empty]
-------------------
Number of attendees: 1
Please enter a command: accept
0: [empty]
1: Marge
2: [empty]
Enter a row number between 0 and 2: 1
Is there an additional guest? [yes/no]: yes
Please enter a command: print
--- Guest List ---
0: [empty]
1: [empty]
2: [empty]
-------------------
-- Accepted List --
0: Homer
1: Marge + guest
-------------------
Number of attendees: 3
The accepted list is always maintained in lexicographical ASCIIbetical sorted order. (Hint: that's the same order used by strcmp().) When a new name is added, "accept" goes through the existing list, and figures out where the new name needs to be added to maintain the correct ordering. Next, it checks if there are any extra spaces at the end of the list. (Unlike the guest list, blank spaces in the accepted list are always kept at the end of the list; there are never any gaps, since we can't remove someone from the accepted list in this particular program.) If there aren't any spaces, we grow the array by ACCEPTED_LIST_INCREMENT_SIZE spaces. In either case, we then shift down every name that would occur after our newly added name, so that there is an empty space for the new name in the appropriate location.
As a concrete example, if our accepted list had the following two items:
0: Homer
1: Marge + guest
and we wanted to add Bart, we would first add two new spaces to the list:
0: Homer
1: Marge + guest
2: [empty]
3: [empty]
Next, we would figure out that Bart should be inserted at index 0, since "B" comes before "H". We would therefore need to move every name between index 1 (the last non-NULL index) and index 0 (the index that we want to fill in with our newly added name). So, we would move Marge down:
0: Homer
1: [empty]
2: Marge + guest
3: [empty]
And then move Homer down:
0: [empty]
1: Homer
2: Marge + guest
3: [empty]
And finally insert Bart:
0: Bart
1: Homer
2: Marge + guest
3: [empty]
Note that none of these intermediate versions of the list would ever be printed out. These steps are simply to illustrate the process that your program would follow when adding a name to the list. This shifting can be done with a single loop. (Hint: the loop is quite simple, since you don't have to actually swap anything. You're just moving elements over by one space. However, make sure you've carefully thought about the starting and ending conditions of the loop.)
Clarification: as is the case for "delete", you can assume that the user will never enter "accept" if the guest list is empty.
Quit
"quit" cleans up all of the memory, and exits the program.
Output Format
All prompts and output should appear as indicated on the handout. Note the spacing of the headers and footers for both lists.
You can assume that there will never be more than 99 names in either list.
Input Format
All commands (and yes/no responses) are case sensitive.
getLine()
We have provided you with the helper function getLine(). This function operates like fgets() (and in fact calls fgets() to do most of its work), but getLine() strips the trailing '\n' off the end of the resulting string. This makes it more useful for the tasks we are doing, since our commands are things like "add", not "add\n". It also takes care of adding the stdin parameter to fgets(), so that you don't have to type that yourself, and makes sure that any whitespace characters left over from a call to scanf() are removed. You do not have to use getLine(), but it is highly recommended.
Commands
The valid commands appear as the constants MENU_ADD, MENU_DELETE, MENU_PRINT, MENU_ACCEPT, and MENU_QUIT. Any other command should result in a message Unknown command.:
Please enter a command: hello
Unknown command.
Please enter a command:
You can assume that the response entered by the user will be at most CMD_MAX_LENGTH characters long.
Yes and No
When your program prompts for a yes/no response, the valid responses are CMD_YES and CMD_NO. Any other response should result in the message Invalid response.
Please enter a command: accept
0: Homer
1: [empty]
2: [empty]
Enter a row number between 0 and 2: 0
Is there an additional guest? [yes/no]: maybe
Invalid response.
Is there an additional guest? [yes/no]: no
You can assume that the response entered by the user will be at most CMD_MAX_LENGTH characters long.
Row numbers
When your program prompts for a row number, your prompt should display the correct maximum value, and you need to validate that the input is between 0 and the maximum. You do not need to validate that the user enters a non-empty row number, and you can assume that the user will not do so. However, there is a bonus available if you choose to add this additional validation; see the section Bonus for more information.
Please enter a command: accept
0: Marge
1: [empty]
2: [empty]
Enter a row number between 0 and 2: -5
Invalid row number.
Enter a row number between 0 and 2: 10
Invalid row number.
Enter a row number between 0 and 2: 0
Is there an additional guest? [yes/no]: no
1 or 2, which are both empty rows; as indicated, you may assume that the user will never enter the number of an empty row.
Names
The name is any non-empty string up to NAME_MAX_LENGTH characters in length. You can assume that the user will not enter the empty string when prompted for a name.
What to do
The starter code is available here, and a Makefile is available here.
Begin by carefully reading over the starter code.
The basic pseudocode of main() is:
Allocate our guest list and accepted list
Set each of those pointers in both of those lists to NULL
Allocate a buffer for the user's command and initialize it to ""
while (that command is not "quit")
{
Prompt for and read in a command from the user
if (the command is "add")
{
Prompt for a name
Add it to the guest list
}
else if (the command is "print")
{
Print out the guest list (with header and footer)
Print out the accepted list (with header and footer)
Print out the number of attendees
}
else if (the command is "delete")
{
Print out the guest list
Prompt for a row number
free() that string
Set that pointer to NULL to indicate an empty space
}
else if (the command is "accept")
{
Print out the guest list
Prompt for a row number
Prompt if there is an additional guest for this person
if (there is no additional guest)
{
Add one person to our number of attendees
The name that we're going to add is what is stored in guestList
}
else
{
Add two people to the number of attendees
Figure out how long a string we need to hold the name plus the text TEXT_PLUS_GUEST
Allocate a new string of that length
Copy in the existing name...
... and add on the text TEXT_PLUS_GUEST
free() the old name string
}
Add the name (either the original or the newly modified version) to the accepted list
Remove the name from guestList
}
else if (the command isn't "quit")
{
Print out "Unknown command."
}
}
Clean up
We will slowly replace the pseudocode with real code in each of these steps.
Feel free to add debugging information anywhere you want. The DEBUGGING constant is already defined for you. However, you should make sure that DEBUGGING is set to false prior to submission.
Step 1
Begin by filling in the loops that set every pointer in both arrays to NULL. (Recall that the memory we get from malloc() is uninitialized, so that we need to set them to NULL ourselves if we want the pointers to all point at NULL.)
Step 2
Next, add in the code that prompts the user for a command, and then keeps looping until that command is quit. Remember that you can't compare strings with == (well, you can, but it won't do what you want it to).
Step 3
Next, add in the checks for each of the other commands (and the "Unknown command" option), and simply print out a simple message for each (e.g., "You selected add"). You will delete these messages when you actually implement the code for that command, but these messages will help indicate that your parsing code is working correctly.
Step 4
Next, write the code for print. To do this, you will need to implement the function printList(), which you can use to print out both lists. printList() does not print the headers. In addition, remember that printList() needs to handle the case where the pointer is NULL (i.e., the case where we are printing out an empty spot in the list). You'll need to print [empty], and you'll need to make sure you don't dereference the pointer, or pass the pointer to another function that will dereference it. (Hint: remember that each name is just a string, so it's easy to print it out.)
Step 5
Now, we'll fill in add. All add does is call two helper functions: getName() to prompt for and allocate a string to hold the name, and addToGuestList() to add the name to the list. Write the code that makes these two function calls. (Remember that calling addToGuestList() potentially invalidates the existing pointer to guestList, so you'll need to update it when you call the function. Also, make sure you are passing guestListSize correctly.)
Step 6
Now we need to fill in the two helper functions that we called in the previous step. Start by filling in getName(). Remember that you need to create an automatically allocated (i.e., normal) array to hold the user's input, prompt for and read a line of input into that array, and then malloc() a new array of the appropriate length to store the string. You can't return a pointer to the automatically allocated input buffer, since that array will disappear as soon as the function ends.
Step 7
Now we need to implement addToGuestList(). The pseudocode is:
for (each position in the list)
{
if (the current position is NULL)
{
Add the name at that position
}
}
if (we got to the end and didn't add the new name)
{
Increase the size of the list by GUEST_LIST_INCREMENT_SIZE
Add the name at the first new spot
Set the rest of the new spots to NULL
}
Things to remember: 1) n is an int *, and it needs to be updated if you resize the list. 2) You need to return a pointer to the list when you're done with it (the same as realloc()). If you didn't end up calling realloc(), then the pointer is the same as the one passed into the function. If you did call realloc(), then it's the new pointer you received from realloc().
Step 8
Next, we'll fill in delete. You'll need to call getValidRow() to get a row number, and then free() that string and set the appropriate pointer to NULL. Right now you'll always remove row 0 without prompting the user, since getValidRow() is a stub function that always returns 0, but we'll fix that next. Hint: what is the correct value for maxRow?
Step 9
Write getValidRow(). Remember that you need to validate that the input is between 0 and the maximum row number, inclusive, but you do not need to validate that the row is non-empty.
Step 10
Finally, we'll write "accept". Fill in the code for this command, but don't write the two helper functions yet. Remember that if there is an extra guest, you'll need to create a new string to hold the longer name (consisting of the original name plus the text TEXT_PLUS_GUEST) and free() the original name string.
Step 11
Write getIsExtraGuest(). Remember that this function turns a response of "yes" or "no" into a bool.
Step 12
Now, we'll write addToAcceptedList(). The pseudocode is:
Start at the beginning of the list
for (each position in the list)
{
if (the current position is NULL)
{
Stop looking, since we're at the end of the actual strings in the list
}
else if (the name we're adding comes before the string at the current position)
{
Stop looking, since the new string needs to be added at the current position
}
}
At this point, our position is pointing one element past where we want to add the name,
since we incremented it once before leaving the loop, so decrement it
Check if there are any empty spaces in the array
if (there isn't)
{
Calculate the new size by adding ACCEPTED_LIST_INCREMENT to the current size
Grow the array
Set each of the new pointers to NULL
}
Shift every element between the last index and the position that we're adding the name
This creates an empty space where we want to add the name
For simplicity, we just copy every pointer in those indices, including any NULL pointers.
Add the name in the newly vacant position
Step 13
And last but not least, we need to clean up our memory before we exit. Write cleanup code that free()s any remaining memory that was allocated with malloc(). We don't need to free() any strings that were already removed from the list, since they were free()ed when we removed them, but we do need to free the remaining contents of the lists, and the lists themselves.
That's it!
Tester
We will provide you with a simple tester program that will check the format of your output. Details will be posted here shortly. The tester is now available. See the Announcements and Updates section for details.
Bonus
There are two small bonus marks available for additional input validation on this assignment. You shouldn't spend time on these until the rest of your program is working. You should also make sure that you haven't broken your program when trying to add the bonus validation (e.g., make sure that "delete" still works for the normal cases after adding the new validation logic), since the bonus is awarded independently of the main tests cases.
"delete" and "accept" on an Empty Guest List
The first bonus relates to the fact that the program currently assumes that the user never enters "delete" or "accept" when the guest list is empty. Any program that adds the following validation is eligible for a bonus mark:
Please enter a command: print
--- Guest List ---
0: [empty]
1: [empty]
2: [empty]
-------------------
-- Accepted List --
0: [empty]
1: [empty]
-------------------
Number of attendees: 0
Please enter a command: delete
The guest list is already empty.
Please enter a command: accept
The guest list is empty.
Please enter a command:
Notice that neither command prints the lists or prompts for a row number after printing the error message. The behaviour of the commands should be unchanged for non-empty lists.
Hint: the validation logic is the same for both commands. This might be a good opportunity for a helper function.
Non-empty Row Numbers
The second bonus relates to the fact that the program currently assumes that the user will never enter a row number for an empty row when asked for a row selection. Any program that adds the following validation is eligible for a bonus mark:
Please enter a command: add
Enter a name: Homer
Please enter a command: accept
0: Homer
1: [empty]
2: [empty]
Enter a row number between 0 and 2: 1
Invalid selection. That row is empty.
Enter a row number between 0 and 2: 2
Invalid selection. That row is empty.
Enter a row number between 0 and 2: 0
Is there an additional guest? [yes/no]: no
Please enter a command: add
Enter a name: Marge
Please enter a command: delete
0: Marge
1: [empty]
2: [empty]
Enter a row number between 0 and 2: 1
Invalid selection. That row is empty.
Enter a row number between 0 and 2: 2
Invalid selection. That row is empty.
Enter a row number between 0 and 2: 0
Please enter a command:
Notice that the prompt ("Enter a row number between 0 and 2") doesn't change. (In fact, the auto-marker is expecting that prompt (with the correct maximum value, of course), and submissions that have a different prompt will be marked as incorrect.)
Hint: this might be another good opportunity for a helper function. This helper function could call one of the existing functions.
Submission
Submit the file guestList.c via MarkUs before the due date. Late submissions will not be accepted. Even if you have not finished the entire assignment, you should still submit whatever code you have working; partially working submissions are eligible for part marks on sections that do function correctly.