/// \file // Range v3 library // // Copyright Eric Niebler 2013-2014. // Copyright Casey Carter 2017. // // Use, modification and distribution is subject to the // Boost Software License, Version 1.0. (See accompanying // file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) // // Project home: https://github.com/ericniebler/range-v3 // #ifndef RANGES_V3_VIEW_CARTESIAN_PRODUCT_HPP #define RANGES_V3_VIEW_CARTESIAN_PRODUCT_HPP #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include // for dereference_fn #include namespace ranges { /// \cond namespace detail { template using product_cardinality = std::integral_constant< cardinality, State::value == 0 || Value::value == 0 ? static_cast(0) : State::value == unknown || Value::value == unknown ? unknown : State::value == infinite || Value::value == infinite ? infinite : State::value == finite || Value::value == finite ? finite : static_cast( State::value * Value::value)>; struct cartesian_size_fn { template(typename Size, typename Rng)( /// \pre requires integer_like_ AND sized_range AND common_with>) common_type_t> operator()(Size s, Rng && rng) const { using S = common_type_t>; return static_cast(s) * static_cast(ranges::size(rng)); } }; template using cartesian_product_cardinality = meta::fold...>, std::integral_constant( (sizeof...(Views) > 0))>, meta::quote>; } // namespace detail /// \endcond /// \addtogroup group-views /// @{ // clang-format off template CPP_concept cartesian_produce_view_can_const = and_v...>; template(typename IsConst, typename... Views)( concept (cartesian_produce_view_can_size_)(IsConst, Views...), and_v>>...> ); template CPP_concept cartesian_produce_view_can_size = and_v>...> && CPP_concept_ref(ranges::cartesian_produce_view_can_size_, IsConst, Views...); template(typename IsConst, typename... Views)( concept (cartesian_produce_view_can_distance_)(IsConst, Views...), and_v>, iterator_t>>...> ); template CPP_concept cartesian_produce_view_can_distance = cartesian_produce_view_can_size && CPP_concept_ref(ranges::cartesian_produce_view_can_distance_, IsConst, Views...); template(typename IsConst, typename... Views)( concept (cartesian_produce_view_can_random_)(IsConst, Views...), and_v>>...> ); template CPP_concept cartesian_produce_view_can_random = cartesian_produce_view_can_distance && CPP_concept_ref(ranges::cartesian_produce_view_can_random_, IsConst, Views...); template(typename IsConst, typename... Views)( concept (cartesian_produce_view_can_bidi_)(IsConst, Views...), and_v>..., bidirectional_iterator>>...> ); template CPP_concept cartesian_produce_view_can_bidi = cartesian_produce_view_can_random || CPP_concept_ref(ranges::cartesian_produce_view_can_bidi_, IsConst, Views...); // clang-format on template struct cartesian_product_view : view_facade, detail::cartesian_product_cardinality::value> { private: friend range_access; CPP_assert(and_v<(forward_range && view_)...>); CPP_assert(sizeof...(Views) != 0); static constexpr auto my_cardinality = detail::cartesian_product_cardinality::value; std::tuple views_; template struct cursor { private: using IsConst = meta::bool_; friend cursor; template using constify_if = meta::const_if_c; using difference_type = common_type_t...>; constify_if * view_; std::tuple>...> its_; void next_(meta::size_t<1>) { auto & v = std::get<0>(view_->views_); auto & i = std::get<0>(its_); auto const last = ranges::end(v); RANGES_EXPECT(i != last); ++i; } template void next_(meta::size_t) { auto & v = std::get(view_->views_); auto & i = std::get(its_); auto const last = ranges::end(v); RANGES_EXPECT(i != last); if(++i == last) { i = ranges::begin(v); next_(meta::size_t{}); } } void prev_(meta::size_t<0>) { RANGES_EXPECT(false); } template void prev_(meta::size_t) { auto & v = std::get(view_->views_); auto & i = std::get(its_); if(i == ranges::begin(v)) { CPP_assert(cartesian_produce_view_can_bidi); // cartesian_produce_view_can_bidi implies this // advance call is O(1) ranges::advance(i, ranges::end(v)); prev_(meta::size_t{}); } --i; } bool equal_(cursor const &, meta::size_t<0>) const { return true; } template bool equal_(cursor const & that, meta::size_t) const { return std::get(its_) == std::get(that.its_) && equal_(that, meta::size_t{}); } difference_type distance_(cursor const & that, meta::size_t<1>) const { return difference_type{std::get<0>(that.its_) - std::get<0>(its_)}; } template difference_type distance_(cursor const & that, meta::size_t) const { difference_type const d = distance_(that, meta::size_t{}); auto const scale = ranges::distance(std::get(view_->views_)); auto const increment = std::get(that.its_) - std::get(its_); return difference_type{d * scale + increment}; } void advance_(meta::size_t<0>, difference_type) { RANGES_EXPECT(false); } RANGES_DIAGNOSTIC_PUSH RANGES_DIAGNOSTIC_IGNORE_DIVIDE_BY_ZERO template void advance_(meta::size_t, difference_type n) { if(n == 0) return; auto & i = std::get(its_); auto const my_size = static_cast( ranges::size(std::get(view_->views_))); auto const first = ranges::begin(std::get(view_->views_)); auto const idx = static_cast(i - first); RANGES_EXPECT(0 <= idx); RANGES_EXPECT(idx < my_size || (N == 1 && idx == my_size && n < 0)); RANGES_EXPECT(n < INTMAX_MAX - idx); n += idx; auto n_div = n / my_size; auto n_mod = n % my_size; if(RANGES_CONSTEXPR_IF(N != 1)) { if(n_mod < 0) { n_mod += my_size; --n_div; } advance_(meta::size_t{}, n_div); } RANGES_EXPECT(0 <= n_mod && n_mod < my_size); if(RANGES_CONSTEXPR_IF(N == 1)) { if(n_div > 0) { RANGES_EXPECT(n_div == 1); RANGES_EXPECT(n_mod == 0); n_mod = my_size; } else if(n_div < 0) { RANGES_EXPECT(n_div == -1); RANGES_EXPECT(n_mod == 0); } } using D = iter_difference_t; i = first + static_cast(n_mod); } RANGES_DIAGNOSTIC_POP void check_at_end_(meta::size_t<1>, bool at_end = false) { if(at_end) ranges::advance(std::get<0>(its_), ranges::end(std::get<0>(view_->views_))); } template void check_at_end_(meta::size_t, bool at_end = false) { return check_at_end_( meta::size_t{}, at_end || bool(std::get(its_) == ranges::end(std::get(view_->views_)))); } cursor(end_tag, constify_if * view, std::true_type) // common_with : cursor(begin_tag{}, view) { CPP_assert( common_range...>, 0>>); std::get<0>(its_) = ranges::end(std::get<0>(view->views_)); } cursor(end_tag, constify_if * view, std::false_type) // !common_with : cursor(begin_tag{}, view) { using View0 = meta::at_c...>, 0>; CPP_assert(!common_range && random_access_range && sized_range); std::get<0>(its_) += ranges::distance(std::get<0>(view->views_)); } public: using value_type = std::tuple...>; cursor() = default; explicit cursor(begin_tag, constify_if * view) : view_(view) , its_(tuple_transform(view->views_, ranges::begin)) { // If any of the constituent views is empty, the cartesian_product is // empty and this "begin" iterator needs to become an "end" iterator. check_at_end_(meta::size_t{}); } explicit cursor(end_tag, constify_if * view) : cursor( end_tag{}, view, meta::bool_< common_range...>, 0>>>{}) {} template(bool Other)( /// \pre requires IsConst_ AND CPP_NOT(Other)) // cursor(cursor that) : view_(that.view_) , its_(std::move(that.its_)) {} common_tuple>...> read() const { return tuple_transform(its_, detail::dereference_fn{}); } void next() { next_(meta::size_t{}); } bool equal(default_sentinel_t) const { return std::get<0>(its_) == ranges::end(std::get<0>(view_->views_)); } bool equal(cursor const & that) const { return equal_(that, meta::size_t{}); } CPP_member auto prev() -> CPP_ret(void)( /// \pre requires cartesian_produce_view_can_bidi) { prev_(meta::size_t{}); } CPP_auto_member auto CPP_fun(distance_to)(cursor const & that)( const requires cartesian_produce_view_can_distance) { return distance_(that, meta::size_t{}); } CPP_member auto advance(difference_type n) // -> CPP_ret(void)( /// \pre requires cartesian_produce_view_can_random) { advance_(meta::size_t{}, n); } }; cursor begin_cursor() { return cursor{begin_tag{}, this}; } CPP_member auto begin_cursor() const // -> CPP_ret(cursor)( /// \pre requires cartesian_produce_view_can_const) { return cursor{begin_tag{}, this}; } CPP_member auto end_cursor() // -> CPP_ret(cursor)( /// \pre requires cartesian_produce_view_can_bidi) { return cursor{end_tag{}, this}; } CPP_member auto end_cursor() const // -> CPP_ret(cursor)( /// \pre requires cartesian_produce_view_can_bidi) { return cursor{end_tag{}, this}; } CPP_member auto end_cursor() const // -> CPP_ret(default_sentinel_t)( /// \pre requires (!cartesian_produce_view_can_bidi)) { return {}; } public: cartesian_product_view() = default; constexpr explicit cartesian_product_view(Views... views) : views_{detail::move(views)...} {} template(typename...)( /// \pre requires (my_cardinality >= 0)) // static constexpr std::size_t size() noexcept { return std::size_t{my_cardinality}; } CPP_auto_member auto CPP_fun(size)()(const // requires (my_cardinality < 0) && cartesian_produce_view_can_size) { return tuple_foldl(views_, std::uintmax_t{1}, detail::cartesian_size_fn{}); } CPP_auto_member auto CPP_fun(size)()( /// \pre requires (my_cardinality < 0) && cartesian_produce_view_can_size) { return tuple_foldl(views_, std::uintmax_t{1}, detail::cartesian_size_fn{}); } }; #if RANGES_CXX_DEDUCTION_GUIDES >= RANGES_CXX_DEDUCTION_GUIDES_17 template cartesian_product_view(Rng &&...) // -> cartesian_product_view...>; #endif namespace views { struct cartesian_product_fn { constexpr empty_view> operator()() const noexcept { return {}; } template(typename... Rngs)( /// \pre requires (sizeof...(Rngs) != 0) AND concepts::and_v<(forward_range && viewable_range)...>) constexpr cartesian_product_view...> operator()(Rngs &&... rngs) const { return cartesian_product_view...>{ all(static_cast(rngs))...}; } #if defined(_MSC_VER) template(typename Rng0)( /// \pre requires forward_range AND viewable_range) constexpr cartesian_product_view> operator()(Rng0 && rng0) const { return cartesian_product_view>{ all(static_cast(rng0))}; } template(typename Rng0, typename Rng1)( /// \pre requires forward_range AND viewable_range AND forward_range AND viewable_range) constexpr cartesian_product_view, all_t> // operator()(Rng0 && rng0, Rng1 && rng1) const { return cartesian_product_view, all_t>{ all(static_cast(rng0)), // all(static_cast(rng1))}; } template(typename Rng0, typename Rng1, typename Rng2)( /// \pre requires forward_range AND viewable_range AND forward_range AND viewable_range AND forward_range AND viewable_range) constexpr cartesian_product_view, all_t, all_t> // operator()(Rng0 && rng0, Rng1 && rng1, Rng2 && rng2) const { return cartesian_product_view, all_t, all_t>{ all(static_cast(rng0)), // all(static_cast(rng1)), // all(static_cast(rng2))}; } #endif }; RANGES_INLINE_VARIABLE(cartesian_product_fn, cartesian_product) } // namespace views /// @} } // namespace ranges #include #endif