Queue implementation with circular arrays: Which is the best way to resize a circular array?

Question

I'm implementing a queue using a circular array, and I'm kind of stuck in the resize() method implementation (when the array is full).

Inside the enqueue() method I check if the size of the array equals it's length, and get if it's full. Now, instead of throwing an exception, I'm trying to resize the array.

The thing is, I have two cases to consider

1. front <= rear
2. rear < front

Which is the best way to copy the elements of the old array into the new, larger one?

I thought it using a for-loop, like:

newArray = new Array[oldArray.length*2];

if (front <= rear) {
    for (int i = front; i < rear; i++) {
        newArray[i] = oldArray[i];
    } 
} else {
    for (int i = front; i < newArray.length; i++) {
        newArray[i] = oldArray[i];
    }

    for (int j = rear; j < front; j++) {
        // i'm using the variable i, the order is maintained
        newArray[i] = oldArray[j];
        i++;
    }
}

Then oldArray = newArray, return newArray and the resize it's done

I'm not sure of the amount of for's used to do this and I'm afraid I lose values.

Can someone tell me if there is a better way to do this?

Answer 1

For copying arrays with more than a handful of elements, use System.arraycopy(), since it is usually implemented as native code, e.g. Sun's VM uses hand-coded assembler.

front > rear

Since the data is contiguous, it can remain in the same place in the new array.

System.arraycopy(oldArray, front, newArray, front, front-rear);

front <= rear

The data is non-contiguous, so copy both blocks to the start of the new array.

// copy [rear to end]
System.arraycopy(oldArray, rear, newArray, 0, oldArray.length-rear);
// copy [0 to front]
System.arraycopy(oldArray, 0, newArray, oldArray.length-rear, front);
front = oldArray.length-(rear-front);
rear = 0;