A Circular Buffer

The other day, I came across one of those rare situations where I needed a collection class type that’s not supported by the JSE. I had the need to gather some statistics, and only needed to know the most recent 100 values... the sort of functionality that can easily be supplied by an old fashioned circular buffer.

Circular buffers are good when you need an ever changing list of items and need to conserve memory. Note that this version of a circular buffer implements the Iterator interface allowing you to use the new for loop.


package marin.utils.util;

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
* Demonstration of buffer circular buffer. Given that it's a fixed size buffer, then once it's
* full, it overwrites the elements at the start of the buffer, as they're considered invalid.
*
* Uses: In that certain situation where you only need the last 'n' values of buffer constantly
* updating list.
*
* @author Roger
* @param <T>
*            The type of object held by the buffer
* @Date 11/1/2011
*/
public class CircularBuffer<T> implements Iterable<T> {

  /** The elements in the buffer */
  private final T[] buffer;
  /** number of elements on buffer */
  private int num;
  /** index of last used slot */
  private int last = -1;
  /** The first element to retrieve */
  private int first;

  /**
   * @param capacity
   *            The fixed size of the buffer
   */
  @SuppressWarnings("unchecked")
  public CircularBuffer(int capacity) {
    buffer = (T[]) new Object[capacity];
  }

  /**
   * @return true if the buffer is empty
   */
  public boolean isEmpty() {
    return num == 0;
  }

  /**
   * @return The number of elements in the buffer
   */
  public int size() {
    return num;
  }

  /**
   * insert an item into the buffer. If the buffer is full then overwrite old values
   *
   * @param item
   *            The item to insert
   */
  public void enqueue(T item) {

    last = getPositionValue(last);
    buffer[last] = item;
    incrementSize();
    setFirst();
  }

  private void setFirst() {
    if ((num == buffer.length) && (first == last)) {
      first = getPositionValue(first);
    }
  }

  private int getPositionValue(int pos) {
    return ++pos % buffer.length; // wrap-around
  }

  private void incrementSize() {

    if (++num > buffer.length) {
      num = buffer.length;
    }
  }

  /**
   * Remove the least recently added item
   *
   * @return The oldest item in the buffer
   */
  // - doesn't check for underflow
  public T dequeue() {
    if (isEmpty()) {
      throw new RuntimeException("Circular buffer underflow");
    }

    T item = getNextValue();
    return item;
  }

  private T getNextValue() {
    T item = buffer[first];
    buffer[first] = null; // to help with garbage collection
    num--;
    first = getPositionValue(first);
    return item;
  }

  /**
   * @see java.lang.Iterable#iterator()
   */
  @Override
  public Iterator<T> iterator() {
    return new CircularBufferIterator();
  }

  // an iterator, doesn't implement remove() since it's optional
  private class CircularBufferIterator implements Iterator<T> {

    private int index = first;
    private int i = 0;

    public boolean hasNext() {
      return i < num;
    }

    public void remove() {
      throw new UnsupportedOperationException();
    }

    public T next() {
      if (!hasNext()) {
        throw new NoSuchElementException();
      }

      T retVal = buffer[index];
      index = getPositionValue(index);
      i++;
      return retVal;
    }
  }

}