Iterators is one of the big, expected, new feature of C# 2.0. It should revolutionize the way you define your collection. Since iteration is fun, people have started to do some interresting and smart things with tem. So I decided, it was time I started playing with them. I'll assume that you have a basic knowledge of the new Generic syntax.

Background: STL algorithms

There was some ancient time where I was still a C++ user. At that time, I was using the Standard Template Library (STL) , a famous C++ library. This library makes an extensive use of template and what is called "generic programming". This library features containers, iterators and algorithms and was the basis of the work I have done in this post.

An introductrory example: filtered enumeration

Let's start with a simple, and yet, usefull iterator: we would like to create a filtered enumeration with regards to a given predicate. To do so, we first define the predicate interface (this interface defines a functor, funtion-like object)

public interface IPredicate<T>
{
    bool Invoke(T item);
}

And then, we can define the Select enumerator which returns the item of the predicate is true:

static public IEnumerable<T> Select<T>(IEnumerable<T> collection, IPredicate<T> pred)
{
    foreach(T item in collection)
    {
        if (pred.Invoke(item))
            yield return item;
    }
}

Let's apply this iterator to an example. Consider a list of string containing some names and a predicate that checks if a string starts with a particular string:

public class StartsWithPredicate : IPredicate<String>
{
    private string start;
    public StartsWithPredicate(string start)
    {
        this.start=start;
    }
    public bool Invoke(string item)
    {
        if (item==null)
            return false;
        return item.StartsWith(start);
    }
}

...
List<String> names = new List<String>();
names.Add("Marc");
names.Add("Jonathan");
names.Add("Julia");

Iterating and displaying the names that start with "J" is done using the Select method:

foreach(string name in Select(names, new StartWithPredicate("J")))
{ Console.WriteLine(name);}

-- output
Jonathan
Julia

This snippet is alreay nice but it is still quite verbose since we have to define a class before using it as a filter. It would be nice to use another new feature, namely anonymous methods, to define filters:

foreach(string name in Select(names, delegate(string s){ return s.StartsWith("J");}))
{ Console.WriteLine(name);}

In order to acheive this, we need to do 3 things: 1) declare a delegate that matches the signature of IPredicate.Invoke method, 2) create a IPredicate instance that wraps up a call to such delegate, 3) overload Select to take a delegate as argument:

// 1
public delegate bool PredicateDelegate(T item);

// 2
public class PredicateDelegateInvoker<T> : IPredicate<T>
{
   private PredicateDelegate<T> del;
   public PredicateDelegateInvoker(PredicateDelegate<T> del)
   {
      this.del = del;
   }
   public bool Invoke(T item)
   {
      return del(item);
   }
}

// 3
public IEnumerable<T> Select<T>(IEnumerable<T> collection, PredicateDelegate<T> pred)
{
   return Select(collection, new PredicateDelegateInvoker<T>(pred));
}

Now, we can use anonymous methods as shown above to filter any enumeration. In the following, I will define a framework to define a variety of enumerator, like in the good old days of STL.

Enumerator framework

1 Functors

First, we need to define some functor interfaces. There are two main families. Transformers take T instances as arguments and return a R instance. A transformer can accept one or two arguments (Binary). This interface represents the conversion T -> R:

public interface ITransformer<T,R>T
{
    R Invoke(T item);
}
public interface IBinaryTransformer<T,R>
{
    R Invoke(T left, T right);
}

Predicates are a specialized kind of transformer which returns bool:

public interface IPredicate<T> : ITransformer<T,bool>
{}

public interface IBinaryPredicate<T> : IBinaryTransformer<T,bool>
{}

There are a number of pre-built predicate that we can implement: And, Or, Not, etc... I will show how the And predicate, which applies the boolean and operator to the result of two IPredicate is implemented:

public class AndPredicate<T> : IPredicate<T>
{
    private IPredicate<T> leftPred;
    private IPredicate<T> rightPred;
    public AndPredicate(IPredicate<T> leftPred, IPredicate<T> rightPred)
    {
        this.leftPred = leftPred;
        this.rightPred = rightPred;
    }
    public bool Invoke(T value)
    {
        return leftPred.Invoke(value) && rightPred.Invoke(value);
    }
}

2 Delegates and delegate wrappers

As in the introductory example, we define 4 delegates and their functor wrapper for each functor interface:

public delegate R TransformerDelegate<T,R>(T item);
public delegate R BinaryTransformerDelegate<T,R>(T left, T right);
public delegate bool PredicateDelegate<T>(T item);
public delegate bool BinaryPredicateDelegate<T>(T left, T right);

+ wrappers

The wrappers are proxies to the delegate invokation.

3 Algorithms

Now that we are equipped with functors, we can start having fun and defining algorithms/enumerators.

3.1 Select

The Select enumerator (filtered enumeration) was already defined in the example, so we can skip it.

3.2 Transformation

The Transform enumerator applies a ITransformer to each item and returns the result:

static public IEnumerable<R> Transform<T,R>(
    IEnumerable<T> collection,
    ITransformer<T,R> transformer)
{
    foreach (T item in collection)
    {
        yield return transformer.Invoke(item);
    }
}

We also take care of writing the overload that handles anonymous methods. For example, we can use this method to convert all the strings in the names collection to upper case:

foreach(string upperCaseName in Transform<string,string>(names,delegate(string s){return s.ToUpper();}))
{Console.WriteLine(name);}

-- output
MARC
JONATHAN
JULIA

Note that in this case,  we need to specify the T,R parameters because the compiler cannot resolve them.

3.3 Others...

The list of possible enumeration is quite long, so I'll stop here for today.

Download the bits

You can download the bits from this example at www.dotnetwiki.org (look for Iterate project in the download section).