In this assignment you will build a custom data structure named UndoArray. Building this data structure will give you practice with pointers, dynamic array allocation and deallocation, and writing templated classes. The implementation of this data structure will involve writing one new class. You are not allowed to use any of the STL container classes in your implementation or use any additional classes or structs. Please read the entire handout before beginning your implementation. Also, be sure to review the Lecture 8 notes and our implementation of the Vec class mimicing STLs vector.
The UndoArray works like an ordinary fixed-size array that stores n values of template type T. Like ordinary C/C++ arrays, you can get and set individual entries in the array. What is unusual is that you can sequentially undo the calls to set. To make this work, well need to store the history of all values that were assigned to each index. Below is a diagram of the data structure you will implement. In this example T is type char: see image.
The UndoArray class has 3 member variables: size_, an unsigned integer representing the size of the UndoArray; counts_, an array that stores the number of times each position in the UndoArray has been set; and values_, an array of arrays that store the history of values for each position in the UndoArray. The current value of a position in the UndoArray is the last entry in the history. In the above example, a call to get(1) returns e. The length of each history array is equal to the number of times that value has been set (minus the number of times it has been undone). If a position in the UndoArray is uninitialized, the corresponding position in the values array stores a NULL pointer (indicated with a slash). Attempting to read an uninitialized value in the UndoArray is an error. The boolean initialized function can be used to verify that the value is initialized. See the provided testing code for examples of the usage.
When a position is set, the counts array is appropriately incremented, a new history array is allocated that is one longer than the previous history array, all values in the history are copied with the new value written at the end, the old history is deleted, and the corresponding values pointer is changed. For example, a call to set(4,z) will result in the new data structure diagram below left. see image.
When a position is undone, the counts array is decremented, a new history array is allocated that is one shorter than the previous history array, the history values are copied (except for the most recent value), the old history is deleted, and the corresponding values pointer is changed. It is an error to undo an uninitialized value. If the history contains only one value, that position becomes uninitialized; for example a call to undo(6) results in the data structure diagram above right.
We provide a main.cpp file with a small set of tests of your data structure. Some of these tests are initially commented out. We recommend you get your class working on the basic tests, and then uncomment the additional tests as you implement and debug the key functionality of the UndoArray class. Study the provided test cases to understand what code triggers calls to your UndoArray copy constructor, assignment operator, and destructor and verify that these functions are working correctly.
It is your responsibility to add additional test cases, including examples where the template class type T is something other than char. You must also implement a simple print function to help as you debug your class. Include examples of the use of this function in your new test cases. Your function should work for UndoArrays containing char, int, and reasonably short strings. The print function does not need to work for more complex types. Please use the example output as a guide (the TAs will grade this output by hand).
When your data structure encounters an invalid request, for example, getting the value of a slot in the array that is uninitialized, setting a slot in the array that does not exist, etc., your program should print a descriptive message to std::cerr and exit. We will be compiling the submitted UndoArray header file multiple times with different test cases to fully test your implementation.
The data structure for this assignment (intentionally) involves a lot of memory allocation & deallocation. Certainly it is possible to revise this design for improved performance and efficiency or adapt the data struc- ture to specific applications. For this assignment, please implement the data structure exactly as described.
In your README.txt file include the order notation for each of the UndoArray member functions described above: size, set, initialized, get, undo, and print and dont forget the constructors, destructor, and assignment operator. You should assume that calling new [] or delete [] on an array will take time proportional to the number of elements in the array. In your answers use the variables n = the size of the array and h = the length of the longest history for one space of the array.
To help verify that your data structure does not contain any memory leaks and that your destructor is correctly deleting everything, we include a batch test function that repeatedly allocates an UndoArray, performs many operations, and then deallocates the data structure. To run the batch test case, specify 2 command line arguments, a file name (small.txt, medium.txt, or large.txt) and the number of times to process that file. If you dont have any bugs or memory leaks, this code can be repeated indefinitely with no problems.
./undo_array_test.exe small.txt 100
On Unix/Linux/OSX, open another shell and run the top command. While your program is running, watch the value of RES or RPRVT (resident memory) for your program. If your program is leaking memory, that number will continuously increase and your program will eventually crash. Alternately, on Windows, open the Task Manager (Ctrl-Shift-Esc). Select View Select Columns and check the box next to Memory Usage. View the Processes tab. Now when your program is running, watch the value of Mem Usage for your program (it may help to sort the programs alphabetically by clicking on the Image Name column). If your program is leaking memory, that number will continuously increase. Go ahead, comment out some of your delete statements to confirm you can see this behavior.
We recommend using a memory debugging tool to find memory errors and memory leaks. Information on installation and use of the memory debuggers Dr. Memory (available for Linux/MacOSX/Windows) and Valgrind (available for Linux/OSX) is presented on the course webpage:
http://www.cs.rpi.edu/academics/courses/fall16/csci1200/memory_debugging.php
See also the notes from Lecture 6. Submitty will run your code with Dr. Memory to search for memory problems. Your program must be memory error free and memory leak free to receive full credit.