Thread: Java tip Aug 26, 2010 - Circular Buffers

Introduction

Circular buffers are an interesting way of fitting a queue into into an array. They require less memory than a traditional linked-list implementation for queues, and I think are quite elegant. Also, because of the way circular buffers can be implemented you get random access basically for free (a little slower than array random access, but this usually is insignificant). Why you would want to use a queue with random access is still a mystery to me, but hey, why not

One downside (or upside) to using circular buffers is that they are fixed size, so once they're filled you have two options: re-allocate a new buffer with more space, or over-write the oldest data with the new data. They're also still limited to slower insertions/removal than linked lists because of the way arrays work (however, you could argue that a linked list must navigate to the location before inserting/removing an item, which takes O(n), the same as insertions/removals from an array).

Complexity analysis:

Enqueue - O(1) (unless resizing, but the average Enqueue can still be O(1))
Dequeue - O(1)
Insertion (not at the tail) - O(n)
Removal (not at the head) - O(n)
Search - O(n)
Sorting - O(n log(n)) (depends on which algorithm is being used, this is a little difficult to implement)
Random access - O(1) (a little slower than a pure array access, but not O(n) like a linked list)

Difficulty: Medium. I'm going to assume you have some knowledge of the Java syntax and basic OO principles, but there won't be any advanced topics discussed here.

Code

Sorry for just posting the code, but I'm a little stretched for time right now. As of right now, my implementation does not support random access.

import java.lang.reflect.Array;
import java.util.Collection;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Queue;
 
/**
 * @author Andrew
 * @param <E>
 *            the data type this Circular Buffer can hold
 */
public class CircularBuffer<E> implements Queue<E>
{
	private boolean	autoExpand;
	private E[]		data;
	private int		head;
	private int		size;
	private int		tail;
 
	/**
	 * Creates a Circular buffer with the default capacity of 10 that doesn't
	 * automatically expand.
	 */
	public CircularBuffer()
	{
		this(10, false);
	}
 
	/**
	 * Creates a circular buffer with the given capacity that doesn't
	 * automatically expand its size.
	 * 
	 * @param capacity
	 *            The capacity of this circular buffer.
	 */
	public CircularBuffer(int capacity)
	{
		this(capacity, false);
	}
 
	/**
	 * Creates a circular buffer with the given capacity
	 * 
	 * @param capacity
	 *            The initial capacity
	 * @param autoExpand
	 *            true if this buffer will automatically expand it's size
	 */
	@SuppressWarnings("unchecked")
	public CircularBuffer(int capacity, boolean autoExpand)
	{
		// unsafe, but this should be ok.
		data = (E[]) new Object[capacity];
		head = 0;
		tail = 0;
		this.autoExpand = autoExpand;
	}
 
	@Override
	public boolean add(E e)
	{
		if (!offer(e))
		{
			throw new IllegalStateException();
		}
		return true;
	}
 
	@Override
	public boolean addAll(Collection<? extends E> c)
	{
		Iterator<? extends E> iterator = c.iterator();
		while (iterator.hasNext())
		{
			add(iterator.next());
		}
		return false;
	}
 
	/**
	 * @return The current capacity of this circular buffer
	 */
	public int capacity()
	{
		return data.length;
	}
 
	@SuppressWarnings("unchecked")
	@Override
	public void clear()
	{
		data = (E[]) new Object[data.length];
		head = 0;
		tail = 0;
	}
 
	@Override
	public boolean contains(Object o)
	{
		Iterator<? extends E> iterator = iterator();
		while (iterator.hasNext())
		{
			E e = iterator.next();
			if (o == null ? e == null : o.equals(e))
			{
				return true;
			}
		}
		return false;
	}
 
	@Override
	public boolean containsAll(Collection<?> c)
	{
		Iterator<?> iterator = c.iterator();
		while (iterator.hasNext())
		{
			if (!contains(iterator.next()))
			{
				return false;
			}
		}
		return true;
	}
 
	@Override
	public E element()
	{
		if (size != 0)
		{
			return peek();
		}
		throw new NoSuchElementException();
	}
 
	/**
	 * @return true if this buffer auto expands
	 */
	public boolean getAutoExpand()
	{
		return autoExpand;
	}
 
	@Override
	public boolean isEmpty()
	{
		return size == 0;
	}
 
	@Override
	public Iterator<E> iterator()
	{
		return new Iterator<E>()
		{
			@SuppressWarnings("synthetic-access")
			private int	index	= head;
 
			@SuppressWarnings("synthetic-access")
			@Override
			public boolean hasNext()
			{
				return index != tail;
			}
 
			@SuppressWarnings("synthetic-access")
			@Override
			public E next()
			{
				if (!hasNext())
				{
					throw new NoSuchElementException();
				}
				E o = data[index];
				++index;
				if (index == data.length)
				{
					index = 0;
				}
				return o;
			}
 
			@Override
			public void remove()
			{
				// TODO
				throw new UnsupportedOperationException();
			}
		};
	}
 
	@SuppressWarnings("unchecked")
	@Override
	public boolean offer(E e)
	{
		if (size == data.length)
		{
			if (autoExpand)
			{
				// re-allocate a larger buffer
				E[] temp = (E[]) new Object[data.length * 2];
				Iterator<? extends E> iterator = iterator();
				for (int i = 0; i < size; ++i)
				{
					temp[i] = iterator.next();
				}
				head = 0;
				tail = size;
				data = temp;
			}
			else
			{
				return false;
			}
		}
		data[tail] = e;
		++tail;
		++size;
		if (tail == data.length)
		{
			tail = 0;
		}
		return true;
	}
 
	@Override
	public E peek()
	{
		if (size == 0)
		{
			return null;
		}
		return data[head];
	}
 
	@Override
	public E poll()
	{
		E o = peek();
		if (o != null)
		{
			data[head] = null;
			++head;
			--size;
			if (head == data.length)
			{
				head = 0;
			}
		}
		return o;
	}
 
	@Override
	public E remove()
	{
		E o = element();
		data[head] = null;
		++head;
		--size;
		if (head == data.length)
		{
			head = 0;
		}
		return o;
	}
 
	@Override
	public boolean remove(Object o)
	{
		// TODO Auto-generated method stub
		throw new UnsupportedOperationException();
	}
 
	@Override
	public boolean removeAll(Collection<?> c)
	{
		// TODO Auto-generated method stub
		throw new UnsupportedOperationException();
	}
 
	@Override
	public boolean retainAll(Collection<?> c)
	{
		// TODO Auto-generated method stub
		throw new UnsupportedOperationException();
	}
 
	/**
	 * Sets whether or not this circular buffer automatically expands when it
	 * reaches the capacity
	 * 
	 * @param autoExpand
	 *            true to enable auto expand
	 */
	public void setAutoExpand(boolean autoExpand)
	{
		this.autoExpand = autoExpand;
	}
 
	@Override
	public int size()
	{
		return size;
	}
 
	@Override
	public Object[] toArray()
	{
		Object[] array = new Object[size];
		Iterator<? extends E> iterator = iterator();
		for (int i = 0; i < size; ++i)
		{
			array[i] = iterator.next();
		}
		return array;
	}
 
	@SuppressWarnings("unchecked")
	@Override
	public <T> T[] toArray(T[] a)
	{
		if (a.length < size)
		{
			// use reflection to create a new array that's the correct size
			a = (T[]) Array.newInstance(a.getClass().getComponentType(), size);
		}
		Iterator<? extends E> iterator = iterator();
		for (int i = 0; i < size; ++i)
		{
			a[i] = (T) iterator.next();
		}
		return a;
	}
}

Usage

Because I chose to implement the Queue interface, you can use the circular buffer anywhere a Queue can be used (and for that matter, anywhere a Collection can be used).

// sample usage
// create a circular buffer with an initial capacity of 10 and auto-expand enabled
CircularBuffer<Integer> a = new CircularBuffer<Integer>(10, true);
a.offer(5);
a.offer(3);
// remove an item from the head
System.out.println(a.poll());
System.out.println(a.poll());
System.out.println(a.poll());
a.offer(6);
// peek at the item at the head
System.out.println(a.peek());
System.out.println(a.peek());
// clear the list
a.clear();

Conclusion

Hopefully this will serve as a useful piece of code you can use right away, and serve as a template for how to implement an efficient queue using arrays, or any other situation where circular buffers can help your program.

This code is provided "as is" and you are free to use it any way you want. I haven't tested it extensively, but it should work. If you do find any bugs, I would greatly appreciate the feedback (just post the feedback below). Some credit in your final product would be nice, but I don't feel compelled to enforce this if you don't.