Multi-Level Sorting

Sunday, February 5, 2006

Let's talk about sorting again. Our goal is to set up ad-hoc multi-level comparisons in a simplified, but type-safe fashion. Recall the problem of not having a suitable comparer, or items that are not comparable at all. With Whidbey, I've settled on two techniques:

1. Using covariant open instance delegates pointing to anonymous methods. For this the ComparableGetter<T> delegate type is used by CDelegatingComparer<T>. The procedural API is the following query operator in Gregor.Core.Walk: IList<T> Walk.Sort<T>(IList<T>, params ComparableGetter<T>).
2. Creating covariant property delegates, using the same delegate and comparer types. It's wrapped up procedurally here in Gregor.Core.Walk as well: IList<T> Walk.Sort<T>(IList<T>, params string[]).

The first approach offers the most flexibility. It solves the problems mentioned above, in that you can easily compare any non-comparable object, and set up custom rules. In addition to that:

• Multi-level comparisons are implemented centrally in a library. You only provide the order of your sort criteria (by passing the delegates in the appropriate order.
• The rules governing the comparison of null references are handled in one central place. The callback need not worry about them.
• The callback has no chance of mixing up two elements or their properties, (ig., string sName2 = person1.Name - ever happened to you?), because it has only one parameter to deal with.

A additional benefit is that custom rankings may be supported easily:

IList<Person> people = new List<Person>();
people.Add(new Person("Joe", "Admin"));
people.Add(new Person("Sue", "Programmer"));

foreach(Person p in Walk.Sort<Person>(people,
    delegate(Person p){
        switch(p.Profession){
            case "Admin":
                return 2;
            case "Programmer":
                return 1;
            default:
                return 0;
        }
    },
    delegate(Person p){
        return p.Name;
    }
){
    // ...
}

Because ComparableGetter<T> returns IComparable, values are automatically boxed. This fulfills the requirement of delegate return type covariance.

Note that when using the second approach mentioned above (using property names in order to have Walk.Sort or CDelegatingComparer.Create set up the appropriate ComparableGetter delegates behind the scenes), the return type covariance requirement must be met be reference-type-returning properties for things to work (things are guarded by exceptions). This is because in the latter case, the methods referenced by ComparableGetter are the actual property getters that do not "know" about the context of the expected return type IComparable.