[boost] [MPL] interest in algo that creates all possible permutations of a type?

From: Kevin Sopp (baraclese_at_[hidden])
Date: 2005-11-10 13:42:55

Hi,

I just joined the list and I would like to show you what I have done here.

Given a type T which is a model of MPL lambda expression, permute<T, Args1, 
..., ArgsN>::type is an MPL vector that contains all possible permutations 
of type T, where ArgsN is a model of an MPL forward sequence.

Example:
template<class X, class Y>
struct base{};

permute<
  base<_1,_2>, vector<int, float>, vector<double, bool>
>::type types;

types is an MPL vector containing all possible permutations of base with the 
supplied argument lists:
vector<
  base<int,double>,
  base<int,bool>,
  base<float,double>,
  base<float,bool>
>

(not necessarily in this order)

I believe I can easily extend this algo to n-ary lambda expressions with 
some preprocessor macros. The version for binary expressions is attached 
below because the code is short. I tested the code with gcc 3.4.4.

Example usage: I use this algo to create a typelist that is given to my 
renderer which instantiates a 'dispatch table' (see More Effective C++, Item 
31) and the appropriate render functions for these types. Then at runtime 
the entities to be rendered are dispatched based on their dynamic type to 
the specialized render functions which only work on concrete types.

#ifndef permute_h
#define permute_h

#include <boost/mpl/apply.hpp>
#include <boost/mpl/at.hpp>
#include <boost/mpl/bool.hpp>
#include <boost/mpl/if.hpp>
#include <boost/mpl/eval_if.hpp>
#include <boost/mpl/int.hpp>
#include <boost/mpl/modulus.hpp>
#include <boost/mpl/push_back.hpp>
#include <boost/mpl/size.hpp>
#include <boost/mpl/vector.hpp>

template<class T, class Args1, class Args2, class Seq, int N, int K>
struct permute_impl
{
typedef typename boost::mpl::modulus<
   boost::mpl::int_<N>,boost::mpl::size<Args2>
>::type args2_index;

typedef typename boost::mpl::push_back<
     Seq
   , typename boost::mpl::apply<
         T
       , typename boost::mpl::at_c<Args1, K>::type
       , typename boost::mpl::at<Args2, args2_index>::type
     >::type
>::type Seq2;

typedef typename boost::mpl::eval_if_c<
   N == 0
, Seq
, permute_impl<
     T
   , Args1,Args2
   , Seq2
   , N-1
   , boost::mpl::if_c<
       args2_index::value == 1
     , boost::mpl::int_<K+1>
     , boost::mpl::int_<K>
     >::type::value
   >
>::type type;
};

template<class T, class Args1, class Args2>
struct permute
{
typedef typename permute_impl<
   T, Args1, Args2, boost::mpl::vector<>,
   boost::mpl::size<Args1>::value*boost::mpl::size<Args2>::value, 0
>::type type;
};

#endif

_________________________________________________________________
Express yourself instantly with MSN Messenger! Download today it's FREE! 
http://messenger.msn.click-url.com/go/onm00200471ave/direct/01/