Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I have written my own for practice and also some tweaks for my specific requirement. There is an insert which can copy a range (well array copy really) which I am hoping is more efficient than individual element insert.

Can anyone make any comments specifically as regards efficiency and code elegance. I need to use this with Java 1.6 and am getting a warning on the array = newArray(size); line in the constructor. But that is the only issue I am currently aware of.

import java.util.Arrays;  //copyOf

public class CircularBuffer<T> {
    private T[] array;  //storage
    private int put_idx, get_idx, count; //get/put & internal num elements counter
    private final int size;   //size of internal array storage

    public CircularBuffer(int size) {
        get_idx = 0;
        put_idx = 0;
        count   = 0;
        this.size = size;

        //Type safety: A generic array of T is created for a varargs parameter - investigate how to remove warning
        array = newArray(size); 
    }

    //@SafeVarargs - ok in java 1.7
    static <T> T[] newArray(int length, T... array)
    {
        return Arrays.copyOf(array, length);
    }    

    void reset(){
        get_idx=put_idx=count=0;
    }

    public boolean empty() { return count == 0; }

    public boolean full() { return count == size; }


    int get_count() { return count; }

    //inserts a single new element
    public void insert(T element)
    {
        if(full())
            throw new ArrayIndexOutOfBoundsException("buffer full");

        array[put_idx++] = element;
        put_idx %= size;
        ++count;
    }

    //insert array of specified length
    public void insert(T[] thearray) {
        if(thearray.length + count > size)
            throw new ArrayIndexOutOfBoundsException("insufficient space to insert array");     

        //first copy to end - contiguous array copy
        int remaining = size - put_idx;
        if(remaining >= thearray.length) {
            System.arraycopy(thearray, 0, array, put_idx, thearray.length);
            put_idx += thearray.length;
            put_idx %= size;
        } else {
            System.arraycopy(thearray, 0, array, put_idx, remaining);
            int rest = thearray.length - remaining;
            System.arraycopy(thearray, remaining, array, 0, rest);
            put_idx = rest;
        }
        count += thearray.length;
    }

    //get the oldest element, move read pointer
    public T get()
    {
        if(empty())
            throw new ArrayIndexOutOfBoundsException("buffer empty");

        final T ret = array[get_idx++];
        get_idx %= size;
        --count;
        return ret;
    }  
}

Code to exercise class:

public class TestCircularBuffer {
    static public void main(String args[]) {
        new TestCircularBuffer().go();
    }

    void go() {
        int SIZE = 1000;
        int arr[] = new int[SIZE];

        for(int i = 0; i < SIZE; ++i) {
            arr[i] = i;
        }

        CircularBuffer<Integer> cb = new CircularBuffer<Integer>(10);

        //exercise circ buffer
        int i = 0;
        while(i < SIZE) {
            while(!cb.full())
                cb.insert(arr[i++]);

            while(!cb.empty())
                System.out.print(cb.get() + " ");
        }

        //now exercise array insert
        System.out.println("\nrange insert test");
        Integer marr[] = {1,2,3,4};

        i = 0;
        while(i < 20) {
            //will only be able to fit 2 lots
            cb.insert(marr);
            cb.insert(marr);

            while(!cb.empty())
                System.out.print(cb.get() + " ");

            ++i;
        }
    }
}
share|improve this question
add comment

2 Answers

up vote 1 down vote accepted
+100

I agree with everything from palacsint (7. could be discussed. If it is a requirement, then it is fine)
I will add some more thoughts.


import java.util.Arrays;  //copyOf

This comment is not necessary. Even more, noone (with an IDE) will read comments in the import section.


public class CircularBuffer<T> {

As far as I see it, your implementation is a fixed size (FIFO) queue. If I am right, I would choose this name instead of CircularBuffer.
With this name, even if it is not well defined, I would expect some circularity. There is none. (Not for the caller, the inside details are not interesting for anyone using this class.)
One could even argument, that using java collection (implement an interface, using collection classes) would be a good way to integrate it inside the java world.


private T[] array;  //storage
private int put_idx, get_idx, count; //get/put & internal num elements counter
private final int size;   //size of internal array storage

I would change the names, the array is in fact the buffer, put_idx the head, get_idx the tail, count the number of elements and size is not needed:

private final T[] buffer;
private int headIndex = 0;
private int tailIndex = 0;
private int numberOfElements = 0;

void reset(){
    get_idx=put_idx=count=0;
}

Do you need this method? If no, remove it. If you need it, it could be a good idea to clear the buffer, too. The garbage collector would appreciate this.


public boolean empty() { return count == 0; }

public boolean full() { return count == size; }

A typical and good name for a method returning a method is isSomething() or hasSomething(). So in this case isEmpty(), isFull().


int get_count() { return count; }

If we look at java collections, the typical and expected name would bet getSize()


//inserts a single new element
public void insert(T element)
{
    if(full())
        throw new ArrayIndexOutOfBoundsException("buffer full");

    array[put_idx++] = element;
    put_idx %= size;
    ++count;
}

I would throw an IllegalStateException exception. ArrayIndexOutOfBoundsException is not true, the buffer is full, it can not be out of bounds, unless the implementation is wrong.
In this case, the expected state is "not full", but it is "full".
Remark: Depending on the requirements, you could start to overwrite old entries. This would be typical for a circular buffer.

I would add some javadoc comments, at least to tell the caller about the exception he could catch.


//insert array of specified length
public void insert(T[] thearray) {

This comment is already clear from the method signature.
If we look at java collections again, I would rename it to addAll.
Which is quite important if you try to add for example null. Does it go to insert(T element) or insert(T[] thearray) ? Should it be there?

And again, javadoc


    if(thearray.length + count > size)
        throw new ArrayIndexOutOfBoundsException("insufficient space to insert array");     

See above


    //first copy to end - contiguous array copy
    int remaining = size - put_idx;
    if(remaining >= thearray.length) {
        System.arraycopy(thearray, 0, array, put_idx, thearray.length);
        put_idx += thearray.length;
        put_idx %= size;
    } else {
        System.arraycopy(thearray, 0, array, put_idx, remaining);
        int rest = thearray.length - remaining;
        System.arraycopy(thearray, remaining, array, 0, rest);
        put_idx = rest;
    }

This could be simplified, you do not need 2 complex cases:

    final int remaining = Math.min(thearray.length, size - put_idx);
    System.arraycopy(thearray, 0, buffer, put_idx, remaining);
    final int rest = thearray.length - remaining;
    System.arraycopy(thearray, remaining, buffer, 0, rest);
    put_idx = (put_idx + thearray.length) % size;
    numberOfElements += thearray.length;

And because the name and argument behavior of System.arraycopy is awful, I would introduce a small method. So anyone reading it could understand it without spending time on thinking about arraycopy:

private void copyNumberOfElementsFromArraySourceStartToBuffer(final int numberOfElements, final T[] arraySource, final int sourceStart) {
    System.arraycopy(arraySource, sourceStart, buffer, head, numberOfElements);
    head = (head + numberOfElements) % buffer.length;
}

//get the oldest element, move read pointer
public T get()
{
    if(empty())
        throw new ArrayIndexOutOfBoundsException("buffer empty");

    final T ret = array[get_idx++];
    get_idx %= size;
    --count;
    return ret;
}  

If we look at java collections again, I would rename it too removeOldest(). Or if you want to be very specific removeAndGetOldest().
It is not the typical expectation to remove the element if get is called. If you do so, add at least some javadoc comment indicating this behavior.
Exception: See above.


arr[var++]

This is only a personal opinion: I would avoid using the postincrement operator overall. This case looks simple, but you can easily get complicated cases because of side effects in all languages.
And with current compilers, it does (in most of the scenarios) not make any change in size, speed or whatever.
So I would go for readability.


All together, it could be something like this:

/**
 * A circular buffer. This is practically a fixed size FIFO queue. Which means you can enter a maximum amount of overall elements and can get the oldest.
 */
public class CircularBuffer<T> {
    private final T[] buffer;
    private int headIndex = 0;
    private int tailIndex = 0;
    private int numberOfElements = 0;

    public CircularBuffer(final int size) {
        buffer = newArray(size);
    }

    @SuppressWarnings("unchecked")
    // generics and arrays do not mix. we should be safe here.
    private T[] newArray(final int length) {
        return (T[]) new Object[length];
    }

    public boolean isEmpty() {
        return numberOfElements == 0;
    }

    public boolean isFull() {
        return numberOfElements == buffer.length;
    }

    /** Returns the current number of elements inside the buffer */
    public int getSize() {
        return numberOfElements;
    }

    /**
     * Inserts the given element.
     * @throws IllegalStateException if buffer has not enough free space
     */
    public void add(final T newElement) {
        if (isFull())
            throw new IllegalStateException("buffer full");

        buffer[headIndex] = newElement;
        headIndex = (headIndex + 1) % buffer.length;
        ++numberOfElements;
    }

    /**
     * Inserts the given elements.
     * @throws IllegalStateException if buffer has not enough free space
     */
    public void addAll(final T[] newElements) {
        if (newElements.length + numberOfElements > buffer.length)
            throw new IllegalStateException("insufficient space to insert array");

        // or: call add() method for all elements. Which should be the favored way.
        final int elementsToFillAtHead = Math.min(newElements.length, buffer.length - headIndex);
        copyNumberOfElementsFromArraySourceStartToBuffer(elementsToFillAtHead, newElements, 0);
        final int rest = newElements.length - elementsToFillAtHead;
        copyNumberOfElementsFromArraySourceStartToBuffer(rest, newElements, elementsToFillAtHead);
        numberOfElements += newElements.length;
    }

    private void copyNumberOfElementsFromArraySourceStartToBuffer(final int numberOfElements, final T[] arraySource, final int sourceStart) {
        System.arraycopy(arraySource, sourceStart, buffer, headIndex, numberOfElements);
        headIndex = (headIndex + numberOfElements) % buffer.length;
    }

    /** 
     * Get and remove the oldest element
     * @throws  IllegalStateException if buffer is empty
     */
    public T removeOldest() {
        if (isEmpty())
            throw new IllegalStateException("buffer empty");

        final T oldest = buffer[tailIndex];
        tailIndex = (tailIndex + 1) % buffer.length;
        --numberOfElements;
        return oldest;
    }
}
share|improve this answer
add comment

A few minor notes:

  1. Comments like the following are unnecessary:

    private T[] array; // storage
    

    You could call the field as storage and remove the comment.

  2. A "solution" for the warning in the constructor:

    @SuppressWarnings("unchecked")
    private T[] newArray(int length) {
        return (T[]) new Object[length];
    }
    

    Reference: Java how to: Generic Array creation

  3. camelCase variable and method names are more common in Java than underscored ones. (Code Conventions for the Java Programming Language, 9 - Naming Conventions)

  4. From Code Complete, 2nd Edition, p761:

    Use only one data declaration per line

    [...]

    It’s easier to modify declarations because each declaration is self-contained.

    [...]

    It’s easier to find specific variables because you can scan a single column rather than reading each line. It’s easier to find and fix syntax errors because the line number the compiler gives you has only one declaration on it.

  5. Setting default integer field values to zero is unnecessary in the constructor since zero is the default int value:

    getIdx = 0;
    putIdx = 0;
    count = 0;
    
  6. Does it make sense to create a CircularBuffer instance with zero size? If not check it and throw an IllegalArgumentException in the constructor.

  7. The second insert method might be a premature optimization.

  8. I'd throw IllegalStateException instead of ArrayIndexOutOfBoundsException. The clients of the class should not know that it uses an array (or anything else) for storage.

  9. Here are a few unit tests:

    @Test(expected = IllegalArgumentException.class)
    public void testZeroSize() {
        new CircularBuffer<String>(0);
    }
    
    @Test
    public void testIsEmptyOnNewBuffer() {
        final CircularBuffer<String> buffer = new CircularBuffer<String>(3);
        assertTrue(buffer.isEmpty());
    }
    
    @Test
    public void testIsFullOnNewBuffer() {
        final CircularBuffer<String> buffer = new CircularBuffer<String>(3);
        assertFalse(buffer.isFull());
    }
    
    @Test
    public void testIsEmpty() {
        final CircularBuffer<String> buffer = new CircularBuffer<String>(3);
        buffer.insert("a");
        assertFalse(buffer.isEmpty());
    }
    
    @Test
    public void testIsFull() {
        final CircularBuffer<String> buffer = new CircularBuffer<String>(3);
        buffer.insert("a");
        buffer.insert("b");
        buffer.insert("c");
        assertTrue(buffer.isFull());
    }
    
    @Test
    public void testIsEmptyAfterReset() {
        final CircularBuffer<String> buffer = new CircularBuffer<String>(3);
        buffer.insert("a");
        buffer.reset();
        assertTrue(buffer.isEmpty());
    }
    
    @Test
    public void testIsFullAfterReset() {
        final CircularBuffer<String> buffer = new CircularBuffer<String>(3);
        buffer.insert("a");
        buffer.insert("b");
        buffer.insert("c");
        buffer.reset();
        assertFalse(buffer.isFull());
    }
    
    @Test
    public void testIsEmptyOnUsedBuffer() {
        final CircularBuffer<String> buffer = new CircularBuffer<String>(3);
        buffer.insert("a");
        buffer.insert("b");
        buffer.insert("c");
    
        assertFalse("isEmpty 1", buffer.isEmpty());
        buffer.get();
        assertFalse("isEmpty 2", buffer.isEmpty());
        buffer.get();
        assertFalse("isEmpty 3", buffer.isEmpty());
        buffer.get();
        assertTrue("isEmpty 4", buffer.isEmpty());
    }
    
    @Test
    public void testIsFullOnUsedBuffer() {
        final CircularBuffer<String> buffer = new CircularBuffer<String>(3);
        buffer.insert("a");
        buffer.insert("b");
        buffer.insert("c");
        buffer.get();
    
        assertFalse("isFull 1", buffer.isFull());
        buffer.get();
        assertFalse("isFull 2", buffer.isFull());
        buffer.get();
        assertFalse("isFull 3", buffer.isFull());
    }
    
    @Test
    public void testInsert() {
        final CircularBuffer<String> buffer = new CircularBuffer<String>(3);
        buffer.insert("a");
        buffer.insert("b");
        buffer.insert("c");
    }
    
    @Test(expected = IllegalStateException.class)
    public void testInsertFull() {
        final CircularBuffer<String> buffer = new CircularBuffer<String>(3);
        buffer.insert("a");
        buffer.insert("b");
        buffer.insert("c");
        buffer.insert("d");
    }
    
    @Test(expected = IllegalStateException.class)
    public void testGetOnEmptyBuffer() {
        final CircularBuffer<String> buffer = new CircularBuffer<String>(3);
        buffer.get();
    }
    
    @Test(expected = IllegalStateException.class)
    public void testGetOnEmptyUsedBuffer() {
        final CircularBuffer<String> buffer = new CircularBuffer<String>(3);
        buffer.insert("a");
        buffer.get();
    
        buffer.get();
    }
    
    @Test
    public void testGet() {
        final CircularBuffer<String> buffer = new CircularBuffer<String>(3);
        buffer.insert("a");
        assertEquals("a", buffer.get());
        buffer.insert("b");
        buffer.insert("c");
    }
    
    @Test
    public void testDelayedGet() {
        final CircularBuffer<String> buffer = new CircularBuffer<String>(3);
        buffer.insert("a");
        buffer.insert("b");
        buffer.insert("c");
        assertEquals("a", buffer.get());
    }
    
    @Test
    public void testInsertAndGetTwice() {
        final CircularBuffer<String> buffer = new CircularBuffer<String>(3);
        buffer.insert("a");
        buffer.insert("b");
        buffer.insert("c");
        assertEquals("a", buffer.get());
        assertEquals("b", buffer.get());
        assertEquals("c", buffer.get());
    
        buffer.insert("d");
        buffer.insert("e");
        buffer.insert("f");
        assertEquals("d", buffer.get());
        assertEquals("e", buffer.get());
        assertEquals("f", buffer.get());
    }
    
    @Test
    public void testGetAndInsert() {
        final CircularBuffer<String> buffer = new CircularBuffer<String>(3);
        buffer.insert("a");
        assertEquals("a", buffer.get());
    
        buffer.insert("b");
        assertEquals("b", buffer.get());
    
        buffer.insert("c");
        assertEquals("c", buffer.get());
    
        buffer.insert("d");
        buffer.insert("e");
        assertEquals("d", buffer.get());
        assertEquals("e", buffer.get());
    
        buffer.insert("f");
        assertEquals("f", buffer.get());
    
        assertTrue("empty", buffer.isEmpty());
    }
    

    (I've renamed a few methods.)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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