Horizon
cartesian_product.hpp
Go to the documentation of this file.
1 // Range v3 library
3 //
4 // Copyright Eric Niebler 2013-2014.
5 // Copyright Casey Carter 2017.
6 //
7 // Use, modification and distribution is subject to the
8 // Boost Software License, Version 1.0. (See accompanying
9 // file LICENSE_1_0.txt or copy at
10 // http://www.boost.org/LICENSE_1_0.txt)
11 //
12 // Project home: https://github.com/ericniebler/range-v3
13 //
14 
15 #ifndef RANGES_V3_VIEW_CARTESIAN_PRODUCT_HPP
16 #define RANGES_V3_VIEW_CARTESIAN_PRODUCT_HPP
17 
18 #include <cstdint>
19 
20 #include <concepts/concepts.hpp>
21 
22 #include <range/v3/range_fwd.hpp>
23 
30 #include <range/v3/utility/static_const.hpp>
32 #include <range/v3/view/all.hpp>
33 #include <range/v3/view/empty.hpp>
34 #include <range/v3/view/facade.hpp>
35 #include <range/v3/view/view.hpp> // for dereference_fn
36 
37 #include <range/v3/detail/prologue.hpp>
38 
39 namespace ranges
40 {
42  namespace detail
43  {
44  template<typename State, typename Value>
45  using product_cardinality = std::integral_constant<
46  cardinality,
47  State::value == 0 || Value::value == 0
48  ? static_cast<cardinality>(0)
49  : State::value == unknown || Value::value == unknown
50  ? unknown
51  : State::value == infinite || Value::value == infinite
52  ? infinite
53  : State::value == finite || Value::value == finite
54  ? finite
55  : static_cast<cardinality>(
56  State::value * Value::value)>;
57 
58  struct cartesian_size_fn
59  {
60  template(typename Size, typename Rng)(
61  requires integer_like_<Size> AND sized_range<Rng> AND
62  common_with<Size, range_size_t<Rng>>)
63  common_type_t<Size, range_size_t<Rng>> operator()(Size s, Rng && rng) const
64  {
65  using S = common_type_t<Size, range_size_t<Rng>>;
66  return static_cast<S>(s) * static_cast<S>(ranges::size(rng));
67  }
68  };
69 
70  template<typename... Views>
71  using cartesian_product_cardinality =
73  std::integral_constant<cardinality, static_cast<cardinality>(
74  (sizeof...(Views) > 0))>,
76  } // namespace detail
78 
81 
82  // clang-format off
85  template<typename...Views>
87  and_v<range<Views const>...>;
88 
91  template(typename IsConst, typename... Views)(
92  concept (cartesian_produce_view_can_size_)(IsConst, Views...),
93  and_v<common_with<std::uintmax_t, range_size_t<meta::const_if<IsConst, Views>>>...>
94  );
97  template<typename IsConst, typename...Views>
99  and_v<sized_range<meta::const_if<IsConst, Views>>...> &&
100  CPP_concept_ref(ranges::cartesian_produce_view_can_size_, IsConst, Views...);
101 
104  template(typename IsConst, typename... Views)(
105  concept (cartesian_produce_view_can_distance_)(IsConst, Views...),
106  and_v<sized_sentinel_for<
109  );
112  template<typename IsConst, typename...Views>
114  cartesian_produce_view_can_size<IsConst, Views...> &&
115  CPP_concept_ref(ranges::cartesian_produce_view_can_distance_, IsConst, Views...);
116 
119  template(typename IsConst, typename... Views)(
120  concept (cartesian_produce_view_can_random_)(IsConst, Views...),
121  and_v<random_access_iterator<iterator_t<meta::const_if<IsConst, Views>>>...>
122  );
125  template<typename IsConst, typename...Views>
127  cartesian_produce_view_can_distance<IsConst, Views...> &&
128  CPP_concept_ref(ranges::cartesian_produce_view_can_random_, IsConst, Views...);
129 
132  template(typename IsConst, typename... Views)(
133  concept (cartesian_produce_view_can_bidi_)(IsConst, Views...),
134  and_v<common_range<meta::const_if<IsConst, Views>>...,
135  bidirectional_iterator<iterator_t<meta::const_if<IsConst, Views>>>...>
136  );
139  template<typename IsConst, typename...Views>
141  cartesian_produce_view_can_random<IsConst, Views...> ||
142  CPP_concept_ref(ranges::cartesian_produce_view_can_bidi_, IsConst, Views...);
143  // clang-format on
144 
145  template<typename... Views>
147  : view_facade<cartesian_product_view<Views...>,
148  detail::cartesian_product_cardinality<Views...>::value>
149  {
150  private:
151  friend range_access;
152  CPP_assert(and_v<(forward_range<Views> && view_<Views>)...>);
153  CPP_assert(sizeof...(Views) != 0);
154 
155  static constexpr auto my_cardinality =
156  detail::cartesian_product_cardinality<Views...>::value;
157 
158  std::tuple<Views...> views_;
159 
160  template<bool IsConst_>
161  struct cursor
162  {
163  private:
164  using IsConst = meta::bool_<IsConst_>;
165  friend cursor<true>;
166  template<typename T>
167  using constify_if = meta::const_if_c<IsConst_, T>;
168  using difference_type =
169  common_type_t<std::intmax_t, range_difference_t<Views>...>;
170 
171  constify_if<cartesian_product_view> * view_;
172  std::tuple<iterator_t<constify_if<Views>>...> its_;
173 
174  void next_(meta::size_t<1>)
175  {
176  auto & v = std::get<0>(view_->views_);
177  auto & i = std::get<0>(its_);
178  auto const last = ranges::end(v);
179  RANGES_EXPECT(i != last);
180  ++i;
181  }
182  template<std::size_t N>
183  void next_(meta::size_t<N>)
184  {
185  auto & v = std::get<N - 1>(view_->views_);
186  auto & i = std::get<N - 1>(its_);
187  auto const last = ranges::end(v);
188  RANGES_EXPECT(i != last);
189  if(++i == last)
190  {
191  i = ranges::begin(v);
192  next_(meta::size_t<N - 1>{});
193  }
194  }
195  void prev_(meta::size_t<0>)
196  {
197  RANGES_EXPECT(false);
198  }
199  template<std::size_t N>
200  void prev_(meta::size_t<N>)
201  {
202  auto & v = std::get<N - 1>(view_->views_);
203  auto & i = std::get<N - 1>(its_);
204  if(i == ranges::begin(v))
205  {
206  CPP_assert(cartesian_produce_view_can_bidi<IsConst, Views...>);
207  // cartesian_produce_view_can_bidi<IsConst, Views...> implies this
208  // advance call is O(1)
209  ranges::advance(i, ranges::end(v));
210  prev_(meta::size_t<N - 1>{});
211  }
212  --i;
213  }
214  bool equal_(cursor const &, meta::size_t<0>) const
215  {
216  return true;
217  }
218  template<std::size_t N>
219  bool equal_(cursor const & that, meta::size_t<N>) const
220  {
221  return std::get<N - 1>(its_) == std::get<N - 1>(that.its_) &&
222  equal_(that, meta::size_t<N - 1>{});
223  }
224  difference_type distance_(cursor const & that, meta::size_t<1>) const
225  {
226  return difference_type{std::get<0>(that.its_) - std::get<0>(its_)};
227  }
228  template<std::size_t N>
229  difference_type distance_(cursor const & that, meta::size_t<N>) const
230  {
231  difference_type const d = distance_(that, meta::size_t<N - 1>{});
232  auto const scale = ranges::distance(std::get<N - 1>(view_->views_));
233  auto const increment = std::get<N - 1>(that.its_) - std::get<N - 1>(its_);
234  return difference_type{d * scale + increment};
235  }
236  void advance_(meta::size_t<0>, difference_type)
237  {
238  RANGES_EXPECT(false);
239  }
240  RANGES_DIAGNOSTIC_PUSH
241  RANGES_DIAGNOSTIC_IGNORE_DIVIDE_BY_ZERO
242  template<std::size_t N>
243  void advance_(meta::size_t<N>, difference_type n)
244  {
245  if(n == 0)
246  return;
247 
248  auto & i = std::get<N - 1>(its_);
249  auto const my_size = static_cast<difference_type>(
250  ranges::size(std::get<N - 1>(view_->views_)));
251  auto const first = ranges::begin(std::get<N - 1>(view_->views_));
252 
253  auto const idx = static_cast<difference_type>(i - first);
254  RANGES_EXPECT(0 <= idx);
255  RANGES_EXPECT(idx < my_size || (N == 1 && idx == my_size && n < 0));
256  RANGES_EXPECT(n < INTMAX_MAX - idx);
257  n += idx;
258 
259  auto n_div = n / my_size;
260  auto n_mod = n % my_size;
261 
262  if(RANGES_CONSTEXPR_IF(N != 1))
263  {
264  if(n_mod < 0)
265  {
266  n_mod += my_size;
267  --n_div;
268  }
269  advance_(meta::size_t<N - 1>{}, n_div);
270  }
271  RANGES_EXPECT(0 <= n_mod && n_mod < my_size);
272 
273  if(RANGES_CONSTEXPR_IF(N == 1))
274  {
275  if(n_div > 0)
276  {
277  RANGES_EXPECT(n_div == 1);
278  RANGES_EXPECT(n_mod == 0);
279  n_mod = my_size;
280  }
281  else if(n_div < 0)
282  {
283  RANGES_EXPECT(n_div == -1);
284  RANGES_EXPECT(n_mod == 0);
285  }
286  }
287 
288  using D = iter_difference_t<decltype(first)>;
289  i = first + static_cast<D>(n_mod);
290  }
291  RANGES_DIAGNOSTIC_POP
292  void check_at_end_(meta::size_t<1>, bool at_end = false)
293  {
294  if(at_end)
295  ranges::advance(std::get<0>(its_),
296  ranges::end(std::get<0>(view_->views_)));
297  }
298  template<std::size_t N>
299  void check_at_end_(meta::size_t<N>, bool at_end = false)
300  {
301  return check_at_end_(
303  at_end || bool(std::get<N - 1>(its_) ==
304  ranges::end(std::get<N - 1>(view_->views_))));
305  }
306  cursor(end_tag, constify_if<cartesian_product_view> * view,
307  std::true_type) // common_with
308  : cursor(begin_tag{}, view)
309  {
310  CPP_assert(
311  common_range<meta::at_c<meta::list<constify_if<Views>...>, 0>>);
312  std::get<0>(its_) = ranges::end(std::get<0>(view->views_));
313  }
314  cursor(end_tag, constify_if<cartesian_product_view> * view,
315  std::false_type) // !common_with
316  : cursor(begin_tag{}, view)
317  {
318  using View0 = meta::at_c<meta::list<constify_if<Views>...>, 0>;
319  CPP_assert(!common_range<View0> && random_access_range<View0> &&
320  sized_range<View0>);
321  std::get<0>(its_) += ranges::distance(std::get<0>(view->views_));
322  }
323 
324  public:
325  using value_type = std::tuple<range_value_t<Views>...>;
326 
327  cursor() = default;
328  explicit cursor(begin_tag, constify_if<cartesian_product_view> * view)
329  : view_(view)
330  , its_(tuple_transform(view->views_, ranges::begin))
331  {
332  // If any of the constituent views is empty, the cartesian_product is
333  // empty and this "begin" iterator needs to become an "end" iterator.
334  check_at_end_(meta::size_t<sizeof...(Views)>{});
335  }
336  explicit cursor(end_tag, constify_if<cartesian_product_view> * view)
337  : cursor(
338  end_tag{}, view,
339  meta::bool_<
340  common_range<meta::at_c<meta::list<constify_if<Views>...>, 0>>>{})
341  {}
342  template(bool Other)(
343  requires IsConst_ AND CPP_NOT(Other)) //
344  cursor(cursor<Other> that)
345  : view_(that.view_)
346  , its_(std::move(that.its_))
347  {}
349  {
350  return tuple_transform(its_, detail::dereference_fn{});
351  }
352  void next()
353  {
354  next_(meta::size_t<sizeof...(Views)>{});
355  }
356  bool equal(default_sentinel_t) const
357  {
358  return std::get<0>(its_) == ranges::end(std::get<0>(view_->views_));
359  }
360  bool equal(cursor const & that) const
361  {
362  return equal_(that, meta::size_t<sizeof...(Views)>{});
363  }
364  CPP_member
365  auto prev() -> CPP_ret(void)(
366  requires cartesian_produce_view_can_bidi<IsConst, Views...>)
367  {
368  prev_(meta::size_t<sizeof...(Views)>{});
369  }
370  CPP_auto_member
371  auto CPP_fun(distance_to)(cursor const & that)(
372  const requires cartesian_produce_view_can_distance<IsConst, Views...>)
373  {
374  return distance_(that, meta::size_t<sizeof...(Views)>{});
375  }
376  CPP_member
377  auto advance(difference_type n) //
378  -> CPP_ret(void)(
379  requires cartesian_produce_view_can_random<IsConst, Views...>)
380  {
381  advance_(meta::size_t<sizeof...(Views)>{}, n);
382  }
383  };
384  cursor<false> begin_cursor()
385  {
386  return cursor<false>{begin_tag{}, this};
387  }
388  CPP_member
389  auto begin_cursor() const //
390  -> CPP_ret(cursor<true>)(
391  requires cartesian_produce_view_can_const<Views...>)
392  {
393  return cursor<true>{begin_tag{}, this};
394  }
395  CPP_member
396  auto end_cursor() //
397  -> CPP_ret(cursor<false>)(
398  requires cartesian_produce_view_can_bidi<std::false_type, Views...>)
399  {
400  return cursor<false>{end_tag{}, this};
401  }
402  CPP_member
403  auto end_cursor() const //
404  -> CPP_ret(cursor<true>)(
405  requires cartesian_produce_view_can_bidi<std::true_type, Views...>)
406  {
407  return cursor<true>{end_tag{}, this};
408  }
409  CPP_member
410  auto end_cursor() const //
411  -> CPP_ret(default_sentinel_t)(
412  requires (!cartesian_produce_view_can_bidi<std::true_type, Views...>))
413  {
414  return {};
415  }
416 
417  public:
418  cartesian_product_view() = default;
419  constexpr explicit cartesian_product_view(Views... views)
420  : views_{detail::move(views)...}
421  {}
422  template(typename...)(
423  requires (my_cardinality >= 0)) //
424  static constexpr std::size_t size() noexcept
425  {
426  return std::size_t{my_cardinality};
427  }
428  CPP_auto_member
429  auto CPP_fun(size)()(const //
430  requires (my_cardinality < 0) &&
431  cartesian_produce_view_can_size<std::true_type, Views...>)
432  {
433  return tuple_foldl(views_, std::uintmax_t{1}, detail::cartesian_size_fn{});
434  }
435  CPP_auto_member
436  auto CPP_fun(size)()(
437  requires (my_cardinality < 0) &&
438  cartesian_produce_view_can_size<std::false_type, Views...>)
439  {
440  return tuple_foldl(views_, std::uintmax_t{1}, detail::cartesian_size_fn{});
441  }
442  };
443 
444 #if RANGES_CXX_DEDUCTION_GUIDES >= RANGES_CXX_DEDUCTION_GUIDES_17
445  template<typename... Rng>
446  cartesian_product_view(Rng &&...) //
448 #endif
449 
450  namespace views
451  {
453  {
454  constexpr empty_view<std::tuple<>> operator()() const noexcept
455  {
456  return {};
457  }
458  template(typename... Rngs)(
459  requires (sizeof...(Rngs) != 0) AND
460  concepts::and_v<(forward_range<Rngs> && viewable_range<Rngs>)...>)
461  constexpr cartesian_product_view<all_t<Rngs>...> operator()(Rngs &&... rngs)
462  const
463  {
465  all(static_cast<Rngs &&>(rngs))...};
466  }
467 #if defined(_MSC_VER)
468  template(typename Rng0)(
469  requires forward_range<Rng0> AND viewable_range<Rng0>)
470  constexpr cartesian_product_view<all_t<Rng0>> operator()(Rng0 && rng0) const
471  {
473  all(static_cast<Rng0 &&>(rng0))};
474  }
475  template(typename Rng0, typename Rng1)(
476  requires forward_range<Rng0> AND viewable_range<Rng0> AND
477  forward_range<Rng1> AND viewable_range<Rng1>)
478  constexpr cartesian_product_view<all_t<Rng0>, all_t<Rng1>> //
479  operator()(Rng0 && rng0, Rng1 && rng1) const
480  {
481  return cartesian_product_view<all_t<Rng0>, all_t<Rng1>>{
482  all(static_cast<Rng0 &&>(rng0)), //
483  all(static_cast<Rng1 &&>(rng1))};
484  }
485  template(typename Rng0, typename Rng1, typename Rng2)(
486  requires forward_range<Rng0> AND viewable_range<Rng0> AND
487  forward_range<Rng1> AND viewable_range<Rng1> AND
488  forward_range<Rng2> AND viewable_range<Rng2>)
489  constexpr cartesian_product_view<all_t<Rng0>, all_t<Rng1>, all_t<Rng2>> //
490  operator()(Rng0 && rng0, Rng1 && rng1, Rng2 && rng2) const
491  {
492  return cartesian_product_view<all_t<Rng0>, all_t<Rng1>, all_t<Rng2>>{
493  all(static_cast<Rng0 &&>(rng0)), //
494  all(static_cast<Rng1 &&>(rng1)), //
495  all(static_cast<Rng2 &&>(rng2))};
496  }
497 #endif
498  };
499 
501  } // namespace views
502 
504 } // namespace ranges
505 
506 #include <range/v3/detail/epilogue.hpp>
507 
508 #endif
CPP_concept sized_sentinel_for
\concept sized_sentinel_for
Definition: concepts.hpp:332
CPP_concept common_range
\concept common_range
Definition: concepts.hpp:180
CPP_concept view_
\concept view_
Definition: concepts.hpp:252
decltype(begin(declval(Rng &))) iterator_t
Definition: access.hpp:698
RANGES_INLINE_VARIABLE(detail::to_container_fn< detail::from_range< std::vector >>, to_vector) template< template< typename... > class ContT > auto to(RANGES_HIDDEN_DETAIL(detail
For initializing a container of the specified type with the elements of an Range.
Definition: conversion.hpp:399
CPP_concept cartesian_produce_view_can_const
\concept cartesian_produce_view_can_const
Definition: cartesian_product.hpp:86
CPP_concept cartesian_produce_view_can_bidi
\concept cartesian_produce_view_can_bidi
Definition: cartesian_product.hpp:140
CPP_concept cartesian_produce_view_can_size
\concept cartesian_produce_view_can_size
Definition: cartesian_product.hpp:98
CPP_concept cartesian_produce_view_can_random
\concept cartesian_produce_view_can_random
Definition: cartesian_product.hpp:126
CPP_concept cartesian_produce_view_can_distance
\concept cartesian_produce_view_can_distance
Definition: cartesian_product.hpp:113
std::integral_constant< bool, B > bool_
An integral constant wrapper for bool.
Definition: meta.hpp:168
std::integral_constant< std::size_t, N > size_t
An integral constant wrapper for std::size_t.
Definition: meta.hpp:163
_t< detail::at_< L, N > > at_c
Return the N th element in the meta::list L.
Definition: meta.hpp:1962
front< Pair > first
Retrieve the first element of the pair Pair.
Definition: meta.hpp:2251
meta::size_t< L::size()> size
An integral constant wrapper that is the size of the meta::list L.
Definition: meta.hpp:1696
reverse_fold< ListOfLists, list< list<> >, quote_trait< detail::cartesian_product_fn > > cartesian_product
Given a list of lists ListOfLists, return a new list of lists that is the Cartesian Product.
Definition: meta.hpp:3720
_t< detail::fold_< L, id< State >, Fn > > fold
Return a new meta::list constructed by doing a left fold of the list L using binary invocable Fn and ...
Definition: meta.hpp:1589
A list of types.
Definition: meta.hpp:1684
Turn a template C into an invocable.
Definition: meta.hpp:913
Definition: range_fwd.hpp:488
Definition: cartesian_product.hpp:149
Definition: common_tuple.hpp:96
Definition: default_sentinel.hpp:26
Definition: empty.hpp:29
Definition: range_fwd.hpp:490
A utility for constructing a view from a (derived) type that implements begin and end cursors.
Definition: facade.hpp:66
Definition: cartesian_product.hpp:453