3
\$\begingroup\$

I had an application where I really wanted a double-ended queue that supports random access. Java's ArrayDeque would have been perfect, except that it doesn't expose random access into its backing array. So I went and implemented my own, which I named RingBuffer.

I'm looking for any constructive criticism about either the data structure implementation itself, or the test suite.

Implementation:

import java.util.NoSuchElementException;

public class RingBuffer<T> {

    private Object[] backingArray;
    private int firstIdx = 0;   // Index of the first elements
    private int nextIdx = 0;    // Index of the slot into which we would insert an element on addLast
                                // If nextIdx == (firstIdx - 1) % array_size, then insertion requires resizing the array.
                                // If nextIdx == firstIdx, then the buffer is empty.

    public RingBuffer() {
        backingArray = new Object[2];
    }

    synchronized private void doubleBackingArraySize() {
        int newSize = backingArray.length * 2;
        Object[] newArray = new Object[newSize];
        int oldSize;

        if (nextIdx < firstIdx) {
            int numElementsToEndOfArray = backingArray.length - firstIdx;
            System.arraycopy(backingArray, firstIdx, newArray, 0, numElementsToEndOfArray);
            System.arraycopy(backingArray, 0, newArray, numElementsToEndOfArray, nextIdx);
            oldSize = numElementsToEndOfArray + nextIdx;
        } else {
            // This will happen if firstIdx == 0
            System.arraycopy(backingArray, firstIdx, newArray, 0, nextIdx - firstIdx);
            oldSize = nextIdx - firstIdx;
        }

        backingArray = newArray;
        // Update our indices into that array.
        firstIdx = 0;
        nextIdx = oldSize;
    }

    /**
     * Returns the number of elements that the array backing this can hold.
     * This is NOT necessarily the number of elements presently in the buffer.
     * Useful for testing that the implementation works correctly, and for figuring out if an add{First, Last} will
     * cause a re-allocation.
     */
    public int capacity() {
        return backingArray.length - 1;
    }

    /**
     * The number of elements currently held in the buffer.
     */
    public int size() {
        if (firstIdx <= nextIdx) {
            return nextIdx - firstIdx;
        } else {
            return (backingArray.length - firstIdx + nextIdx);
        }
    }

    public void addLast(T x) {
        if ((nextIdx + 1) % backingArray.length == firstIdx) {
            doubleBackingArraySize();
        }

        backingArray[nextIdx] = x;
        nextIdx +=1;
        nextIdx %= backingArray.length;
    }

    public void addFirst(T x) {
        if ((nextIdx + 1) % backingArray.length == firstIdx) {
            doubleBackingArraySize();
        }

        firstIdx -= 1;
        // Note: in Java -1 % n == -1
        if (firstIdx < 0) {
            firstIdx += backingArray.length;
        }
        backingArray[firstIdx] = x;
    }

    public void removeFirst() {
        if (size() == 0) {
            throw new NoSuchElementException();
        } else {
            firstIdx += 1;
            firstIdx %= backingArray.length;
        }
    }

    public void removeLast() {
        if (size() == 0) {
            throw new NoSuchElementException();
        } else {
            nextIdx -= 1;
            if (nextIdx < 0) {
                nextIdx += backingArray.length;
            }
        }
    }

    public T getFromFirst(int i) {
        if (i < 0 || i >= size()) {
            throw new NoSuchElementException();
        } else {
            //noinspection unchecked
            return (T)backingArray[(firstIdx + i) % backingArray.length];
        }
    }

    public T getFromLast(int i) {
        if (i < 0 || i >= size()) {
            throw new NoSuchElementException();
        } else {
            int idx = nextIdx - 1 - i;
            if (idx < 0) {
                idx += backingArray.length;
            }
            //noinspection unchecked
            return (T)backingArray[idx];
        }
    }

}

Tests:

import org.junit.Assert;
import org.junit.Test;

import java.util.NoSuchElementException;

public class RingBufferTests {

    @Test
    public void populateAndRandomAccess() {
        RingBuffer<Integer> buffer = new RingBuffer<>();
        buffer.addLast(5); // [5]
        buffer.addLast(6); // [5, 6]
        buffer.addLast(7); // [5, 6, 7]

        Assert.assertEquals(5, (int)buffer.getFromFirst(0));
        Assert.assertEquals(6, (int)buffer.getFromFirst(1));
        Assert.assertEquals(7, (int)buffer.getFromFirst(2));
    }

    @Test
    public void populateAndRandomAccessFromLast() {
        RingBuffer<Integer> buffer = new RingBuffer<>();
        buffer.addLast(5); // [5];
        buffer.addLast(6); // [5, 6]
        buffer.addLast(7); // [5, 6, 7]

        Assert.assertEquals(7, (int)buffer.getFromLast(0));
        Assert.assertEquals(6, (int)buffer.getFromLast(1));
        Assert.assertEquals(5, (int)buffer.getFromLast(2));
    }

    @Test
    public void populateFromFirst() {
        RingBuffer<Integer> buffer = new RingBuffer<>();
        buffer.addFirst(5); // [5]
        buffer.addFirst(6); // [6, 5]
        buffer.addFirst(7); // [7, 6, 5]

        Assert.assertEquals(5, (int)buffer.getFromLast(0));
        Assert.assertEquals(6, (int)buffer.getFromLast(1));
        Assert.assertEquals(7, (int)buffer.getFromLast(2));

        Assert.assertEquals(7, (int)buffer.getFromFirst(0));
        Assert.assertEquals(6, (int)buffer.getFromFirst(1));
        Assert.assertEquals(5, (int)buffer.getFromFirst(2));
    }

    @Test
    public void populateFromBothEnds() {
        RingBuffer<Integer> buffer = new RingBuffer<>();
        buffer.addFirst(6); // [6]
        buffer.addFirst(5); // [5, 6]
        buffer.addLast(7);  // [5, 6, 7]
        buffer.addLast(8);  // [5, 6, 7, 8]

        Assert.assertEquals(8, (int)buffer.getFromLast(0));
        Assert.assertEquals(7, (int)buffer.getFromLast(1));
        Assert.assertEquals(6, (int)buffer.getFromLast(2));
        Assert.assertEquals(5, (int)buffer.getFromLast(3));

        Assert.assertEquals(5, (int)buffer.getFromFirst(0));
        Assert.assertEquals(6, (int)buffer.getFromFirst(1));
        Assert.assertEquals(7, (int)buffer.getFromFirst(2));
        Assert.assertEquals(8, (int)buffer.getFromFirst(3));
    }

    @Test
    public void outOfBoundsAccessThrows() {
        RingBuffer<Integer> buffer = new RingBuffer<>();
        buffer.addLast(5); // [5]
        buffer.addLast(6); // [5, 6]
        buffer.addLast(7); // [5, 6, 7]

        Assert.assertThrows(NoSuchElementException.class, () -> buffer.getFromFirst(3));
        Assert.assertThrows(NoSuchElementException.class, () -> buffer.getFromFirst(4));
        Assert.assertThrows(NoSuchElementException.class, () -> buffer.getFromFirst(5));
        Assert.assertThrows(NoSuchElementException.class, () -> buffer.getFromLast(3));
        Assert.assertThrows(NoSuchElementException.class, () -> buffer.getFromLast(4));
        Assert.assertThrows(NoSuchElementException.class, () -> buffer.getFromLast(5));

        Assert.assertThrows(NoSuchElementException.class, () -> buffer.getFromFirst(-1));
        Assert.assertThrows(NoSuchElementException.class, () -> buffer.getFromLast(-1));
    }

    @Test
    public void removingWhenEmptyThrows() {
        RingBuffer<Integer> buffer = new RingBuffer<>();
        buffer.addLast(5); // [5]
        buffer.addLast(6); // [5, 6]
        buffer.addLast(7); // [5, 6, 7]

        buffer.removeFirst();
        buffer.removeFirst();
        buffer.removeFirst();

        Assert.assertThrows(NoSuchElementException.class, buffer::removeFirst);
        Assert.assertThrows(NoSuchElementException.class, buffer::removeLast);
    }

    @Test
    public void populateAndRemove() {
        RingBuffer<Integer> buffer = new RingBuffer<>();
        buffer.addLast(5); // [5]
        buffer.addLast(6); // [5, 6]
        buffer.addLast(7); // [5, 6, 7]

        buffer.removeFirst();   // Should remove the 5

        Assert.assertEquals(6, (int)buffer.getFromFirst(0));
        Assert.assertEquals(7, (int)buffer.getFromFirst(1));

        Assert.assertEquals(6, (int)buffer.getFromLast(1));
        Assert.assertEquals(7, (int)buffer.getFromLast(0));
    }

    @Test
    public void populateAndRemoveManyTimes() {
        RingBuffer<Integer> buffer = new RingBuffer<>();

        // This should result in the buffer always containing between 3 and 5 elements.
        buffer.addLast(-1);
        buffer.addLast(-1);
        buffer.addLast(-1);
        for (int i=0; i < 100; i+=2) {
            buffer.addLast(i);
            buffer.addLast(i+1);
            buffer.removeFirst();
            buffer.removeFirst();
        }

        // Check that the buffer has only 3 elements
        Assert.assertEquals(3, buffer.size());
        // Check that these elements are [97, 98, 99]
        Assert.assertEquals(97, (int)buffer.getFromFirst(0));
        Assert.assertEquals(98, (int)buffer.getFromFirst(1));
        Assert.assertEquals(99, (int)buffer.getFromFirst(2));

        // Check that the buffer has not grown in capacity to some absurd size
        // Will use 8 since my implementation will probably grow by doubling the backing array size.
        Assert.assertTrue(buffer.capacity() <= 8);
    }
}

By the way, I know this never shrinks the backing array, even if the number of elements in the RingBuffer drops well below the capacity. I don't consider this to be an issue for my application.

\$\endgroup\$
1
\$\begingroup\$

Observations

  • The class is not thread-safe, so why is method doubleBackingArraySize synchronized?
  • All methods perform some sort of redundancy in circular incrementation and decrementation. This kind of arithmetic could be placed in 2 separate methods, which you would then call in the other methods to have more DRY code.
  • Deciding when to allocate more space is a repeating code block that could be placed into a helper method.
  • You present a great set of unit tests.

Circular arithmetic

These could be the reusable helpers methods. Naming conventions conform Java's implementation of ArrayBlockingQueue.

final int inc(int i) {
    return ++i % items.length;
}

final int dec(int i) {
    return (--i + items.length) % items.length;
}

DRY

Put the following recurring code into a helper:

if ((nextIdx + 1) % backingArray.length == firstIdx) {
    doubleBackingArraySize();
}
final void CheckArrayCapacity() {
    if ((nextIdx + 1) % backingArray.length == firstIdx) {
        doubleBackingArraySize();
    }
}

Refactoring Code

For instance, addFirst could be written as:

public void addFirst(T x) {
    CheckArrayCapacity();
    firstIdx = dec(firstIdx);
    backingArray[firstIdx] = x;
}

instead of:

public void addFirst(T x) {
    if ((nextIdx + 1) % backingArray.length == firstIdx) {
        doubleBackingArraySize();
    }

    firstIdx -= 1;
    // Note: in Java -1 % n == -1
    if (firstIdx < 0) {
        firstIdx += backingArray.length;
    }
    backingArray[firstIdx] = x;
}

All other methods could be written in a succinct way as above.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Great, those refactorings are much cleaner. Adding synchronized was just a bad habit - I thought "Oh, I'm modifying the backing array, better not have two threads trying to do this at once!". But there's so many other places that this isn't thread-safe that it was just misleading. I've removed it now. \$\endgroup\$ – Harry Braviner Sep 24 '19 at 14:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.