How to copy content of a circular array into a bigger array when array size is full

Question

I have implemented a queue ADT using circular array. However, I want to be able to copy all content of the circular array to a bigger array when full. I have read about the system.arraycopy in Java, but this function does not exist in C++. In the enqueue function below, if the array is full, instead of throwing an error, it should copy into a bigger array.

My code:

template <class Obj>

class Circular_Queue
{
    int MAX;
    private:
    Obj *cqueue_arr;
    Obj *cqueue_arr2;
    int front, rear;
    public:
    Circular_Queue()
    {
        cqueue_arr = NULL;
        cout << "Enter size of the queue:";
        cin >> MAX;
        cqueue_arr = new Obj[MAX];
        rear = -1, front = -1;
    }

    ~Circular_Queue() {
        delete[]cqueue_arr;
    }

    void qfront() {
        if (front == -1)
        {
            throw QueueEmptyException();
        }
        cout << "Front item is : " << cqueue_arr[front] << endl;
    }

    //Insert into Circular Queue
    void enqueue(Obj item)
    {
        int i;

        if ((front == 0 && rear == MAX - 1) || (front == (rear + 1)% MAX))
        { 
            Obj* cqueue_arr2 = new Obj[MAX * 2];     // Creates a bigger array.
            for (int i = 0; i < (MAX * 2); i++) {   // This section doesnt workas intended.
                cqueue_arr2[i] = cqueue_arr[i];
            }

        }
        if (front == -1)
        {
            front = 0;
            rear = 0;
        }
        else
        {
            if (rear == MAX - 1)
                rear = 0;
            else
                rear = ((rear + 1) % MAX);
        }
        cqueue_arr[rear] = item;
        cout << "Insertion Success!!!\n";
        cout << "The number of space left in the queue is  ";
        cout << MAX - (rear + 1) << endl;
        cout << "                                       \n";
        cout << "Content of new array is:";
        for (int i = 0; i < MAX * 2; i++)
            cout << cqueue_arr[i] << " ";
    }

    // Delete from Circular Queue
    Obj dequeue()
    {
        if (front == -1)
        {
            throw QueueEmptyException();
        }
        cout << "Element deleted from queue is : " << cqueue_arr[front] << endl;
        if (front == rear)
        {
            front = -1;
            rear = -1;
        }
        else
        {
            if (front == MAX - 1)
                front = 0;
            else
                front = ((front + 1) % MAX);
        }
    }

    //Display Circular Queue

    void display()
    {
        int front_pos = front, rear_pos = rear;
        if (front == -1)
        {
            cout << "Cannot display, Queue is EMPTY!\n";
            return;
        }
        cout << "Circular Queue elements are:\n";
        if (front_pos <= rear_pos)
        {
            while (front_pos <= rear_pos)
            {
                cout << cqueue_arr[front_pos] << "  ";
                front_pos++;
            }
        }
        else
        {
            while (front_pos <= MAX - 1)
            {
                cout << cqueue_arr[front_pos] << "  ";
                front_pos++;
            }
            front_pos = 0;
            while (front_pos <= rear_pos)
            {
                cout << cqueue_arr[front_pos] << "  ";
                front_pos++;
            }
        }
        cout << endl;
    }
};

The two arrays have different sizes. To avoid undefined behaviour, the number of elements copied should be the number of elements in the SMALLER array, not the number of elements in the larger array. Of course, there is then the question of managing lifetimes of both arrays, which your code also does nothing about. — Peter, Apr 23 '17 at 22:46

score 1 · Accepted Answer · answered Apr 23 '17 at 23:26

The main problem is that you are accessing the array out of bounds. You should loop over the existing size, not the new size. Also, you are just discarding the new array, you need to delete the old and swap in the new array, i.e.

if ((front == 0 && rear == MAX - 1) || (front == (rear + 1)% MAX))
{ 
    auto newMax = MAX * 2;
    Obj* cqueue_arr2 = new Obj[newMax];     // Creates a bigger array.
    for (int i = 0; i < (MAX); i++) {   // loop over original array size, not new size
        cqueue_arr2[i] = cqueue_arr[i];
    }
    // remember to actually use the new array, and discard the old one.
    delete[] cqueue_arr;
    cqueue_arr = cqueue_arr2
    MAX = newMax;
}

As an aside, just using std::vector instead of Data[] would make all of this moot. It will efficiently grow itself, avoiding a copy if possible (similar to realloc()). It will also avoid some other limitations (e.g. your current implementation requires a default constructor and copy assignment operator), and all access will be inlined to pointer arithmetic anyway, so you don't gain anything by using raw pointers. The implementation can largely remain the same, except the growing part, which just becomes queue_vec.push_back(val);.

Also, using cin in a constructor is bad practice. You should just pass an int as a parameter instead. You can read that from cin in a main() if you want. That way your class can be used elsewhere without interfering with IO.

Thanks. This was helpful. I did not notice I was looping over the new array instead of the old one. As regards the constructor, I passed the value MAX as a parameter as advised. Circular_Queue(int MAX).. but I got an error when i did " Circular_Queue cqi; " in the main program. error message: No default constructor exist for class Circular_Queue — Awani, Apr 25 '17 at 16:08
add `explicit Circular_Queue(int max=128);` as a constructor, and you will have a default constructor (that will set max to 128 if none is specified). If you want to specify the max in the main, you need to construct it like this: `Circular_Queue cqi(1024);`, or you can pass in an int. Also I really recommend [reading a c++ book](http://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). — Joseph Ireland, Apr 25 '17 at 16:33

score 0 · Answer 2 · answered Apr 23 '17 at 23:31

I hope it would give you a hint for solving it.

First, I recommend the pre-existed datatype from stl or boost because it has been optimized and stable.

Second, Just for copying array... I would do like that. (TargetArray should be allocated in advance. However, you can just allocate it in the function if you want.)

    typedef Obj value_type;
    int Clone(Obj *&TargetArray) {
          unsigned int curArraySize=sizeof(value_type)*`YourArraySize'
          memcpy(TargetArray,cqueue_arr, curArraySize);
          TargetArray[curArraySize+1]=NULL;
          return curArraySize;
    }

Good Luck

score 0 · Answer 3 · answered Apr 25 '17 at 16:21

Thank you Joseph Ireland and Kwang-Chun Kang. Following your advice and making further research, my code works as intended. This is what i did. `

 void resize() {

    auto newMAX = 2 * MAX;

    Obj *cqueue_arr2 = new Obj[newMAX];
    int i = 0;                                 //  controls new array 

                                                            position
    int j = front;                            //  controls old array 
                                                           position
    bool rearReached = false;
    while (!rearReached) {
        rearReached = j % MAX == rear;        // is true when rear is 
                                                              reached
        cqueue_arr2[i] = cqueue_arr[j % MAX];
        i++;
        j++;
    }
    front = 0;
    rear = MAX - 1;
    cqueue_arr = cqueue_arr2;
    MAX = newMAX;`

As shown two integer variables controls the position of items in old and new array. Which makes it works perfectly for circular queue where front position is not always index 0. After copying all the items, I then set the index as front = 0 and rear = MAX -1 in the new array. Hope this helps others.

You can also do it with two memcpy calls. – Donnie Apr 25 '17 at 16:23 — Donnie, Apr 25 '17 at 16:23

How to copy content of a circular array into a bigger array when array size is full

3 Answers3