Type-level list and compile-time sort in C++

type-level-list.cpp

template <int n>
struct Int { static const int val = n; }; // Wrap an integer

template <class fst, class snd>
struct pair {
  typedef fst first;
  typedef snd second;
};

struct nil {
  static const bool isnil = true;
};

template <class hd, class tl>
struct cons : public pair<hd, tl> {
  static const bool isnil = false;
};

template <class list>
struct head : public list::first {};

template <class list>
struct tail : public list::second {};

// =============================================================================
// foldl
// =============================================================================

template <bool, template <class, class> class f, class acc, class list>
struct __foldl_aux {
  typedef acc type;
};

template <template <class, class> class f, class acc, class list>
struct __foldl_aux <false, f, acc, list> {
  typedef typename __foldl_aux<tail<list>::isnil,
                               f, f<acc, head<list> >, tail<list> >::type type;
};

template <template <class, class> class f, class init, class list>
struct foldl : public __foldl_aux<list::isnil, f, init, list>::type {};

// =============================================================================
// foldr
// =============================================================================

template <bool, template <class, class> class f, class list, class acc>
struct __foldr_aux {
  typedef acc type;
};

template <template <class, class> class f, class list, class acc>
struct __foldr_aux <false, f, list, acc> {
  typedef f<head<list>, typename __foldr_aux<tail<list>::isnil,
                                             f, tail<list>, acc>::type> type;
};

template <template <class, class> class f, class list, class init>
struct foldr : public __foldr_aux<list::isnil, f, list, init>::type {};

// =============================================================================
// length
// =============================================================================

template <class acc, class>
struct __length_aux : public Int<acc::val + 1> {};

template <class list>
struct length : public foldl<__length_aux, Int<0>, list> {};

// =============================================================================
// append (concatenate two lists)
// =============================================================================

template <class elm, class acc>
struct __append_aux : public cons<elm, acc> {};

template <class x, class y>
struct append : public foldr<__append_aux, x, y> {};

// =============================================================================
// filter
// =============================================================================

template <template <class> class f, class list>
struct __filter_imp {
private:
  template <bool, class elm, class acc>
  struct __if_cons { typedef cons<elm, acc> type; };

  template <class elm, class acc>
  struct __if_cons <false, elm, acc> { typedef acc type; };

  template <class elm, class acc>
  struct __aux : public __if_cons<f<elm>::val, elm, acc>::type {};

public:
  typedef foldr<__aux, list, nil> type;
};

template <template <class> class f, class list>
struct filter : public __filter_imp<f, list>::type {};

// =============================================================================
// selection sort
// =============================================================================

template <bool, class acc, class elm>
struct __ssort_min_aux2 {
  typedef pair<typename acc::first, cons<elm, typename acc::second> > type;
};

template <class acc, class elm>
struct __ssort_min_aux2 <false, acc, elm> {
  typedef pair<elm, cons<typename acc::first, typename acc::second> > type;
};

template <class acc, class elm>
struct __ssort_min_aux
  : public __ssort_min_aux2<(acc::first::val < elm::val), acc, elm>::type {};

template <class list>
struct __ssort_min
  : public foldl<__ssort_min_aux, pair<head<list>, nil>, tail<list> > {};

template <bool, class list>
struct __ssort_aux {
  typedef __ssort_min<list> pair;
  typedef typename pair::second rest;
  typedef cons<typename pair::first,
               typename __ssort_aux<rest::isnil, rest>::type> type;
};

template <class list>
struct __ssort_aux <true, list> {
  typedef nil type;
};

template <class list>
struct ssort : public __ssort_aux<list::isnil, list>::type {};

// =============================================================================
// quick sort
// =============================================================================

template <bool, class list>
struct __qsort_aux {
private:
  typedef head<list> pivot;

  template <class elm>
  struct le_pivot { static const bool val = elm::val <= pivot::val; };

  template <class elm>
  struct gt_pivot { static const bool val = elm::val > pivot::val; };

  typedef tail<list> rest;
  typedef filter<le_pivot, rest> le_part;
  typedef filter<gt_pivot, rest> gt_part;
  typedef typename __qsort_aux<length<le_part>::val >= 2, le_part>::type sorted_le_part;
  typedef typename __qsort_aux<length<gt_part>::val >= 2, gt_part>::type sorted_gt_part;

public:
  typedef append<sorted_le_part, cons<pivot, sorted_gt_part> > type;
};

template <class list>
struct __qsort_aux <false, list> {
  typedef list type;
};

template <class list>
struct qsort : public __qsort_aux<length<list>::val >= 2, list>::type {};

// =============================================================================
// Printer
// =============================================================================

#include <cstdio>

struct __print_init {
  static inline void run () {}
};

template <class acc, class elm>
struct __print_aux : public acc {
  static inline void run () {
    acc::run();
    std::printf("%d; ", elm::val);
  }
};

template <class list>
struct print : public foldl<__print_aux, __print_init, list> {};

// =============================================================================
// Test
// =============================================================================

// An unsorted type-level list.
typedef cons<Int<5>,
        cons<Int<4>,
        cons<Int<8>,
        cons<Int<1>,
        cons<Int<6>,
        cons<Int<3>,
        cons<Int<7>,
        cons<Int<2>, nil> > > > > > > > my_lst;

int main () {
  print<my_lst>::run(); // 5; 4; 8; 1; 6; 3; 7; 2;
  std::printf("\n");

  print<ssort<my_lst> >::run(); // 1; 2; 3; 4; 5; 6; 7; 8;
  std::printf("\n");

  print<qsort<my_lst> >::run(); // 1; 2; 3; 4; 5; 6; 7; 8;
  std::printf("\n");

  return 0;
}