Two common data structures for implementing First-In-First-Out (FIFO) queues are singly-linked lists and arrays used as circular buffers. The advantage of using an array is that we can add and remove items from the FIFO queue quickly simply by updating the indices of the start and the end of the queue. As items are added and removed from the array, the indices would "wrap around" and space in the array is reused. In the example below, 14 is at the start of the queue and 21 is at the end. If we added another item to the FIFO queue, it would go in index #1. If we remove an item from the FIFO queue, 14 would be removed.

When using an array for a circular buffer, we must make sure that the array is big enough to hold the largest number of items that can be in the FIFO queue simultaneously. Suppose we added two more values22 and 23to the circular buffer above. Then, the buffer would be full:

We cannot add another item to the circular buffer. What do we do? (There is a version of circular buffers that allow the data structure to drop the oldest item in the queue if the buffer is full. This is useful in some applications. For example, if we use the circular buffer to store the last 5 seconds of an audio recording, we can just "erase" the oldest part of the recording and reuse the space for the newest. For this project we are not allowed to drop any data.)

The standard trick when we run out of space in an array is to make a new array that holds twice as much data and copy the data over, freeing the old array afterwards. Copying is slow, though. So, instead of copying, we will just add another array for new values, and keep both arrays. (Note that we are still using the strategy of allocating a new array that is twice as big.) The following diagram shows what happens if we add 24, 25, 26, 27, 28 and 29 to the example above.

The resulting situation is slightly more complex than a simple expanded single array. We now have to remember that when we remove something from the FIFO queue, we remove it from the start of the old array. but when we add something to the FIFO queue, we add it to the end of the new array. For example, if we added 30, 31 and 32 and removed two items from the queue above, then we would have:

In a simple world, eventually, all of the items in the old array will be removed and we would be left with just the new array. We then fall back to the "normal" circular buffer implemented as a single array. For example, if we removed 11 items from the figure above, we would get:

But, what if we add lots of items to the FIFO queue and even the second array fills up? Then, we just create a third array. What if that one becomes full? Then we create another one. And if that one is full? In the general case, we have a bunch of arrays. We keep track of which array is the oldest and which one is the newest. We always add to the newest array and remove from the oldest array:

Once the oldest array is emptied, we can deallocate that array, and we remove items from the next oldest array. If the newest array is full, then we create another with twice the capacity. We use an array of pointers to keep track of these circular buffers. In the general case, the array of pointers might also wrap around, because (yes, you guessed it) the array of pointers (in blue below) is itself a circular buffer:

The limited version of the data structure we are implementing here, where the outer buffer is fixed at some size (in our case, 7), displays an interesting behavior: the ultimate capacity before it throws an exception depends on the exact usage pattern. Imagine a toy case where we limit our outer circular buffer to size 3, and start our first inner buffer at size 1. If the user starts right off doing nothing but enqueues, the whole data structure will top out at 7 items before throwing an exception on the 8th addition. However, if the user enqueues 7 items, but then dequeues them all, it will cause all but the newestand largest, at size 4inner buffer to be deallocated. Then, if the user starts enqueuing again, after 4 items are added, another inner buffer will be allocated with size 8, and a third with size 16 after that if the user keeps enqueuing. At that point, our total capacity would be 28. You can see that the implementation we are doing for this project is therefore overly sensitive to the exact growth pattern of the user's storage needs, which is not a good characteristic of a data structure. Luckily, you are not planning to try to sell this system commercially...

Your assignment is to implement the "circular buffer of circular buffers" data structure described above. For this project, you will have very limited design choices. You are required to use the class definitions given in InnerCB.h and CBofCB.h. (Specifications are given below.) The InnerCB class is an implementation of a simple circular buffer of int values. (Like the green arrays above.) The CBofCB class is the circular buffer of circular buffers.

#ifndef _INNERCB_H_ #define _INNERCB_H_ class InnerCB { public: // Constructor, default size is 10. InnerCB(int n=10) ; // Copy constructor InnerCB(const InnerCB& other) ; // Destructor ~InnerCB() ; // Add item to circular buffer void enqueue(int data) ; // Remove item from circular buffer int dequeue() ; // True if no space left in buffer bool isFull() ; // True if buffer holds no items bool isEmpty() ; // return maximum number of items this buffer can hold int capacity() ; // return number of items currently held in the buffer int size() ; // overloaded assignment operator const InnerCB& operator=(const InnerCB& rhs) ; // debugging function. Prints out contents. void dump() ; // grading function used to examine private data members. // Do not implement! bool inspect (int* &buf, int &cap, int &size, int &start, int &end) ; private : int *m_buffer ; // pointer to dynamically allocate array for buffer int m_capacity ; // length of the allocated space pointed by m_buffer int m_size ; // # of items in the buffer int m_start ; // index of the first (oldest) item in the buffer int m_end ; // index of the last (newest) item in the buffer } ; #endif 

#ifndef _CBOFCB_H_ #define _CBOFCB_H_ #include "InnerCB.h" class CBofCB { public: // default constructor CBofCB() ; // copy constructor CBofCB(const CBofCB& other) ; // destructor ~CBofCB() ; // add item to this data structure void enqueue(int data) ; // remove item from this data structure int dequeue() ; // returns true if cannot add more items bool isFull() ; // returns true if no items stored in data structure bool isEmpty() ; // number of items in the data structure as a whole. // Note: not the number of InnerCB's int size() ; // overloaded assignment operator const CBofCB& operator=(const CBofCB& rhs) ; // debugging function, prints out contents of data structure void dump() ; // grading function. Do not implement! bool inspect (InnerCB** &buf, int &cap, int &size, int &start, int &end) ; private : // max number of Inner Circular Buffers // static const int m_obCapacity=7 ; // array of pointers to InnerCB's. // Each entry of the array is a pointer. // Note: array itself is NOT dynamically allocated InnerCB * m_buffers[m_obCapacity] ; int m_obSize ; // number of inner circular buffers in the outer CB int m_oldest ; // index of the oldest circular buffer (start) int m_newest ; // index of the newest circular buffer (end) } ; #endif