ECE244 Linked Lists
Objectives C++
The main objective of this assignment is to give you practice in creating and manipulating linked lists in C++. In the process, the assignment re-enforces earlier concepts of writing classes with constructors and the destructor. It also serves as an exercise on dynamic allocation and de-allocation of data without memory leaks. This is done by writing a program (called “the program” hereafter) extending your previous lab assignment to represent the Shapes database as a set of linked lists, but with a simplified set of commands in which there are (mostly) no errors in input. This assignment will require more code writing compared to the previous assignments. You are encouraged to start early.
Problem Statement
The assignment consists of two parts. In the first part, you will write a command parser similar to that of the previous lab. The parser provides a textual input interface to your program. In contrast to the previous lab, you need not check for errors in the input (with some exceptions). These commands create shapes, create groups of shapes, move shapes across groups and delete shapes/groups.
Each command consists of an operation keyword followed by arguments. The command and the arguments are separated by one or more spaces. Thus, the code you will write for this part of the assignment should take input from the standard input, parse it, and print responses. The command parser loops, processing input as long as input is available.
In the second part of the assignment, you will implement a linked list based data structure to serve as a simple “database” of objects that store the created shapes. To do so, you will implement several classes: Shape, ShapeNode, ShapeList, GroupNode and GroupList.
Specifications
Similar to the previous lab, it is important that you follow the specifications below carefully. Where the specification says shall or must (or their negatives), following the instruction is required to receive credit for the assignment. If instead it says may or can, these are optional suggestions. The use of should indicates a recommendation; compliance is not specifically required. However, some of the recommendations may hint at a known-good way to do something or pertain to good programming style.
Example input and output for the program are provided in Section 4 for your convenience. They do not cover all parts of the specification. You are responsible for making sure your program meets the specification by reading and applying the description below.
Coding Requirements
The code you will write shall be contained in only the source files named Parser.cpp, Shape.cpp, ShapeNode.cpp, ShapeList.cpp, GroupNode.cpp and GroupList.cpp. Skeletons of these files are released with the assignment’s zip file on the course website. The zip file also contains corresponding .h files: globals.h, Shape.h, ShapeNode.h. ShapeList.h, GroupNode.h and GroupList.h. These .h files contain comments that describe the classes defined in them and their methods. Please note that the .h files are NOT to be modified in any way. Modifying these files almost always results in a mark of 0 for the assignment. You may make use of helper functions to split up the code for readability and to make it easier to re-use. These functions (and their prototypes) must be in one of the aforementioned .cpp files. That is, you must not add any new .h or .cpp files.
Input and output must be done only using the C++ standard library streams cin and cout.
The stream input operator >> and associated functions such as fail() and eof() shall be used for all input. C-style IO such as printf and scanf shall not be used.
Strings shall be stored using the C++ library type string, and operations shall be done using its class members, not C-style strings.
C-library string-to-integer conversions (including but not limited to atoi, strtol, etc.) shall not be used.
The Standard Template Library (STL) shall not be used. The point of this assignment is for you to create your own linked list implementation.
Your program shall not leak memory. Unlike the previous assignment, you will be penalized for leaking memory.
Command Line Input
Input will be given one command on one line at a time. The entire command must appear on one line. All input must be read using the C++ standard input cin. The program shall indicate that it is ready to receive user input by prompting with a greater-than sign followed by a single space (> ); see Section 4 for an example. Input shall always be accepted one line at a time, with each line terminated by a newline character.
Unlike the previous lab, you shall assume that input values are error-free (i.e., commands are always valid, integers are always valid, no arguments are missing, no extra arguments, etc.). Nonetheless, there will be some errors you must check for and print an appropriate error message (see Section 3.3). In this case, the input line shall be discarded, and processing shall resume at the next line. The program shall continue to accept and process input until an end-of-file (eof) condition is received.
Each line of valid input shall start with a command name, followed by zero or more arguments, each separated by one or more space characters. The number and type of arguments accepted depend on the command. The arguments and their permissible types/ranges are shown below in
Table 1.
Argument Description, type, and range
name a string consisting of any non-whitespace characters3 ; except strings that represent commands, shape types or reserved words (e.g., pool).
type a string that represents the type of a shape and must be one of: ellipse, rectangle or triangle
loc a positive integer (0 or larger) that represents the location of the shape in either the x or y dimension
size a positive integer (0 or larger) that represents the size of a shape in either the x or y dimension
The valid commands, their arguments, and their output if the command and its arguments are all legal are shown below in Table 2. In the case of the draw command, which takes no arguments, the program prints not only the message shown in the table, but also all the groups and shapes in the database (see the example in Section 4).
Command Arguments Output if Command is Valid
shape name type loc loc size size name: type loc loc size size
group name name: group
draw drawing:
move name1 name2 moved name1 to name2
delete name name: deleted
If there is an error, a message shall be displayed as described in Section 3.3. Otherwise, a successful command produces a single line of output on the C++ standard output, cout, as shown in Table 2. The values in italics in Table 2 must be replaced with the values given by the command argument. Strings must be reproduced exactly as entered. Where locs or sizes are printed, they shall appear on the order entered in the command.
Error Checking
Errors shall cause a message to be printed to cout, consisting of the text “error:” followed by a single space and the error message from Table 3. In the messages, italicized values such as name
Error message Cause
invalid name The name used for a shape or a group is a reserved word (e.g., a command word, a shape type or pool)
name name exists A shape/group with the name name exists in the database, i.e., has once been created and has not been deleted
shape name not found A shape with the name name specified in a command does not exist
group name not found A group with the name name specified in a command does not exist
should be replaced by the value causing the error. Error message output must comply exactly (content, case, and spacing) with the table below to receive credit. There are no trailing spaces following the text.
The program is not required to deal with errors other than those listed in Table 3. Please note:
The commands and the shape types are case sensitive. Thus, while a shape or a group cannot be named pool or triangle, it can be named Pool or triAngle.
For every line of input, your program must output something. Either a message indicating success (Table 2) or an error (Table 3). For an empty line of input (nothing or just whitespace) your program should just output the command prompt.
You are guaranteed that autotester will not use test cases that have any errors other than the ones listed above. However, You may reuse your code from lab assignment 3 along with its error checking, if you wish. This part of your code will not be exercised or tested.
Program Use
Users of the program use the command line to create and delete shapes, similar to the previous assignment. In addition, users can create and delete shape groups, where a group is a collection of already created shapes. Finally, users can “draw” the groups and shapes, meaning to print them to the standard output.
A database is used to organize the shapes and the groups. When the database is initially created, there is only one group called pool. A shape command creates a new Shape object and this object is by default a member of the pool group. The group command is used to create a new group, initially empty. The move command is used to move a shape from the group it is currently in to a new group (which can be the one it is currently in). A shape cannot belong to more than one group.
The delete command can be used to delete shapes or groups. If used to delete a shape, only the shape specified in the command is deleted from the group it currently in. If the command is used to delete a group, then all the shapes in the group are moved to the pool group and the group is deleted. The pool group cannot be deleted (pool is a reserved word that cannot be used in commands or as shape/group names).
The examples in Section 4 further illustrate the above commands, the actions they take and the output they produce.
The Database
The program shall keep track of all shapes and groups using a linked list based data structure. An example of which is shown in Figure 1. There is a linked list of type GroupList s that represents the list of groups created during program execution. Each node in the list is a GroupNode, which in turn has a pointer to a ShapeList that represents the shapes belonging to the group. A ShapeList is a linked list of ShapeNodes, where each ShapeNode has a pointer to the Shape object it represents.
At the onset of execution, a GroupList object is created to represent a linked list of GroupNodes. The list contains exactly one GroupNode with the name pool. The ShapeList of the pool is initially empty. As shapes are created, they are added the pool group by inserting them at the end of its ShapeList. When new groups are created, they are added to the end of the GroupList. Thus, the order of the groups on the GroupList is that of the order in which they are created.
When a shape is deleted, it is removed from the ShapeList of the group it currently belongs to. When a group is deleted, all the ShapeNodes in it ShapeList are added at the end of the pool’s ShapeList, keeping their order, and the corresponding GroupNode is deleted from the GroupList.
It is critical that your program deletes all dynamic data it allocates so as no memory leaks occur. In this assignment, memory leaks will be checked for and reported by exercise and the autotester, and there is penalty for having memory leaks. It is highly recommended that you use the valgrind memory checking program. A tutorial on valgrind as released with the previous assignment. Please learn and use this tool. It is used by exercise to check for memory leaks in your code.
Program Classes and Files
The Shape Class
The Shape class holds the properties of a shape, including its name, type, location, and size. It is mostly identical to the Shape class in the previous assignment. The definition of the class appears in Shape.h. Examine the file and read through the comments to understand the variables and methods of the class. You must implement this class in the file Shape.cpp.
The ShapeNode Class
This class defines a node in a linked list of ShapeNodes. It has two data members: myShape, which points to the Shape object associated with the node, and next, which is a pointer to the next ShapeNode in a list. It is defined in the file ShapeNode.h and you must implement this class in the file ShapeNode.cpp. Read through the comments in ShapeNode.h to find out what the methods of the class do.
The GroupNode Class
This class defines a node in a linked list of GroupNodes. It has three data members: name, which stores the name of the group, myShapeList, which points to the ShapeList object associated with the group, and next, which is a pointer to the next GroupNode in a list. It is defined in the file GroupNode.h and you must implement this class in the file GroupNode.cpp. Again, read through the comments in GroupNode.h to find out what the methods of the class do.
The ShapeList Class
This class defines a linked list of ShapeNodes. It contains a single data member, head, which points to the first ShapeNode in the list. It is defined in the file ShapeList.h and the files contains comments that describe what the methods of the class do. You must implement this class in ShapeList.cpp.
The GroupList Class
This class defined a linked list of GroupNodess. It contains one data member called head, which is a pointer to the first GroupNode in the list. The class is defined in the file GroupList.h and you must implement it in the file GroupList.cpp. The comments in the GroupList.h indicate what the methods of the class should do.
The Command Line Parser
A suggested (but not mandatory) structure for your command line parser appears in the skeleton Parser.cpp file released within the assignment’s zip file. It is identical to that of the previous assignment and it is recommended that you reuse your code from that assignment.
Examples
An Annotated Example
The program when first started, is ready to receive input:
>
Now the user types a command (ending with Enter) to create a new rectangle called sqr located at x and y positions of 10 and 10 and with a x and y sizes of 30 and 40:
> shape sqr rectangle 10 10 30 40
To which the program should respond with the message indicating the successful creation of the shape:
sqr: rectangle 10 10 30 40
The user then creates a new ellipse called circ:
> shape circ ellipse 30 40 10 10
To which the program should respond with the message for a successful creation of a shape:
circ: ellipse 30 40 10 10
The user then creates a new triangle called trig:
> shape trig triangle 60 80 30 50
To which the program should respond with the message for a successful creation of a shape:
trig: triangle 60 80 30 50
The user issues a draw command and the following is printed:
drawing:
pool:
sqr: rectangle 10 10 30 40
circ: ellipse 30 40 10 10
trig: triangle 60 80 30 50
Observe how the shapes belong to the pool group and are printed in the order in which they were created. Now the user creates a new group called no corners:
group no_corners
The program should respond by printing:
no_corners: group
The user issues a draw command and the following is printed:
drawing:
pool:
sqr: rectangle 10 10 30 40
circ: ellipse 30 40 10 10
trig: triangle 60 80 30 50
no_corners:
Observe how the no corners group is printed after the pool group and is empty. Now, the user moves the shape circ to the group no corners:
move circ no_corners
The program should respond:
moved circ to no_corners
The user issues a draw command and the following is printed:
drawing:
pool:
sqr: rectangle 10 10 30 40
trig: triangle 60 80 30 50
no_corners:
circ: ellipse 30 40 10 10
Observe how the circ is now in the no corners group and is removed from the pool group. The user deletes the no corners group:
delete no_corners
The program should respond as:
no_corners: deleted
Finally, the user issues a draw command and the following is printed:
drawing:
pool:
sqr: rectangle 10 10 30 40
trig: triangle 60 80 30 50
circ: ellipse 30 40 10 10
Observe how the group no corners is no longer printed since it is deleted. Also observe how circ is back at the end of the pool group.
Full session
The following is an example session. Note that the text from the prompt (> ) up to the end of the line is typed by the user, whereas the prompt and line without a prompt are program output.
> shape my_circle ellipse 50 65 20 20
my_circle: ellipse 50 65 20 20
> shape my_square rectangle 100 150 60 60
my_square: rectangle 100 150 60 60
> shape a_circle ellipse 120 200 40 40
a_circle: ellipse 120 200 40 40
> shape my_triangle triangle 40 75 90 90
my_triangle: triangle 40 75 90 90
> draw
drawing:
pool:
my_circle: ellipse 50 65 20 20
my_square: rectangle 100 150 60 60
a_circle: ellipse 120 200 40 40
my_triangle: triangle 40 75 90 90
> group my_first_group
my_first_group: group
> shape my_rectangle rectangle 100 275 90 180
my_rectangle: rectangle 100 275 90 180
> shape my_rectangle triangle 70 50 10 5
error: name my_rectangle exists
> shape second_triangle triangle 70 50 10 5
second_triangle: triangle 70 50 10 5
> draw
drawing:
pool:
my_circle: ellipse 50 65 20 20
my_square: rectangle 100 150 60 60
a_circle: ellipse 120 200 40 40
my_triangle: triangle 40 75 90 90
my_rectangle: rectangle 100 275 90 180
second_triangle: triangle 70 50 10 5
my_first_group:
> move my_triangle my_first_group
moved my_triangle to my_first_group
> move my_circle my_first_group
moved my_circle to my_first_group
> draw
drawing:
pool:
my_square: rectangle 100 150 60 60
a_circle: ellipse 120 200 40 40
my_rectangle: rectangle 100 275 90 180
second_triangle: triangle 70 50 10 5
my_first_group:
my_triangle: triangle 40 75 90 90
my_circle: ellipse 50 65 20 20
> delete my_first_group
my_first_group: deleted
> draw
drawing:
pool:
my_square: rectangle 100 150 60 60
a_circle: ellipse 120 200 40 40
my_rectangle: rectangle 100 275 90 180
second_triangle: triangle 70 50 10 5
my_triangle: triangle 40 75 90 90
my_circle: ellipse 50 65 20 20
> delete pool
error: invalid name
> delete abc
error: shape abc not found
>
Procedure
Create a sub-directory called lab4 in your ece244 directory, and set its permissions so no one else can read it. Download the lab4.zip file, un-zip it and place the resulting files in the lab4 directory.
In the release, there are 6 .h files: globals.h, Shape.h, ShapeNode.h, ShapeList.h, GroupNode.h and GroupList.h. The first has a number of global definitions and the remaining ones define the various classes, as described in Section 3.6. You may NOT modify these files to add to or delete from their content. Modifying the files commonly results in a mark of zero for the assignment.
In the release, there are also 6 .cpp files in which you will add your code: Parser.cpp, Shape.cpp, ShapeNode.cpp, ShapeList.cpp, GroupNode.cpp and GroupList.cpp. In the first file, you will implement the command parser code. In the rest you will implement the various classes described in Section 3.6.
Finally, there is a Makefile that is used by NetBeans to separately compile your project. Do not modify this file either.
Write and test the program to conform to the specifications laid out in Section 3. The example sessions in Section 4 may be used for testing. Further, there is a reference executable provided. When in doubt, run the executable to observe its behaviour. Should there be any conflict between the specifications in this handout and the reference executable, please follow what the reference executable does. To execute the reference solution, run the following command:
~ece244i/public/Parser.exe
The ~ece244i/public/exercise command will also be helpful in testing your program. You should exercise the executable, i.e., Parser.exe, using the command:
~ece244i/public/exercise 4 Parser.exe
As with previous assignments, some of the exercise test cases will be used by the autotester during marking of your assignment. We will not provide all the autotester test cases in exercise.
It is highly recommended to create additional test cases yourself to ensure you fully meet the specification listed above.
Deliverables
Submit the Parser.cpp, Shape.cpp, ShapeNode.cpp, ShapeList.cpp, GroupNode.cpp and GroupList.cpp files as lab 4 using the command
~ece244i/public/submit 4