cartesian_product.cpp

#include <tuple>
#include <utility>
#include <algorithm>
#include <memory>
#include <vector>
#include <set>

#include <iostream>
#include <iterator>
#include <ostream>
#include <type_traits>

#include "tuples/for_each.hpp"
#include "tuples/printer.hpp"
#include "mpl/identity.hpp"
#include "mpl/transform.hpp"

namespace mpl
{


template<typename T>
struct container_type {
  typedef typename T::container_type type;
};

template<typename T>
struct value_type : T::value_type { };

template<bool B, typename T>
struct iter_kind_h : identity<T> { };

template<typename T>
struct iter_kind_h<true,T> : identity<typename T::container_type> { };

template<typename T>
struct iter_kind : iter_kind_h< std::is_void<typename T::value_type>::value, T> { };

}

namespace algorithm
{

namespace detail
{

template<size_t N, typename tuple_type, typename Out>
struct cartesian_product_impl
{
  template<typename C, typename ... Containers>
  void operator()( Out& out, tuple_type tt_, C const& c, Containers const& ... containers )
  {
    for( auto it = c.begin() ; it != c.end(); ++it )
    {
      tuple_type tt( tt_ );
      ::std::get<N-sizeof...(Containers)-1>(tt) = *it;
      cartesian_product_impl<N, tuple_type, Out>()(out, tt, containers... );
    }
  }

  template< typename C >
  void operator()( Out& out, tuple_type tt_, C const& c )
  {
    for( auto it = c.begin() ; it != c.end(); ++it )
    {
      tuple_type tt( tt_ );
      ::std::get<N-1>(tt) = *it;
      *out = tt;
      ++out;
    }
  }
};

template< class Cont>
struct get_value_type
{
  typedef typename mpl::normalize<Cont>::type::value_type type;
};

template<typename ... Containers>
struct cartesian_product_value_type :
  mpl::transform<std::tuple<Containers...>, mpl::lambda<get_value_type> > { };


} // deatil

                                           size_t get_cartesian_size_( size_t init) { return init; }
template< typename T, typename ... Args  > size_t get_cartesian_size_( size_t init, T&&t, Args&&... args) { return get_cartesian_size_( init * t.size(), args... ); }
template< typename T>                      size_t get_cartesian_size_( size_t init, T&&t ) { return init*t.size(); }
template< typename T>                      size_t get_cartesian_size( T&&t ) { return t.size(); }
template< typename T, typename ... Args  > size_t get_cartesian_size( T&&t, Args&&... args) { return get_cartesian_size_( t.size(), args... ); }
                                           size_t get_cartesian_size() { return 0; }

template<
    typename OutIterator,
    typename ... Containers>
struct cartesian_product
{
  typedef typename detail::cartesian_product_value_type<Containers...>::type value_type;

  cartesian_product( OutIterator& out, Containers&& ... in )
  {
    value_type t = {};
    detail::cartesian_product_impl< sizeof...(in), value_type, OutIterator >()
        ( out, t, in...);
  }
};

template<
    typename OutIterator,
    typename ... Containers>
void get_cartesian_product( OutIterator out, Containers&&... in )
{
  static_assert( sizeof...(in) >= 1, "Cartesian product requires at least 1 container" );
  typedef typename detail::cartesian_product_value_type<Containers...>::type ResultValueType;
  typedef typename mpl::iter_kind< OutIterator >::type::value_type IteratorValueType;
  static_assert(
    std::is_same<
      ResultValueType,
      IteratorValueType
    >::value,
    "Output Iterator type does not match result type"
  );
  cartesian_product<OutIterator,Containers...>( out, in... );
}

template<
    template<typename,typename...> class OutContainer,
    typename ... Containers>
struct cartesian_product_create
{
  typedef typename detail::cartesian_product_value_type<Containers...>::type value_type;
  typedef OutContainer< value_type > container_type;
  typedef typename container_type::iterator iterator;

  container_type container;

  iterator begin() { return container.begin(); }
  iterator end() { return container.end(); }

  cartesian_product_create( Containers&& ... containers ) :
      container( get_cartesian_size( containers... ) )
  {

    value_type t = {};
    iterator it = container.begin();
    detail::cartesian_product_impl< sizeof...(containers), value_type, iterator >()
        ( it, t, containers...);
  }
};

template<
    template<typename,typename...> class OutContainer = std::vector,
    typename ... Containers>
auto get_cartesian_product( Containers&&... in ) ->
    cartesian_product_create< OutContainer, Containers... >
{
  static_assert( sizeof...(in) >= 1, "Cartesian product requires at least 1 container" );
  typedef typename detail::cartesian_product_value_type<Containers...>::type ResultValueType;

  return cartesian_product_create<OutContainer,Containers...>( in... );
}

} //algorithm

namespace std {
using tuples::operator<<;
}

int main()
{
  using namespace std;
  vector<int> a;
  vector<const char*> b;
  vector<float> c;

  a.push_back(1); a.push_back(2);
  b.push_back("Hello"); b.push_back("World");
  c.push_back(.1); c.push_back(.2);


  auto cs = algorithm::get_cartesian_product<vector>( a,b,c);
  typedef decltype(cs) cst;
  copy(cs.begin(), cs.end(), ostream_iterator<typename cst::value_type>(cout,"\n") );
  cout<<endl;

  typedef tuple<int, const char*, float> tup;
  set< tup > z;
  algorithm::get_cartesian_product( inserter(z,z.begin()),a,b,c);
  copy(z.begin(), z.end(), ostream_iterator<tup>(cout,"\n") );
  cout<<endl;

  vector< tup > y( algorithm::get_cartesian_size(a,b,c) );
  algorithm::get_cartesian_product(y.begin(),a,b,c);
  copy(y.begin(), y.end(), ostream_iterator<tup>(cout,"\n") );
  cout<<endl;
}