Click here to Skip to main content
14,454,989 members

A Generic Circular Buffer in C#

Rate this:
4.84 (9 votes)
Please Sign up or sign in to vote.
4.84 (9 votes)
6 Feb 2020MIT
A circular buffer implementing IList

CircularDemo

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

  • 6th February, 2020 - Initial submission

License

This article, along with any associated source code and files, is licensed under The MIT License

Share

About the Author

honey the codewitch
United States United States
Just a shiny lil monster. Casts spells in C++. Mostly harmless.

Comments and Discussions

 
QuestionThis is DList<T> Pin
Qwertie16-Feb-20 6:24
MemberQwertie16-Feb-20 6:24 
QuestionActually a Circular Buffer? Pin
Bruce Greene8-Feb-20 6:26
MemberBruce Greene8-Feb-20 6:26 
AnswerRe: Actually a Circular Buffer? Pin
honey the codewitch8-Feb-20 6:50
mvahoney the codewitch8-Feb-20 6:50 
GeneralRe: Actually a Circular Buffer? Pin
Bruce Greene8-Feb-20 7:37
MemberBruce Greene8-Feb-20 7:37 
GeneralRe: Actually a Circular Buffer? Pin
honey the codewitch8-Feb-20 8:24
mvahoney the codewitch8-Feb-20 8:24 
QuestionCircularBuffer Pin
Howard Duane Allman7-Feb-20 10:55
professionalHoward Duane Allman7-Feb-20 10:55 
AnswerRe: CircularBuffer Pin
honey the codewitch7-Feb-20 12:08
mvahoney the codewitch7-Feb-20 12:08 
AnswerRe: CircularBuffer Pin
Member 116912058-Feb-20 4:13
MemberMember 116912058-Feb-20 4:13 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Tip/Trick
Posted 6 Feb 2020

Stats

5.5K views
145 downloads
7 bookmarked