A Generic Circular Buffer in C#

• Download source - 14.4 KB

Introduction

Microsoft .NET provides a few basic generic data structures such as Stack<T>, Queue<T>, and LinkedList<T>, but no circular buffer or DEque ("double ended" queue). This class aims to fill that gap.

Conceptualizing this Mess

A circular buffer allows for rapid pushing and popping from the front and back of the container. These operations are O(1) while other inserts and removes are O(n) assuming no reallocations.

This makes the buffer suitable as a generic stack or queue. The reason one might want to use this class this way despite Microsoft's stack or queue is that this class allows access by index, and fully implements IList<T>. 

Using this Mess

The class is relatively easy to use. Most of the IList<T> and ICollection<T> interface members are explicit because most of their operations are O(n) instead of O(1). This means you'll have to cast to the appropriate interface in order to fully access its list or collection members. This is to prevent casual misuse of the data structure - it's not intended primarily as a list class, but may be used as one. The access modifiers reflect this.

The primary API consists of PushBack()/PopBack() and PushFront()/PopFront() which add and remove items from the back or front of the container, respectively. There are also some more standard list/collection members like Contains(), IndexOf(), this[] and Clear()

Here's an excerpt from the demo/test code:

Console.WriteLine("Adding 10 items");
for (var i = 0; i < 10; ++i)
    list.PushBack(i + 1);

Console.Write("Enumerating "+ list.Count+" items:");
foreach (var item in list)
    Console.Write(" " + item.ToString());
Console.WriteLine();

Console.WriteLine("Removing 1 item");
list.PopFront();

It's all doc commented and straightforward.

Points of Interest

I really can't stand implementing Insert(), especially over a circular buffer, and if there's a bug, it's probably in the Insert() code. I'm not sure if the routine can be simplified. There are a lot of corner cases.

History

• 6^th February, 2020 - Initial submission