Closing the Gap Between IEnumerator and IEnumerable

From eqqon

Latest revision as of 09:35, 22 February 2009

Ever found yourself writing a custom collection in C# just to be able to pass an IEnumerator into a method that expects IEnumerable? Writing such boilerplate code is never a good idea. The classes Iterator and Iterator<T> presented in this article fill in the missing link from IEnumerator to IEnumerable allowing you to be more productive with iterators.

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:

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:

IEnumerator and Iteration Blocks

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 makes use of C# compiler magic and is called iterator block:

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

IEnumerator SimpleIterator()

{

yield return 1;

yield return 1;

yield return 2;

yield return 3;

yield return 5;

yield return 8;

yield return 13;

}

Here is an iterator block which generates a Fibonacci sequence of arbitrary length

IEnumerator<int> Fibonacci(int count)

{

int n0=0;

int n1=1;

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

{

yield return n1;

int next = n0 + n1;

n0 = n1;

n1 = next;

}

}

The iterator block is a method, indexer or property-getter which returns IEnumerator or IEnumerator<T>. 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 its underlying iterator on each iteration step.

Chaining Iterators to Processing Pipelines

Example of chaining iteration blocks

IEnumerator<int> FibonacciSquared(int count)

{

var inner_iterator = Fibonacci(count);

while(inner_iterator.MoveNext())

{

int n = inner_iterator.Current;

yield return n * n;

}

}

For the sake of improved readability I prefer to use the foreach statement over manually incrementing the iterator via the IEnumerator interface but this is not directly supported by C#. Writing a custom collection which implements IEnumerable to wrap 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 using our featured class Iterator<T>

IEnumerator<int> FibonacciSquared(int count)

{

foreach( int n in new Iterator<int>( Fibonacci(count)))

{

yield return n*n;

}

}

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

Iterator is a generalized wrapper to "convert" IEnumerator into IEnumerable.

public class Iterator : IEnumerable
{
    IEnumerator m_iterator;

    public Iterator(IEnumerator iter)
    {
        m_iterator = iter;
    }

    public Iterator(IEnumerable enumerable)
    {
        m_iterator = enumerable.GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return m_iterator;
    }
}

class Iterator<T>

The generic version of Iterator.

public class Iterator<T> : IEnumerable<T>
{
    IEnumerator<T> m_iterator;

    public Iterator(IEnumerator<T> iter)
    {
        m_iterator = iter;
    }

    public Iterator(IEnumerable<T> enumerable)
    {
        m_iterator = enumerable.GetEnumerator();
    }

    public IEnumerator<T> GetEnumerator()
    {
        return m_iterator;
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return (IEnumerator)m_iterator;
    }
}

--Henon 01:00, 21 April 2008 (CEST)