CMSC 202 Fall 2019
Project 3 – Decay
Assignment: Project 3 – Decay
Value: 80 points
1.Overview
In this project you will:
Implement a linked-list data structure,
Use dynamic memory allocation to create new objects,
Practice using C++ class syntax,
Practice vectors,
Practice object-oriented thinking.
2.Background
For this project, we are going to be building a simple linked list where each node holds a boolean value. The basic linked list looks like this:
There are two main ways to populate each node in the linked list. The first is by loading a file where each linked list is on a single line. Each linked list will be a multiple of three but has no defined limit in size (minimum 3 nodes, maximum unknown – but will be a multiple of 3). The input file will look like this:
In this example, there are three individual linked lists – the first has three nodes, the second has 6 nodes, and the third has 30 nodes. Each linked list will be seperated by a semi-colon. A test file can have any number of linked lists with any number of nodes in each list.
In the example below, there are six nodes. The more challenging part of this project is creating the decay simulation. The simulation would traverse the list and remove all groups of three 1s in a row starting from the left.
If there were additional sets of exactly three 1s in a row, it would remove them as well. After all sets of three 1s have been removed, the user can choose a node to switch from zero to one or one to zero and it checks for groups of three again. This repeats until the entire list is emptied.
3.Assignment Description
Your assignment is to build an application that can either read a file of decay lists or randomly generate a decay list.
1.The file may contain one or more lists.
2.Each list will be separated by a semi-colon (;).
3.Each list will have at least three nodes but no upper limit (but the upper limit must be a multiple of three).
4.Each node only holds one Boolean value (if it is a 0 or 1).
5.If a random list is generated, the user will enter a size of the new DecayList and then multiply the entered value by three to define the number of nodes. Each node will randomly be assigned a 0 or 1.
6.The simulation will iterate through the list and if there are three nodes in a row with a “true” or 1 value, it will remove those three nodes. If there are four or more nodes in a row with a “true” or 1 then it will remove the first three trues then continue to see if there are more sequences of three “trues” or 1s in a row.
7.Between each round of checking for trues or 1s, the user can choose one node to invert its value – switching a 0 to a 1 or a 1 to a 0.
8.All user inputs will be assumed to be the correct data type. For example, if you ask the user for an integer, they will provide an integer.
9.Regardless of the sample output below, all user input must be validated. If you ask for a number between 1 and 5 with the user entering an 8, the user should be re-prompted.
10.Have a main menu that asks the user if they want to:
a.What would you like to do?:
i.Load File
ii.Simulate Loaded File (if no file is loaded, it prompts you to do option 1 first)
iii.Simulate Random File
iv.Exit
1.Upon exit, nothing is saved
4.Requirements:
Initially, you will have to use the following files Node.h, DecayList.h, Decay.h, makefile, driver.cpp, and a simple test file. You can copy the files from Prof. Dixon’s folder at:
/afs/umbc.edu/users/j/d/jdixon/pub/cs202/proj3
To copy it into your project folder, just navigate to your project 3 folder in your home folder and use the command:
cp /afs/umbc.edu/users/j/d/jdixon/pub/cs202/proj3/* .
Notice the trailing period is required (it says copy it into this folder).
The project must be completed in C++. You may not use any libraries or data structures that we have not learned in class. Libraries we have learned include , , , , , , and . You should only use namespace std.
You must use the function prototypes as outlined in the Node.h, DecayList.h, and Decay.h header file. Do not edit the header files.
There is one provided test file. The file is named test1.txt.You can easily create an additional test file to check other scenarios.
You need to write the functions for the three classes for this project. You need to code Node.cpp, DecayList.cpp, and Decay.cpp. Do not use the STL list for this project.
The DecayList is the linked list class for this project. Here are some general descriptions of each of the functions:
oDecayList() – The constructor creates a new empty linked list. m_head is nullptr and m_size is zero.
o~DecayList() – The destructor de-allocates any dynamically allocated memory.
oGetSize() – Returns the number of nodes in the list.
oInvertValue(int index) – for a specific node in the list, inverts the value in the node. A 1 turns into 0 or 0 turns into a 1.
oPrintDecayList() – Displays the value in each node in the decay list.
oCheckEmpty() – Returns if the linked list is empty.
oInsertEnd() – This inserts a node into the end of the DecayList. There is no m_tail so you must iterate over the list to the end!
oTraverseList() – The iterates through the list to identify groups of three nodes to remove. Calls RemoveNodes(index,3) to remove those nodes. May call RemoveNodes multiple times in one traversal (due to a new list being loaded).
oRemoveNodes(index, numNodes) – At a specific index, removes some number of nodes in a row. This is a tricky function so wait until the end to code! Don’t forget about the special cases when the nodes are in the beginning, middle or end of the list.
The Decay class manages the application and populates the various DecayLists. Decay.cpp file that are prototyped in Decay.h.
oDecay() – The constructor just sets m_file = ""
o~Decay() – The destructor de-allocates any dynamically allocated memory (each list).
oEmptyLists() – This function de-allocates any dynamically allocated list.
oLoadFile()– The LoadFile function loads one to many DecayLists each with a different number of nodes. Each list is terminated in the data file with a semi-colon (;).
oChooseList() – Allows the user to choose one of the lists loaded into m_lists.
oCreateRandomList() – Creates a list of a specific number of nodes (user entered * 3). Each node is randomly assigned either a 0 or 1.
oRunSimulation(int index) – After a specific list is chosen or a random list is generated, RunSimulation is called. It is passed the index of the list from the vector m_lists.
oStart() – Calls the various functions in the DecayList.
Choices 1 – Calls LoadFile
Choice 2 – Calls ChooseList
Choice 3 - Calls CreateRandomList
Choice 4 - Exits.
5.Sample Input and Output
5.1.Sample Run
A normal run of the compiled code would look like this with user input highlighted in blue:
Welcome to Decay, where you code a frustrating system instead of doing your physics homework.
1. Load File
2. Simulate Loaded File
3. Simulate Random List
4. Quit
1
What is the name of the file?
test1.txt
Welcome to Decay, where you code a frustrating system instead of doing your physics homework.
1. Load File
2. Simulate Loaded File
3. Simulate Random List
4. Quit
Here are the runs looking at 2. Simulate Loaded File then choosing list 1 with 3 nodes.
2
Which Decay scenario do you want to experience?
1. List 1(3 nodes)
2. List 2(6 nodes)
3. List 3(30 nodes)
4. Quit
1
The sequence has been initialized.
|1|->|0|->|1|->END
Which node to change?
1 2 3
2
3 nodes removed!
All nodes from that list have been removed!
All lists have been cleared.
Welcome to Decay, where you code a frustrating system instead of doing your physics homework.
1. Load File
2. Simulate Loaded File
3. Simulate Random List
4. Quit
As you can see in the example above, there were three nodes and only the center node had a value of 0. By switching that node to a 1, there were three 1s in a row and those nodes were removed.
Here is an full example where a random list is simulated with a starting size of 3 (so 9 nodes).
Welcome to Decay, where you code a frustrating system instead of doing your physics homework.
1. Load File
2. Simulate Loaded File
3. Simulate Random List
4. Quit
3
How large a list would you like?
3
|0|->|1|->|0|->|0|->|0|->|0|->|1|->|0|->|0|->END
Which node to change?
1 2 3 4 5 6 7 8 9
3
|0|->|1|->|1|->|0|->|0|->|0|->|1|->|0|->|0|->END
Which node to change?
1 2 3 4 5 6 7 8 9
4
3 nodes removed!
|0|->|0|->|0|->|1|->|0|->|0|->END
Which node to change?
1 2 3 4 5 6
5
|0|->|0|->|0|->|1|->|1|->|0|->END
Which node to change?
1 2 3 4 5 6
6
3 nodes removed!
|0|->|0|->|0|->END
Which node to change?
1 2 3
1
|1|->|0|->|0|->END
Which node to change?
1 2 3
2
|1|->|1|->|0|->END
Which node to change?
1 2 3
3
3 nodes removed!
All nodes from that list have been removed!
All lists have been cleared.
Welcome to Decay, where you code a frustrating system instead of doing your physics homework.
1. Load File
2. Simulate Loaded File
3. Simulate Random List
4. Quit
Here is an example with some validation.
./proj3
Welcome to Decay, where you code a frustrating system instead of doing your physics homework.
1. Load File
2. Simulate Loaded File
3. Simulate Random List
4. Quit
2
Load a file first!
Welcome to Decay, where you code a frustrating system instead of doing your physics homework.
1. Load File
2. Simulate Loaded File
3. Simulate Random List
4. Quit
3
How large a list would you like?
-1
How large a list would you like?
1
|0|->|1|->|1|->END
Which node to change?
1 2 3
6.Compiling and Running
Because we are using a significant amount of dynamic memory for this project, you are required to manage any memory leaks that might be created. For a linked list, this is most commonly related to the dynamically allocated nodes. Remember, in general, for each item that is dynamically created, it should be deleted using a destructor.
One way to test to make sure that you have successfully removed any of the memory leaks is to use the valgrind command.
Since this project makes extensive use of dynamic memory, it is important that you test your program for memory leaks using valgrind:
valgrind ./proj3
Note: If you accidently use valgrind make run, you may end up with some memory that is still reachable. Do not test this – test using the command above where you include the input file. The makefile should include make val1 (which is ok).
If you have no memory leaks, you should see output like the following:
==5606==
==5606== HEAP SUMMARY:
==5606== in use at exit: 0 bytes in 0 blocks
==5606== total heap usage: 87 allocs, 87 frees, 10,684 bytes allocated
==5606==
==5606== All heap blocks were freed -- no leaks are possible
==5606==
==5606== For counts of detected and suppressed errors, rerun with: -v
==5606== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 6 from 6)
The important part is “in use at exit: 0 bytes 0 blocks,” which tells me all the dynamic memory was deleted before the program exited. If you see anything other than "0 bytes 0 blocks" there is probably an error in one of your destructors. We will evaluate this as part of the grading for this project.
Additional information on valgrind can be found here: http://valgrind.org/docs/manual/quick-start.html
Once you have compiled using your makefile, enter the command ./proj3 to run your program. You can use make val1 to test each of the input files using valgrind (do NOT use valgrind make run!). They have differing sizes. If your executable is not proj3, you will lose points. It should look like the sample output provided above.
7.Completing your Project
When you have completed your project, you can copy it into the submission folder. You can copy your files into the submission folder as many times as you like (before the due date). We will only grade what is in your submission folder.
For this project, you should submit these files to the proj3 subdirectory:
driver.cpp — should be unchanged.
Node.h — should be unchanged.
Node.cpp – should include your implementations of the class functions.
DecayList.h — should be unchanged.
DecayList.cpp – should include your implementations of the class functions.
Decay.h — should be unchanged.
Decay.cpp – should include your implementations of the class functions.
As you should have already set up your symbolic link for this class, you can just copy your files listed above to the submission folder
b.cd to your project 3 folder. An example might be cd ~/202/projects/proj3
c.cp driver.cpp Node.h Node.cpp DecayList.h DecayList.h Decay.h Decay.cpp ~/cs202proj/proj3
You can check to make sure that your files were successfully copied over to the submission directory by entering the command
ls ~/cs202proj/proj3
You can check that your program compiles and runs in the proj3 directory, but please clean up any .o and executable files. Again, do not develop your code in this directory and you should not have the only copy of your program here. Uploading of any .gch files will result in a severe penalty.
For additional information about project submissions, there is a more complete document available in Blackboard under “Course Materials” and “Project Submission.”
IMPORTANT: If you want to submit the project late (after the due date), you will need to copy your files to the appropriate late folder. If you can no longer copy the files into the proj3 folder, it is because the due date has passed. You should be able to see your proj3 files, but you can no longer edit or copy the files in to your proj3 folder. (They will be read only)
If it is 0-24 hours late, copy your files to ~/cs202proj/proj3-late1
If it is 24-48 hours late, copy your files to ~/cs202proj/proj3-late2
If it is after 48 hours late, it is too late to be submitted.