Is it possible to generate types with all combinations of template arguments?

Question

I have a templated class

template<class U, class V, class W> 
class S
{
//... implementations 
};

and some stock type implementations for type U, V and W:

typedef boost::mpl::vector<U0, U1> u_types;
typedef boost::mpl::vector<V0, V1, V2, V3, V4> u_types;
typedef boost::mpl::vector<W0, W1, W2, W3, W4> w_types;

I want to test class S with all possible combinations of the template arguments,

typedef boost::mpl::vector<
    S<U0,V0,W0>, 
    S<U0,V0,W1>,
    // ...
    S<U1,V4,W4>,
    > s_types;

like this:

boost::mpl::for_each<s_types>(test_func).

The only problem is there are 2 ** 5 ** 5 = 50 combinations that I do not wish to type in one by one.

Is there a way to generate all the combinations(s_types) with Boost::mpl or Boost.Preprocessor?

thanks.

---

Added my initial failed attempts:

I was trying to resort to indexes(hence defining u_types and the like) and partial template specialization like this

namespace wrapper
{
  template <int Uidx, int Vidx, int Widx> 
  struct S_Wrapper
  {
    typedef S<Uidx, Vidx, Widx> type;

    S_Wrapper() // auto test in the ctor
    {
      cout << "test result = " << test(type());
    }

    // test with S<Uidx, Vidx, Widx>
    static bool test(type t)
    {
      // implementations
    }

    // get stuck here, 
    S_Wrapper<Uidx-1, Vidx, Widx> s; // temp varible to invoke recursive-ness
    // what else to complete all recursive path?
  };

  // specializations       
  template <0, 0, 0> 
  struct S_Wrapper
  {
    typedef S<0, 0, 0> type;

    // test with S<Uidx, Vidx, Widx>
    //
    static bool test(type t)
    {
      // implementations
    }  
  };

  // get stuck here, too
  // what other specializations are ?
  // other specializations
}

then with

wrapper::S_Wrapper< 
  mpl::size<u_types>::type::value, 
  mpl::size<v_types>::type::value, 
  mpl::size<w_types>::type::value
> s; 

all S types should be gengerated and tested ;

However I failed to cover all the combination by determining

1) the proper specializations and
2) recursive-ness triggers in struct S_Wrapper

All my trials either ended up in partial coverage of the combinations at runtime or deduction failure at compile time.

Any thoughts?

---

Solution

Inspired by Matthieu, I've come up with a templated class Combine so that I could achieve my goal in 2 lines like this:

typedef Combine<
            u_types,
            v_types,
            w_type,
            print_typeid
        >::Generate<> base_generator_type;
base_generator_type::Run();

which will print all generated types.

---

Code

// example test implementation
struct print_typeid
{
    template<
        class U, 
        class V, 
        class W
    >
    static void run()
    {
        // print the typeinfo
        std::cout 
            <<  total_recursions << ":"
            << typeid(U).name() << ","
            << typeid(V).name() << ","
            << typeid(W).name()
            << std::endl;  
    }            
}; 

// solution implemented in one wrapper class
namespace argument_combination
{
    using boost::is_same;
    using boost::mpl::begin;
    using boost::mpl::end;
    using boost::mpl::next;        
    using boost::mpl::if_;  
    using boost::mpl::deref;    

    unsigned int total_recursions = 0;

    struct end_of_recursion_tag 
    {
        static void Run()
        {
            std::cout << "end of " 
                 << total_recursions 
                 << " recursions\n"
                ;
        }
    };

    template <
        class UTypes,    // Forward Sequence, e.g. boost::mpl::vector
        class VTypes,    // Forward Sequence, e.g. boost::mpl::vector
        class WTypes,    // Forward Sequence, e.g. boost::mpl::vector
        class TestFunc  // class type that has a nested templated run() member function
    >
    struct Combine
    {
        // forward declaration
        template <
            class UIterator,
            class VIterator,
            class WIterator 
        >   
        class Generate;

        // this class implements recursion body 
        template <
            class UIterator,
            class VIterator,
            class WIterator
        >            
        struct Next
        {
            // u_begin is not necessary ;)
            // it would be cheaper not to pre-declare all of them since we force evaluation
            // however this dramatically increase the readability
            typedef typename begin<VTypes>::type v_begin;
            typedef typename begin<WTypes>::type w_begin;

            typedef typename end<UTypes>::type u_end;
            typedef typename end<VTypes>::type v_end;
            typedef typename end<WTypes>::type w_end;

            typedef typename next<UIterator>::type u_next;
            typedef typename next<VIterator>::type v_next;
            typedef typename next<WIterator>::type w_next;

            typedef typename if_< is_same<typename w_next, w_end>,
                                typename if_< is_same<v_next, v_end>,
                                    typename if_< is_same<u_next, u_end>,
                                        end_of_recursion_tag,
                                        Generate< 
                                            u_next, 
                                            v_begin, 
                                            w_begin 
                                        >
                                    >::type,
                                    Generate< 
                                        UIterator, 
                                        v_next,
                                        w_begin 
                                    >
                                >::type,
                                Generate< 
                                    UIterator, 
                                    VIterator, 
                                    w_next
                                    >
                            >::type type;
        };

        //  this class run test on generated types in thos round and go to next*/
        template <
            class UIterator = typename begin<UTypes>::type,
            class VIterator = typename begin<VTypes>::type,
            class WIterator = typename begin<WTypes>::type
        >
        struct Generate
        {
            //  generate <<next>> target type         
            typedef typename Next<
                    UIterator, 
                    VIterator, 
                    WIterator 
                >::type next_type;

            static void Run()
            {
                // increment recursion counter                
                ++total_recursions;

                // test on the generated types of this round of recursion
                TestFunc::run<
                     typename deref<UIterator>::type,
                     typename deref<VIterator>::type,
                     typename deref<WIterator>::type
                 >();

                // go to the next round of recursion
                next_type::Run();
            }
        };
    };

}//  namespace argument_combination

Rama

I don't think you have a choice, but to write all the combinations yourself, should you chose to proceed with templates MP. remember that template evaluation takes place before compilation. – Maroon

Um, template evaluation is done during compilation :) This task should be easy for mpl :) It solves much more difficult problems than just enumerating a few vector items mate. – Irrelevancy

Answer 1

If what you really want to do is generating the vector of all possibles solutions and then test them, you will have to use the preprocessor to generate them all for you.

However, another solution would consist into using a generator: a wrapper class which will instantiate all your solutions and test them. You might want to consult the Hierarchy Generators of Loki (detailed in the book).

// never remember where they put boost::same_type :x
#include <boost/mpl/if.hpp>
#include <boost/mpl/deref.hpp>
#include <boost/mpl/begin.hpp>
#include <boost/mpl/end.hpp>
#include <boost/mpl/next.hpp>

using namespace boost::mpl;

struct None
{
   static void test() {}
};

template <class UIterator, class UTypes,
          class VIterator, class VTypes,
          class WIterator, class WTypes>
class Generator;

template <class UIterator, class UTypes,
          class VIterator, class VTypes,
          class WIterator, class WTypes>
struct Next
{
  // u_begin is not necessary ;)
  // it would be cheaper not to pre-declare all of them since we force evaluation
  // however this dramatically increase the readability
  typedef typename begin<VIterator>::type v_begin;
  typedef typename begin<WIterator>::type w_begin;

  typedef typename next<UIterator>::type u_next;
  typedef typename next<VIterator>::type v_next;
  typedef typename next<WIterator>::type w_next;

  typedef typename end<UIterator>::type u_end;
  typedef typename end<VIterator>::type v_end;
  typedef typename end<WIterator>::type w_end;


  typedef if_< boost::same_type<w_next, w_end>,
               if_< boost::same_type<v_next, v_end>,
                    if_< boost::same_type<u_next, u_end>,
                         None,
                         Generator< u_next, UTypes,
                                    v_begin, VTypes,
                                    w_begin, WTypes >
                    >,
                    Generator< UIterator, UTypes,
                               v_next, VTypes,
                               w_begin, WTypes >
                >,
                Generator< UIterator, UTypes,
                           VIterator, VTypes,
                           w_next, WTypes>
           >::type type;
};

template <class UIterator, class UTypes,
          class VIterator, class VTypes,
          class WIterator, class WTypes>
struct Generator
{
   typedef S< deref<UIterator>::type,
              deref<VIterator>::type,
              deref<WIterator>::type > S_type;

   typedef Next<UIterator, UTypes,
                VIterator, VTypes,
                WIterator, WTypes>::type next_type;

   static void test()
   {
     // test my variation of S
     S_Type my_S;
     test_func(my_S);

     // test the variations of my next and its next and... you get the idea :)
     next_type::test();
   }
};

// And finally
int main(int argc, char* argv[])
{
  typedef Generator< begin<u_types>::type, u_types,
                     begin<v_types>::type, v_types,
                     begin<w_types>::type, w_types > base_generator_type;

  base_generator_type::test();
}

Disclaimer: this code has not been compiled and may lack some include / typename / use directives... nevertheless I hope you get my point.

If you have any idea of what the Design Patterns are, it is highly similar to a 'decorator' or a 'composite' design in its way of adding another round of tests at each step layer.

I would also like to note that this takes more that 50 lines of code... but at least it will grow nicely with the vectors :)

Glori

Nice, i think something like this could do it. However, if you already can traverse all possible combinations - why isn't it possible then to stuff these into an mpl::vector? You seem to have a good grasp at mpl, i'm rather n00by on it. Any chance you wanted to say ?Types for begin and end instead of ?Iterator though? – Irrelevancy

It is possible to stuff them in a mpl::vector, but I am not convinced it would be more efficient or better. I merely wanted to demonstrate the feasibility and the fact that sometimes you can do things in another way that the one you first thought of. If you want to get started on Template Meta-Programming, I can only recommend C++ Template MetaProgramming by David Abrahams and Alexei Gurtovoy 'portal.acm.org/citation.cfm?id=1044941'. – Glori

Thanks, I get the idea. I'll try it tomorrow. Please see my update with my earlier failed trials. Do you think there is a way out in that direction? – Rama

i think with some nested transform calls, this should be possible to build up the list. but i'm cleaning the room currently so i'm busy. later i will try to do it if you haven't come up with it yet. – Irrelevancy

Yes there is a way. If you have trouble with recursion, try to represent with iteration (and at runtime), basically you are looking for 3 'for' loops nested within each others. You have to establish a clear order for your evaluation: in my example w's first, then v's, then u's. The problem is that you only want to decrement one integer per instanciation (and you have to choose which), try to use a 'Next' structure like mine with the same 'if_' tree :) – Glori

@ Matthieu, I just returned from the Golden Week holidays and actually tested your idea. It works very well. Many thanks. In case it might be useful for others. I post my code in the OP. @litb, I thought about the mpl::transform way, It might work but probably less concise and elegant and the mpl::if_ tree as Matthieu suggested. Thanks. – Rama

Answer 2

Dear Matthieu your solution works fine. For my framework I needed a more generic way to implement type combination so I developed something different that seems to work. I propose here my implementation. I think it may be also more MPL oriented if you take the mpl view concept into account. It provides the combination of type sequences as a special combine view and combine iterators:

template < class Seq >
class combine_view {
    typedef typename mpl::transform<Seq, mpl::begin<_1> >::type Pos_begin;
    typedef typename mpl::transform<Seq, mpl::end<_1> >::type   Pos_end;
public:
    typedef combine_iterator<Seq, Pos_begin> begin;
    typedef combine_iterator<Seq, Pos_end>  end;
    typedef combine_view type;
};

This creates a new fwd sequence from a sequence of random access sequences. The combine_iterator that provides begin and end of the sequence must know both the sequences and the iterators that provide position, such as this implementation:

 template < typename Seq, typename Itrs >
 struct combine_iterator {
     typedef mpl::forward_iterator_tag category;
     typedef Seq  seq;
     typedef typename transform <
         Itrs,
         deref<_1>
       >::type
     type;
 };

Now you have to tell boost mpl how to reach the next position specializing mpl::next operation.

namespace boost {
namespace mpl {

template <class Seq, class Pos>
struct next< combine_iterator<Seq, Pos> > {
    typedef typename SequenceCombiner<Seq,Pos>::next next_Pos;
    typedef combine_iterator< Seq, next_Pos > type;
};

} // mpl
} // boost

Finally the combiner trick can be implemented using mpl::fold like in this class:

template <class Seq, class ItrSeq>
class SequenceCombiner {

   template < class _Seq = mpl::vector<int_<1> > >
   struct StateSeq {
       typedef typename pop_front<_Seq>::type sequence;
       typedef typename mpl::at< _Seq, int_<0> >::type state;
       typedef _Seq type;
   };

   template < class _Seq, class _State >
   struct set_state {
       typedef StateSeq< typename push_front<_Seq, _State >::type > type;
   };

   struct NextOp {

       template < typename Out, typename In, typename Enable = typename Out::state >
       class apply {
           typedef typename Out::sequence seq;
           typedef typename Out::state new_state;
           typedef typename mpl::at<In,int_<0> >::type in_seq;
        typedef typename mpl::at<In,int_<1> >::type in_itr;

        typedef typename mpl::push_back<seq, in_itr >::type new_seq;
    public:
        typedef typename set_state<new_seq, int_<0> >::type type;
    };

    template < typename Out, typename In >
    class apply<Out,In,mpl::int_<1> > {
        typedef typename Out::sequence seq;
        typedef typename Out::state state;
        typedef typename mpl::at<In,int_<0> >::type in_seq;
        typedef typename mpl::at<In,int_<1> >::type in_itr;

        typedef typename mpl::begin<in_seq>::type Itr_begin;
        typedef typename mpl::next<in_itr>::type  Itr_next;
        typedef typename mpl::end<in_seq>::type   Itr_end;

        typedef typename mpl::if_< boost::is_same<Itr_next,Itr_end>,
        typename mpl::push_back<seq,Itr_begin>::type,
        typename mpl::push_back<seq,Itr_next>::type
        >::type
        new_seq;

        typedef typename mpl::if_< boost::is_same<Itr_next,Itr_end>,
        mpl::int_<1>,
        mpl::int_<0>
        >::type
        new_state;
    public:
        typedef typename set_state<new_seq, new_state>::type type;
    };
};

typedef typename mpl::fold<
                            typename mpl::zip_view< mpl::vector<Seq, ItrSeq > >::type,
                            StateSeq<>,
                            NextOp
                          >::type
StateResult;

public:

typedef typename mpl::if_< boost::is_same< typename StateResult::state, int_<1> >,
                           typename mpl::transform< Seq, mpl::end<_1> >::type,
                           typename StateResult::sequence >::type
next;
};

Let me show you how to use the resulting new sequence view in a test app.

struct A {};
struct B {};
struct C {};
struct D {};
struct E {};
struct F {};
struct G {};
struct H {};
struct I {};

namespace {        
struct PrintTypeId {
    template <class T>
    void operator()(T) const
    { std::cout << typeid(T).name() << "  "; }
};
struct PrintSeq {
    template < typename T >
    void operator()(T) {
        mpl::for_each<T>( PrintTypeId() );
        std::cout << "\n";
    }
};
}

int main() {
    BEGIN_TESTING( Mpl Sequence Combiner Test);

    typedef mpl::vector<A,B,C>   seq1;
    typedef mpl::vector<D,E,F>   seq2;
    typedef mpl::vector<G,H,I>   seq3;

    typedef mpl::combine_view< mpl::vector<seq1,seq2,seq3> > cv;
    mpl::for_each< cv >( PrintSeq() );

    END_TESTING;
}

The result should be something like this:

..:: Testing Mpl Sequence Combiner Test ::..
1A  1D  1G  
1B  1D  1G  
1C  1D  1G  
1A  1E  1G  
1B  1E  1G  
1C  1E  1G  
1A  1F  1G  
1B  1F  1G  
1C  1F  1G  
1A  1D  1H  
1B  1D  1H  
1C  1D  1H  
1A  1E  1H  
1B  1E  1H  
1C  1E  1H  
1A  1F  1H  
1B  1F  1H  
1C  1F  1H  
1A  1D  1I  
1B  1D  1I  
1C  1D  1I  
1A  1E  1I  
1B  1E  1I  
1C  1E  1I  
1A  1F  1I  
1B  1F  1I  
1C  1F  1I  

Thanks for your Attention.

Andrea Rigoni Garola

Leprechaun