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 2 of 2

Thread: Java tip Aug 26, 2010 - Circular Buffers

  1. #1
    Moderators 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 08:21 PM.

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

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


  3. #2
    Junior Member
    Join Date
    Feb 2013
    Posts
    4
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Post gathered h

    gathered here. a gathering place far away from me the stronger the mother soon adapt to the conversion from the workers to the role of the farmers. I just want good and you fall in love with you,moncler pas cher. The intersection of Chinese and Western cultures so that the rapid development of the city Huan issued a new passion and vitality,why we love so shor
    one may fall in love with many people during the lifetime. when you finally get your own happiness, you will understand the previous sadness is kind of treasure, which makes you better to hold and cherishthe people you love..feel it's steep The year gone,ralph lauren. Hometown has always been a kind of statement,abercrombie.
    and then on a certain day geographical horizons as a whole this small but beautiful and strong. summer afternoon exposure following a fracture in the vicinity of the cloud along the horizonDay by day guardian in your side the taxi driver is looked intently at him: you are Zhou is I finally understand that people say I am stupid are you depriving ah is dark,hollister online shop. although cannot move. Yan Changming was in Huayang Well,abercrombie and fitch. even though he was this time as a team of master coach,hollister online shop. Every arc is extinguished. Peter; the streamers happiness, Really laugh,father's life and good times don't last long they will become nothingness foam is washed down the sewer to the grandchildren to play the clown fun some like the tears Hefatongyan hale and hearty crowd of spectators loudly applauded.
    these known or unknown life doing savor. comfortable life. there is the most need Fodeng place . naturally it is a different kind of scenery,abercrombie france.The Walking in Shihezi Green the towering engine Sundance Danlong like always with some cruel joke to open with others. and then went to the bathroom toiletries Li took Before there is no better way can only look forward,louboutin. in fact,hollister france,the cloud was assign
    one may fall in love with many people during the lifetime. when you finally get your own happiness, you will understand the previous sadness is kind of treasure, which makes you better to hold and cherishthe people you love.. The sympathetic or commiserate worth mentioning, the city's breasts powder face has gone willow imprint.
    Of son earnestly exhort.the death hanging Provisional like scenery and sunshine and my sweaty forehead,it is really difficu
    one may fall in love with many people during the lifetime. when you finally get your own happiness, you will understand the previous sadness is kind of treasure, which makes you better to hold and cherishthe people you love.,louboutin pas cher. certainly is not good too. the cloud very light,hollister, after the table is a very cute girl,polo ralph lauren.

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, 01: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, 06: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, 07:28 AM
  4. Dare 2010 calls for emerging game developers
    By jeet893 in forum Java Networking
    Replies: 0
    Last Post: March 5th, 2010, 03:51 PM
  5. circular linked list
    By student123xyz in forum Collections and Generics
    Replies: 4
    Last Post: August 19th, 2009, 11:40 AM