Horizon
Loading...
Searching...
No Matches
join.hpp
Go to the documentation of this file.
1
2// Range v3 library
3//
4// Copyright Eric Niebler 2014-present
5//
6// Use, modification and distribution is subject to the
7// Boost Software License, Version 1.0. (See accompanying
8// file LICENSE_1_0.txt or copy at
9// http://www.boost.org/LICENSE_1_0.txt)
10//
11// Project home: https://github.com/ericniebler/range-v3
12//
13
14#ifndef RANGES_V3_VIEW_JOIN_HPP
15#define RANGES_V3_VIEW_JOIN_HPP
16
17#include <type_traits>
18#include <utility>
19
20#include <meta/meta.hpp>
21
23
30#include <range/v3/utility/static_const.hpp>
32#include <range/v3/view/all.hpp>
36
37#include <range/v3/detail/prologue.hpp>
38
39namespace ranges
40{
42 namespace detail
43 {
44 // Compute the cardinality of a joined range
45 constexpr cardinality join_cardinality_(
46 cardinality Outer, cardinality Inner,
47 cardinality Joiner = static_cast<cardinality>(0)) noexcept
48 {
49 return Outer == infinite || Inner == infinite ||
50 (Joiner == infinite && Outer != 0 && Outer != 1)
51 ? infinite
52 : Outer == unknown || Inner == unknown ||
53 (Joiner == unknown && Outer != 0 && Outer != 1)
54 ? unknown
55 : Outer == finite || Inner == finite ||
56 (Joiner == finite && Outer != 0 && Outer != 1)
57 ? finite
58 : static_cast<cardinality>(
59 Outer * Inner +
60 (Outer == 0 ? 0 : (Outer - 1) * Joiner));
61 }
62
63 template<typename Range>
64 constexpr cardinality join_cardinality() noexcept
65 {
66 return detail::join_cardinality_(
67 range_cardinality<Range>::value,
68 range_cardinality<range_reference_t<Range>>::value);
69 }
70
71 template<typename Range, typename JoinRange>
72 constexpr cardinality join_cardinality() noexcept
73 {
74 return detail::join_cardinality_(
75 range_cardinality<Range>::value,
76 range_cardinality<range_reference_t<Range>>::value,
77 range_cardinality<JoinRange>::value);
78 }
79
80 template<typename Inner>
81 struct store_inner_
82 {
83 non_propagating_cache<std::remove_cv_t<Inner>> inner_ = {};
84
85 template<typename OuterIt>
86 constexpr auto && update_inner_(OuterIt && it)
87 {
88 return inner_.emplace_deref(it);
89 }
90 constexpr Inner & get_inner_(ignore_t) noexcept
91 {
92 return *inner_;
93 }
94 };
95
96 struct pass_thru_inner_
97 {
98 // Intentionally promote xvalues to lvalues here:
99 template<typename OuterIt>
100 static constexpr auto && update_inner_(OuterIt && it) noexcept
101 {
102 return *it;
103 }
104 template<typename OuterIt>
105 static constexpr decltype(auto) get_inner_(OuterIt && outer_it)
106 {
107 return *outer_it;
108 }
109 };
110
111 template<typename Rng>
112 using join_view_inner =
114 store_inner_<range_reference_t<Rng>>, pass_thru_inner_>;
115
116 // clang-format off
119 template<typename I>
120 CPP_requires(has_member_arrow_,
121 requires(I i) //
122 (
123 i.operator->()
124 ));
125
128 template<typename I>
129 CPP_concept has_arrow_ =
130 input_iterator<I> &&
131 (std::is_pointer<I>::value || CPP_requires_ref(detail::has_member_arrow_, I));
132 // clang-format on
133 } // namespace detail
135
138
139 // Join a range of ranges
140 template<typename Rng>
141 struct RANGES_EMPTY_BASES join_view
142 : view_facade<join_view<Rng>, detail::join_cardinality<Rng>()>
143 , private detail::join_view_inner<Rng>
144 {
145 CPP_assert(input_range<Rng> && view_<Rng>);
146 CPP_assert(input_range<range_reference_t<Rng>>);
147
148 join_view() = default;
149 explicit join_view(Rng rng)
150 : outer_(views::all(std::move(rng)))
151 {}
152 // Not to spec
153 CPP_member
154 static constexpr auto size() //
155 -> CPP_ret(std::size_t)(
156 requires (detail::join_cardinality<Rng>() >= 0))
157 {
158 return static_cast<std::size_t>(detail::join_cardinality<Rng>());
159 }
160 // Not to spec
161 CPP_auto_member
162 constexpr auto CPP_fun(size)()(
163 requires(detail::join_cardinality<Rng>() < 0) &&
166 sized_range<range_reference_t<Rng>>)
167 {
168 range_size_t<range_reference_t<Rng>> n = 0;
169 RANGES_FOR(auto && inner, outer_)
170 n += ranges::size(inner);
171 return n;
172 }
173 // // ericniebler/stl2#605
174 constexpr Rng base() const
175 {
176 return outer_;
177 }
178
179 private:
180 friend range_access;
181 Rng outer_{};
182
183 template<bool Const>
184 struct cursor
185 {
186 private:
189 using CInner = range_reference_t<COuter>;
190 using ref_is_glvalue = std::is_reference<CInner>;
191
192 Parent * rng_ = nullptr;
193 iterator_t<COuter> outer_it_{};
194 iterator_t<CInner> inner_it_{};
195
196 void satisfy()
197 {
198 for(; outer_it_ != ranges::end(rng_->outer_); ++outer_it_)
199 {
200 auto && inner = rng_->update_inner_(outer_it_);
201 inner_it_ = ranges::begin(inner);
202 if(inner_it_ != ranges::end(inner))
203 return;
204 }
205 if(RANGES_CONSTEXPR_IF(ref_is_glvalue::value))
206 inner_it_ = iterator_t<CInner>();
207 }
208
209 public:
211 single_pass_iterator_<iterator_t<CInner>> ||
212 !ref_is_glvalue::value>;
213 cursor() = default;
214 template<typename BeginOrEnd>
215 constexpr cursor(Parent * rng, BeginOrEnd begin_or_end)
216 : rng_{rng}
217 , outer_it_(begin_or_end(rng->outer_))
218 {
219 satisfy();
220 }
221 template(bool Other)(
222 requires Const AND CPP_NOT(Other) AND
223 convertible_to<iterator_t<Rng>, iterator_t<COuter>> AND
224 convertible_to<iterator_t<range_reference_t<Rng>>,
226 constexpr cursor(cursor<Other> that)
227 : rng_(that.rng_)
228 , outer_it_(std::move(that.outer_it_))
229 , inner_it_(std::move(that.inner_it_))
230 {}
231 CPP_member
232 constexpr auto arrow() //
233 -> CPP_ret(iterator_t<CInner>)(
234 requires detail::has_arrow_<iterator_t<CInner>>)
235 {
236 return inner_it_;
237 }
238 constexpr bool equal(default_sentinel_t) const
239 {
240 return outer_it_ == ranges::end(rng_->outer_);
241 }
242 CPP_member
243 constexpr auto equal(cursor const & that) const //
244 -> CPP_ret(bool)(
245 requires ref_is_glvalue::value && //
246 equality_comparable<iterator_t<COuter>> && //
247 equality_comparable<iterator_t<CInner>>)
248 {
249 return outer_it_ == that.outer_it_ && inner_it_ == that.inner_it_;
250 }
251 constexpr void next()
252 {
253 auto && inner_rng = rng_->get_inner_(outer_it_);
254 if(++inner_it_ == ranges::end(inner_rng))
255 {
256 ++outer_it_;
257 satisfy();
258 }
259 }
260 CPP_member
261 constexpr auto prev() //
262 -> CPP_ret(void)(
263 requires ref_is_glvalue::value && //
266 common_range<CInner>) // ericniebler/stl2#606
267 {
268 if(outer_it_ == ranges::end(rng_->outer_))
269 inner_it_ = ranges::end(*--outer_it_);
270 while(inner_it_ == ranges::begin(*outer_it_))
271 inner_it_ = ranges::end(*--outer_it_);
272 --inner_it_;
273 }
274 // clang-format off
275 constexpr auto CPP_auto_fun(read)()(const)
276 (
277 return *inner_it_
278 )
279 constexpr auto CPP_auto_fun(move)()(const)
280 (
281 return iter_move(inner_it_)
282 )
283 // clang-format on
284 };
285 static constexpr bool use_const_always() noexcept
286 {
287 return simple_view<Rng>() && std::is_reference<range_reference_t<Rng>>::value;
288 }
289 struct end_cursor_fn
290 {
291 constexpr auto operator()(join_view * this_, std::true_type) const
292 {
293 return cursor<use_const_always()>{this_, ranges::end};
294 }
295 constexpr auto operator()(join_view *, std::false_type) const
296 {
297 return default_sentinel_t{};
298 }
299 };
300 struct cend_cursor_fn
301 {
302 constexpr auto operator()(join_view const * this_, std::true_type) const
303 {
304 return cursor<true>{this_, ranges::end};
305 }
306 constexpr auto operator()(join_view const *, std::false_type) const
307 {
308 return default_sentinel_t{};
309 }
310 };
311
312 constexpr cursor<use_const_always()> begin_cursor()
313 {
314 return {this, ranges::begin};
315 }
316
317 template(bool Const = true)(
318 requires Const AND input_range<meta::const_if_c<Const, Rng>> AND
319 std::is_reference<range_reference_t<meta::const_if_c<Const, Rng>>>::value)
320 constexpr cursor<Const> begin_cursor() const
321 {
322 return {this, ranges::begin};
323 }
324
325 constexpr auto end_cursor()
326 {
327 using cond =
331 return end_cursor_fn{}(this, cond{});
332 }
333
334 template(bool Const = true)(
335 requires Const AND input_range<meta::const_if_c<Const, Rng>> AND
336 std::is_reference<range_reference_t<meta::const_if_c<Const, Rng>>>::value)
337 constexpr auto end_cursor() const
338 {
339 using CRng = meta::const_if_c<Const, Rng>;
340 using cond =
345 return cend_cursor_fn{}(this, cond{});
346 }
347 };
348
349 // Join a range of ranges, inserting a range of values between them.
350 // TODO: Support const iteration when range_reference_t<Rng> is a true reference.
351 template<typename Rng, typename ValRng>
353 : view_facade<join_with_view<Rng, ValRng>, detail::join_cardinality<Rng, ValRng>()>
354 , private detail::join_view_inner<Rng>
355 {
356 CPP_assert(input_range<Rng>);
357 CPP_assert(input_range<range_reference_t<Rng>>);
358 CPP_assert(forward_range<ValRng>);
359 CPP_assert(
360 common_with<range_value_t<range_reference_t<Rng>>, range_value_t<ValRng>>);
361 CPP_assert(semiregular<common_type_t<range_value_t<range_reference_t<Rng>>,
362 range_value_t<ValRng>>>);
363
364 join_with_view() = default;
365 join_with_view(Rng rng, ValRng val)
366 : outer_(views::all(std::move(rng)))
367 , val_(views::all(std::move(val)))
368 {}
369 CPP_member
370 static constexpr auto size() //
371 -> CPP_ret(std::size_t)(
372 requires (detail::join_cardinality<Rng, ValRng>() >= 0))
373 {
374 return static_cast<std::size_t>(detail::join_cardinality<Rng, ValRng>());
375 }
376 CPP_auto_member
377 auto CPP_fun(size)()(const //
378 requires(detail::join_cardinality<Rng, ValRng>() < 0) &&
380 sized_range<range_reference_t<Rng>> && sized_range<ValRng>)
381 {
382 range_size_t<range_reference_t<Rng>> n = 0;
383 RANGES_FOR(auto && inner, outer_)
384 n += ranges::size(inner);
385 return n + (range_cardinality<Rng>::value == 0
386 ? 0
387 : ranges::size(val_) * (range_cardinality<Rng>::value - 1));
388 }
389
390 private:
391 friend range_access;
392 using Outer = views::all_t<Rng>;
393 // Intentionally promote xvalues to lvalues here:
394 using Inner = views::all_t<range_reference_t<Outer> &>;
395
396 Outer outer_{};
397 views::all_t<ValRng> val_{};
398
399 class cursor
400 {
401 join_with_view * rng_ = nullptr;
402 iterator_t<Outer> outer_it_{};
404
405 void satisfy()
406 {
407 while(true)
408 {
409 if(cur_.index() == 0)
410 {
411 if(ranges::get<0>(cur_) != ranges::end(rng_->val_))
412 break;
413 // Intentionally promote xvalues to lvalues here:
414 auto && inner = rng_->update_inner_(outer_it_);
415 ranges::emplace<1>(cur_, ranges::begin(inner));
416 }
417 else
418 {
419 auto && inner = rng_->get_inner_(outer_it_);
420 if(ranges::get<1>(cur_) != ranges::end(inner))
421 break;
422 if(++outer_it_ == ranges::end(rng_->outer_))
423 break;
424 ranges::emplace<0>(cur_, ranges::begin(rng_->val_));
425 }
426 }
427 }
428
429 public:
430 using value_type = common_type_t<range_value_t<Inner>, range_value_t<ValRng>>;
431 using reference =
432 common_reference_t<range_reference_t<Inner>, range_reference_t<ValRng>>;
433 using rvalue_reference = common_reference_t<range_rvalue_reference_t<Inner>,
434 range_rvalue_reference_t<ValRng>>;
435 using single_pass = std::true_type;
436 cursor() = default;
437 cursor(join_with_view * rng)
438 : rng_{rng}
439 , outer_it_(ranges::begin(rng->outer_))
440 {
441 if(outer_it_ != ranges::end(rng->outer_))
442 {
443 auto && inner = rng_->update_inner_(outer_it_);
444 ranges::emplace<1>(cur_, ranges::begin(inner));
445 satisfy();
446 }
447 }
448 bool equal(default_sentinel_t) const
449 {
450 return outer_it_ == ranges::end(rng_->outer_);
451 }
452 void next()
453 {
454 // visit(cur_, [](auto& it){ ++it; });
455 if(cur_.index() == 0)
456 {
457 auto & it = ranges::get<0>(cur_);
458 RANGES_ASSERT(it != ranges::end(rng_->val_));
459 ++it;
460 }
461 else
462 {
463 auto & it = ranges::get<1>(cur_);
464 #ifndef NDEBUG
465 auto && inner = rng_->get_inner_(outer_it_);
466 RANGES_ASSERT(it != ranges::end(inner));
467 #endif
468 ++it;
469 }
470 satisfy();
471 }
472 reference read() const
473 {
474 // return visit(cur_, [](auto& it) -> reference { return *it; });
475 if(cur_.index() == 0)
476 return *ranges::get<0>(cur_);
477 else
478 return *ranges::get<1>(cur_);
479 }
480 rvalue_reference move() const
481 {
482 // return visit(cur_, [](auto& it) -> rvalue_reference { return
483 // iter_move(it); });
484 if(cur_.index() == 0)
485 return iter_move(ranges::get<0>(cur_));
486 else
487 return iter_move(ranges::get<1>(cur_));
488 }
489 };
490 cursor begin_cursor()
491 {
492 return {this};
493 }
494 };
495
496 namespace views
497 {
499 // Don't forget to update views::for_each whenever this set
500 // of concepts changes
501 // clang-format off
504 template(typename Rng)(
505 concept (joinable_range_)(Rng),
506 input_range<range_reference_t<Rng>>
507 );
510 template<typename Rng>
511 CPP_concept joinable_range =
513 CPP_concept_ref(views::joinable_range_, Rng);
514
517 template(typename Rng, typename ValRng)(
518 concept (joinable_with_range_)(Rng, ValRng),
519 common_with<
520 range_value_t<ValRng>,
521 range_value_t<range_reference_t<Rng>>> AND
522 semiregular<
523 common_type_t<
524 range_value_t<ValRng>,
525 range_value_t<range_reference_t<Rng>>>> AND
526 common_reference_with<
527 range_reference_t<ValRng>,
528 range_reference_t<range_reference_t<Rng>>> AND
529 common_reference_with<
530 range_rvalue_reference_t<ValRng>,
531 range_rvalue_reference_t<range_reference_t<Rng>>>
532 );
535 template<typename Rng, typename ValRng>
536 CPP_concept joinable_with_range =
537 joinable_range<Rng> &&
539 CPP_concept_ref(views::joinable_with_range_, Rng, ValRng);
540 // clang-format on
542
544 {
545 template(typename Rng)(
546 requires joinable_range<Rng>)
547 join_view<all_t<Rng>> operator()(Rng && rng) const
548 {
549 return join_view<all_t<Rng>>{all(static_cast<Rng &&>(rng))};
550 }
551 };
552
554 {
555 private:
556 template<typename Rng>
557 using inner_value_t = range_value_t<range_reference_t<Rng>>;
558 public:
559 using cpp20_join_fn::operator();
560
561 template(typename Rng)(
562 requires joinable_with_range<Rng, single_view<inner_value_t<Rng>>>)
564 operator()(Rng && rng, inner_value_t<Rng> v) const
565 {
566 return {all(static_cast<Rng &&>(rng)), single(std::move(v))};
567 }
568
569 template(typename Rng, typename ValRng)(
570 requires joinable_with_range<Rng, ValRng>)
571 join_with_view<all_t<Rng>, all_t<ValRng>> //
572 operator()(Rng && rng, ValRng && val) const
573 {
574 return {all(static_cast<Rng &&>(rng)), all(static_cast<ValRng &&>(val))};
575 }
576
578 template<typename Rng, typename T>
579 invoke_result_t<join_base_fn, Rng, T &> //
580 operator()(Rng && rng, detail::reference_wrapper_<T> r) const
581 {
582 return (*this)(static_cast<Rng &&>(rng), r.get());
583 }
585 };
586
588 {
589 template(typename T)(
590 requires (!joinable_range<T>)) // TODO: underconstrained
591 constexpr auto operator()(T && t)const
592 {
593 return make_view_closure(bind_back(join_base_fn{}, static_cast<T &&>(t)));
594 }
595 template(typename T)(
596 requires (!joinable_range<T &>) AND range<T &>)
597 constexpr auto operator()(T & t) const
598 {
599 return make_view_closure(bind_back(join_base_fn{},
600 detail::reference_wrapper_<T>(t)));
601 }
602 };
603
604 struct RANGES_EMPTY_BASES join_fn
606 {
607 using join_base_fn::operator();
608 using join_bind_fn::operator();
609 };
610
613 RANGES_INLINE_VARIABLE(view_closure<join_fn>, join)
614 } // namespace views
616
617#if RANGES_CXX_DEDUCTION_GUIDES >= RANGES_CXX_DEDUCTION_GUIDES_17
618 template(typename Rng)(
619 requires views::joinable_range<Rng>)
620 explicit join_view(Rng &&)
621 ->join_view<views::all_t<Rng>>;
622
623 template(typename Rng, typename ValRng)(
624 requires views::joinable_with_range<Rng, ValRng>)
625 explicit join_with_view(Rng &&, ValRng &&)
626 ->join_with_view<views::all_t<Rng>, views::all_t<ValRng>>;
627#endif
628
629 namespace cpp20
630 {
631 namespace views
632 {
633 RANGES_INLINE_VARIABLE(
635 }
636 template(typename Rng)(
637 requires input_range<Rng> AND view_<Rng> AND
638 input_range<iter_reference_t<iterator_t<Rng>>>) //
639 using join_view = ranges::join_view<Rng>;
640 } // namespace cpp20
641} // namespace ranges
642
643#include <range/v3/detail/epilogue.hpp>
644
645#include <range/v3/detail/satisfy_boost_range.hpp>
646RANGES_SATISFY_BOOST_RANGE(::ranges::join_view)
647RANGES_SATISFY_BOOST_RANGE(::ranges::join_with_view)
648
649#endif
The bidirectional_range concept.
The common_range concept.
The forward_range concept.
The input_range concept.
The range concept.
The sized_range concept.
The view_ concept.
The viewable_range concept.
decltype(begin(declval(Rng &))) iterator_t
Definition access.hpp:698
std::integral_constant< bool, B > bool_
An integral constant wrapper for bool.
Definition meta.hpp:168
typename detail::_cond< If >::template invoke< Then, Else > conditional_t
Select one type or another depending on a compile-time Boolean.
Definition meta.hpp:1148
Tiny meta-programming library.
Definition default_sentinel.hpp:26
Definition join.hpp:144
Definition join.hpp:355
Definition traits.hpp:128
Definition single.hpp:41
Definition variant.hpp:621
A utility for constructing a view from a (derived) type that implements begin and end cursors.
Definition facade.hpp:66
Definition join.hpp:544
Definition join.hpp:554
Definition join.hpp:588
Definition join.hpp:606
Definition view.hpp:178