CS 202: Assignment 7
Function and Class Templates
Description
In this program we are going to implement a ring buffer or circular buffer. The specialty
of this kind of buffer is that it loops over itself creating a circular or ring structure. When
the last location in this buffer is filled up, it loops around and starts over from the beginning.
This type of buffer is commonly used for streaming. In the early days of computing, this
type of buffer was used for buffering keyboard input when the processor was busy with
something else and could not handle IO at that instant. It is also commonly used fo
uffering input in video games.
We will be using dynamic memory allocation to implement this kind with 3 major pointers.
The first pointer buffer p holds the dynamically allocated buffer. The second pointe
write p starts at the first index of the buffer and increments itself after writing data. The
third pointer read p also starts at the first index of the buffer, reads something, and then
increments itself. The read pointer cannot read past the write pointer because if it does
1
each the write pointer, it has already read everything prior to it. Both these pointers loop
around to the beginning of the buffer after they pass the end of it. Technically, this type
of buffer does not have a beginning or an end.
Since we are not using linked lists for this assignment, we will be sticking to linear one-
dimensional a
ays and implementing wrap around logic using pointer arithmetic.
NOTE: You are not allowed to use STL for this assignment.
Implementation
We will be implementing just one class template for this assignment called rBuffer. The
function declarations have already been provided to you in the handout. In addition, the
print() function has been implemented for your convenience. You are required to implement
all other functions in the rBuffer.h file. Note that class templates cannot be split into .h
and .cpp files and must be implemented entirely in the header file. The UML diagram fo
this class template is given below.
2
rBuffer(int=8) : The constructor takes size as a parameter. Initialize the buffer to
whatever value is provided by this parameter. If no value is provided, this will behave
like a default constructor with default size set to 8. Here’s a detailed description of
this constructor.
– The minimum size of the buffer is 1 and there is no maximum. If an incredibly
large size is given, then the std::bad alloc exception will be thrown which is up
to the user to handle. If a size lower than 1 is given, set the size to 8.
– Set empty to true. This indicates that the buffer is empty.
– Set full to false. This indicates that the buffer is NOT full. When the buffer is
full, this variable should be set to true.
– Initialize buffer p by allocating memory to hold 8 elements of T. The size vari-
able should also be set to 8.
– Set read p and write p to point to the same location as buffer p.
Once this is done, the buffer should look something like this:
rBuffer(const rBuffe
T> &) : This is the copy constructor. Make sure to
perform a deep copy of all elements of the passed object.
∼
uffer() : The destructor must free all allocated memory.
void write(T) : This function will write the value of T to wherever write p is
pointing. If a value already exists, it will be overwritten. Increment write p afte
this operation. Set the empty variable to false if anything was written. If the write p
pointer is at the end of the buffer, it should wrap around to the beginning. If the
uffer is full, set the full variable to true.
T read() : This function reads the value that is being referenced by pointer read p
and then increments this pointer. Returns the read value. If the buffer is cu
ently
empty, throw an exception with the text “Cannot read from empty buffer!”. If this
pointer is at the write p pointer (read pointer cannot cross over the write pointer),
then it should return the last read value from the buffer (read p - 1). Note that if
3
the pointer is at the beginning of the buffer, the value at the last index of the buffe
should be returned. This pointer should also wrap around to the beginning same way
as the write p pointer.
bool resize(int) : This function will resize the buffer to the integer value passed to
it. Note that the value passed in is the new buffer size and not the value to be added
or subtracted from the cu
ent size. The following conditions must be satisfied:
– New size cannot be less than 1.
– All existing data in the buffer must be preserved after this operation. Therefore,
a buffer cannot be shrunk if it is full; it can only be expanded. However, if the
uffer is not full, then it can be shrunk up to the last element in the buffer. Fo
example, if the buffer size is 8, and there are 5 elements in the buffer, the buffe
cannot be shrunk to a size less than 5. Since a buffer will always be loaded from
the beginning to the end, it can only be shrunk from the end.
– If the buffer is enlarged, it must be enlarged from the end. In other words,
empty space must be added to the end of the buffer and NOT the beginning.
– The read p and write p pointers must preserve their original positions, except
in the following two cases:
1. If the write p pointer is pointing to the last buffer location and the buffe
is enlarged, then the pointer will point to the next new empty location.
2. If the write p pointer is pointing to an empty buffer location and the buffe
is shrunk past this location, then the pointer must be moved to the new
last location of the buffer. For example, if the original buffer size was 8,
the pointer was at index 7 (8th position), and the buffer was resized to
7, the new write p location would be index 6 (7th position). Note that
this adjustment might also be required for the read p pointer. Hint: If the
uffer is not full, how many elements would be present in it upto the write p
pointer?
Another Hint: You can use pointer arithmetic like this:
DistanceP = Pointer1 − Pointer2
Note that both Pointer1 and Pointer2 must be pointing to the same a
ay
(contiguous dynamically allocated memory of the same type). DistanceP is an
integer indicating the number of elements between the two pointers.
– The function must return true for successful change in size and false for failure
to change size.
The only way to achieve resizing of dynamic a
ays is to allocate memory for a new
a
ay and copy data over. Make sure to use the delete function as needed to prevent
memory leaks. Note that the full variable may have to be changed.
4
void clear() : This function should empty the buffer and reset all pointers and
variables. Consider allocating memory for a new buffer and deleting the old one.
void print() const : Provided to you in the handout. A sample output of this
function is given below:
| +14 | 11 | 5 | *2 | 9 |
Here “+” indicates the position of the write pointer and “∗” indicates the position
of the read pointer.
rBuffe
A> joinBuffers (const rBuffe
A> &, const rBuffe
B> &) : Re-
turns a new rBuffer object of buffer size Sizenew where
Sizenew = Sizebuffer1 + Sizebuffer2
This new buffer contains all elements from buffer1 (first parameter) followed by all
elements from buffer2 (second parameter). Note that this function is a friend of the
template class and can access all members. The read pointer should be set to the
eginning of this buffer and the write pointer should be set to the index just afte
the last element of the buffer if the buffer is not full, or the first element if the buffe
is full.
Additional Notes
This assignment has potential for a lot of memory leaks. Make sure you use valgrind
to check for them. You will lose points for memory leaks.
You may not add or remove functions/variables from the provided declarations. You
may not change the print function.
Use the provided print function for hints on what the read and write pointers are
doing. Write extensive tests for your code.
None of the functions (except the print function) must print anything to the screen.
Feel free to use cout statements for testing, but make sure to not leave them in there
after you’re done.
A sample testing file (main.cpp) has been provided to you. By no means is this an
extensive test of all possible failure cases. Write your own test file to make sure all
your functions are doing what they are supposed to do. The output of the given test
file has been provided to you in the handout (sample output.txt).
5
*
Sample main.cpp for Assignment 7.
Feel free to modify and use to test your program.
*
#include
#include "rBuffer.h"
int main() {
rBuffe
int> a(2);
Initialize an integer buffer.
rBuffe
double> b(4);
Initialize a double buffer.
This code will test if the read function throws an exception
if the buffer is empty.
try {
XXXXXXXXXXa.read();
} catch (const char* e) {
XXXXXXXXXXstd::cout
"EXCEPTION: "
e
"\n";
}
Write a bunch of data to the buffer and print it to see changes.
a.write(12);
a.print();
a.write(11);
a.print();
a.write(14);
a.print();
Test the resize function.
if (a.resize(6)) std::cout
"Resize successful\n";
else std::cout
"Resize failed\n";
a.print();
if (a.resize(5)) std::cout
"Resize successful\n";
else std::cout
"Resize failed\n";
Call read a bunch of times to check if read pointer is working.
This will also call print to check pointer location after each call.
std::cout
"Read: "
a.read()