rear value not working properly in circular array queue

Question

I have this code for adding:

public void add(AnyType item){
    if(isEmpty()){
        q[f]=item;
    }
    else{
        if(size==q.length){
            AnyType[] copyQ = (AnyType[]) new Object[q.length*2];
            System.arraycopy(q, f, copyQ, 0, q.length-f);
            System.arraycopy(q, 0, copyQ, q.length-f, r);
            f = 0;
            q = copyQ;
        }
    }
    q[r]=item;
    r = (r+1)%(q.length);
    size++;
}

But then when I want to get the value of r it gives me one more value than it actually is. Also, when I copy the values from one Array to the other there is a value that it is skipping one value. I know everything has to do with the value of r = (r+1)%(q.length); and I've been working on it for hours and can't figure it out. After assigning the value to q[r], even if it is only the first value, and I try to get the value of where r should be it gives me 1 because it is increased by the formula, but I can't figure out how to write it in a different way without messing up the circular queue formula. Any help would be greatly appreciated. Thanks!

Answer 1

Unit tests are your friend! :-)

Express your desired behaviour as tests, gradually building up complexity in your add() method until it all works. I did it for your circular buffer and the working add() looked like this:

public void add(AnyType item){
    if(isEmpty()){
        q[f]=item;
    } 
    else {
        if (size == q.length) {
            AnyType[] copyQ = (AnyType[]) new Object[q.length*2];
            System.arraycopy(q, f, copyQ, 0, q.length-f);
            System.arraycopy(q, 0, copyQ, q.length-f, (r + 1));
            f = 0;
            r = q.length -1;
            q = copyQ;
        }
    }

    r = (r+1)%(q.length); 
    q[r]=item;
    size++;
}

Note the differences:

• r is an offset - you can't use it as a length in the second arraycopy()
• r needs to be updated when you resize your internal array
• Changed order of evaluation, incrementing r before storing item