Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 1 of 1

Thread: Java tip Aug 26, 2010 - Circular Buffers

  1. #1
    Super Moderator helloworld922's Avatar
    Join Date
    Jun 2009
    Posts
    2,896
    Thanks
    23
    Thanked 619 Times in 561 Posts
    Blog Entries
    18

    Default 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.
    Last edited by helloworld922; August 27th, 2010 at 07:21 PM.

  2. The Following 2 Users Say Thank You to helloworld922 For This Useful Post:

    copeg (August 26th, 2010), JavaPF (August 27th, 2010)


Similar Threads

  1. Java Tip Jul 29, 2010 - Swing Console Component
    By helloworld922 in forum Java Swing Tutorials
    Replies: 6
    Last Post: April 16th, 2014, 12:08 AM
  2. Java Tip Aug 4, 2010 - How to use File Filters
    By helloworld922 in forum Java Programming Tutorials
    Replies: 0
    Last Post: August 4th, 2010, 05:08 PM
  3. Java Tip Jul 5, 2010 - [Eclipse IDE] Navigating through code
    By helloworld922 in forum Java JDK & IDE Tutorials
    Replies: 1
    Last Post: July 5th, 2010, 06:28 AM
  4. Dare 2010 calls for emerging game developers
    By jeet893 in forum Java Networking
    Replies: 0
    Last Post: March 5th, 2010, 02:51 PM
  5. circular linked list
    By student123xyz in forum Collections and Generics
    Replies: 4
    Last Post: August 19th, 2009, 10:40 AM