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.
computer science
Description
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 6 and Lab 4 material with our implementation of the Vec class mimicing STL’s vector.
The Data Structure
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, we’ll 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:
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.
