How to order classes by inheritence?

Question

I'm using reflection to retrieve a list of available classes and I want to adapt the input object to the most specific class that matches; i.e. I want to do something like:

RawData input = new RawData() { ... };
Type targetAdapter = AdapterSelector.SelectAdapterFor(input);
AdapterSelector.TryGetAdaptMethod(targetAdapter, out Func<RawData, Adapter> fAdapt);
Adapter adapted = fAdapt(input);

Each applicable class has the following signature:

public class Adapter
{
    public static Adapter Adapt(RawData input) { ... }
    public static bool Matches(RawData input) { ... }
}

Retrieving the list of classes with the required methods can be done as follows using reflection¹:

public partial class AdapterSelector
{
    public static IEnumerable<Type> GetApplicableAdapterTypes()
    {
        IEnumerable<Type> allTypes = typeof(AdapterSelector).Assembly.GetTypes();
        IEnumerable<Type> applicableTypes = from t in allTypes
                                            where TryGetAdaptMethod(t, _) &&
                                                  TryGetMatchMethod(t, _)
                                            select t;
        return applicableTypes;
    }

    private static bool TryGetAdaptMethod(Type type, out Func<RawData, Adapter> adapt)
    {
        MethodInfo adaptMethod = type.GetMethod("Adapt", BindingFlags.Static|BindingFlags.Public, null, new Type[] { typeof(RawData) }, null);
        if (adaptMethod != null)
        {
            adapt = (Func<RawData, Adapter>)Delegate.CreateDelegate(typeof(Func<RawData, Adapter>), null, adapterMethod);
            return true;
        }
        else
        {
            adapt = null;
            return false;
        }
    }

    private static bool TryGetMatchMethod(Type type, out Func<RawData, bool> match)
    {
        MethodInfo matchMethod = type.GetMethod("Match", BindingFlags.Static|BindingFlags.Public, null, new Type[] { typeof(RawData) }, null);
        if (matchMethod != null)
        {
            match = (Func<RawData, bool>)Delegate.CreateDelegate(typeof(Func<RawData, bool>), null, matchMethod);
            return true;
        }
        else
        {
            match = null;
            return false;
        }
    }
}

I assumed that I could use the following IComparer<Type> to order this list of adapters:

public class TypeHierarchyComparer: IComparer<Type>
{
    public int Compare(Type lhs, Type rhs)
    {
        if (rhs.IsSubclassOf(lhs))
        {
            return -1;
        }
        else if (lhs.IsSubclassOf(rhs))
        {
            return +1;
        }
        else
        {
            // Return arbitrary but fixed value for siblings, cousins, etc.
            return lhs.FullName.CompareTo(rhs.FullName);
        }
    }
}

Note that this is intended to be a partial ordering: if one type is a subclass of the other that type should be ordered after² the latter. If neither type is a subclass of the other, the order is undefined.

With this ordering I hoped that the following hierarchy of adapters would be sorted correctly³:

• Adapter
  • N
  • F
  • H
  • I
  • K
    • E
    • G
    • L
    • M
    • Q
    • R
  • O
  • B
  • C
  • J
  • P
    • AA
    • AB
    • D
    • S
    • T

However, the results of:

AdapterSelector.GetApplicableAdapterTypes().OrderBy((x) => x, new TypeHierarchyComparer());

are:

Adapter, AA, AB, B, C, D, N, F, H, I, J, K, P, E, G, L, M, O, P, Q, R, S, T

Is the correct order O and P should be ordered before AA, AB, D, S, and T and O should be before B, C, and J. It appears that subclasses are ordered after one of their parents but not necessarily after all their parents.

How can I sort classes by specificity? (I.e. ordering the subclasses before/after all their parents)

---

¹⁾ _{See Assembly.GetTypes(), Type.GetMethod(string, BindingFlags, Binder, Type[], ParameterModifier[]), Can you get a Func<T> (or similar) from a MethodInfo object?, and Delegate.CreateDelegate(Type, object, methodInfo)}

²⁾ _{I'm using Enumerable.OrderByDescending<TSource, TKey>(this IEnumerable<TSource>, Func<TSource, TKey>, IComparer<TKey>) to get the matcher to apply first in the front of the list.}

³⁾ _{The class hierarchy as shown by Visual Studio's Solution Explorer. I cannot disclose the names of the adapters, therefore I used AA to T, I preserved the alphabetical order of the names.}

Answer 1

The problem is that your arbitrary sorting rule is too arbitrary.

Rather than sorting on type names (so, comparing G and B, would say that G should come after B), you should instead find the closest common ancestor of two unrelated types. Then, you should apply sorting based on the immediate descendent of the common ancestor through which the two types descend.

So, for comparing G and B, you find the closest common ancestor (Adapter), and then find the types through which these two types are descended (K and B) and then perform your arbitrary sorting rule on those types.

---

Something like this (no promises about code quality :-)):

    public List<Type> Ancestors(Type any)
    {
        var result = new List<Type>();
        result.Add(any);
        while (any != typeof(object))
        {
            any = any.BaseType;
            result.Insert(0, any);
        }
        return result;
    }
    public int Compare(Type lhs, Type rhs)
    {
        if (rhs.IsSubclassOf(lhs))
        {
            return -1;
        }
        else if (lhs.IsSubclassOf(rhs))
        {
            return +1;
        }
        else
        {
            var lAncs = Ancestors(lhs);
            var rAncs = Ancestors(rhs);
            int ix = 0;
            while (lAncs[ix] == rAncs[ix])
            {
                ix++;
            }
            return lAncs[ix].FullName.CompareTo(rAncs[ix].FullName);
        }
    }

I think this code is safe from wandering off of the end of the lists since if one of the lists is exhausted, it means that one of the types is in fact an ancestor of the other so the previous subclassing rules should have already resolved the comparison.

Also, you may wish to consider "memoizing" the Ancestors lookup using a Dictionary<Type,List<Type>>.

Answer 2

Sorting algorithms used by Linq OrderBy (quick-sort) require a complete order relation. You have extended your partial order with an arbitrary assignment on pairs not ordered by your partial order relation, but the result isn't going to fulfil the axioms of complete ordering, in particular it's not going to be transitive (e.g. in your toy example P<AA and AA<E, but E<P when transitivity requires P<E) and the sorting algorithms that rely on transitivity will behave arbitrarily badly. That's what you observe. Instead of OrderBy which uses quick sort internally, you want a topological sorting algorithm.