Closing the Gap Between IEnumerator and IEnumerable

From eqqon

(Difference between revisions)

Revision as of 09:26, 21 April 2008

Ever found yourself writing a custom collection in C# just to be able to fill in an IEnumerator into an interface that expects IEnumerable? Boilerplate code like such is never a good idea. The class Iterator<T> presented in this article fills the missing link between IEnumerator and IEnumerable.

Introduction

C# defines two interfaces for convenient iteration over a sequence of values or objects. IEnumerable which allows to "foreach" over a collection and is implemented basically by every collection of the .NET framework and IEnumerator which is exposed by an iterator which is the return value of an iteration function. Both interfaces exist in generic and non-generic versions but for simplicity we only talk about the non-generic versions without loss of generality. The definition of IEnumerable is as simple as this:

interface IEnumerable

interface IEnumerable: IEnumerator GetEnumerator();

The main purpose of this interface is to allow a syntactically uncomplicated and hence convenient way to iterate over a collection by using the foreach statement. This convenience and the fact, that it is exposed by every standard collection makes IEnumerable the perfect parameter type for methods that accept any kind of collection. A prominent example use case is LINQ which allows to pipeline IEnumerables through a number of cascaded transformation functions.

Strictly speaking IEnumerable is just a wrapper for IEnumerator which enables foreach magic for any type which implements it. So let's have a look at IEnumerator:

interface IEnumerator

interface IEnumerator: void Reset();; bool MoveNext();; object Current{ get; }

Obviously IEnumerator is the typical interface of an iterator. To create a custom iterator (an object exposing interface IEnumerator) there are two major approaches. Your class can "manually" implement the IEnumerator interface. The second and much more interesting one is to use another magic syntax of C# which is called iterator block:

Example iterator block which generates the first 7 elements of the Fibonacci sequence

IEnumerator SimpleIterator()

{

yield return 1;

yield return 2;

yield return 3;

yield return 5;

yield return 8;

yield return 13;

}

Example iterator block which generates a Fibonacci sequence

IEnumerator Fibonacci(int count)

{

int n0=0;

int n1=1;

for(int i=0; i<count; i++) {

yield return n0+n1;

n0=n1

}

The iterator block is a simple method, indexer or property getter which returns IEnumerator. This is an incredibly useful and even more convenient way to write custom iterators. Moreover iterator blocks are evaluated on demand only so they are the most efficient way to handle large sequences, transformation pipelines or sequences which are created by a mathematical function without consuming memory unnecessarily. If one chains together a number of iterators each iteration block pulls objects from the next iterator for each iteration on demand.

Chaining Iterators to form Processing Pipelines

Example of two chained iteration blocks

IEnumerator OuterIterator()

{

var inner = InnerIterator();

while(inner.MoveNext())

yield return ApplySomeTransformation(inner.Current); // <--- forward the transformed current item returned by the inner iterator.

}

I would prefer to use the foreach statement over using the IEnumerator interface for the sake of improved readability but sadly this is not directly supported by C#. Writing a custom collection which implements IEnumerable and wraps the iterator block just to be able to foreach over the iterator block is nonsense. Besides some classes may expose several iterators which support different ways of traversal (i.e. bottom-up vs. top-down iteration over a tree). Also if one wants to use a custom iterator with LINQ the conversion from IEnumerator to IEnumerable is necessary. The solution is simple and elegant:

Example of foreach-ing over an iteration block with Iterator<T>

IEnumerator OuterIterator()

{

foreach(var item in new Iterator( InnerIterator()))

yield return ApplySomeTransformation(item); // <--- again forward the transformed item to the next step in the pipeline

}

Example of using LINQ with an iteration block called Traverse which enumerates all nodes in a tree.

var nodes = new Iterator( tree.Traverse()); // <--- Traverse is an iteration block and returns an IEnumerator which cannot directly be fed into a LINQ query. var leaves = from n in nodes where n.IsLeaf() select n;

class Iterator

... will be filled in tomorrow

class Iterator<T>