Saving the State of Enumerators

Cyrus and I were writing some code together the other day and we used an interesting data structure that I wanted to share with you. This data structure I will call a chain which is essentially a immutable singlely linked list.

interface

IChain<T> : IEnumerable<T>
{
IChain<T> Next { get; }
T Value { get; }
}

It is possible to provide a lot of the necessary functionality through an abstract class.

abstract

class AbstractChain<T> : IChain<T>
{
public abstract IChain<T> Next { get; }
public abstract T Value { get; }

public IEnumerator<T> GetEnumerator()
{
IChain<T> current = this;
while (current != null)
{
yield return current.Value;
current = current.Next;
}
}

System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
}

Of course, a simple concrete Chain class has a very straightforward implementation.

class Chain<T> : AbstractChain<T>
{
IChain<T> next;
T value;

public Chain(IChain<T> next, T value)
{
this.next = next;
this.value = value;
}

public Chain(T value)
: this(null, value)
{
}

public override T Value
{
get { return value; }
}

public override IChain<T> Next
{
get { return next; }
}
}

In this implementation, each node contains a value and every node but the last node has a link to the next node. The last node has a null instead of a link to the next node. But what if I don't want to create the whole list upfront? What if I know how to create it, but I don't want the overhead of creation and then traversal. The solution of course is to lazily create the linked list or create it on demand.

class LazyChain<T> : AbstractChain<T>
{
IChain<T> next;
T value;
IEnumerator<T> enumerator;

LazyChain(T value, IEnumerator<T> enumerator)
{
this.value = value;
this.enumerator = enumerator;
}

public static IChain<T> Create(IEnumerable<T> enumerable)
{
return Create(enumerable.GetEnumerator());
}

static IChain<T> Create(IEnumerator<T> enumerator)
{
if (enumerator.MoveNext())
{
return new LazyChain<T>(enumerator.Current, enumerator);
}
return null;
}

public override IChain<T> Next
{
get
{
if (enumerator != null)
{
next = Create(enumerator);
enumerator = null;
}
return next;
}
}

public override T Value
{
get { return value; }
}
}

Notice how the constructor to a lazy chain does not take a link to the next chain, it takes an enumerator. It uses this enumerator to create the next link when it is first accessed. One great application where this is useful is in rollbacking an enumerator. It is sometimes useful to be able to mark a place in the execution of an enumerator and then reset to that point and iterate again. The lazy chain makes such behavior possible and efficient. For an example, consider the following program.

class Program
{
static IEnumerable<int> GetNumbers()
{
for (int i = 0; i < 10; ++i)
{
yield return i;
}
}
static void Main(string[] args)
{
IChain<int> intChain = LazyChain<int>.Create(GetNumbers());
IChain<int> savedChain = null;
for (int i = 0; intChain != null; ++i)
{
if (intChain.Value == 5)
{
savedChain = intChain;
}
intChain = intChain.Next;
}
if (savedChain != null)
{
foreach (int i in savedChain)
{
Console.WriteLine(i);
}
}
}
}

Although the iterator iterates through all of the numbers, we pick execution up again where the value was five and then proceed to print out the numbers. Furthermore, the code to iterate over the chains is ignorant of the fact of what kind of chain it is dealing with. While this example is a bit contrived, it does illustrate the ability of the data structure to mark and continue over enumerators while preserving immutability. For Cyrus and I, it greatly simplified the design of a component that we were working on while preserving performance.

Comments

• Anonymous
  January 25, 2007
  That is very nice

• Anonymous
  February 12, 2007
  One of the things that I have noticed when participating in interviews with potential candidates is that

• Anonymous
  October 06, 2007
  One of the things that I have noticed when participating in interviews with potential candidates is that

• Anonymous
  January 14, 2010
  Why do you need an implementation of the IEnumerable<T> in IChain<T>? Next is more anemic :o) And do not requres to add [same!] implementation of the IEnumerable<T> in any implementation of the IChain<T>. interface IChain<T> {   IChain<T> Next { get; }   T Value { get; } } public static class ChainExtensions {  public static IEnumerable<T> AsEnumerable<T>(this IChain<T> source) {    if(source == null) {      throw new ArgumentNullException("source");    }//if    return AsEnumerableIterator(source);  }  private static IEnumerable<T> AsEnumerableIterator<T>(IChain<T> source) {    Debug.Assert(source != null, "source != null");    do {      yield return source.Value;    } while((source = source.Next) != null);  } }