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.

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here