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

Asked 2009-02-26T11:02:23.113

I want a simple class that implements a fixed-size circular buffer. It should be efficient, easy on the eyes, generically typed.

For now it need not be MT-capable. I can always add a lock later, it won't be high-concurrency in any case.

Methods should be: .Add() and I guess .List(), where I retrieve all the entries. On second thought, Retrieval I think should be done via an indexer. At any moment I will want to be able to retrieve any element in the buffer by index. But keep in mind that from one moment to the next Element[n] may be different, as the circular buffer fills up and rolls over. This isn't a stack, it's a circular buffer.

Regarding "overflow": I would expect internally there would be an array holding the items, and over time the head and tail of the buffer will rotate around that fixed array. But that should be invisible from the user. There should be no externally-detectable "overflow" event or behavior.

This is not a school assignment - it is most commonly going to be used for a MRU cache or a fixed-size transaction or event log.

c# java class-design

Edit Report

2 Answers

System.Collections.Generic.Queue - is simple circular buffer inside (T[] with head and tail, just like in sample from JeeBee).

answered 2010-05-10T18:57:35.750

-8

// The following is in C#

public class fqueue
{

  // The following code implements a circular queue of objects

  //private data:

    private bool empty;
    private bool full;

    private int begin, end;

    private object[] x;

  //public data:

    public fqueue()
    {
        empty = !(full = false);
        begin = end = 0xA2;

        x = new object[256];
        return;
    }

    public fqueue(int size)
    {
        if (1 > size) throw new Exception("fqueue: Size cannot be zero or negative");

        empty = !(full = false);
        begin = end = 0xA2;

        x = new object[size];
        return;
    }

    public object write
    {
        set
        {
            if(full) throw new Exception("Write error: Queue is full");

            end = empty ? end : (end + 1) % x.Length;

            full = ((end + 1) % x.Length) == begin;
            empty = false;

            x[end] = value;
        }
    }

    public object read
    {
        get
        {
            if(empty) throw new Exception("Read error: Queue is empty");
            full = false;

            object ret = x[begin];

            begin = (empty=end==begin) ?
                begin :
                (begin + 1) % x.Length;

            return ret;
        }
    }

    public int maxSize
    {
        get
        {
            return x.Length;
        }
    }

    public int queueSize
    {
        get
        {
            return end - begin + (empty ? 0 : 1 + ((end < begin) ? x.Length : 0));
        }
    }

    public bool isEmpty
    {
        get
        {
            return empty;
        }
    }

    public bool isFull
    {
        get
        {
            return full;
        }
    }

    public int start
    {
        get
        {
            return begin;
        }
    }        

    public int finish
    {
        get
        {
            return end;
        }
    }
}

answered 2010-05-22T21:25:43.770

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

2 Answers

Your Answer