505 lines
19 KiB
C++
505 lines
19 KiB
C++
/// \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 <cstdint>
|
|
|
|
#include <concepts/concepts.hpp>
|
|
|
|
#include <range/v3/range_fwd.hpp>
|
|
|
|
#include <range/v3/iterator/default_sentinel.hpp>
|
|
#include <range/v3/iterator/operations.hpp>
|
|
#include <range/v3/range/access.hpp>
|
|
#include <range/v3/range/concepts.hpp>
|
|
#include <range/v3/range/primitives.hpp>
|
|
#include <range/v3/range/traits.hpp>
|
|
#include <range/v3/utility/static_const.hpp>
|
|
#include <range/v3/utility/tuple_algorithm.hpp>
|
|
#include <range/v3/view/all.hpp>
|
|
#include <range/v3/view/empty.hpp>
|
|
#include <range/v3/view/facade.hpp>
|
|
#include <range/v3/view/view.hpp> // for dereference_fn
|
|
|
|
#include <range/v3/detail/prologue.hpp>
|
|
|
|
namespace ranges
|
|
{
|
|
/// \cond
|
|
namespace detail
|
|
{
|
|
template<typename State, typename Value>
|
|
using product_cardinality = std::integral_constant<
|
|
cardinality,
|
|
State::value == 0 || Value::value == 0
|
|
? static_cast<cardinality>(0)
|
|
: State::value == unknown || Value::value == unknown
|
|
? unknown
|
|
: State::value == infinite || Value::value == infinite
|
|
? infinite
|
|
: State::value == finite || Value::value == finite
|
|
? finite
|
|
: static_cast<cardinality>(
|
|
State::value * Value::value)>;
|
|
|
|
struct cartesian_size_fn
|
|
{
|
|
template(typename Size, typename Rng)(
|
|
/// \pre
|
|
requires integer_like_<Size> AND sized_range<Rng> AND
|
|
common_with<Size, range_size_t<Rng>>)
|
|
common_type_t<Size, range_size_t<Rng>> operator()(Size s, Rng && rng) const
|
|
{
|
|
using S = common_type_t<Size, range_size_t<Rng>>;
|
|
return static_cast<S>(s) * static_cast<S>(ranges::size(rng));
|
|
}
|
|
};
|
|
|
|
template<typename... Views>
|
|
using cartesian_product_cardinality =
|
|
meta::fold<meta::list<range_cardinality<Views>...>,
|
|
std::integral_constant<cardinality, static_cast<cardinality>(
|
|
(sizeof...(Views) > 0))>,
|
|
meta::quote<detail::product_cardinality>>;
|
|
} // namespace detail
|
|
/// \endcond
|
|
|
|
/// \addtogroup group-views
|
|
/// @{
|
|
|
|
// clang-format off
|
|
template<typename...Views>
|
|
CPP_concept cartesian_produce_view_can_const =
|
|
and_v<range<Views const>...>;
|
|
|
|
template(typename IsConst, typename... Views)(
|
|
concept (cartesian_produce_view_can_size_)(IsConst, Views...),
|
|
and_v<common_with<std::uintmax_t, range_size_t<meta::const_if<IsConst, Views>>>...>
|
|
);
|
|
template<typename IsConst, typename...Views>
|
|
CPP_concept cartesian_produce_view_can_size =
|
|
and_v<sized_range<meta::const_if<IsConst, Views>>...> &&
|
|
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<sized_sentinel_for<
|
|
iterator_t<meta::const_if<IsConst, Views>>,
|
|
iterator_t<meta::const_if<IsConst, Views>>>...>
|
|
);
|
|
template<typename IsConst, typename...Views>
|
|
CPP_concept cartesian_produce_view_can_distance =
|
|
cartesian_produce_view_can_size<IsConst, Views...> &&
|
|
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<random_access_iterator<iterator_t<meta::const_if<IsConst, Views>>>...>
|
|
);
|
|
template<typename IsConst, typename...Views>
|
|
CPP_concept cartesian_produce_view_can_random =
|
|
cartesian_produce_view_can_distance<IsConst, Views...> &&
|
|
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<common_range<meta::const_if<IsConst, Views>>...,
|
|
bidirectional_iterator<iterator_t<meta::const_if<IsConst, Views>>>...>
|
|
);
|
|
template<typename IsConst, typename...Views>
|
|
CPP_concept cartesian_produce_view_can_bidi =
|
|
cartesian_produce_view_can_random<IsConst, Views...> ||
|
|
CPP_concept_ref(ranges::cartesian_produce_view_can_bidi_, IsConst, Views...);
|
|
// clang-format on
|
|
|
|
template<typename... Views>
|
|
struct cartesian_product_view
|
|
: view_facade<cartesian_product_view<Views...>,
|
|
detail::cartesian_product_cardinality<Views...>::value>
|
|
{
|
|
private:
|
|
friend range_access;
|
|
CPP_assert(and_v<(forward_range<Views> && view_<Views>)...>);
|
|
CPP_assert(sizeof...(Views) != 0);
|
|
|
|
static constexpr auto my_cardinality =
|
|
detail::cartesian_product_cardinality<Views...>::value;
|
|
|
|
std::tuple<Views...> views_;
|
|
|
|
template<bool IsConst_>
|
|
struct cursor
|
|
{
|
|
private:
|
|
using IsConst = meta::bool_<IsConst_>;
|
|
friend cursor<true>;
|
|
template<typename T>
|
|
using constify_if = meta::const_if_c<IsConst_, T>;
|
|
using difference_type =
|
|
common_type_t<std::intmax_t, range_difference_t<Views>...>;
|
|
|
|
constify_if<cartesian_product_view> * view_;
|
|
std::tuple<iterator_t<constify_if<Views>>...> 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<std::size_t N>
|
|
void next_(meta::size_t<N>)
|
|
{
|
|
auto & v = std::get<N - 1>(view_->views_);
|
|
auto & i = std::get<N - 1>(its_);
|
|
auto const last = ranges::end(v);
|
|
RANGES_EXPECT(i != last);
|
|
if(++i == last)
|
|
{
|
|
i = ranges::begin(v);
|
|
next_(meta::size_t<N - 1>{});
|
|
}
|
|
}
|
|
void prev_(meta::size_t<0>)
|
|
{
|
|
RANGES_EXPECT(false);
|
|
}
|
|
template<std::size_t N>
|
|
void prev_(meta::size_t<N>)
|
|
{
|
|
auto & v = std::get<N - 1>(view_->views_);
|
|
auto & i = std::get<N - 1>(its_);
|
|
if(i == ranges::begin(v))
|
|
{
|
|
CPP_assert(cartesian_produce_view_can_bidi<IsConst, Views...>);
|
|
// cartesian_produce_view_can_bidi<IsConst, Views...> implies this
|
|
// advance call is O(1)
|
|
ranges::advance(i, ranges::end(v));
|
|
prev_(meta::size_t<N - 1>{});
|
|
}
|
|
--i;
|
|
}
|
|
bool equal_(cursor const &, meta::size_t<0>) const
|
|
{
|
|
return true;
|
|
}
|
|
template<std::size_t N>
|
|
bool equal_(cursor const & that, meta::size_t<N>) const
|
|
{
|
|
return std::get<N - 1>(its_) == std::get<N - 1>(that.its_) &&
|
|
equal_(that, meta::size_t<N - 1>{});
|
|
}
|
|
difference_type distance_(cursor const & that, meta::size_t<1>) const
|
|
{
|
|
return difference_type{std::get<0>(that.its_) - std::get<0>(its_)};
|
|
}
|
|
template<std::size_t N>
|
|
difference_type distance_(cursor const & that, meta::size_t<N>) const
|
|
{
|
|
difference_type const d = distance_(that, meta::size_t<N - 1>{});
|
|
auto const scale = ranges::distance(std::get<N - 1>(view_->views_));
|
|
auto const increment = std::get<N - 1>(that.its_) - std::get<N - 1>(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<std::size_t N>
|
|
void advance_(meta::size_t<N>, difference_type n)
|
|
{
|
|
if(n == 0)
|
|
return;
|
|
|
|
auto & i = std::get<N - 1>(its_);
|
|
auto const my_size = static_cast<difference_type>(
|
|
ranges::size(std::get<N - 1>(view_->views_)));
|
|
auto const first = ranges::begin(std::get<N - 1>(view_->views_));
|
|
|
|
auto const idx = static_cast<difference_type>(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 - 1>{}, 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<decltype(first)>;
|
|
i = first + static_cast<D>(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<std::size_t N>
|
|
void check_at_end_(meta::size_t<N>, bool at_end = false)
|
|
{
|
|
return check_at_end_(
|
|
meta::size_t<N - 1>{},
|
|
at_end || bool(std::get<N - 1>(its_) ==
|
|
ranges::end(std::get<N - 1>(view_->views_))));
|
|
}
|
|
cursor(end_tag, constify_if<cartesian_product_view> * view,
|
|
std::true_type) // common_with
|
|
: cursor(begin_tag{}, view)
|
|
{
|
|
CPP_assert(
|
|
common_range<meta::at_c<meta::list<constify_if<Views>...>, 0>>);
|
|
std::get<0>(its_) = ranges::end(std::get<0>(view->views_));
|
|
}
|
|
cursor(end_tag, constify_if<cartesian_product_view> * view,
|
|
std::false_type) // !common_with
|
|
: cursor(begin_tag{}, view)
|
|
{
|
|
using View0 = meta::at_c<meta::list<constify_if<Views>...>, 0>;
|
|
CPP_assert(!common_range<View0> && random_access_range<View0> &&
|
|
sized_range<View0>);
|
|
std::get<0>(its_) += ranges::distance(std::get<0>(view->views_));
|
|
}
|
|
|
|
public:
|
|
using value_type = std::tuple<range_value_t<Views>...>;
|
|
|
|
cursor() = default;
|
|
explicit cursor(begin_tag, constify_if<cartesian_product_view> * 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<sizeof...(Views)>{});
|
|
}
|
|
explicit cursor(end_tag, constify_if<cartesian_product_view> * view)
|
|
: cursor(
|
|
end_tag{}, view,
|
|
meta::bool_<
|
|
common_range<meta::at_c<meta::list<constify_if<Views>...>, 0>>>{})
|
|
{}
|
|
template(bool Other)(
|
|
/// \pre
|
|
requires IsConst_ AND CPP_NOT(Other)) //
|
|
cursor(cursor<Other> that)
|
|
: view_(that.view_)
|
|
, its_(std::move(that.its_))
|
|
{}
|
|
common_tuple<range_reference_t<constify_if<Views>>...> read() const
|
|
{
|
|
return tuple_transform(its_, detail::dereference_fn{});
|
|
}
|
|
void next()
|
|
{
|
|
next_(meta::size_t<sizeof...(Views)>{});
|
|
}
|
|
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<sizeof...(Views)>{});
|
|
}
|
|
CPP_member
|
|
auto prev() -> CPP_ret(void)(
|
|
/// \pre
|
|
requires cartesian_produce_view_can_bidi<IsConst, Views...>)
|
|
{
|
|
prev_(meta::size_t<sizeof...(Views)>{});
|
|
}
|
|
CPP_auto_member
|
|
auto CPP_fun(distance_to)(cursor const & that)(
|
|
const requires cartesian_produce_view_can_distance<IsConst, Views...>)
|
|
{
|
|
return distance_(that, meta::size_t<sizeof...(Views)>{});
|
|
}
|
|
CPP_member
|
|
auto advance(difference_type n) //
|
|
-> CPP_ret(void)(
|
|
/// \pre
|
|
requires cartesian_produce_view_can_random<IsConst, Views...>)
|
|
{
|
|
advance_(meta::size_t<sizeof...(Views)>{}, n);
|
|
}
|
|
};
|
|
cursor<false> begin_cursor()
|
|
{
|
|
return cursor<false>{begin_tag{}, this};
|
|
}
|
|
CPP_member
|
|
auto begin_cursor() const //
|
|
-> CPP_ret(cursor<true>)(
|
|
/// \pre
|
|
requires cartesian_produce_view_can_const<Views...>)
|
|
{
|
|
return cursor<true>{begin_tag{}, this};
|
|
}
|
|
CPP_member
|
|
auto end_cursor() //
|
|
-> CPP_ret(cursor<false>)(
|
|
/// \pre
|
|
requires cartesian_produce_view_can_bidi<std::false_type, Views...>)
|
|
{
|
|
return cursor<false>{end_tag{}, this};
|
|
}
|
|
CPP_member
|
|
auto end_cursor() const //
|
|
-> CPP_ret(cursor<true>)(
|
|
/// \pre
|
|
requires cartesian_produce_view_can_bidi<std::true_type, Views...>)
|
|
{
|
|
return cursor<true>{end_tag{}, this};
|
|
}
|
|
CPP_member
|
|
auto end_cursor() const //
|
|
-> CPP_ret(default_sentinel_t)(
|
|
/// \pre
|
|
requires (!cartesian_produce_view_can_bidi<std::true_type, Views...>))
|
|
{
|
|
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<std::true_type, Views...>)
|
|
{
|
|
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<std::false_type, Views...>)
|
|
{
|
|
return tuple_foldl(views_, std::uintmax_t{1}, detail::cartesian_size_fn{});
|
|
}
|
|
};
|
|
|
|
#if RANGES_CXX_DEDUCTION_GUIDES >= RANGES_CXX_DEDUCTION_GUIDES_17
|
|
template<typename... Rng>
|
|
cartesian_product_view(Rng &&...) //
|
|
-> cartesian_product_view<views::all_t<Rng>...>;
|
|
#endif
|
|
|
|
namespace views
|
|
{
|
|
struct cartesian_product_fn
|
|
{
|
|
constexpr empty_view<std::tuple<>> operator()() const noexcept
|
|
{
|
|
return {};
|
|
}
|
|
template(typename... Rngs)(
|
|
/// \pre
|
|
requires (sizeof...(Rngs) != 0) AND
|
|
concepts::and_v<(forward_range<Rngs> && viewable_range<Rngs>)...>)
|
|
constexpr cartesian_product_view<all_t<Rngs>...> operator()(Rngs &&... rngs)
|
|
const
|
|
{
|
|
return cartesian_product_view<all_t<Rngs>...>{
|
|
all(static_cast<Rngs &&>(rngs))...};
|
|
}
|
|
#if defined(_MSC_VER)
|
|
template(typename Rng0)(
|
|
/// \pre
|
|
requires forward_range<Rng0> AND viewable_range<Rng0>)
|
|
constexpr cartesian_product_view<all_t<Rng0>> operator()(Rng0 && rng0) const
|
|
{
|
|
return cartesian_product_view<all_t<Rng0>>{
|
|
all(static_cast<Rng0 &&>(rng0))};
|
|
}
|
|
template(typename Rng0, typename Rng1)(
|
|
/// \pre
|
|
requires forward_range<Rng0> AND viewable_range<Rng0> AND
|
|
forward_range<Rng1> AND viewable_range<Rng1>)
|
|
constexpr cartesian_product_view<all_t<Rng0>, all_t<Rng1>> //
|
|
operator()(Rng0 && rng0, Rng1 && rng1) const
|
|
{
|
|
return cartesian_product_view<all_t<Rng0>, all_t<Rng1>>{
|
|
all(static_cast<Rng0 &&>(rng0)), //
|
|
all(static_cast<Rng1 &&>(rng1))};
|
|
}
|
|
template(typename Rng0, typename Rng1, typename Rng2)(
|
|
/// \pre
|
|
requires forward_range<Rng0> AND viewable_range<Rng0> AND
|
|
forward_range<Rng1> AND viewable_range<Rng1> AND
|
|
forward_range<Rng2> AND viewable_range<Rng2>)
|
|
constexpr cartesian_product_view<all_t<Rng0>, all_t<Rng1>, all_t<Rng2>> //
|
|
operator()(Rng0 && rng0, Rng1 && rng1, Rng2 && rng2) const
|
|
{
|
|
return cartesian_product_view<all_t<Rng0>, all_t<Rng1>, all_t<Rng2>>{
|
|
all(static_cast<Rng0 &&>(rng0)), //
|
|
all(static_cast<Rng1 &&>(rng1)), //
|
|
all(static_cast<Rng2 &&>(rng2))};
|
|
}
|
|
#endif
|
|
};
|
|
|
|
RANGES_INLINE_VARIABLE(cartesian_product_fn, cartesian_product)
|
|
} // namespace views
|
|
|
|
/// @}
|
|
} // namespace ranges
|
|
|
|
#include <range/v3/detail/epilogue.hpp>
|
|
|
|
#endif
|