OrderedDataBuffer subclass of DataBuffer

Just like in Java, you can create new versions of existing functions in subclasses of the original class. Creating another function with the same name and signature as an existing function, but with different behavior, is called overriding.

In this assignment, you are to create a subclass of the DataBuffer from the prior assignment 7. A subclass uses the original implementation and extends it in some way. In this case, the subclass you are to create will add two properties: a) it stores only one copy of any given value (no duplicates), and b) that the data in the buffer is always in order. Call this subclass OrderedDataBuffer. In VisualStudio, when you to the add class, you must specify that DataBuffer is its parent class. To give the subclass a new behavior with the above properties, you need only to override the insert and copy functions by redefining them in the OrderedDataBuffer subclass. In order to make the private data in DataBuffer class usable by functions in the subclass, change the declarations in DataBuffer.h from private to protected. Everything else in your DataBuffer.h and DataBuffer.cpp files should be exactly the same as in the buffer assignment.

The OrderedDataBuffer subclass does not need to say anything about the DataBuffer member function being inherited. For the ones it needs to replace, it must declare new ones and provide new implements. Just like the similar insert function in the DataBuffer class, the insert member function in the OrderedDataBuffer class will add a new value to the data buffer, thus increasing its numberOfElements by one. However, unlike in the DataBuffer class, the OrderedDataBuffers insert function does not necessarily put the new value at the end, nor does it necessarily add it at all, even if there is space.

The insert member function defined in OrderedDataBuffer must first check if the value already exists in the buffer. If it is already there, it should not add another copy, but it should return true (indicating that the buffer has that value). Note that even if the buffer is full, this version of insert should return true if the value is already in the buffer, in essence confirming that that value is in the buffer one way or another.

Second, it has to make sure that space exists for a new value. Finally, instead of just putting the new value at the end, the insert member function must find the correct position within the buffer array where the value can be added, to preserves the property that the array is in smallest to largest order, and then insert the value at that location. In other word, if the current sequence of numbers is 2 7 9, and you add the value 5, the new sequence in the buffer array must be 2 5 7 9, not 2 7 9 5. As before, it must also take care not to let the buffer get longer than the size of its capacity. It should simply return false if the buffer is full.

In order to insert a value into the middle of an array, every element starting at that location and continuing until the end of the array, must be moved one location higher in the array, to open up a space without losing data. Create a separate helper function, called shiftUpOne, to perform that task. The shiftUpOne member function should take one argument which is the index of the location to be vacated so that the new value can be stored at that location. Since the shiftUpOne is a helper function and should not be called from outside the class, make the shiftUpOne member function protected, rather than public. When you implement the shiftUpOne operation, make sure that you do not overwrite any value in the array before it has been moved (or copied) to a new location. Each move has to be from an occupied location to a safely unoccupied location in the array. In other words, it matters in which order you do the moving. After it is done moving data, and inserting the new value, the numberOfElements in the buffer should be increased by one (incremented).

Once you have the new insert member function working correctly, then you should also write new versions of the copy and insert member functions that take an array argument. In these versions of the function instead of just copying the data over from one array to another. The array version of insert should use the version of the insert member function, that takes a single integer argument, to put each new value being added into ordered positions. It should return true if all inserts were successful, and false if it fails to insert all of them because the buffer is full. The copy function does exactly the same thing as the insert array function, with only one difference. The copy function does not keep any data already in the buffer. To dump the existing data, simply set the numberOfElements back to 0. Then call the insert array function to do the rest, rather than writing another loop. In other words, the copy function needs only two lines of code. Using existing functions that already do the work instead of duplicating their code is good coding practice. That way, if the code needs to be changed or fixed, it only needs to be changed in one place. (Having the same bug in multiple places creates a maintenance problem because it is so easy to think you fixed it after fixing it once.)

In all of the new operations, remember the buffer properties from the previous Buffer assignment. The buffer is a reserved amount of space allocated as an array. So there are two separate measures of the length. One is for the amount of space available (the size of the array) and the second is for the amount of space that is occupied (the count or length of the data). Also, note that the data in the buffer is never unsorted (the only way data can be added puts it in sorted order), so there is no need to implement a separate sort function.

Now, add one more new member function called remove, which takes one argument for the value. The remove member function will remove the element from the buffer that has the given value, and return true. If the value is not there, it should return false. To implement the remove function, you will need another helper function, called shiftDownOne, to move data into the cell being vacated before shortening the count by 1.

void testDataBuffer(int arr[], int arrLength);

void testOrderedDataBuffer(int arr[], int length);

int main()

{

const int ARR0_LEN = 2;

int arr0[ARR0_LEN] = { -2, -1 };

const int ARR1_LEN = 10;

int arr1[ARR1_LEN] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };

const int ARR2_LEN = 25;

int arr2[ARR2_LEN] = { 2, 4, 6, 8, 10, 12, 14, 16, 7, 6, 22, 8,

9, 16, 5, 2, 7, 8, 12, 2, 0, 14, 17, 19, 22 };

testDataBuffer(arr0, ARR0_LEN);

testDataBuffer(arr1, ARR1_LEN);

testDataBuffer(arr2, ARR2_LEN);

testOrderedDataBuffer(arr0, ARR0_LEN);

testOrderedDataBuffer(arr2, ARR2_LEN);

return 0;

}

void testDataBuffer(int arr[], int arrLength)

{

DataBuffer buf;

buf.insert(44);

buf.insert(arr, arrLength);

cout << "Display after insert 44 and insert arr" << endl;

buf.display();

buf.copy(arr, arrLength);

cout << "Display after copy arr" << endl;

buf.display();

cout << "Sum " << buf.sum() << endl;

cout << "Min " << buf.minValue() << endl;

cout << "Max " << buf.maxValue() << endl;

cout << "Range " << buf.range() << endl;

cout << "Mean " << buf.mean() << endl << endl;

}

void testOrderedDataBuffer(int arr[], int arrLength)

{

OrderedDataBuffer obuf;

obuf.insert(5);

obuf.insert(0);

cout << " Ordered data buffer" << endl;

obuf.display();

obuf.insert(arr, arrLength);

obuf.insert(13);

cout << " Ordered data buffer after inserts" << endl;

obuf.display();

obuf.remove(2);

obuf.remove(5);

cout << " After extra credit removes" << endl;

obuf.print();

}

Turn in all 5 files in a single zip folder. The files are the .cpp with your main(), DataBuffer.h, DataBuffer.cpp, OrdereredDataBuffer.h, and OrderedDataBuffer.cpp. Remember that the OrderedDataBuffer files should be implemented as a subclass of the DataBuffer class and only contain the bits that are new or overridden (4 public member functions and 2 protected helper functions). Look in the book for how to implement a subclass. In Visual Studio, the add -> class form has a field where you specify the base class. (Other than that, you declare and implement just the new code.)