Click here to Skip to main content
11,705,451 members (51,889 online)
Click here to Skip to main content

A Circular List

, 4 Mar 2007 64.9K 703 35
Rate this:
Please Sign up or sign in to vote.
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:

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.

License

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

Share

About the Author

Marc Clifton
United States United States
Marc is the creator of two open source projects, MyXaml, a declarative (XML) instantiation engine and the Advanced Unit Testing framework, and Interacx, a commercial n-tier RAD application suite.  Visit his website, www.marcclifton.com, where you will find many of his articles and his blog.

Marc lives in Philmont, NY.

You may also be interested in...

Comments and Discussions

 
QuestionLicensing question Pin
FahadAsh9-Sep-11 10:06
memberFahadAsh9-Sep-11 10:06 
Questiontype is missing? Pin
Richard Savoie14-Aug-11 19:41
memberRichard Savoie14-Aug-11 19:41 
GeneralYou've have a Typo Pin
aspdotnetdev16-Aug-09 11:48
memberaspdotnetdev16-Aug-09 11:48 
GeneralRe: You've have a Typo Pin
Marc Clifton16-Aug-09 12:05
protectorMarc Clifton16-Aug-09 12:05 
aspdotnetdev wrote:
"I've specifically have not derived the CircularList" -- You have specifically h


I have not. It's correct as I wrote it. Smile | :)

Marc

Will work for food.
Interacx


I'm not overthinking the problem, I just felt like I needed a small, unimportant, uninteresting rant! - Martin Hart Turner


GeneralRe: You've have a Typo Pin
aspdotnetdev16-Aug-09 12:13
memberaspdotnetdev16-Aug-09 12:13 
Questionfor value types only? Pin
Federico Sasso7-Mar-07 3:17
memberFederico Sasso7-Mar-07 3:17 
AnswerRe: for value types only? Pin
Colin Angus Mackay7-Mar-07 3:36
mvpColin Angus Mackay7-Mar-07 3:36 
GeneralRe: for value types only? Pin
Marc Clifton7-Mar-07 4:03
protectorMarc Clifton7-Mar-07 4:03 
GeneralRe: for value types only? [modified] Pin
Federico Sasso7-Mar-07 11:04
memberFederico Sasso7-Mar-07 11:04 
GeneralRe: for value types only? Pin
Colin Angus Mackay7-Mar-07 11:53
mvpColin Angus Mackay7-Mar-07 11:53 
GeneralRe: for value types only? Pin
Federico Sasso7-Mar-07 13:20
memberFederico Sasso7-Mar-07 13:20 
Generalvery useful article Pin
CIDev6-Mar-07 8:30
memberCIDev6-Mar-07 8:30 
GeneralQuickly define the circular list in the introduction. Pin
Christian Klauser5-Mar-07 9:18
memberChristian Klauser5-Mar-07 9:18 
GeneralWell, this is an odd coincidence..... Pin
James Curran5-Mar-07 6:40
memberJames Curran5-Mar-07 6:40 
GeneralRe: Well, this is an odd coincidence..... Pin
Marc Clifton5-Mar-07 7:55
protectorMarc Clifton5-Mar-07 7:55 
Generalenumeratiom Pin
Luc Pattyn4-Mar-07 18:19
memberLuc Pattyn4-Mar-07 18:19 
GeneralRe: enumeratiom Pin
S. Senthil Kumar4-Mar-07 18:35
memberS. Senthil Kumar4-Mar-07 18:35 
GeneralRe: enumeratiom Pin
Marc Clifton5-Mar-07 4:13
protectorMarc Clifton5-Mar-07 4:13 

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

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

| Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.150819.1 | Last Updated 4 Mar 2007
Article Copyright 2007 by Marc Clifton
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid