1 /*! 2 @file 3 Defines `boost::hana::cartesian_product`. 4 5 @copyright Louis Dionne 2013-2017 6 Distributed under the Boost Software License, Version 1.0. 7 (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt) 8 */ 9 10 #ifndef BOOST_HANA_CARTESIAN_PRODUCT_HPP 11 #define BOOST_HANA_CARTESIAN_PRODUCT_HPP 12 13 #include <boost/hana/fwd/cartesian_product.hpp> 14 15 #include <boost/hana/at.hpp> 16 #include <boost/hana/concept/sequence.hpp> 17 #include <boost/hana/config.hpp> 18 #include <boost/hana/core/dispatch.hpp> 19 #include <boost/hana/core/make.hpp> 20 #include <boost/hana/detail/array.hpp> 21 #include <boost/hana/integral_constant.hpp> 22 #include <boost/hana/length.hpp> 23 #include <boost/hana/unpack.hpp> 24 25 #include <cstddef> 26 #include <utility> 27 28 29 BOOST_HANA_NAMESPACE_BEGIN 30 //! @cond 31 template <typename Xs> operator ()(Xs && xs) const32 constexpr auto cartesian_product_t::operator()(Xs&& xs) const { 33 using S = typename hana::tag_of<Xs>::type; 34 using CartesianProduct = BOOST_HANA_DISPATCH_IF( 35 cartesian_product_impl<S>, 36 hana::Sequence<S>::value 37 ); 38 39 #ifndef BOOST_HANA_CONFIG_DISABLE_CONCEPT_CHECKS 40 static_assert(hana::Sequence<S>::value, 41 "hana::cartesian_product(xs) requires 'xs' to be a Sequence"); 42 #endif 43 44 return CartesianProduct::apply(static_cast<Xs&&>(xs)); 45 } 46 //! @endcond 47 48 namespace detail { 49 template <std::size_t ...Lengths> 50 struct cartesian_product_indices { total_lengthdetail::cartesian_product_indices51 static constexpr std::size_t total_length() { 52 std::size_t lengths[sizeof...(Lengths)] = {Lengths...}; 53 std::size_t r = 1; 54 for (std::size_t len: lengths) 55 r *= len; 56 return r; 57 } 58 59 static constexpr std::size_t length = total_length(); 60 indices_ofdetail::cartesian_product_indices61 static constexpr auto indices_of(std::size_t i) { 62 constexpr std::size_t lengths[sizeof...(Lengths)] = {Lengths...}; 63 constexpr std::size_t n = sizeof...(Lengths); 64 detail::array<std::size_t, n> result{}; 65 for (std::size_t j = n; j--;) { 66 result[j] = i % lengths[j]; 67 i /= lengths[j]; 68 } 69 return result; 70 } 71 72 template <typename S, std::size_t n, std::size_t ...k, typename ...Xs> 73 static constexpr auto product_elementdetail::cartesian_product_indices74 product_element(std::index_sequence<k...>, Xs&& ...xs) { 75 constexpr auto indices = indices_of(n); 76 return hana::make<S>(hana::at_c<indices[k]>(xs)...); 77 } 78 79 template <typename S, std::size_t ...n, typename ...Xs> 80 static constexpr auto create_productdetail::cartesian_product_indices81 create_product(std::index_sequence<n...>, Xs&& ...xs) { 82 return hana::make<S>(product_element<S, n>( 83 std::make_index_sequence<sizeof...(Xs)>{}, xs... 84 )...); 85 } 86 }; 87 } 88 89 // Credits: implementation adapted from http://github.com/alexk7/hel. 90 template <typename S, bool condition> 91 struct cartesian_product_impl<S, when<condition>> : default_ { 92 template <typename Xs> applycartesian_product_impl93 static constexpr auto apply(Xs&& xs) { 94 return hana::unpack(static_cast<Xs&&>(xs), cartesian_product_impl{}); 95 } 96 97 template <typename ...Xs> operator ()cartesian_product_impl98 constexpr auto operator()(Xs&& ...xs) const { 99 using indices = detail::cartesian_product_indices< 100 decltype(hana::length(xs))::value... 101 >; 102 return indices::template create_product<S>( 103 std::make_index_sequence<indices::length>{}, 104 static_cast<Xs&&>(xs)...); 105 } 106 operator ()cartesian_product_impl107 constexpr auto operator()() const { 108 return hana::make<S>(); 109 } 110 }; 111 BOOST_HANA_NAMESPACE_END 112 113 #endif // !BOOST_HANA_CARTESIAN_PRODUCT_HPP 114