v3/view/cartesian_product.hpp

0001 /// \file
0002 // Range v3 library
0003 //
0004 //  Copyright Eric Niebler 2013-2014.
0005 //  Copyright Casey Carter 2017.
0006 //
0007 //  Use, modification and distribution is subject to the
0008 //  Boost Software License, Version 1.0. (See accompanying
0009 //  file LICENSE_1_0.txt or copy at
0010 //  http://www.boost.org/LICENSE_1_0.txt)
0011 //
0012 // Project home: https://github.com/ericniebler/range-v3
0013 //
0014
0015 #ifndef RANGES_V3_VIEW_CARTESIAN_PRODUCT_HPP
0016 #define RANGES_V3_VIEW_CARTESIAN_PRODUCT_HPP
0017
0018 #include <cstdint>
0019
0020 #include <concepts/concepts.hpp>
0021
0022 #include <range/v3/range_fwd.hpp>
0023
0024 #include <range/v3/iterator/default_sentinel.hpp>
0025 #include <range/v3/iterator/operations.hpp>
0026 #include <range/v3/range/access.hpp>
0027 #include <range/v3/range/concepts.hpp>
0028 #include <range/v3/range/primitives.hpp>
0029 #include <range/v3/range/traits.hpp>
0030 #include <range/v3/utility/static_const.hpp>
0031 #include <range/v3/utility/tuple_algorithm.hpp>
0032 #include <range/v3/view/all.hpp>
0033 #include <range/v3/view/empty.hpp>
0034 #include <range/v3/view/facade.hpp>
0035 #include <range/v3/view/view.hpp> // for dereference_fn
0036
0037 #include <range/v3/detail/prologue.hpp>
0038
0039 namespace ranges
0040 {
0041     /// \cond
0042     namespace detail
0043     {
0044         template<typename State, typename Value>
0045         using product_cardinality = std::integral_constant<
0046             cardinality,
0047             State::value == 0 || Value::value == 0
0048                 ? static_cast<cardinality>(0)
0049                 : State::value == unknown || Value::value == unknown
0050                       ? unknown
0051                       : State::value == infinite || Value::value == infinite
0052                             ? infinite
0053                             : State::value == finite || Value::value == finite
0054                                   ? finite
0055                                   : static_cast<cardinality>(
0056                                         State::value * Value::value)>;
0057
0058         struct cartesian_size_fn
0059         {
0060             template(typename Size, typename Rng)(
0061                 requires integer_like_<Size> AND sized_range<Rng> AND
0062                     common_with<Size, range_size_t<Rng>>)
0063             common_type_t<Size, range_size_t<Rng>> operator()(Size s, Rng && rng) const
0064             {
0065                 using S = common_type_t<Size, range_size_t<Rng>>;
0066                 return static_cast<S>(s) * static_cast<S>(ranges::size(rng));
0067             }
0068         };
0069
0070         template<typename... Views>
0071         using cartesian_product_cardinality =
0072             meta::fold<meta::list<range_cardinality<Views>...>,
0073                        std::integral_constant<cardinality, static_cast<cardinality>(
0074                                                                (sizeof...(Views) > 0))>,
0075                        meta::quote<detail::product_cardinality>>;
0076     } // namespace detail
0077       /// \endcond
0078
0079     /// \addtogroup group-views
0080     /// @{
0081
0082     // clang-format off
0083     /// \concept cartesian_produce_view_can_const
0084     /// \brief The \c cartesian_produce_view_can_const concept
0085     template<typename...Views>
0086     CPP_concept cartesian_produce_view_can_const =
0087         and_v<range<Views const>...>;
0088
0089     /// \concept cartesian_produce_view_can_size_
0090     /// \brief The \c cartesian_produce_view_can_size_ concept
0091     template(typename IsConst, typename... Views)(
0092     concept (cartesian_produce_view_can_size_)(IsConst, Views...),
0093         and_v<common_with<std::uintmax_t, range_size_t<meta::const_if<IsConst, Views>>>...>
0094     );
0095     /// \concept cartesian_produce_view_can_size
0096     /// \brief The \c cartesian_produce_view_can_size concept
0097     template<typename IsConst, typename...Views>
0098     CPP_concept cartesian_produce_view_can_size =
0099         and_v<sized_range<meta::const_if<IsConst, Views>>...> &&
0100         CPP_concept_ref(ranges::cartesian_produce_view_can_size_, IsConst, Views...);
0101
0102     /// \concept cartesian_produce_view_can_distance_
0103     /// \brief The \c cartesian_produce_view_can_distance_ concept
0104     template(typename IsConst, typename... Views)(
0105     concept (cartesian_produce_view_can_distance_)(IsConst, Views...),
0106         and_v<sized_sentinel_for<
0107             iterator_t<meta::const_if<IsConst, Views>>,
0108             iterator_t<meta::const_if<IsConst, Views>>>...>
0109     );
0110     /// \concept cartesian_produce_view_can_distance
0111     /// \brief The \c cartesian_produce_view_can_distance concept
0112     template<typename IsConst, typename...Views>
0113     CPP_concept cartesian_produce_view_can_distance =
0114         cartesian_produce_view_can_size<IsConst, Views...> &&
0115         CPP_concept_ref(ranges::cartesian_produce_view_can_distance_, IsConst, Views...);
0116
0117     /// \concept cartesian_produce_view_can_random_
0118     /// \brief The \c cartesian_produce_view_can_random_ concept
0119     template(typename IsConst, typename... Views)(
0120     concept (cartesian_produce_view_can_random_)(IsConst, Views...),
0121         and_v<random_access_iterator<iterator_t<meta::const_if<IsConst, Views>>>...>
0122     );
0123     /// \concept cartesian_produce_view_can_random
0124     /// \brief The \c cartesian_produce_view_can_random concept
0125     template<typename IsConst, typename...Views>
0126     CPP_concept cartesian_produce_view_can_random =
0127         cartesian_produce_view_can_distance<IsConst, Views...> &&
0128         CPP_concept_ref(ranges::cartesian_produce_view_can_random_, IsConst, Views...);
0129
0130     /// \concept cartesian_produce_view_can_bidi_
0131     /// \brief The \c cartesian_produce_view_can_bidi_ concept
0132     template(typename IsConst, typename... Views)(
0133     concept (cartesian_produce_view_can_bidi_)(IsConst, Views...),
0134         and_v<common_range<meta::const_if<IsConst, Views>>...,
0135             bidirectional_iterator<iterator_t<meta::const_if<IsConst, Views>>>...>
0136     );
0137     /// \concept cartesian_produce_view_can_bidi
0138     /// \brief The \c cartesian_produce_view_can_bidi concept
0139     template<typename IsConst, typename...Views>
0140     CPP_concept cartesian_produce_view_can_bidi =
0141         cartesian_produce_view_can_random<IsConst, Views...> ||
0142         CPP_concept_ref(ranges::cartesian_produce_view_can_bidi_, IsConst, Views...);
0143     // clang-format on
0144
0145     template<typename... Views>
0146     struct cartesian_product_view
0147       : view_facade<cartesian_product_view<Views...>,
0148                     detail::cartesian_product_cardinality<Views...>::value>
0149     {
0150     private:
0151         friend range_access;
0152         CPP_assert(and_v<(forward_range<Views> && view_<Views>)...>);
0153         CPP_assert(sizeof...(Views) != 0);
0154
0155         static constexpr auto my_cardinality =
0156             detail::cartesian_product_cardinality<Views...>::value;
0157
0158         std::tuple<Views...> views_;
0159
0160         template<bool IsConst_>
0161         struct cursor
0162         {
0163         private:
0164             using IsConst = meta::bool_<IsConst_>;
0165             friend cursor<true>;
0166             template<typename T>
0167             using constify_if = meta::const_if_c<IsConst_, T>;
0168             using difference_type =
0169                 common_type_t<std::intmax_t, range_difference_t<Views>...>;
0170
0171             constify_if<cartesian_product_view> * view_;
0172             std::tuple<iterator_t<constify_if<Views>>...> its_;
0173
0174             void next_(meta::size_t<1>)
0175             {
0176                 auto & v = std::get<0>(view_->views_);
0177                 auto & i = std::get<0>(its_);
0178                 auto const last = ranges::end(v);
0179                 RANGES_EXPECT(i != last);
0180                 ++i;
0181             }
0182             template<std::size_t N>
0183             void next_(meta::size_t<N>)
0184             {
0185                 auto & v = std::get<N - 1>(view_->views_);
0186                 auto & i = std::get<N - 1>(its_);
0187                 auto const last = ranges::end(v);
0188                 RANGES_EXPECT(i != last);
0189                 if(++i == last)
0190                 {
0191                     i = ranges::begin(v);
0192                     next_(meta::size_t<N - 1>{});
0193                 }
0194             }
0195             void prev_(meta::size_t<0>)
0196             {
0197                 RANGES_EXPECT(false);
0198             }
0199             template<std::size_t N>
0200             void prev_(meta::size_t<N>)
0201             {
0202                 auto & v = std::get<N - 1>(view_->views_);
0203                 auto & i = std::get<N - 1>(its_);
0204                 if(i == ranges::begin(v))
0205                 {
0206                     CPP_assert(cartesian_produce_view_can_bidi<IsConst, Views...>);
0207                     // cartesian_produce_view_can_bidi<IsConst, Views...> implies this
0208                     // advance call is O(1)
0209                     ranges::advance(i, ranges::end(v));
0210                     prev_(meta::size_t<N - 1>{});
0211                 }
0212                 --i;
0213             }
0214             bool equal_(cursor const &, meta::size_t<0>) const
0215             {
0216                 return true;
0217             }
0218             template<std::size_t N>
0219             bool equal_(cursor const & that, meta::size_t<N>) const
0220             {
0221                 return std::get<N - 1>(its_) == std::get<N - 1>(that.its_) &&
0222                        equal_(that, meta::size_t<N - 1>{});
0223             }
0224             difference_type distance_(cursor const & that, meta::size_t<1>) const
0225             {
0226                 return difference_type{std::get<0>(that.its_) - std::get<0>(its_)};
0227             }
0228             template<std::size_t N>
0229             difference_type distance_(cursor const & that, meta::size_t<N>) const
0230             {
0231                 difference_type const d = distance_(that, meta::size_t<N - 1>{});
0232                 auto const scale = ranges::distance(std::get<N - 1>(view_->views_));
0233                 auto const increment = std::get<N - 1>(that.its_) - std::get<N - 1>(its_);
0234                 return difference_type{d * scale + increment};
0235             }
0236             void advance_(meta::size_t<0>, difference_type)
0237             {
0238                 RANGES_EXPECT(false);
0239             }
0240             RANGES_DIAGNOSTIC_PUSH
0241             RANGES_DIAGNOSTIC_IGNORE_DIVIDE_BY_ZERO
0242             template<std::size_t N>
0243             void advance_(meta::size_t<N>, difference_type n)
0244             {
0245                 if(n == 0)
0246                     return;
0247
0248                 auto & i = std::get<N - 1>(its_);
0249                 auto const my_size = static_cast<difference_type>(
0250                     ranges::size(std::get<N - 1>(view_->views_)));
0251                 auto const first = ranges::begin(std::get<N - 1>(view_->views_));
0252
0253                 auto const idx = static_cast<difference_type>(i - first);
0254                 RANGES_EXPECT(0 <= idx);
0255                 RANGES_EXPECT(idx < my_size || (N == 1 && idx == my_size && n < 0));
0256                 RANGES_EXPECT(n < INTMAX_MAX - idx);
0257                 n += idx;
0258
0259                 auto n_div = n / my_size;
0260                 auto n_mod = n % my_size;
0261
0262                 if(RANGES_CONSTEXPR_IF(N != 1))
0263                 {
0264                     if(n_mod < 0)
0265                     {
0266                         n_mod += my_size;
0267                         --n_div;
0268                     }
0269                     advance_(meta::size_t<N - 1>{}, n_div);
0270                 }
0271                 RANGES_EXPECT(0 <= n_mod && n_mod < my_size);
0272
0273                 if(RANGES_CONSTEXPR_IF(N == 1))
0274                 {
0275                     if(n_div > 0)
0276                     {
0277                         RANGES_EXPECT(n_div == 1);
0278                         RANGES_EXPECT(n_mod == 0);
0279                         n_mod = my_size;
0280                     }
0281                     else if(n_div < 0)
0282                     {
0283                         RANGES_EXPECT(n_div == -1);
0284                         RANGES_EXPECT(n_mod == 0);
0285                     }
0286                 }
0287
0288                 using D = iter_difference_t<decltype(first)>;
0289                 i = first + static_cast<D>(n_mod);
0290             }
0291             RANGES_DIAGNOSTIC_POP
0292             void check_at_end_(meta::size_t<1>, bool at_end = false)
0293             {
0294                 if(at_end)
0295                     ranges::advance(std::get<0>(its_),
0296                                     ranges::end(std::get<0>(view_->views_)));
0297             }
0298             template<std::size_t N>
0299             void check_at_end_(meta::size_t<N>, bool at_end = false)
0300             {
0301                 return check_at_end_(
0302                     meta::size_t<N - 1>{},
0303                     at_end || bool(std::get<N - 1>(its_) ==
0304                                    ranges::end(std::get<N - 1>(view_->views_))));
0305             }
0306             cursor(end_tag, constify_if<cartesian_product_view> * view,
0307                    std::true_type) // common_with
0308               : cursor(begin_tag{}, view)
0309             {
0310                 CPP_assert(
0311                     common_range<meta::at_c<meta::list<constify_if<Views>...>, 0>>);
0312                 std::get<0>(its_) = ranges::end(std::get<0>(view->views_));
0313             }
0314             cursor(end_tag, constify_if<cartesian_product_view> * view,
0315                    std::false_type) // !common_with
0316               : cursor(begin_tag{}, view)
0317             {
0318                 using View0 = meta::at_c<meta::list<constify_if<Views>...>, 0>;
0319                 CPP_assert(!common_range<View0> && random_access_range<View0> &&
0320                            sized_range<View0>);
0321                 std::get<0>(its_) += ranges::distance(std::get<0>(view->views_));
0322             }
0323
0324         public:
0325             using value_type = std::tuple<range_value_t<Views>...>;
0326
0327             cursor() = default;
0328             explicit cursor(begin_tag, constify_if<cartesian_product_view> * view)
0329               : view_(view)
0330               , its_(tuple_transform(view->views_, ranges::begin))
0331             {
0332                 // If any of the constituent views is empty, the cartesian_product is
0333                 // empty and this "begin" iterator needs to become an "end" iterator.
0334                 check_at_end_(meta::size_t<sizeof...(Views)>{});
0335             }
0336             explicit cursor(end_tag, constify_if<cartesian_product_view> * view)
0337               : cursor(
0338                     end_tag{}, view,
0339                     meta::bool_<
0340                         common_range<meta::at_c<meta::list<constify_if<Views>...>, 0>>>{})
0341             {}
0342             template(bool Other)(
0343                 requires IsConst_ AND CPP_NOT(Other)) //
0344             cursor(cursor<Other> that)
0345               : view_(that.view_)
0346               , its_(std::move(that.its_))
0347             {}
0348             common_tuple<range_reference_t<constify_if<Views>>...> read() const
0349             {
0350                 return tuple_transform(its_, detail::dereference_fn{});
0351             }
0352             void next()
0353             {
0354                 next_(meta::size_t<sizeof...(Views)>{});
0355             }
0356             bool equal(default_sentinel_t) const
0357             {
0358                 return std::get<0>(its_) == ranges::end(std::get<0>(view_->views_));
0359             }
0360             bool equal(cursor const & that) const
0361             {
0362                 return equal_(that, meta::size_t<sizeof...(Views)>{});
0363             }
0364             CPP_member
0365             auto prev() -> CPP_ret(void)(
0366                 requires cartesian_produce_view_can_bidi<IsConst, Views...>)
0367             {
0368                 prev_(meta::size_t<sizeof...(Views)>{});
0369             }
0370             CPP_auto_member
0371             auto CPP_fun(distance_to)(cursor const & that)(
0372                 const requires cartesian_produce_view_can_distance<IsConst, Views...>)
0373             {
0374                 return distance_(that, meta::size_t<sizeof...(Views)>{});
0375             }
0376             CPP_member
0377             auto advance(difference_type n) //
0378                 -> CPP_ret(void)(
0379                     requires cartesian_produce_view_can_random<IsConst, Views...>)
0380             {
0381                 advance_(meta::size_t<sizeof...(Views)>{}, n);
0382             }
0383         };
0384         cursor<false> begin_cursor()
0385         {
0386             return cursor<false>{begin_tag{}, this};
0387         }
0388         CPP_member
0389         auto begin_cursor() const //
0390             -> CPP_ret(cursor<true>)(
0391                 requires cartesian_produce_view_can_const<Views...>)
0392         {
0393             return cursor<true>{begin_tag{}, this};
0394         }
0395         CPP_member
0396         auto end_cursor() //
0397             -> CPP_ret(cursor<false>)(
0398                 requires cartesian_produce_view_can_bidi<std::false_type, Views...>)
0399         {
0400             return cursor<false>{end_tag{}, this};
0401         }
0402         CPP_member
0403         auto end_cursor() const //
0404             -> CPP_ret(cursor<true>)(
0405                 requires cartesian_produce_view_can_bidi<std::true_type, Views...>)
0406         {
0407             return cursor<true>{end_tag{}, this};
0408         }
0409         CPP_member
0410         auto end_cursor() const //
0411             -> CPP_ret(default_sentinel_t)(
0412                 requires (!cartesian_produce_view_can_bidi<std::true_type, Views...>))
0413         {
0414             return {};
0415         }
0416
0417     public:
0418         cartesian_product_view() = default;
0419         constexpr explicit cartesian_product_view(Views... views)
0420           : views_{detail::move(views)...}
0421         {}
0422         template(typename...)(
0423             requires (my_cardinality >= 0)) //
0424         static constexpr std::size_t size() noexcept
0425         {
0426             return std::size_t{my_cardinality};
0427         }
0428         CPP_auto_member
0429         auto CPP_fun(size)()(const //
0430             requires (my_cardinality < 0) &&
0431                 cartesian_produce_view_can_size<std::true_type, Views...>)
0432         {
0433             return tuple_foldl(views_, std::uintmax_t{1}, detail::cartesian_size_fn{});
0434         }
0435         CPP_auto_member
0436         auto CPP_fun(size)()(
0437             requires (my_cardinality < 0) &&
0438                 cartesian_produce_view_can_size<std::false_type, Views...>)
0439         {
0440             return tuple_foldl(views_, std::uintmax_t{1}, detail::cartesian_size_fn{});
0441         }
0442     };
0443
0444 #if RANGES_CXX_DEDUCTION_GUIDES >= RANGES_CXX_DEDUCTION_GUIDES_17
0445     template<typename... Rng>
0446     cartesian_product_view(Rng &&...) //
0447         -> cartesian_product_view<views::all_t<Rng>...>;
0448 #endif
0449
0450     namespace views
0451     {
0452         struct cartesian_product_fn
0453         {
0454             constexpr empty_view<std::tuple<>> operator()() const noexcept
0455             {
0456                 return {};
0457             }
0458             template(typename... Rngs)(
0459                 requires (sizeof...(Rngs) != 0) AND
0460                 concepts::and_v<(forward_range<Rngs> && viewable_range<Rngs>)...>)
0461             constexpr cartesian_product_view<all_t<Rngs>...> operator()(Rngs &&... rngs)
0462                 const
0463             {
0464                 return cartesian_product_view<all_t<Rngs>...>{
0465                     all(static_cast<Rngs &&>(rngs))...};
0466             }
0467 #if defined(_MSC_VER)
0468             template(typename Rng0)(
0469                 requires forward_range<Rng0> AND viewable_range<Rng0>)
0470             constexpr cartesian_product_view<all_t<Rng0>> operator()(Rng0 && rng0) const
0471             {
0472                 return cartesian_product_view<all_t<Rng0>>{
0473                     all(static_cast<Rng0 &&>(rng0))};
0474             }
0475             template(typename Rng0, typename Rng1)(
0476                 requires forward_range<Rng0> AND viewable_range<Rng0> AND
0477                              forward_range<Rng1> AND viewable_range<Rng1>)
0478             constexpr cartesian_product_view<all_t<Rng0>, all_t<Rng1>> //
0479             operator()(Rng0 && rng0, Rng1 && rng1) const
0480             {
0481                 return cartesian_product_view<all_t<Rng0>, all_t<Rng1>>{
0482                     all(static_cast<Rng0 &&>(rng0)), //
0483                     all(static_cast<Rng1 &&>(rng1))};
0484             }
0485             template(typename Rng0, typename Rng1, typename Rng2)(
0486                 requires forward_range<Rng0> AND viewable_range<Rng0> AND
0487                     forward_range<Rng1> AND viewable_range<Rng1> AND
0488                     forward_range<Rng2> AND viewable_range<Rng2>)
0489             constexpr cartesian_product_view<all_t<Rng0>, all_t<Rng1>, all_t<Rng2>> //
0490             operator()(Rng0 && rng0, Rng1 && rng1, Rng2 && rng2) const
0491             {
0492                 return cartesian_product_view<all_t<Rng0>, all_t<Rng1>, all_t<Rng2>>{
0493                     all(static_cast<Rng0 &&>(rng0)), //
0494                     all(static_cast<Rng1 &&>(rng1)), //
0495                     all(static_cast<Rng2 &&>(rng2))};
0496             }
0497 #endif
0498         };
0499
0500         RANGES_INLINE_VARIABLE(cartesian_product_fn, cartesian_product)
0501     } // namespace views
0502
0503     /// @}
0504 } // namespace ranges
0505
0506 #include <range/v3/detail/epilogue.hpp>
0507
0508 #endif