File indexing completed on 2025-01-18 10:09:57
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010
0011
0012
0013
0014 #ifndef RANGES_V3_VIEW_JOIN_HPP
0015 #define RANGES_V3_VIEW_JOIN_HPP
0016
0017 #include <type_traits>
0018 #include <utility>
0019
0020 #include <meta/meta.hpp>
0021
0022 #include <range/v3/range_fwd.hpp>
0023
0024 #include <range/v3/functional/bind_back.hpp>
0025 #include <range/v3/iterator/default_sentinel.hpp>
0026 #include <range/v3/range/access.hpp>
0027 #include <range/v3/range/primitives.hpp>
0028 #include <range/v3/range/traits.hpp>
0029 #include <range/v3/range_for.hpp>
0030 #include <range/v3/utility/static_const.hpp>
0031 #include <range/v3/utility/variant.hpp>
0032 #include <range/v3/view/all.hpp>
0033 #include <range/v3/view/facade.hpp>
0034 #include <range/v3/view/single.hpp>
0035 #include <range/v3/view/view.hpp>
0036
0037 #include <range/v3/detail/prologue.hpp>
0038
0039 namespace ranges
0040 {
0041
0042 namespace detail
0043 {
0044
0045 constexpr cardinality join_cardinality_(
0046 cardinality Outer, cardinality Inner,
0047 cardinality Joiner = static_cast<cardinality>(0)) noexcept
0048 {
0049 return Outer == infinite || Inner == infinite ||
0050 (Joiner == infinite && Outer != 0 && Outer != 1)
0051 ? infinite
0052 : Outer == unknown || Inner == unknown ||
0053 (Joiner == unknown && Outer != 0 && Outer != 1)
0054 ? unknown
0055 : Outer == finite || Inner == finite ||
0056 (Joiner == finite && Outer != 0 && Outer != 1)
0057 ? finite
0058 : static_cast<cardinality>(
0059 Outer * Inner +
0060 (Outer == 0 ? 0 : (Outer - 1) * Joiner));
0061 }
0062
0063 template<typename Range>
0064 constexpr cardinality join_cardinality() noexcept
0065 {
0066 return detail::join_cardinality_(
0067 range_cardinality<Range>::value,
0068 range_cardinality<range_reference_t<Range>>::value);
0069 }
0070
0071 template<typename Range, typename JoinRange>
0072 constexpr cardinality join_cardinality() noexcept
0073 {
0074 return detail::join_cardinality_(
0075 range_cardinality<Range>::value,
0076 range_cardinality<range_reference_t<Range>>::value,
0077 range_cardinality<JoinRange>::value);
0078 }
0079
0080 template<typename Inner>
0081 struct store_inner_
0082 {
0083 non_propagating_cache<std::remove_cv_t<Inner>> inner_ = {};
0084
0085 template<typename OuterIt>
0086 constexpr auto && update_inner_(OuterIt && it)
0087 {
0088 return inner_.emplace_deref(it);
0089 }
0090 constexpr Inner & get_inner_(ignore_t) noexcept
0091 {
0092 return *inner_;
0093 }
0094 };
0095
0096 struct pass_thru_inner_
0097 {
0098
0099 template<typename OuterIt>
0100 static constexpr auto && update_inner_(OuterIt && it) noexcept
0101 {
0102 return *it;
0103 }
0104 template<typename OuterIt>
0105 static constexpr decltype(auto) get_inner_(OuterIt && outer_it)
0106 {
0107 return *outer_it;
0108 }
0109 };
0110
0111 template<typename Rng>
0112 using join_view_inner =
0113 meta::conditional_t<!std::is_reference<range_reference_t<Rng>>::value,
0114 store_inner_<range_reference_t<Rng>>, pass_thru_inner_>;
0115
0116
0117
0118
0119 template<typename I>
0120 CPP_requires(has_member_arrow_,
0121 requires(I i)
0122 (
0123 i.operator->()
0124 ));
0125
0126
0127
0128 template<typename I>
0129 CPP_concept has_arrow_ =
0130 input_iterator<I> &&
0131 (std::is_pointer<I>::value || CPP_requires_ref(detail::has_member_arrow_, I));
0132
0133 }
0134
0135
0136
0137
0138
0139
0140 template<typename Rng>
0141 struct RANGES_EMPTY_BASES join_view
0142 : view_facade<join_view<Rng>, detail::join_cardinality<Rng>()>
0143 , private detail::join_view_inner<Rng>
0144 {
0145 CPP_assert(input_range<Rng> && view_<Rng>);
0146 CPP_assert(input_range<range_reference_t<Rng>>);
0147
0148 join_view() = default;
0149 explicit join_view(Rng rng)
0150 : outer_(views::all(std::move(rng)))
0151 {}
0152
0153 CPP_member
0154 static constexpr auto size()
0155 -> CPP_ret(std::size_t)(
0156 requires (detail::join_cardinality<Rng>() >= 0))
0157 {
0158 return static_cast<std::size_t>(detail::join_cardinality<Rng>());
0159 }
0160
0161 CPP_auto_member
0162 constexpr auto CPP_fun(size)()(
0163 requires(detail::join_cardinality<Rng>() < 0) &&
0164 (range_cardinality<Rng>::value >= 0) &&
0165 forward_range<Rng> &&
0166 sized_range<range_reference_t<Rng>>)
0167 {
0168 range_size_t<range_reference_t<Rng>> n = 0;
0169 RANGES_FOR(auto && inner, outer_)
0170 n += ranges::size(inner);
0171 return n;
0172 }
0173
0174 constexpr Rng base() const
0175 {
0176 return outer_;
0177 }
0178
0179 private:
0180 friend range_access;
0181 Rng outer_{};
0182
0183 template<bool Const>
0184 struct cursor
0185 {
0186 private:
0187 using Parent = meta::conditional_t<Const, join_view const, join_view>;
0188 using COuter = meta::conditional_t<Const, Rng const, Rng>;
0189 using CInner = range_reference_t<COuter>;
0190 using ref_is_glvalue = std::is_reference<CInner>;
0191
0192 Parent * rng_ = nullptr;
0193 iterator_t<COuter> outer_it_{};
0194 iterator_t<CInner> inner_it_{};
0195
0196 void satisfy()
0197 {
0198 for(; outer_it_ != ranges::end(rng_->outer_); ++outer_it_)
0199 {
0200 auto && inner = rng_->update_inner_(outer_it_);
0201 inner_it_ = ranges::begin(inner);
0202 if(inner_it_ != ranges::end(inner))
0203 return;
0204 }
0205 if(RANGES_CONSTEXPR_IF(ref_is_glvalue::value))
0206 inner_it_ = iterator_t<CInner>();
0207 }
0208
0209 public:
0210 using single_pass = meta::bool_<single_pass_iterator_<iterator_t<COuter>> ||
0211 single_pass_iterator_<iterator_t<CInner>> ||
0212 !ref_is_glvalue::value>;
0213 cursor() = default;
0214 template<typename BeginOrEnd>
0215 constexpr cursor(Parent * rng, BeginOrEnd begin_or_end)
0216 : rng_{rng}
0217 , outer_it_(begin_or_end(rng->outer_))
0218 {
0219 satisfy();
0220 }
0221 template(bool Other)(
0222 requires Const AND CPP_NOT(Other) AND
0223 convertible_to<iterator_t<Rng>, iterator_t<COuter>> AND
0224 convertible_to<iterator_t<range_reference_t<Rng>>,
0225 iterator_t<CInner>>)
0226 constexpr cursor(cursor<Other> that)
0227 : rng_(that.rng_)
0228 , outer_it_(std::move(that.outer_it_))
0229 , inner_it_(std::move(that.inner_it_))
0230 {}
0231 CPP_member
0232 constexpr auto arrow()
0233 -> CPP_ret(iterator_t<CInner>)(
0234 requires detail::has_arrow_<iterator_t<CInner>>)
0235 {
0236 return inner_it_;
0237 }
0238 constexpr bool equal(default_sentinel_t) const
0239 {
0240 return outer_it_ == ranges::end(rng_->outer_);
0241 }
0242 CPP_member
0243 constexpr auto equal(cursor const & that) const
0244 -> CPP_ret(bool)(
0245 requires ref_is_glvalue::value &&
0246 equality_comparable<iterator_t<COuter>> &&
0247 equality_comparable<iterator_t<CInner>>)
0248 {
0249 return outer_it_ == that.outer_it_ && inner_it_ == that.inner_it_;
0250 }
0251 constexpr void next()
0252 {
0253 auto && inner_rng = rng_->get_inner_(outer_it_);
0254 if(++inner_it_ == ranges::end(inner_rng))
0255 {
0256 ++outer_it_;
0257 satisfy();
0258 }
0259 }
0260 CPP_member
0261 constexpr auto prev()
0262 -> CPP_ret(void)(
0263 requires ref_is_glvalue::value &&
0264 bidirectional_range<COuter> &&
0265 bidirectional_range<CInner> &&
0266 common_range<CInner>)
0267 {
0268 if(outer_it_ == ranges::end(rng_->outer_))
0269 inner_it_ = ranges::end(*--outer_it_);
0270 while(inner_it_ == ranges::begin(*outer_it_))
0271 inner_it_ = ranges::end(*--outer_it_);
0272 --inner_it_;
0273 }
0274
0275 constexpr auto CPP_auto_fun(read)()(const)
0276 (
0277 return *inner_it_
0278 )
0279 constexpr auto CPP_auto_fun(move)()(const)
0280 (
0281 return iter_move(inner_it_)
0282 )
0283
0284 };
0285 static constexpr bool use_const_always() noexcept
0286 {
0287 return simple_view<Rng>() && std::is_reference<range_reference_t<Rng>>::value;
0288 }
0289 struct end_cursor_fn
0290 {
0291 constexpr auto operator()(join_view * this_, std::true_type) const
0292 {
0293 return cursor<use_const_always()>{this_, ranges::end};
0294 }
0295 constexpr auto operator()(join_view *, std::false_type) const
0296 {
0297 return default_sentinel_t{};
0298 }
0299 };
0300 struct cend_cursor_fn
0301 {
0302 constexpr auto operator()(join_view const * this_, std::true_type) const
0303 {
0304 return cursor<true>{this_, ranges::end};
0305 }
0306 constexpr auto operator()(join_view const *, std::false_type) const
0307 {
0308 return default_sentinel_t{};
0309 }
0310 };
0311
0312 constexpr cursor<use_const_always()> begin_cursor()
0313 {
0314 return {this, ranges::begin};
0315 }
0316
0317 template(bool Const = true)(
0318 requires Const AND input_range<meta::const_if_c<Const, Rng>> AND
0319 std::is_reference<range_reference_t<meta::const_if_c<Const, Rng>>>::value)
0320 constexpr cursor<Const> begin_cursor() const
0321 {
0322 return {this, ranges::begin};
0323 }
0324
0325 constexpr auto end_cursor()
0326 {
0327 using cond =
0328 meta::bool_<std::is_reference<range_reference_t<Rng>>::value &&
0329 forward_range<Rng> && forward_range<range_reference_t<Rng>> &&
0330 common_range<Rng> && common_range<range_reference_t<Rng>>>;
0331 return end_cursor_fn{}(this, cond{});
0332 }
0333
0334 template(bool Const = true)(
0335 requires Const AND input_range<meta::const_if_c<Const, Rng>> AND
0336 std::is_reference<range_reference_t<meta::const_if_c<Const, Rng>>>::value)
0337 constexpr auto end_cursor() const
0338 {
0339 using CRng = meta::const_if_c<Const, Rng>;
0340 using cond =
0341 meta::bool_<std::is_reference<range_reference_t<CRng>>::value &&
0342 forward_range<CRng> &&
0343 forward_range<range_reference_t<CRng>> &&
0344 common_range<CRng> && common_range<range_reference_t<CRng>>>;
0345 return cend_cursor_fn{}(this, cond{});
0346 }
0347 };
0348
0349
0350
0351 template<typename Rng, typename ValRng>
0352 struct join_with_view
0353 : view_facade<join_with_view<Rng, ValRng>, detail::join_cardinality<Rng, ValRng>()>
0354 , private detail::join_view_inner<Rng>
0355 {
0356 CPP_assert(input_range<Rng>);
0357 CPP_assert(input_range<range_reference_t<Rng>>);
0358 CPP_assert(forward_range<ValRng>);
0359 CPP_assert(
0360 common_with<range_value_t<range_reference_t<Rng>>, range_value_t<ValRng>>);
0361 CPP_assert(semiregular<common_type_t<range_value_t<range_reference_t<Rng>>,
0362 range_value_t<ValRng>>>);
0363
0364 join_with_view() = default;
0365 join_with_view(Rng rng, ValRng val)
0366 : outer_(views::all(std::move(rng)))
0367 , val_(views::all(std::move(val)))
0368 {}
0369 CPP_member
0370 static constexpr auto size()
0371 -> CPP_ret(std::size_t)(
0372 requires (detail::join_cardinality<Rng, ValRng>() >= 0))
0373 {
0374 return static_cast<std::size_t>(detail::join_cardinality<Rng, ValRng>());
0375 }
0376 CPP_auto_member
0377 auto CPP_fun(size)()(const
0378 requires(detail::join_cardinality<Rng, ValRng>() < 0) &&
0379 (range_cardinality<Rng>::value >= 0) && forward_range<Rng> &&
0380 sized_range<range_reference_t<Rng>> && sized_range<ValRng>)
0381 {
0382 range_size_t<range_reference_t<Rng>> n = 0;
0383 RANGES_FOR(auto && inner, outer_)
0384 n += ranges::size(inner);
0385 return n + (range_cardinality<Rng>::value == 0
0386 ? 0
0387 : ranges::size(val_) * (range_cardinality<Rng>::value - 1));
0388 }
0389
0390 private:
0391 friend range_access;
0392 using Outer = views::all_t<Rng>;
0393
0394 using Inner = views::all_t<range_reference_t<Outer> &>;
0395
0396 Outer outer_{};
0397 views::all_t<ValRng> val_{};
0398
0399 class cursor
0400 {
0401 join_with_view * rng_ = nullptr;
0402 iterator_t<Outer> outer_it_{};
0403 variant<iterator_t<ValRng>, iterator_t<Inner>> cur_{};
0404
0405 void satisfy()
0406 {
0407 while(true)
0408 {
0409 if(cur_.index() == 0)
0410 {
0411 if(ranges::get<0>(cur_) != ranges::end(rng_->val_))
0412 break;
0413
0414 auto && inner = rng_->update_inner_(outer_it_);
0415 ranges::emplace<1>(cur_, ranges::begin(inner));
0416 }
0417 else
0418 {
0419 auto && inner = rng_->get_inner_(outer_it_);
0420 if(ranges::get<1>(cur_) != ranges::end(inner))
0421 break;
0422 if(++outer_it_ == ranges::end(rng_->outer_))
0423 break;
0424 ranges::emplace<0>(cur_, ranges::begin(rng_->val_));
0425 }
0426 }
0427 }
0428
0429 public:
0430 using value_type = common_type_t<range_value_t<Inner>, range_value_t<ValRng>>;
0431 using reference =
0432 common_reference_t<range_reference_t<Inner>, range_reference_t<ValRng>>;
0433 using rvalue_reference = common_reference_t<range_rvalue_reference_t<Inner>,
0434 range_rvalue_reference_t<ValRng>>;
0435 using single_pass = std::true_type;
0436 cursor() = default;
0437 cursor(join_with_view * rng)
0438 : rng_{rng}
0439 , outer_it_(ranges::begin(rng->outer_))
0440 {
0441 if(outer_it_ != ranges::end(rng->outer_))
0442 {
0443 auto && inner = rng_->update_inner_(outer_it_);
0444 ranges::emplace<1>(cur_, ranges::begin(inner));
0445 satisfy();
0446 }
0447 }
0448 bool equal(default_sentinel_t) const
0449 {
0450 return outer_it_ == ranges::end(rng_->outer_);
0451 }
0452 void next()
0453 {
0454
0455 if(cur_.index() == 0)
0456 {
0457 auto & it = ranges::get<0>(cur_);
0458 RANGES_ASSERT(it != ranges::end(rng_->val_));
0459 ++it;
0460 }
0461 else
0462 {
0463 auto & it = ranges::get<1>(cur_);
0464 #ifndef NDEBUG
0465 auto && inner = rng_->get_inner_(outer_it_);
0466 RANGES_ASSERT(it != ranges::end(inner));
0467 #endif
0468 ++it;
0469 }
0470 satisfy();
0471 }
0472 reference read() const
0473 {
0474
0475 if(cur_.index() == 0)
0476 return *ranges::get<0>(cur_);
0477 else
0478 return *ranges::get<1>(cur_);
0479 }
0480 rvalue_reference move() const
0481 {
0482
0483
0484 if(cur_.index() == 0)
0485 return iter_move(ranges::get<0>(cur_));
0486 else
0487 return iter_move(ranges::get<1>(cur_));
0488 }
0489 };
0490 cursor begin_cursor()
0491 {
0492 return {this};
0493 }
0494 };
0495
0496 namespace views
0497 {
0498
0499
0500
0501
0502
0503
0504 template(typename Rng)(
0505 concept (joinable_range_)(Rng),
0506 input_range<range_reference_t<Rng>>
0507 );
0508
0509
0510 template<typename Rng>
0511 CPP_concept joinable_range =
0512 viewable_range<Rng> && input_range<Rng> &&
0513 CPP_concept_ref(views::joinable_range_, Rng);
0514
0515
0516
0517 template(typename Rng, typename ValRng)(
0518 concept (joinable_with_range_)(Rng, ValRng),
0519 common_with<
0520 range_value_t<ValRng>,
0521 range_value_t<range_reference_t<Rng>>> AND
0522 semiregular<
0523 common_type_t<
0524 range_value_t<ValRng>,
0525 range_value_t<range_reference_t<Rng>>>> AND
0526 common_reference_with<
0527 range_reference_t<ValRng>,
0528 range_reference_t<range_reference_t<Rng>>> AND
0529 common_reference_with<
0530 range_rvalue_reference_t<ValRng>,
0531 range_rvalue_reference_t<range_reference_t<Rng>>>
0532 );
0533
0534
0535 template<typename Rng, typename ValRng>
0536 CPP_concept joinable_with_range =
0537 joinable_range<Rng> &&
0538 viewable_range<ValRng> && forward_range<ValRng> &&
0539 CPP_concept_ref(views::joinable_with_range_, Rng, ValRng);
0540
0541
0542
0543 struct cpp20_join_fn
0544 {
0545 template(typename Rng)(
0546 requires joinable_range<Rng>)
0547 join_view<all_t<Rng>> operator()(Rng && rng) const
0548 {
0549 return join_view<all_t<Rng>>{all(static_cast<Rng &&>(rng))};
0550 }
0551 };
0552
0553 struct join_base_fn : cpp20_join_fn
0554 {
0555 private:
0556 template<typename Rng>
0557 using inner_value_t = range_value_t<range_reference_t<Rng>>;
0558 public:
0559 using cpp20_join_fn::operator();
0560
0561 template(typename Rng)(
0562 requires joinable_with_range<Rng, single_view<inner_value_t<Rng>>>)
0563 join_with_view<all_t<Rng>, single_view<inner_value_t<Rng>>>
0564 operator()(Rng && rng, inner_value_t<Rng> v) const
0565 {
0566 return {all(static_cast<Rng &&>(rng)), single(std::move(v))};
0567 }
0568
0569 template(typename Rng, typename ValRng)(
0570 requires joinable_with_range<Rng, ValRng>)
0571 join_with_view<all_t<Rng>, all_t<ValRng>>
0572 operator()(Rng && rng, ValRng && val) const
0573 {
0574 return {all(static_cast<Rng &&>(rng)), all(static_cast<ValRng &&>(val))};
0575 }
0576
0577
0578 template<typename Rng, typename T>
0579 invoke_result_t<join_base_fn, Rng, T &>
0580 operator()(Rng && rng, detail::reference_wrapper_<T> r) const
0581 {
0582 return (*this)(static_cast<Rng &&>(rng), r.get());
0583 }
0584
0585 };
0586
0587 struct join_bind_fn
0588 {
0589 template(typename T)(
0590 requires (!joinable_range<T>))
0591 constexpr auto operator()(T && t)const
0592 {
0593 return make_view_closure(bind_back(join_base_fn{}, static_cast<T &&>(t)));
0594 }
0595 template(typename T)(
0596 requires (!joinable_range<T &>) AND range<T &>)
0597 constexpr auto operator()(T & t) const
0598 {
0599 return make_view_closure(bind_back(join_base_fn{},
0600 detail::reference_wrapper_<T>(t)));
0601 }
0602 };
0603
0604 struct RANGES_EMPTY_BASES join_fn
0605 : join_base_fn, join_bind_fn
0606 {
0607 using join_base_fn::operator();
0608 using join_bind_fn::operator();
0609 };
0610
0611
0612
0613 RANGES_INLINE_VARIABLE(view_closure<join_fn>, join)
0614 }
0615
0616
0617 #if RANGES_CXX_DEDUCTION_GUIDES >= RANGES_CXX_DEDUCTION_GUIDES_17
0618 template(typename Rng)(
0619 requires views::joinable_range<Rng>)
0620 explicit join_view(Rng &&)
0621 ->join_view<views::all_t<Rng>>;
0622
0623 template(typename Rng, typename ValRng)(
0624 requires views::joinable_with_range<Rng, ValRng>)
0625 explicit join_with_view(Rng &&, ValRng &&)
0626 ->join_with_view<views::all_t<Rng>, views::all_t<ValRng>>;
0627 #endif
0628
0629 namespace cpp20
0630 {
0631 namespace views
0632 {
0633 RANGES_INLINE_VARIABLE(
0634 ranges::views::view_closure<ranges::views::cpp20_join_fn>, join)
0635 }
0636 template(typename Rng)(
0637 requires input_range<Rng> AND view_<Rng> AND
0638 input_range<iter_reference_t<iterator_t<Rng>>>)
0639 using join_view = ranges::join_view<Rng>;
0640 }
0641 }
0642
0643 #include <range/v3/detail/epilogue.hpp>
0644
0645 #include <range/v3/detail/satisfy_boost_range.hpp>
0646 RANGES_SATISFY_BOOST_RANGE(::ranges::join_view)
0647 RANGES_SATISFY_BOOST_RANGE(::ranges::join_with_view)
0648
0649 #endif