Ring buffer with random access

Question

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.

Answer 1

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.

• Harry Braviner: 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.