boost/hana/cartesian_product.hpp

0001 /*!
0002 @file
0003 Defines `boost::hana::cartesian_product`.
0004
0005 Copyright Louis Dionne 2013-2022
0006 Distributed under the Boost Software License, Version 1.0.
0007 (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
0008  */
0009
0010 #ifndef BOOST_HANA_CARTESIAN_PRODUCT_HPP
0011 #define BOOST_HANA_CARTESIAN_PRODUCT_HPP
0012
0013 #include <boost/hana/fwd/cartesian_product.hpp>
0014
0015 #include <boost/hana/at.hpp>
0016 #include <boost/hana/concept/sequence.hpp>
0017 #include <boost/hana/config.hpp>
0018 #include <boost/hana/core/dispatch.hpp>
0019 #include <boost/hana/core/make.hpp>
0020 #include <boost/hana/detail/array.hpp>
0021 #include <boost/hana/integral_constant.hpp>
0022 #include <boost/hana/length.hpp>
0023 #include <boost/hana/unpack.hpp>
0024
0025 #include <cstddef>
0026 #include <utility>
0027
0028
0029 namespace boost { namespace hana {
0030     //! @cond
0031     template <typename Xs>
0032     constexpr auto cartesian_product_t::operator()(Xs&& xs) const {
0033         using S = typename hana::tag_of<Xs>::type;
0034         using CartesianProduct = BOOST_HANA_DISPATCH_IF(
0035             cartesian_product_impl<S>,
0036             hana::Sequence<S>::value
0037         );
0038
0039     #ifndef BOOST_HANA_CONFIG_DISABLE_CONCEPT_CHECKS
0040         static_assert(hana::Sequence<S>::value,
0041         "hana::cartesian_product(xs) requires 'xs' to be a Sequence");
0042     #endif
0043
0044         return CartesianProduct::apply(static_cast<Xs&&>(xs));
0045     }
0046     //! @endcond
0047
0048     namespace detail {
0049         template <std::size_t ...Lengths>
0050         struct cartesian_product_indices {
0051             static constexpr std::size_t total_length() {
0052                 std::size_t lengths[sizeof...(Lengths)] = {Lengths...};
0053                 std::size_t r = 1;
0054                 for (std::size_t len: lengths)
0055                     r *= len;
0056                 return r;
0057             }
0058
0059             static constexpr std::size_t length = total_length();
0060
0061             static constexpr auto indices_of(std::size_t i) {
0062                 constexpr std::size_t lengths[sizeof...(Lengths)] = {Lengths...};
0063                 constexpr std::size_t n = sizeof...(Lengths);
0064                 detail::array<std::size_t, n> result{};
0065                 for (std::size_t j = n; j--;) {
0066                     result[j] = i % lengths[j];
0067                     i /= lengths[j];
0068                 }
0069                 return result;
0070             }
0071
0072             template <typename S, std::size_t n, std::size_t ...k, typename ...Xs>
0073             static constexpr auto
0074             product_element(std::index_sequence<k...>, Xs&& ...xs) {
0075                 constexpr auto indices = indices_of(n);
0076                 return hana::make<S>(hana::at_c<indices[k]>(xs)...);
0077             }
0078
0079             template <typename S, std::size_t ...n, typename ...Xs>
0080             static constexpr auto
0081             create_product(std::index_sequence<n...>, Xs&& ...xs) {
0082                 return hana::make<S>(product_element<S, n>(
0083                     std::make_index_sequence<sizeof...(Xs)>{}, xs...
0084                 )...);
0085             }
0086         };
0087     }
0088
0089     // Credits: implementation adapted from http://github.com/alexk7/hel.
0090     template <typename S, bool condition>
0091     struct cartesian_product_impl<S, when<condition>> : default_ {
0092         template <typename Xs>
0093         static constexpr auto apply(Xs&& xs) {
0094             return hana::unpack(static_cast<Xs&&>(xs), cartesian_product_impl{});
0095         }
0096
0097         template <typename ...Xs>
0098         constexpr auto operator()(Xs&& ...xs) const {
0099             using indices = detail::cartesian_product_indices<
0100                 decltype(hana::length(xs))::value...
0101             >;
0102             return indices::template create_product<S>(
0103                         std::make_index_sequence<indices::length>{},
0104                         static_cast<Xs&&>(xs)...);
0105         }
0106
0107         constexpr auto operator()() const {
0108             return hana::make<S>();
0109         }
0110     };
0111 }} // end namespace boost::hana
0112
0113 #endif // !BOOST_HANA_CARTESIAN_PRODUCT_HPP