Compile-time quicksort: Passing comparer as template parameter

Question

As part of a personal project, i have developed a template metaprogramming library that has an implemetation of type lists using C++11 variadic templates.

To test typelists operations, such as merge two typelists, split a typelist in two typelists, push_back a type in a typelist, etc (And to do a very freak programming excercise); i have implemented a compile-time version of the quicksort sorting algorithm using template metaprogramming:

NOTE: "dl32" is the prefix of my library types.

#include "dl32MetaprogrammingLibrary.h"

#include <iostream>
using namespace std;

/* quicksort sorts lists of unsigned ints */
template<unsigned int... Ns>
using uint_list = dl32TypeList<dl32UintWrapper<Ns>...>;
using empty_uint_list = dl32EmptyTypeList;

/* set of unsigned int comparers */
template<typename UINT1, typename UINT2>
struct equal           : public dl32BoolWrapper< UINT1::value == UINT2::value > {};
template<typename UINT1, typename UINT2>
struct not_equal       : public dl32BoolWrapper< UINT1::value != UINT2::value > {};
template<typename UINT1, typename UINT2>
struct bigger_than     : public dl32BoolWrapper< (UINT1::value > UINT2::value) > {};
template<typename UINT1, typename UINT2>
struct less_than       : public dl32BoolWrapper< (UINT1::value < UINT2::value) > {};
template<typename UINT1, typename UINT2>
struct bigger_or_equal : public dl32BoolWrapper< UINT1::value >= UINT2::value > {};
template<typename UINT1, typename UINT2>
struct less_or_equal   : public dl32BoolWrapper< UINT1::value <= UINT2::value > {};


/* Compile-time quicksort implementation */
template<typename UINT_LIST>
class quicksort
{
private:
    //Forward declaration:
    template<unsigned int lenght , typename SUBLIST>
    struct _quicksort;

    //Base-case for empty sublists:
    template<typename... Ns>
    struct _quicksort<0,dl32TypeList<Ns...>>
    {
        using result = empty_uint_list;
    };

    //Base case for one element sublists:
    template<typename UINT_WRAPPER>
    struct _quicksort<1,dl32TypeList<UINT_WRAPPER>>
    {
        using result = dl32TypeList<UINT_WRAPPER>;
    };

    //Base-case for two elements sublists (Simple compare and swap):
    template<typename FIRST , typename LAST >
    struct _quicksort<2,dl32TypeList<FIRST,LAST>>
    {
        using result = typename dl32tmp_if< bigger_or_equal<FIRST,LAST>::value , //CONDITION
                                            dl32TypeList<FIRST,LAST>,            //THEN
                                            dl32TypeList<LAST,FIRST>             //ELSE
                                          >::type;
    };

    //Recursive case:
    template<unsigned int lenght , typename... Ns>
    struct _quicksort<lenght,dl32TypeList<Ns...>>
    {
    private:
        /* STEP 1: Reorder the sublist in two sublists: Left sublist, with elements greater than pivot, and right, with the others */

        //Forward declaration:
        template<typename PIVOT , typename RIGHT /* initial (or actual) right sublist */ , typename LEFT /* initial (or actual) left sublist */ , typename _UINT_LIST /* original sublist */>
        struct _reorder_sublists;

        //Recursive case:
        template<typename PIVOT , typename... RIGHT_UINTS , typename... LEFT_UINTS , typename HEAD , typename... TAIL>
        struct _reorder_sublists<PIVOT,dl32TypeList<RIGHT_UINTS...>,dl32TypeList<LEFT_UINTS...>,dl32TypeList<HEAD,TAIL...>>
        {
            using _next_left  = dl32TypeList<LEFT_UINTS...,HEAD>;  ///< Next left  sublist if HEAD is greather than PIVOT.
            using _next_right = dl32TypeList<HEAD,RIGHT_UINTS...>; ///< Next right sublist if HEAD is less than PIVOT.
            //                                                    CONDITION                  THEN                    ELSE
            using next_left  = typename dl32tmp_if< !bigger_or_equal<PIVOT,HEAD>::value , _next_left  , dl32TypeList<LEFT_UINTS...>>::type;
            using next_right = typename dl32tmp_if<  bigger_or_equal<PIVOT,HEAD>::value , _next_right , dl32TypeList<RIGHT_UINTS...>>::type;

            using next_reorder = _reorder_sublists<PIVOT,next_right,next_left,dl32TypeList<TAIL...>>; // "Recursive call" (Iteration)

            using right = typename next_reorder::right; //Recursive result return
            using left  = typename next_reorder::left;  //Recursive result return
        };

        //Base case (End of the iteration):
        template<typename PIVOT , typename RIGHT , typename LEFT>
        struct _reorder_sublists<PIVOT,RIGHT,LEFT,empty_uint_list>
        {
            using right = RIGHT;
            using left  = LEFT;
        };

        template<typename PIVOT>
        using _right_sublist = typename _reorder_sublists<PIVOT,empty_uint_list,empty_uint_list,dl32TypeList<Ns...>>::right; //Right sublist computation
        template<typename PIVOT>
        using _left_sublist  = typename _reorder_sublists<PIVOT,empty_uint_list,empty_uint_list,dl32TypeList<Ns...>>::left;  //Left sublist computation

    private:
        static const unsigned int _half_size   = lenght/2;
        static const unsigned int _pivot_index = _half_size; //"Silly" pivot policy. Random-pivot instead? http://stackoverflow.com/questions/11498304/generate-random-numbers-in-c-at-compile-time
        using _pivot = typename dl32TypeAt<_pivot_index,dl32TypeList<Ns...>>::type;

        using _right = _right_sublist<_pivot>; //"Call" to reordered right sublist computation
        using _left  = _left_sublist<_pivot>;  //"Call" to reordered left sublist computation

    public:
        /* STEP 2: Recursive "call" to quicksort passing the two generated sublists */

        using result = typename dl32Merge< typename _quicksort< _left::size , _left >::result , typename _quicksort< _right::size , _right >::result >::result;
    };

public:
    using result = typename _quicksort<UINT_LIST::size,UINT_LIST>::result; //"Call" to quicksort computation;
};


/* input/output printing tools */

template<typename OUTPUT>
struct print_output;

template<>
struct print_output<empty_uint_list>{ static void print() { cout << endl << endl; } };

template<typename HEAD , typename... TAIL>
struct print_output<dl32TypeList<HEAD,TAIL...>>
{
    static void print() 
    { 
        cout << HEAD::value << (sizeof...(TAIL) > 0 ? "," : ""); 
        print_output<dl32TypeList<TAIL...>>::print(); 
    }
};


/* unsigned int lists generator */

template<unsigned int BEGIN , unsigned int END>
class uint_list_generator
{
private:
    template<unsigned int _CURRENT,unsigned int _END>
    struct _generator
    {
        using result = typename dl32Merge<uint_list<_CURRENT>,typename _generator<(BEGIN <= END ? _CURRENT + 1 : _CURRENT - 1) , _END>::result>::result;
    };

    template<unsigned int _END>
    struct _generator<_END,_END>
    {
        using result = uint_list<_END>;
    };

public:
    using result  = typename _generator<BEGIN,END>::result;
};

using input  = typename uint_list_generator<0,499>::result;
using output = typename quicksort<input>::result;

int main()
{
    print_output<input>::print();
    print_output<output>::print();

    return 0;
}

The algorithm works perfectly (After the compiler has eaten 4GB of RAM, and waste two minutes to compile an execution of a 500 elements list...).

As you can see, i used a bigger-or-equal comparer in the quicksort implementation. My question is: There are any method to pass the comparer through a template parameter?

The problem is that the algorithm uses lists of unsigned int wrappers as data (See "uint_list" declaration at the beginning of the code), and comparers expect uint wrappers as parameters. So i cannot pass a "generic" comparer through the quicksort template.

That much code, really? Also, prefixes for types were trendy in C : there are namespaces in C++. — Daniel Kamil Kozar, Jun 08 '13 at 23:20
Yeah, its true. I'm thinking about erase the prefixes and put namespaces since a long time ago. But I hesitate. — Manu343726, Jun 09 '13 at 11:26

score 0 · Answer 1 · edited May 23 '17 at 10:25

0

What about a template template parameter:

template <typename UINT_LIST,
          template <typename UINT1, typename UINT2> class compare = less_than>
class quicksort
{
   ...
   using result = typename dl32tmp_if<compare<FIRST,LAST>::value, ...
};
...
using output = typename quicksort<input, bigger_than>::result;

Besides, with such signature, you are not restricted to unsigned int-s at all.

Other than that, sometimes it may be useful to use a wrapper class hiding the template inside to mimic a template typedef.

edited May 23 '17 at 10:25

Community

1
1

answered Jun 07 '13 at 11:32

NonNumeric

1,079
7
19

The problem with template template solution is that numbers are stored at compile-time as wrapper types ( template struct dl32UintWrapper{ static const unsigned int value = n; }; ). So you MUST pass the two values to the comparer. In your solution, you forget the two parameters of less_than. That parameters must be generic, so your solution has the same problem :) – Manu343726 Jun 07 '13 at 12:17
Before asking the question, i had tried the wrap-around solution, but results in compilation errors. If you use a wrapper of the comparer (For example: **struct bigger_than_wrapper { template using comparer = bigger_than; };** ), the use of that comparer is as folows: **... dl32tmp_if< COMPARER::comparer::value , ...** . This results in a ***"expected nested-name specifier"*** error in GCC, event if you put or not the **typename** keyword before the use of COMPARER::comparer. – Manu343726 Jun 07 '13 at 12:23
I don't understand the first comment: I clearly see `compare::value` in the answer passing two parameters to the comparer. – Casey Jun 07 '13 at 15:49
At the quicksort template, last template parameter *COMPARER* has a default value of *less_than*. You must passtwo uint wrappers as parameters of *less_than*. And this makes *less_than* non-generic. I want a method to pass a ***generic*** comparer to the quicksort template. – Manu343726 Jun 07 '13 at 22:53
Note that, for example, **less_than,dl32UintWrapper<1>>** is not the same type as **less_than,dl32UintWrapper<11>>** *THIS is the problem*. I can't pass a comparer "filled" (With parameters) as quicksort parameter, beacuse the comparer passed is not generic. *Its only a comparer for the two numbers that was passed as template parameters to it*. – Manu343726 Jun 07 '13 at 23:16

Compile-time quicksort: Passing comparer as template parameter

1 Answers1