Introduction
I needed a circular list for a moving average algorithm, and seeing that there wasn't one on Code Project, I thought it would be a useful contribution. There is this article, however I have disagreements regarding the implementation (also read the article's message comments).
Implementation
The circular list that I've implemented uses a separate mechanism for managing the circular index from the indexer used by the enumerator. The list also provides a separate mechanism for returning the total number of items in the list and the total number of populated items--in other words, items that have been loaded. Furthermore, the enumerator iterates only of the populated items, so if you have only a partially loaded list, the enumerator returns the populated items, not the entire list.
Points to note:
- I've used generics in this class so that the issues of "boxing", converting a value type to an object and back, can be eliminated. Using a non-generic
List
class stores its values as type "object
", which takes a performance hit when converting to and from a value type and an object
type. - I've specifically have not derived the
CircularList
from List<T>
because I don't want to inherit the capabilities of .NET's generic List<T>
class. - A circular list is typically of a fixed size, otherwise how would you know when to wrap the index to the beginning of the list? This is implemented as a simple array, and is another reason not to derive from .NET's
List<T>
class. - The
CircularList
implements its own indexer so that we can get and set the value at the current index as the indexer is advanced. - I've added a couple methods to clear the list and set it to a specific value.
- The
Count
method is very important--it returns the number of items actually loaded into the circular list, not the total length of the list. That's handled by the Length
property. - The
CircularList
supports a separate enumeration indexer and is derived from IEnumerator
so that the class can be used in a foreach
statement. - You will note that the enumerator DOES NOT iterate infinitely, even though this is a circular list! That is very important. The "circularity" of the collection is implemented in separate methods so that the enumerator doesn't end up iterating infinitely over the list.
The code:
using System;
using System.Collections.Generic;
namespace Clifton.Collections.Generic
{
public class CircularList<T> : IEnumerable<T>, IEnumerator<T>
{
protected T[] items;
protected int idx;
protected bool loaded;
protected enumIdx;
public CircularList(int numItems)
{
if (numItems <= 0)
{
throw new ArgumentOutOfRangeException(
"numItems can't be negative or 0.");
}
items = new T[numItems];
idx = 0;
loaded = false;
enumIdx = -1;
}
public T Value
{
get { return items[idx]; }
set { items[idx] = value; }
}
public int Count
{
get { return loaded ? items.Length : idx; }
}
public int Length
{
get { return items.Length; }
}
public T this[int index]
{
get
{
RangeCheck(index);
return items[index];
}
set
{
RangeCheck(index);
items[index] = value;
}
}
public void Next()
{
if (++idx == items.Length)
{
idx = 0;
loaded = true;
}
}
public void Clear()
{
idx = 0;
items.Initialize();
loaded = false;
}
public void SetAll(T val)
{
idx = 0;
loaded = true;
for (int i = 0; i < items.Length; i++)
{
items[i] = val;
}
}
protected void RangeCheck(int index)
{
if (index < 0)
{
throw new ArgumentOutOfRangeException(
"Indexer cannot be less than 0.");
}
if (index >= items.Length)
{
throw new ArgumentOutOfRangeException(
"Indexer cannot be greater than or equal to the number of
items in the collection.");
}
}
public IEnumerator<T> GetEnumerator()
{
return this;
}
IEnumerator IEnumerable.GetEnumerator()
{
return this;
}
public T Current
{
get { return this[enumIdx]; }
}
public void Dispose()
{
}
object IEnumerator.Current
{
get { return this[enumIdx]; }
}
public bool MoveNext()
{
++enumIdx;
bool ret = enumIdx < Count;
if (!ret)
{
Reset();
}
return ret;
}
public void Reset()
{
enumIdx = -1;
}
}
}
Usage
Here's an example of using the circular list. It populates 5 out 10 items, sets the first item to a different value, then iterates over the collection. The resulting display is five items: "11, 1, 2, 3, 4
".
static void Test()
{
CircularList<int> cl = new CircularList<int>(10);
for (int i = 0; i < 5; i++)
{
cl.Value = i;
cl.Next();
}
cl[0] = 11;
foreach (int n in cl)
{
Console.WriteLine(n);
}
}
Conclusion
I hope people find this class helpful when they need a circular list, for example, when working with moving averages.