Click here to Skip to main content
15,867,308 members
Articles / Programming Languages / C#

A Circular List

Rate me:
Please Sign up or sign in to vote.
4.57/5 (15 votes)
4 Mar 2007CPOL2 min read 104K   1K   36   18
A circular list implementation

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:

C#
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".

C#
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.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Architect Interacx
United States United States
Blog: https://marcclifton.wordpress.com/
Home Page: http://www.marcclifton.com
Research: http://www.higherorderprogramming.com/
GitHub: https://github.com/cliftonm

All my life I have been passionate about architecture / software design, as this is the cornerstone to a maintainable and extensible application. As such, I have enjoyed exploring some crazy ideas and discovering that they are not so crazy after all. I also love writing about my ideas and seeing the community response. As a consultant, I've enjoyed working in a wide range of industries such as aerospace, boatyard management, remote sensing, emergency services / data management, and casino operations. I've done a variety of pro-bono work non-profit organizations related to nature conservancy, drug recovery and women's health.

Comments and Discussions

 
QuestionLicensing question Pin
FahadAsh9-Sep-11 10:06
FahadAsh9-Sep-11 10:06 
Questiontype is missing? Pin
Richard Savoie14-Aug-11 19:41
Richard Savoie14-Aug-11 19:41 
GeneralYou've have a Typo Pin
AspDotNetDev16-Aug-09 11:48
protectorAspDotNetDev16-Aug-09 11:48 
GeneralRe: You've have a Typo Pin
Marc Clifton16-Aug-09 12:05
mvaMarc Clifton16-Aug-09 12:05 
GeneralRe: You've have a Typo Pin
AspDotNetDev16-Aug-09 12:13
protectorAspDotNetDev16-Aug-09 12:13 
Questionfor value types only? Pin
Federico Sasso7-Mar-07 3:17
Federico Sasso7-Mar-07 3:17 
AnswerRe: for value types only? Pin
Colin Angus Mackay7-Mar-07 3:36
Colin Angus Mackay7-Mar-07 3:36 
GeneralRe: for value types only? Pin
Marc Clifton7-Mar-07 4:03
mvaMarc Clifton7-Mar-07 4:03 
GeneralRe: for value types only? [modified] Pin
Federico Sasso7-Mar-07 11:04
Federico Sasso7-Mar-07 11:04 
GeneralRe: for value types only? Pin
Colin Angus Mackay7-Mar-07 11:53
Colin Angus Mackay7-Mar-07 11:53 
GeneralRe: for value types only? Pin
Federico Sasso7-Mar-07 13:20
Federico Sasso7-Mar-07 13:20 
Generalvery useful article Pin
BillW336-Mar-07 8:30
professionalBillW336-Mar-07 8:30 
GeneralQuickly define the circular list in the introduction. Pin
Christian Klauser5-Mar-07 9:18
Christian Klauser5-Mar-07 9:18 
GeneralWell, this is an odd coincidence..... Pin
James Curran5-Mar-07 6:40
James Curran5-Mar-07 6:40 
GeneralRe: Well, this is an odd coincidence..... Pin
Marc Clifton5-Mar-07 7:55
mvaMarc Clifton5-Mar-07 7:55 
Generalenumeratiom Pin
Luc Pattyn4-Mar-07 18:19
sitebuilderLuc Pattyn4-Mar-07 18:19 
GeneralRe: enumeratiom Pin
S. Senthil Kumar4-Mar-07 18:35
S. Senthil Kumar4-Mar-07 18:35 
GeneralRe: enumeratiom Pin
Marc Clifton5-Mar-07 4:13
mvaMarc Clifton5-Mar-07 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.