Increasing capacity of circular queue in C++

Question

I am learning about queues and am trying to write a method to change the maximum capacity of a circular queue using a dynamic array. This is what my code looks like right now.

void ArrayQueue::setCapacity(unsigned newCapacity){
if(newCapacity == 0 || newCapacity < this->getSize()){
    throw QueueException("setCapacity()", "invalid new capacity");
} else if(newCapacity != this->getSize()){
    Item * tempArray = new Item[newCapacity];
    for(unsigned i=0; i<newCapacity; i++){
        tempArray[i] = myArray[i];
    }
    Item * oldArray = myArray;
    myArray = tempArray;
    delete [] oldArray;
}
this->myCapacity = newCapacity;
}

However, when I decrease the capacity, I fail assertions to get the myFirst and myLast values. I understand that I need to write code to account for a case in which the entries have wrapped around but am confused about how to do so.

The test I'm trying to pass has code as follows:

    ArrayQueue q5(10);
for (int i = 0; i < 10; i++){
    q5.append(i+1);
}
for (int i = 0; i < 7; i++){
    q5.remove();
}
assert( q5.getCapacity() == 10 );
assert( q5.getSize() == 3 );
assert( !q5.isEmpty() );
assert( !q5.isFull() );
assert( q5.getFirst() == 8 );
assert( q5.getLast() == 10 );

//reduce the capacity
q5.setCapacity(5);
assert( q5.getCapacity() == 5 );
assert( q5.getSize() == 3 );
assert( !q5.isEmpty() );
assert( !q5.isFull() );
assert( q5.getFirst() == 8 );
assert( q5.getLast() == 10 );

I'm passing my first set of assertions but the second getFirst assertion is failing.

Could you give me a pointer in the right direction? Thanks.

Answer 1

for(unsigned i=0; i<newCapacity; i++){
    tempArray[i] = myArray[i];
}

If your new capacity is larger, then you will access myArray with invalid indices

Answer 2

As best as I can figure out your question, you're referencing assertions thrown elsewhere, other than the code fragment that you posted. Since you have not posted the code that you find problematic, it's unlikely that anyone will give you an answer.

However, I do see a likely bug in the code fragment that you posted. Your code that increases the size of the array:

Item * tempArray = new Item[newCapacity];
for(unsigned i=0; i<newCapacity; i++){
    tempArray[i] = myArray[i];
}
Item * oldArray = myArray;
myArray = tempArray;
delete [] oldArray;

Let's say, for example, the old size of myArray was 20, and you increased it to 40.

You're going to allocate a new 40-element tempArray.

Then proceed to copy the first 40 elements from myArray to tempArray.

Undefined behavior.

Answer 3

May I suggest rewriting this using the following:

#include <algorithm>
//...
void ArrayQueue::setCapacity(unsigned newCapacity)
{
    if(newCapacity == 0 || newCapacity < this->getSize()){
        throw QueueException("setCapacity()", "invalid new capacity");
    ArrayQueue tempQ(newCapacity);
    for(unsigned i=0; i< capacity; i++)
        tempQ.append(myArray[i]);
    std::swap(myArray, tempQ.myArray);
    std::swap(capacity, tempQ.capacity);
    std::swap(size, tempQ.size);
}

How does this work? Well, we create a temporary ArrayQueue with the necessary capacity. Then all we do is copy the data to the temporary object. After that we swap out the temporary object with this.

Done.

The temp object dies with the old data, and this is set with the new data. This is a variation of the copy/swap idiom. This requires a working destructor for ArrayQueue -- once you have that, then it becomes a piece of cake.

Note that if there are more member variables, they need to be swapped also. I just swapped the ones that you posted. I guessed you have a size member variable, so if you named it differently, then replace it with the name you used. Bottom line -- swap everything out with the tempQ, and you should be ok.

If you don't know what std::swap does, it does what it says. It just swaps the two items with each other -- nothing special, just convenient to just use a function to do this.