A Dynamic, Generic, Type-Safe Comparer

• Download source - 25.96 KB

Introduction

In this article, I will present a generic, dynamic and type-safe implementation of an IComparer<T> object.

• Generic: It is a .NET generic class.
• Dynamic: The sort order is settable and changeable at run time.
• Type-safe: Safe for compile time checking, refactoring, and there are no strings involved.

The type safety is manifested in several aspects, as the compiler performs checks to verify that the properties that compose the sort order meet the following requirements:

• They do actually exist on the type being compared.
• They are accessible to the caller (not private, etc.)
• They are of a type that implements IComparable.

Using the Code

Using the code is a matter of instantiating a DynamicComparer<T> object, and calling its SortOrder method to specify the order of properties used in the comparison. Here is a code example (the key lines are highlighted):

public class Person
{
    public Person(string firstName, string lastName, int age)
    {
        FirstName = firstName;
        LastName = lastName;
        Age = age;
    }

    public string FirstName { get; set; }
    public string LastName { get; set; }
    public int Age { get; set; }

    public override string ToString()
    {
        return FirstName + " " + LastName + ", " + Age;
    }
}

class Program
{
    static void Main(string[] args)
    {
        var comp = new DynamicComparer<Person>();
        Person[] ppl = new Person[] {
            new Person("Aviad","P.",35),
            new Person("Goerge","Smith",33),
            new Person("Harry","Burke",30),
            new Person("Harry","Smith",20),
            new Person("George","Harrison",19)
        };

        comp.SortOrder(x => x.FirstName, x => x.LastName, x => x.Age);
        Demo(comp, ppl);

        comp.SortOrder(x => x.FirstName, x => x.Age, x => x.LastName);
        Demo(comp, ppl);

        comp.SortOrder(x => x.Age);
        Demo(comp, ppl);
    }

    private static void Demo(DynamicComparer<Person> comp, Person[] ppl)
    {
        Console.WriteLine(comp);
        Console.WriteLine("------------------------");
        Array.Sort(ppl, comp);
        PrintPeople(ppl);
    }

    private static void PrintPeople(Person[] ppl)
    {
        foreach (var p in ppl)
            Console.WriteLine(p);
    }
}

Note how the sort order is specified as a list of lambda expressions, that is the main factor in the type safety of this class.

Code Aerobatics - The Interesting Parts

The magic is done by using lambda expressions in combination with expression trees to force the compiler to conduct the necessary checks at compile time to make sure everything is ok.

Here is the implementation of the SortOrder method:

public void SortOrder(params Expression<Func<T, IComparable>>[] sortProperties)
{
    sortOrder.Clear();
    sortOrderNames.Clear();
    sortOrder.AddRange(sortProperties.Select(x => x.Compile()));
    sortOrderNames.AddRange(sortProperties.Select(x => GetNameFromExpression(x)));
}

Note that it expects to get a series of lambda expressions that accept an object of the type being compared, and return an IComparable. When this function is called, the compiler makes sure that the lambda expressions used meet these criteria. It will issue an error (and indeed, will prevent the error if intellisense is followed) if we try to reference a nonexistent property, or if the property we reference cannot be cast into IComparable. Also it will make sure that the property is accessible in terms of public/private accessibility.

Here is the implementation of the Compare method:

public int Compare(T x, T y)
{
    foreach (var l in sortOrder)
    {
        int c = l(x).CompareTo(l(y));
        if (c != 0) return c;
    }
    return 0;
}

Note that we are simply going over the compiled lambda expressions in order, and using them to retrieve the property values from the two operands to be compared. Then we call IComparable.CompareTo on the values returned, and if the result tells us the values are different, we return the difference, otherwise, we keep looking for one, and return 0 if none is found.

There is another overload of the SortOrder method which accepts a sequence of strings, this is not the recommended way of using this class, but it is there for those who need it, and for educational value. Here is the implementation:

public void SortOrder(params string[] sortProperties)
{
    string err = sortProperties.FirstOrDefault(x => uncomparable.Contains(x));
    if (err != null)
        throw new InvalidOperationException
		("Property '" + err + "' does not implement IComparable");
    err = sortProperties.FirstOrDefault(x => !properties.ContainsKey(x));
    if (err != null)
        throw new InvalidOperationException("Property '" + err + "' does not exist");
    sortOrder.Clear();
    sortOrderNames.Clear();
    sortOrder.AddRange(sortProperties.Select(x => properties[x]));
    sortOrderNames.AddRange(sortProperties);
}

Here we make a few run time checks, and throw exceptions in some cases. This is why this is the "unsafe" way of using this class, since the compiler will not be able to warn us in time about these cases. Note that once we determine that a property is valid to be used for sorting, we retrieve its lambda function from a mysterious properties dictionary. This dictionary is composed at the constructor, in which we use reflection to go over each property and prepare a lambda expression to retrieve it. Here is the implementation of the constructor:

public DynamicComparer()
{
    var ps = typeof(T).GetProperties(BindingFlags.Instance | BindingFlags.Public | 
		BindingFlags.NonPublic | BindingFlags.FlattenHierarchy);
    foreach (var p in ps)
    {
        // Only consider properties whose type is comparable (implements IComparable).
        if (!typeof(IComparable).IsAssignableFrom(p.PropertyType))
        {
            // Save the names of uncomparable properties for later reference
            // in case an attempt is made to sort by them.
            uncomparable.Add(p.Name);
            continue;
        }
        ParameterExpression pe = Expression.Parameter(typeof(T), "x");
        MemberExpression me = Expression.MakeMemberAccess(pe, p);
        Expression<Func<T, IComparable>> le;
        if (!p.PropertyType.IsValueType)
        {
            le = Expression.Lambda<Func<T, IComparable>>(me, pe);
        }
        else
        {
            UnaryExpression ue = Expression.Convert(me, typeof(IComparable));
            le = Expression.Lambda<Func<T, IComparable>>(ue, pe);
        }
        var f = le.Compile();
        properties[p.Name] = (Func<T, IComparable>)f;
    }
}

Note the clever usage of Expression objects to construct a suitable lambda expression to retrieve each property, and taking care to accommodate for whether the property is a value type or a reference type. Value type properties require an explicit conversion to IComparable.

Points of Interest

A performance issue exists if any of the properties that compose the sort order are value types, as they will be boxed during comparisons. This might or might not be an issue for you, but nevertheless, it's there.

Another performance issue is the overhead of performing a method call for the retrieval of each property; there are two such method calls per comparison. This increases the time taken to compare roughly by a factor of 2, but that depends on the specific circumstances of the comparison (the sort order, the values of the properties, and whether they are value types or reference types).

Note, that in spite of the above performance issues, this comparer is still faster than LINQ's OrderBy operator roughly by a factor of 2, so it is still twice as fast to use over LINQ, in case performance is an issue, but flexibility is to be maintained.

In the download for this article, there are benchmarking methods that show the difference in performance between a hard coded comparer (the fastest way), the dynamic comparer, and LINQ.

History

• March 30^th - Initial version