Horizon
Loading...
Searching...
No Matches
cartesian_product.hpp
Go to the documentation of this file.
1
2// 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
23
30#include <range/v3/utility/static_const.hpp>
32#include <range/v3/view/all.hpp>
35#include <range/v3/view/view.hpp> // for dereference_fn
36
37#include <range/v3/detail/prologue.hpp>
38
39namespace 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>
86 CPP_concept cartesian_produce_view_can_const =
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>
98 CPP_concept cartesian_produce_view_can_size =
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<
107 iterator_t<meta::const_if<IsConst, Views>>,
108 iterator_t<meta::const_if<IsConst, Views>>>...>
109 );
112 template<typename IsConst, typename...Views>
113 CPP_concept cartesian_produce_view_can_distance =
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>
126 CPP_concept cartesian_produce_view_can_random =
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>
140 CPP_concept cartesian_produce_view_can_bidi =
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 {
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>;
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,
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)(
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)(
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)(
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)(
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
500 RANGES_INLINE_VARIABLE(cartesian_product_fn, cartesian_product)
501 } // namespace views
502
504} // namespace ranges
505
506#include <range/v3/detail/epilogue.hpp>
507
508#endif
The cartesian_produce_view_can_bidi_ concept.
The cartesian_produce_view_can_bidi concept.
The cartesian_produce_view_can_const concept.
The cartesian_produce_view_can_distance_ concept.
The cartesian_produce_view_can_distance concept.
The cartesian_produce_view_can_random_ concept.
The cartesian_produce_view_can_random concept.
The cartesian_produce_view_can_size_ concept.
The cartesian_produce_view_can_size concept.
The common_range concept.
The forward_range concept.
The random_access_range concept.
The sized_range concept.
The view_ concept.
The viewable_range concept.
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
_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