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:
- adapt the SorterTest fixture for the ISorter<int> interface (I choose to test int only),
- 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.