Search code examples
c++boostmetaprogrammingboost-mpl

Permutations of a List of Types Using boost::mpl


I am trying to create a list containing the permutations of a given type list.

The below code seems to function, though without the intended result, when I use a specified list instead of generating a new list by removing from the actual input. This is demonstrated by the difference between permutation_helper and broken_helper below.

Does anyone know why mpl::remove doesn't seem to function as expected in this circumstance?

#include <boost/mpl/list.hpp>
#include <boost/mpl/transform.hpp>
#include <boost/mpl/fold.hpp>
#include <boost/mpl/push_front.hpp>
#include <boost/mpl/joint_view.hpp>
#include <boost/mpl/remove.hpp>
#include <boost/mpl/assert.hpp>
#include <boost/mpl/equal.hpp>

namespace mpl = boost::mpl;

struct test_type1 {};
struct test_type2 {};
struct test_type3 {};

template< typename T >
struct permutations;

template <typename value>
struct permutations<mpl::list1< value > >: mpl::list1<mpl::list1< value > > {};

template< typename value, typename T>
struct permutation_helper: 
  mpl::transform< typename permutations< 
      mpl::list1<test_type3> >::type, 
    mpl::push_front< mpl::_1, value> > { };

template< typename value, typename T>
struct broken_helper:
  mpl::transform< typename permutations< 
      mpl::remove<T, value> >::type, 
    mpl::push_front< mpl::_1, value> > { };

template< typename T >
struct permutations: 
  mpl::fold< T,
      mpl::list0<>,
      mpl::joint_view< mpl::_1,
         broken_helper<mpl::_2, T > > > { };

typedef mpl::list2<test_type1, test_type2> typelist;
typedef permutations<typelist>::type perms;

int main() {
  BOOST_MPL_ASSERT(( mpl::equal< perms, typelist > ));
  return 0;
}

I used the assert to determine what is being returned from the function, typelist is not the expected result. This is the message the assert returns for broken_helper:

testcase.cpp: In function ‘int main()’:
testcase.cpp:45: error: no matching function for call to ‘assertion_failed(mpl_::failed************ boost::mpl::equal<boost::mpl::joint_view<boost::mpl::joint_view<boost::mpl::list0<mpl_::na>, boost::mpl::l_end>, boost::mpl::l_end>, boost::mpl::list2<test_type1, test_type2>, boost::is_same<mpl_::arg<-0x00000000000000001>, mpl_::arg<-0x00000000000000001> > >::************)’

The output using permutation_helper is an actual list:

testcase.cpp: In function ‘int main()’:
testcase.cpp:45: error: no matching function for call to ‘assertion_failed(mpl_::failed************ boost::mpl::equal<boost::mpl::list2<test_type1, test_type2>, boost::mpl::joint_view<boost::mpl::joint_view<boost::mpl::list0<mpl_::na>, boost::mpl::l_item<mpl_::long_<1l>, boost::mpl::l_item<mpl_::long_<2l>, test_type1, boost::mpl::list1<test_type3> >, boost::mpl::l_end> >, boost::mpl::l_item<mpl_::long_<1l>, boost::mpl::l_item<mpl_::long_<2l>, test_type2, boost::mpl::list1<test_type3> >, boost::mpl::l_end> >, boost::is_same<mpl_::arg<-0x00000000000000001>, mpl_::arg<-0x00000000000000001> > >::************)’

Solution

  • mpl::remove works correctly. The problem is with your template for permutations of singleton lists: it catches only types that are mpl::lists, while the result of remove has another sequence type.

    With other words, the result of mpl::remove is mpl::equal to the singleton list, but not std::is_same:

    #include <boost/mpl/list.hpp>
    #include <boost/mpl/remove.hpp>
    #include <boost/mpl/equal.hpp>
    
    namespace mpl = boost::mpl;
    
    struct test_type1 {};
    struct test_type2 {};
    
    typedef mpl::list2<test_type1, test_type2> typelist;
    typedef mpl::remove<typelist, test_type1>::type t;
    typedef mpl::list1<test_type2> t_corr;
    
    static_assert(mpl::equal<t,t_corr>::value, "t equals t_corr"); 
    // the following will fail:
    // static_assert(std::is_same<t,t_corr>::value, "t same type as t_corr"); 
    
    int main() {
      return 0;
    }
    

    You can fix this problem by specializing your template for the singleton list not based on the exact type mpl::list, but on the property to have length 1:

    #include <boost/mpl/list.hpp>
    #include <boost/mpl/transform.hpp>
    #include <boost/mpl/fold.hpp>
    #include <boost/mpl/push_front.hpp>
    #include <boost/mpl/joint_view.hpp>
    #include <boost/mpl/remove.hpp>
    #include <boost/mpl/assert.hpp>
    #include <boost/mpl/equal.hpp>
    #include <boost/mpl/size.hpp>
    #include <boost/mpl/front.hpp>
    #include <boost/mpl/begin.hpp>
    #include <boost/mpl/next.hpp>
    
    namespace mpl = boost::mpl;
    
    struct test_type1 {};
    struct test_type2 {};
    struct test_type3 {};
    
    template< typename T, typename _ENABLE=void >
    struct permutations;
    
    template <typename T>
    struct permutations<T, 
                typename std::enable_if<mpl::size<T>::value==1>::type>
    {
      typedef typename mpl::list1<T> type;
    };
    
    template< typename value, typename T>
    struct permutation_helper: 
          mpl::transform< typename permutations< 
          mpl::list1<test_type3> >::type, 
        mpl::push_front< mpl::_1, value> > { };
    
    template< typename value, typename T>
    struct broken_helper:
      mpl::transform< typename permutations< 
                typename mpl::remove<T, value>::type >::type, 
              mpl::push_front< mpl::_1, value> > { };
    
    template< typename T >
    struct permutations<T, 
                typename std::enable_if<(mpl::size<T>::value>1)>::type>: 
      mpl::fold< T,
          mpl::list0<>,
          mpl::joint_view< mpl::_1,
          broken_helper<mpl::_2, T > > > { };
    
    typedef mpl::list2<test_type1, test_type2> typelist;
    typedef permutations<typelist>::type perms;
    typedef mpl::list<mpl::list<test_type1, test_type2>, 
              mpl::list<test_type2, test_type1> > perms_corr;
    
    int main() {
      static_assert(mpl::size<perms>::value == 2, "perms has correct size");
      static_assert(mpl::equal<mpl::front<perms>::type,
                       mpl::front<perms_corr>::type>::value, "perms has correct front");
      typedef mpl::next<mpl::begin<perms>::type>::type perms_2nd;
      typedef mpl::next<mpl::begin<perms_corr>::type>::type perms_corr_2nd;
      static_assert(mpl::equal<perms_2nd, perms_corr_2nd>::value, "perms has correct 2nd element");
      return 0;
    }
    

    By the way,

    static_assert(mpl::equal<perms, perms_corr>::value, "perms correct");
    

    will fail for exactly the same reasons.

    • lars