3.12 Partially Ordering Typelists

Suppose we want to order a typelist by inheritance relationship. We'd like, for instance, derived types to appear before base types. For example, say we have a class hierarchy like the one in Figure 3.1:

If we have this typelist:

TYPELIST_4(Widget, ScrollBar, Button, GraphicButton)

the challenge is to transform it into

TYPELIST_4(ScrollBar, GraphicButton, Button, Widget)

That is, we need to bring the most derived types to the front and leave the order of sibling types unaltered.

This seems like an exercise of intellectual value only, but there are important practical applications for it. Scanning a typelist ordered with the most derived types first ensures a bottom-up traversal of a class hierarchy. The double-dispatch engine in Chapter 11 applies this important property for figuring out information about types.

When ordering a collection, we need an ordering function. We already have a compile-time means to detect inheritance relationships, described in detail in Chapter 2. Recall that we have a handy macro, SUPERSUBCLASS(T, U), which evaluates to true if U is derived from T. We just have to combine the inheritance detection mechanism with typelists.

We cannot use a full-fledged sorting algorithm here because we don't have a total ordering relationship; we don't have the equivalent of operator< for classes. Two sibling classes cannot be ordered by SUPERSUBCLASS(T, U). We will therefore use a custom algorithm that will bring derived classes to the front and will let other classes remain in the same relative positions.

   DerivedToFront
   Input: Typelist TList
   Output: Inner type definition Result

   If TList is NullType, then Result is NullType.
   Else
     Find the most derived type from TList::Head in TList::Tail. Store it in a
       temporary variable TheMostDerived.
     Replace TheMostDerived in TList::Tail with TList::Head, obtaining L as the result.
     Build the result as a typelist having TheMostDerived as its head and L as its tail.

When this algorithm is applied to a typelist, derived types will migrate to the top of the typelist, and base types will be pushed to the bottom.

There is a piece missing here—the algorithm that finds the most derived type of a given type in a typelist. Because SUPERSUBCLASS yields a compile-time Boolean value, we'll find the little Select class template (also presented in Chapter 2) to be useful. Recall that Select is a template that selects one of two types based on a compile-time Boolean constant.

The MostDerived algorithm accepts a typelist and a type Base and returns the most derived type from Base in the typelist (or possibly Base itself, if no derived type is found). It looks like this:

   MostDerived
   Input: Typelist TList, type T
   Output: Inner type definition Result

   If TList is NullType, the result is T.
   Else
     Apply MostDerived to TList::Tail and Base. Obtain Candidate.
     If TList::Head is derived from Candidate, the result is TList::Head.
     Else, the result is Candidate.

The implementation of MostDerived is as follows:

template <class TList, class T> struct MostDerived;





template <class T>


struct MostDerived<NullType, T>


{


   typedef T Result;


};





template <class Head, class Tail, class T>


struct MostDerived<Typelist<Head, Tail>, T>


{


private:


   typedef typename MostDerived<Tail, T>::Result Candidate;


public:


   typedef typename Select<


      SUPERSUBCLASS(Candidate, Head),


         Head, Candidate>::Result Result;


};

The DerivedToFront algorithm uses MostDerived as a primitive. Here is DerivedToFront's implementation:

template <class T> struct DerivedToFront;





template <>


struct DerivedToFront<NullType>


{


   typedef NullType Result;


};





template <class Head, class Tail>


struct DerivedToFront< Typelist<Head, Tail> >


{


private:


   typedef typename MostDerived<Tail, Head>::Result


      TheMostDerived;


   typedef typename Replace<Tail,


      TheMostDerived, Head>::Result L;


public:


   typedef Typelist<TheMostDerived, L> Result;


};

This complex typelist manipulation is of considerable strength. The DerivedToFront transformation effectively automates type processing that otherwise can be performed only with much discipline and attention. Automatic maintenance of parallel class hierarchies, anyone?