Here are the NSort benchmarks for arrays of integer filled with random data. These benchmarks are for the non-generic versions.

The code to generate the benchmarks uses NPerf is given below:

using System;
using System.Collections;
using NPerf.Framework;

namespace NSort.Perf
{
    [PerfTester(typeof(ISorter), 10
        , Description = "Sort Algorithm benchmark for Random data"
        , FeatureDescription = "Collection size")]
    public class SorterBenchmark
    {
        protected int[] list;
        public int CollectionCount(int testIndex)
        {
            int n = 0;
            if (testIndex < 0)
                n=10;
            else
                n = (testIndex+1)*500;
            return n; 
        }
        [PerfRunDescriptor]
        public double RunDescription(int testIndex)
        {
            return (double)CollectionCount(testIndex);
        }

        [PerfSetUp]
        public override void SetUp(int testIndex, ISorter sorter)
        {
            Random rnd = new Random();
            this.list = new int[CollectionCount(testIndex)];
            for (int i = 0; i < this.list.Length; ++i)
                this.list[i] = rnd.Next();
        }
        [PerfTest]
        public void SortRandomData(ISorter sorter)
        {
            sorter.Sort(this.list);
        }
    }
}

NSort is a very nice and flexible package of sorting (15) algorithms from which the developer can choose. This library was a jointly work from me, Marc Clifton and Robert Rohde. In this blog, I'll show how NSort can be quickly "upgraded" to Generic and how you can use the extensibility of MbUnit to test it efficiently.

Generic

Converting the algorithms to Generic was really straightforward. For almost all cases, it was just a matter of adding <T> here and there, and replacing temporary object instance by T. Let's see this with the two interfaces of the project: IStorter and ISwap:

using System.Collections;
...

public interface ISorter
{
    IComparer Comparer {get;}
    void Sort(IList list);
}
public interface ISwap
{
    void Swap(IList array, int left, int right);
    void Set(IList array, int left, int right);
    void Set(IList array, int left, object obj);
}

Now, their generic brothers:

using System.Collections.Generic;
...

public interface ISorter<T>
{
    IComparer<T> Comparer {get;}
    void Sort(IList<T> list);
}
public interface ISwap<T>
{
    void Swap(IList<T> array, int left, int right);
    void Set(IList<T> array, int left, int right);
    void Set(IList<T> array, int left, object obj);
}

That was pretty quick. The conversion of the algorithms followed the same ideas and a dozens of cut/paste/replace later the NSort.Generic namespace was born.

Testing

There is a well-know proverb that says "the one who live by the cut-and-paste, die by the cut-and-paste" and that's exactly how I ported NSort to generics... so to ensure the quality of it really needs proper testing.

Testing NSort

Let's start with the testing of the non-generic classes. The main purpose of the NSort is to provide implementation of the ISorter interface that effectively sort list of elements and that's what we are willing to test. A quick (internal) brain strom for test cases of ISorter yields:

• Sort a null list throws ArgumentNullException,
• Sort a list with 0,1,2, n (n large) elements check it is effectively sorted. The purpse of the 0,1,2 is to test "boundary" lists.

Since we are testing an interface, this is a good candidate to use CompositeUnitTesting the TypeFixture of MbUnit:

[TypeFixture(typeof(ISorter))]
public class SorterTest
{
    private int[] list;
    private void CreateSortAndCheckSorted(ISorter sorter, int length)
    {
        Random rnd = new Random();
        list = new int[length];
        // create data
        for (int i = 0; i < list.Length; ++i)
            list[i] = rnd.Next();

        // sort table
        sorter.Sort(list);

        // verify
        for (int i = 0; i < list.Length - 1; ++i)
        {
            Assert.IsTrue(sorter.Comparer.Compare(list[i], list[i + 1]) <= 0,
                "Element {0} ({1}) is strictly greather that {1} ({2})",
                i, list[i], i + 1, list[i + 1]
            );
        }
    }

    [Test]
    [ExpectedArgumentNullException]
    public void SortNulList(ISorter sorter)
    {
        sorter.Sort(null);
    }

    [Test]
    public void SortEmptyList(ISorter sorter)
    {
        CreateSortAndCheckSorted(sorter, 0);
    }
    [Test]
    public void SortListWithOneElement(ISorter sorter)
    {
        CreateSortAndCheckSorted(sorter, 1);
    }
    [Test]
    public void SortListWithTwoElements(ISorter sorter)
    {
        CreateSortAndCheckSorted(sorter, 2);
    }
    [Test]
    public void SortListOfSize100(ISorter sorter)
    {
        CreateSortAndCheckSorted(sorter, 100);
    }
}

Now that we have defined the fixture, we need to feed it with ISorter instances. Usually, you would need to write a factory class that would create the instance, but this task was too boring not to be automated. What I want is a way to tell MbUnit to look for all the classes in NProf that implemented ISorter that apply the fixture to it...

Implementing a custom factory attribute:

The TypeFixture fixture looks for attributes that derive from ProviderFixtureDecoratorPatternAttribute and invoke their GetRun method to gather the IRun instance. Therefore, we "just" need to inherit from this attribute and implement the behavior we want:

[AttributeUsage(AttributeTargets.Class,AllowMultiple =true,Inherited =true)]
public class AssemblyProviderFactoryAttribute : ProviderFixtureDecoratorPatternAttribute
{
    private Type assemblyType; // type contained in the assembly to test
    private Type targetType; // the tested type
    public AssemblyProviderFactoryAttribute(Type assemblyType, Type targetType)
    {
        ...
        this.assemblyType = assemblyType;
        this.targetType = targetType;
    }
    public Assembly Assembly
    {
        get { return this.assemblyType.Assembly;}
    }
    public Type TargetType
    {
    get { return this.targetType;}
    }
    public override IRun GetRun(Type decoratedType)
    {
        throw new NotImplementedException();
    }
}

The GetRun still needs to be implemented. The task for the returned Run object is to explore the tested Assembly (assemblyType.Assembly) for types  compatible with targetType. MbUnit provides an abstract base class, Run, for implementing IRun:

public class AssemblyProviderRun : Run
{
    private AssemblyProviderFactoryAttribute attribute;
    public AssemblyProviderRun(AssemblyProviderFactoryAttribute attribute)
    {
        this.attribute = attribute;
    }

    public override void Reflect(RunInvokerTree tree, RunInvokerVertex parent, Type t)
    {
        foreach (Type type in this.attribute.Assembly.GetExportedTypes())
        {
            if (!type.IsClass) // interrested in class only,
                continue;
            if (type.IsAbstract) // abstract class cannot be created
                continue;
            if (!this.attribute.TargetType.IsAssignableFrom(type)) // must be assignable to TargetType
                continue;
            // trying to get the default constructor
            ConstructorInfo ci = type.GetConstructor(Type.EmptyTypes);
            if (ci == null)// no default constructor
                continue;

            ActivatorRunInvoker invoker = new ActivatorRunInvoker(this, type);
            tree.AddChild(parent, invoker);
        }
    }
}

ActivatorRunInvoker is a IRunInvoker implementation that takes a type, creates an new instance of it and feeds it to the arguments of the next invoker. We implement this invoker by inheriting from the abstract base class RunInvoker:

public class ActivatorRunInvoker : RunInvoker
{
   private Type targetType;
   public ActivatorRunInvoker(IRun run, Type targetType)
   :base(run)
   {
      this.targetType = targetType;
   }
   public override string Name
   {
   get {return this.targetType.Name;}
   }
   public override object Execute(object o, System.Collections.IList args)
   {
      Object target = Activator.CreateInstance(targetType);
      args.Add(target);
      return null;
   }
}

That's the end of the journey. The attribute is ready to be used to tag the SorterTest fixture:

[TypeFixture(typeof(ISorter))]
[AssemblyProviderFactory(typeof(ISorter),typeof(ISorter))]
public class SorterTest
{
   ...
}

Let's launch those test and see what happens. I like having my Test assemblies "self-executable" so I make it a Console application and the AutorRunner in the Main method. The Text report spits out:

Tests run: 75, Failures: 0, Not run: 0

This makes sense because there are 15 ISorter implementation times 5 tests applied to them. Of course, I would like to have more information, so I generate the Html report:

Here we see clearly which class is being tested and so, our new attribute is working perfectly without recompiling MbUnit!

Testing NSort.Generics

In order to test the generic sort algorithm, we need to take the following steps:

1. adapt the SorterTest fixture for the ISorter<int> interface (I choose to test int only),
2. adapt the AssemblyProviderRun to support generics

The task 1 is trivial and is similar to the ISorter to ISorter<T> transformation. The second task is more technical because we need to check that types are generic and handle them differently. To cut the story short, here is the method that iterates over generic types:

private void ReflectGenericTypes(RunInvokerTree tree, RunInvokerVertex parent)
{
    Type[] args = this.attribute.TargetType.GetGenericArguments();
    foreach (Type type in this.attribute.Assembly.GetExportedTypes())
    {
        if (!type.IsClass)
            continue;
        if (type.IsAbstract)
            continue;
        if (!type.HasGenericArguments) // true if type is a generic
            continue;

        // get the generic type definition
        Type genericType = type.GetGenericTypeDefinition();
        // bind types
        Type gtype = genericType.BindGenericParameters(args);
        // check if assignable
        if (!this.attribute.TargetType.IsAssignableFrom(gtype))
            continue;
        // create new invoker
        AddInvoker(tree, parent, gtype);
    }
}

It took me a while to fix that up but I finally got though. Now, the GenericSorterTest looked as follows and I was ready to hit the "Run" button:

[TypeFixture(typeof(ISorter<int>))]
[AssemblyProviderFactory(typeof(ISorter), typeof(ISorter<int>))]
public class GenericSorterTest
{...

The text report of the tests returned 150 tests, which was logical and they all passed (after some bug fixing). And I'm happy.

The method of testing I showed here worked well because of the nature of the problem to test: the ISorter class are all well separated and do not need mocking and so on.  One of the nicest thing about this is that if you write new ISorter implementations, you do not need to modify your fixutre, they will be automatically tested by MbUnit.

The date finally came through. I will present a workshop on testing on September 9 for the BENUG (Benelux .Net User Group) association on Testing. This will be a "exercise" oriented workshop.

Eric Gunnerson has recently blog about a Trebuchet (that he offered to his wife?). This remembered me of the one I built, with my friends, a few years ago.

The photo below shows the "implementation" of the Trebuchet and some facts about it:

• the rotating pole was 7m long and composed of two wooden poles of 15cm of diameter
• the rotation axis was made of a steel stick of 26mm of diameter. It was at 3.5 m of the ground. Note because the construction was not perfectly symmetric, it got twisted.
• the "counter"-weight was about 100kg altough not measured,
• the structure was composed of 10 wooden poles buried 50cm into ground.
• the projectile was a piece of wood, 50cm long, 15cm diameter, it got throwed at around 60 meter althought the trajectory was far from behing optimal (too vertical).

At first sight it may seem that Singleton and Unit Testing are not compatible since you cannot ensure the separation between the tests. We could solve the problem by instanciating a new "Singleton" instance for each test and apply test on this "local" instance. The problem is that a well implemented Singleton is sealed and it's constructor are private (see Singleton Pattern here) and thus you cannot create this instance.

using System;

public sealed class Singleton
{
   ...
   private Singleton() {}

   public static Singleton Instance
   {
      get { ...}
   }
}

Reflection to the rescue

An elegant way for bypassing the "creation problem" is to use Reflection to get the private constructor (ConstructorInfo) and then use this constructor info to create a new "Singleton" instance.

using System.Reflection;

[TestFixture]
public class SingletonTest
{
    private Singleton target = null;
    [SetUp]
    public void SetUp()
    {
        ConstructorInfo ci =
            typeof(Singleton).GetConstructor(
                BindingFlags.Instance |
                BindingFlags.NonPublic,
                null,
                Type.EmptyTypes,
                null
                );
         Assert.IsNotNull(ci);
         this.target = (Singleton)ci.Invoke(null);
    }
}

Now we have a new instance of the Singleton for each test and we are happy.

Jamie Cansdale has found a hidden gem in .Net 2.0: the much awaited InternalsVisibleTo attribute. This attribute let's you specify the name of an assembly that can view the internals... That's perfect for testing internal classes.

http://weblogs.asp.net/nunitaddin/archive/2004/08/13/214130.aspx

QuickGraph now contains a condensation graph and transitive closure algorithm which were ported from the BGL by Rohit Gadogkar. Here's a recap. of the definitions of those type of graphs (takened from the Boost Graph Library reference)

A condensation graph is a a graph CG=(CV,CE) based on the graph G=(V,E) where each vertex in CV corresponds to a strongly connected component in G and edge (u,v) is in CE if and only if there exists an edge in E connecting any of the vertices in the component of u to any of the vertices in the component of v.

The transitive closure of a graph G = (V,E) is a graph TG = (V,TE) such that TE contains an edge (u,v) if and only if G contains a path (of at least one edge) from u to v.

Condenstation Graph

Assume that you have built a graph g using QuickGraph:

IVertexListGraph g = ...;

The algorithm responsible for the condensation graph creation is QuickGraph.Algorithms.CondensationGraphAlgorithm and takes the graph to condensate as parameter:

CondensationGraphAlgorithm condensator = new CondensationGraphAlgorithm(g);

In order to compute the condensation, we need to provide a mutable graph, for example a AdjacencyGraph, and call the Create method:

AdjacencyGraph cg = new AdjacencyGraph(true);
condensator.Create(cg);

At this moment, cg contains the condensation graph of g. The only problem here, is that we have not stored the information about which vertex from V was associated to a vertex in CV. In order to do that, we need to add some event handlers to the algorithm. 

This algorithm defines one event, InitCondensationGraphVertex, which is trigerred for each new vertex of the condenstation graph CG. Remember that this vertex (in CV) "contains" all the vertices of a component in the original graph. In this example, we will create a condensation graph that creates NamedVertex, which has the Name property, and we concatenate the names of the condensed vertices to make it the name of the condensated vertex:

// using NamedVertexProvider in order 
// to create NamedVertex instances
AdjacencyGraph cg = new AdjacencyGraph(
    new NamedVertexProvider(),
    new EdgeProvider(),
    true);

// attaching event handler
condensation.InitCondensationGraphVertex+=
    new CondensationGraphVertexEventHandler(condensator_InitCondensationGraphVertex);
// computing
condensator.Create(cg);

...
// Event handler
void condensation_InitCondensationGraphVertex(
    object sender, 
    CondensationGraphVertexEventArgs arg)
{
    NamedVertex cv = (NamedVertex)arg.CondensationGraphVertex;
    
    StringWriter sw = new StringWriter();
    foreach (IVertex v in arg.StronglyConnectedVertices)
    {
        sw.Write("{0}\\n", v);
    }
    v.Name = sw.ToString();
}

That's it... Here are two images of graphs. The left image shows a state graph that is not strongly connected and the right image shows the condensation graph of it.

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

Updated the "sick" Reflector.Graph release.

• Compiled against .Net 1.0 and .Net 1.1 (1.0 version does not have the TreeMap)
• Various bugs fixed

Download at www.dotnetwiki.org

There's one new cool feature of the VS2005 that has not received much attention, CodeSnippets. With CodeSnippets, you can write code template in minutes that are directly integrated into the intellisense of VS. That's great.... the sad point is that they are totally undocumented :(

CodeSnippets

Here's a small description of CodeSnippets in VS Express and here's a better tutorial but it is in french.

CodeSnippets for MbUnit

MbUnit has now CodeSnippets to create fixture, test methods, etc... all kinds of snippets that you write again and again. To set up the snippets, you need VS2005 and to download the MbUnit Code Snippets from www.dotnetwiki.org (they will be integrated in the next release).

Unzip the file in a directory and go to the menu Tools -> Code Snippets Manager... In the dialog, push Add and choose the directory where you have unzipped the snippets. The dialog window should look as follows. Clicking on each snippet will give you a short description, the shortcut to execute it, etc...

TestFixture snippet

In you need to create a new fixture, the TestFixture snippet is now here to help. Create a new blank C# file and write te. Intellisense window should pop out and now you will see new items: test, testfixture, etc...

 Go to the textfixture item and double "tab" it. The editor will execute the template and expand the item into an empty TestFixture class definition as follows:

You can also access the MbUnit expansion fixture by looking in the context menu, Intellisense -> Expand Item... -> MbUnitExpansion