A Circular List

• Download CircularList.zip - 1.9 KB

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;

    /// <summary>
    /// Constructor that initializes the list with the 
    /// required number of items.
    /// </summary>
    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;
    }

    /// <summary>
    /// Gets/sets the item value at the current index.
    /// </summary>
    public T Value
    {
      get { return items[idx]; }
      set { items[idx] = value; }
    }

    /// <summary>
    /// Returns the count of the number of loaded items, up to
    /// and including the total number of items in the collection.
    /// </summary>
    public int Count
    {
      get { return loaded ? items.Length : idx; }
    }

    /// <summary>
    /// Returns the length of the items array.
    /// </summary>
    public int Length
    {
      get { return items.Length; }
    }

    /// <summary>
    /// Gets/sets the value at the specified index.
    /// </summary>
    public T this[int index]
    {
      get 
      {
        RangeCheck(index);
        return items[index]; 
      }
      set 
      {
        RangeCheck(index);
        items[index] = value;
      }
    }

    /// <summary>
    /// Advances to the next item or wraps to the first item.
    /// </summary>
    public void Next()
    {
      if (++idx == items.Length)
      {
        idx = 0;
        loaded = true;
      }
    }

    /// <summary>
    /// Clears the list, resetting the current index to the 
    /// beginning of the list and flagging the collection as unloaded.
    /// </summary>
    public void Clear()
    {
      idx = 0;
      items.Initialize();
      loaded = false;
    }

    /// <summary>
    /// Sets all items in the list to the specified value, resets
    /// the current index to the beginning of the list and flags the
    /// collection as loaded.
    /// </summary>
    public void SetAll(T val)
    {
      idx = 0;
      loaded = true;

      for (int i = 0; i < items.Length; i++)
      {
        items[i] = val;
      }
    }

    /// <summary>
    /// Internal indexer range check helper. Throws
    /// ArgumentOutOfRange exception if the index is not valid.
    /// </summary>
    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.");
      }
    }

    // Interface implementations:

    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 the need a circular list, for example when working with moving averages.