How Would You Code an Efficient Circular Buffer in Java or C#

How would you code an efficient Circular Buffer in Java or C#?

I would use an array of T, a head and tail pointer, and add and get methods.

Like: (Bug hunting is left to the user)

// Hijack these for simplicity
import java.nio.BufferOverflowException;
import java.nio.BufferUnderflowException;

public class CircularBuffer<T> {

  private T[] buffer;

  private int tail;

  private int head;

  @SuppressWarnings("unchecked")
  public CircularBuffer(int n) {
    buffer = (T[]) new Object[n];
    tail = 0;
    head = 0;
  }

  public void add(T toAdd) {
    if (head != (tail - 1)) {
        buffer[head++] = toAdd;
    } else {
        throw new BufferOverflowException();
    }
    head = head % buffer.length;
  }

  public T get() {
    T t = null;
    int adjTail = tail > head ? tail - buffer.length : tail;
    if (adjTail < head) {
        t = (T) buffer[tail++];
        tail = tail % buffer.length;
    } else {
        throw new BufferUnderflowException();
    }
    return t;
  }

  public String toString() {
    return "CircularBuffer(size=" + buffer.length + ", head=" + head + ", tail=" + tail + ")";
  }

  public static void main(String[] args) {
    CircularBuffer<String> b = new CircularBuffer<String>(3);
    for (int i = 0; i < 10; i++) {
        System.out.println("Start: " + b);
        b.add("One");
        System.out.println("One: " + b);
        b.add("Two");
        System.out.println("Two: " + b);
        System.out.println("Got '" + b.get() + "', now " + b);

        b.add("Three");
        System.out.println("Three: " + b);
        // Test Overflow
        // b.add("Four");
        // System.out.println("Four: " + b);

        System.out.println("Got '" + b.get() + "', now " + b);
        System.out.println("Got '" + b.get() + "', now " + b);
        // Test Underflow
        // System.out.println("Got '" + b.get() + "', now " + b);

        // Back to start, let's shift on one
        b.add("Foo");
        b.get();
    }
  }
}

How to efficiently wrap the index of a fixed-size circular buffer

Best I've come up with is:

public static int Wrap(int index, int n)
{
    return ((index % n) + n) % n;
}

(Assuming you need to work with negative numbers)

What's the appropriate collection for calculating a running mean?

It appears that you're looking for a Circular Buffer. Here's a .NET implementation on CodePlex. You may also want to look at this question: How would you code an efficient Circular Buffer in Java or C#?

From the sample you've provided, it isn't clear how exactly this relates to an online-mean algorithm. If the only operation allowed on the buffer is to append; it should be trivial to cache and update the "total" inside the buffer (add the new value, subtract the removed one); making the maintaining of the mean an O(1) operation for every append. In this case, the buffer is effectively holding the Simple Moving Average (SMA) of a series.

Removing older values from a List

Alright I finally got a chance to think about this problem myself and found a good compromise without going through too much effort. Why not just use a linked list.

1. For a history type of implementation, just keep track of the pointer.
2. It will still be linear time for sequencing operations.
3. Removing the last value can be done in constant time.

I guess I failed to mention that random access wasn't too important...

How do you implement a circular buffer in C?

Can you enumerate the types needed at the time you code up the buffer, or do you need to be able to add types at run time via dynamic calls? If the former, then I would create the buffer as a heap-allocated array of n structs, where each struct consists of two elements: an enum tag identifying the data type, and a union of all the data types. What you lose in terms of extra storage for small elements, you make up in terms of not having to deal with allocation/deallocation and the resulting memory fragmentation. Then you just need to keep track of the start and end indices that define the head and tail elements of the buffer, and make sure to compute mod n when incrementing/decrementing the indices.

What are the uses of circular buffer?

I've used it for an in-memory log with a restricted size. For example, the application would write log entries while processing user requests. Whenever an exception occurred (that would be disruptive to the processing) the log records currently in memory would be dumped along with it.

The benefit of a circular buffer is, that you don't need infinite amounts of memory, since older entries get overridden automatically. The "challange" is, that you need to find a suitable size for your usecase. In the example above, it would be very unfortunate when the log record with the most vital information about the exception would have already been overridden.

Some systems/applications have tools to let you extract the current content of the buffer on demand, and not only when it would be extract automatically (if ever).

I believe ETW and the CLRs stress log, amongst many other system's kernel or highperformance trace/logging, are implemented that way.

The concept of using such buffers for in-memory tracing/logging is actually pretty common (not to say that this is the only use - certainly not), because it is way faster than written records to a file/database that you might never be interested in unless an error occurs. And on a related note, it conserves harddisk space.

Maximum capacity collection in c#

What you are describing is a circular buffer. I use these occasionally and recently ported some older code into a genericised C# class (attached). This code is part of SharpNeat V2 development.

This has O(1) performance on add and remove oprations whereas the solution posted that encapsulates a List is O(n). This is because removing the 0th item in a list causes all other items to be shuffled down to fill the gap.

using System;
using System.Collections.Generic;
using System.Text;

namespace SharpNeat.Utility
{
    /// 
    /// This is a generic circular buffer of items of type T.  A circular buffer must be assigned
    /// a capacity at construction time. Items can be enqueued indefintely, but when the buffer's 
    /// capacity is reached the oldest values in the buffer are overwritten, thus the buffer is best
    /// thought of as a circular array or buffer.
    /// 
    public class CircularBuffer
    {
        /// 
        /// Internal array that stores the circular buffer's values.
        /// 
        protected T[] _buff;

        /// 
        /// The index of the previously enqueued item. -1 if buffer is empty.
        /// 
        protected int _headIdx;

        /// 
        /// The index of the next item to be dequeued. -1 if buffer is empty.
        /// 
        protected int _tailIdx;

        #region Constructors

        /// 
        /// Constructs a circular buffer with the specified capacity.
        /// 
        /// 
        public CircularBuffer(int capacity)
        {
            _buff = new T[capacity];
            _headIdx = _tailIdx = -1;
        }

        #endregion

        #region Properties

        /// 
        /// Gets the number of items in the buffer. Returns the buffer's capacity
        /// if it is full.
        /// 
        public int Length
        {
            get
            {
                if(_headIdx == -1) 
                    return 0;

                if(_headIdx > _tailIdx)
                    return (_headIdx - _tailIdx) + 1;

                if(_tailIdx > _headIdx)
                    return (_buff.Length - _tailIdx) + _headIdx + 1;

                return 1;
            }
        }

        #endregion

        #region Public Methods

        /// 
        /// Clear the buffer.
        /// 
        public virtual void Clear()
        {
            _headIdx = _tailIdx = -1;
        }

        /// 
        /// Enqueue a new item. This overwrites the oldest item in the buffer if the buffer
        /// has reached capacity.
        /// 
        /// 
        public virtual void Enqueue(T item)
        {
            if(_headIdx == -1)
            {   // buffer is currently empty.
                _headIdx = _tailIdx = 0;
                _buff[0] = item;
                return;
            }

            // Determine the index to write to.
            if(++_headIdx == _buff.Length)
            {   // Wrap around.
                _headIdx = 0;
            }

            if(_headIdx == _tailIdx)
            {   // Buffer overflow. Increment tailIdx.
                if(++_tailIdx == _buff.Length) 
                {   // Wrap around.
                    _tailIdx=0;
                }
                _buff[_headIdx] = item;
                return;
            }

            _buff[_headIdx] = item;
            return;
        }

        /// 
        /// Remove the oldest item from the back end of the buffer and return it.
        /// 
        /// 
        public virtual T Dequeue()
        {
            if(_tailIdx == -1)
            {   // buffer is currently empty.
                throw new InvalidOperationException("buffer is empty.");
            }

            T item = _buff[_tailIdx];

            if(_tailIdx == _headIdx)
            {   // The buffer is now empty.
                _headIdx=_tailIdx=-1;
                return item;
            }

            if(++_tailIdx == _buff.Length)
            {   // Wrap around.
                _tailIdx = 0;
            }

            return item;
        }

        /// 
        /// Pop the most recently added item from the front end of the buffer and return it.
        /// 
        /// 
        public virtual T Pop()
        {
            if(_tailIdx == -1)
            {   // buffer is currently empty.
                throw new InvalidOperationException("buffer is empty.");
            }   

            T item = _buff[_headIdx];

            if(_tailIdx == _headIdx)
            {   // The buffer is now empty.
                _headIdx = _tailIdx =- 1;
                return item;
            }

            if(--_headIdx==-1)
            {   // Wrap around.
                _headIdx=_buff.Length-1;
            }

            return item;
        }

        #endregion
    }
}

---

Related Topics