home screen

Search



Number Of Result : 0

Result :


Tuesday, November 18, 2008

Generic algorithms for C# 2.0 using iterators and anonymous methods

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(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.

Track URL : http://www.testingreflections.com/node/view/433

No comments: