File indexing completed on 2025-01-18 10:09:57
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010
0011
0012
0013
0014
0015 #ifndef RANGES_V3_VIEW_SET_ALGORITHM_HPP
0016 #define RANGES_V3_VIEW_SET_ALGORITHM_HPP
0017
0018 #include <algorithm>
0019 #include <iterator>
0020 #include <type_traits>
0021 #include <utility>
0022
0023 #include <meta/meta.hpp>
0024
0025 #include <range/v3/range_fwd.hpp>
0026
0027 #include <range/v3/functional/comparisons.hpp>
0028 #include <range/v3/functional/identity.hpp>
0029 #include <range/v3/functional/invoke.hpp>
0030 #include <range/v3/iterator/default_sentinel.hpp>
0031 #include <range/v3/range/access.hpp>
0032 #include <range/v3/range/primitives.hpp>
0033 #include <range/v3/range/traits.hpp>
0034 #include <range/v3/utility/move.hpp>
0035 #include <range/v3/utility/semiregular_box.hpp>
0036 #include <range/v3/utility/static_const.hpp>
0037 #include <range/v3/view/all.hpp>
0038 #include <range/v3/view/facade.hpp>
0039 #include <range/v3/view/view.hpp>
0040
0041 #include <range/v3/detail/prologue.hpp>
0042
0043 namespace ranges
0044 {
0045
0046
0047
0048
0049 namespace detail
0050 {
0051 template<typename Rng1, typename Rng2, typename C, typename P1, typename P2,
0052 template<bool, typename...> class Cursor, cardinality Cardinality>
0053 struct set_algorithm_view
0054 : view_facade<set_algorithm_view<Rng1, Rng2, C, P1, P2, Cursor, Cardinality>,
0055 Cardinality>
0056 {
0057 private:
0058 friend range_access;
0059 semiregular_box_t<C> pred_;
0060 semiregular_box_t<P1> proj1_;
0061 semiregular_box_t<P2> proj2_;
0062 Rng1 rng1_;
0063 Rng2 rng2_;
0064
0065 template<bool IsConst>
0066 using cursor = Cursor<IsConst, Rng1, Rng2, C, P1, P2>;
0067
0068 cursor<simple_view<Rng1>() && simple_view<Rng2>()> begin_cursor()
0069 {
0070 return {pred_,
0071 proj1_,
0072 proj2_,
0073 ranges::begin(rng1_),
0074 ranges::end(rng1_),
0075 ranges::begin(rng2_),
0076 ranges::end(rng2_)};
0077 }
0078 CPP_member
0079 auto begin_cursor() const
0080 -> CPP_ret(cursor<true>)(
0081 requires range<Rng1 const> && range<Rng2 const>)
0082 {
0083 return {pred_,
0084 proj1_,
0085 proj2_,
0086 ranges::begin(rng1_),
0087 ranges::end(rng1_),
0088 ranges::begin(rng2_),
0089 ranges::end(rng2_)};
0090 }
0091
0092 public:
0093 set_algorithm_view() = default;
0094 set_algorithm_view(Rng1 rng1, Rng2 rng2, C pred, P1 proj1, P2 proj2)
0095 : pred_(std::move(pred))
0096 , proj1_(std::move(proj1))
0097 , proj2_(std::move(proj2))
0098 , rng1_(std::move(rng1))
0099 , rng2_(std::move(rng2))
0100 {}
0101 };
0102
0103 template<bool IsConst, typename Rng1, typename Rng2, typename C, typename P1,
0104 typename P2>
0105 struct set_difference_cursor
0106 {
0107 private:
0108 friend struct set_difference_cursor<!IsConst, Rng1, Rng2, C, P1, P2>;
0109 using pred_ref_ = semiregular_box_ref_or_val_t<C, IsConst>;
0110 using proj1_ref_ = semiregular_box_ref_or_val_t<P1, IsConst>;
0111 using proj2_ref_ = semiregular_box_ref_or_val_t<P2, IsConst>;
0112 pred_ref_ pred_;
0113 proj1_ref_ proj1_;
0114 proj2_ref_ proj2_;
0115
0116 template<typename T>
0117 using constify_if = meta::const_if_c<IsConst, T>;
0118
0119 using R1 = constify_if<Rng1>;
0120 using R2 = constify_if<Rng2>;
0121
0122 iterator_t<R1> it1_;
0123 sentinel_t<R1> end1_;
0124
0125 iterator_t<R2> it2_;
0126 sentinel_t<R2> end2_;
0127
0128 void satisfy()
0129 {
0130 while(it1_ != end1_)
0131 {
0132 if(it2_ == end2_)
0133 return;
0134
0135 if(invoke(pred_, invoke(proj1_, *it1_), invoke(proj2_, *it2_)))
0136 return;
0137
0138 if(!invoke(pred_, invoke(proj2_, *it2_), invoke(proj1_, *it1_)))
0139 ++it1_;
0140
0141 ++it2_;
0142 }
0143 }
0144
0145 public:
0146 using value_type = range_value_t<constify_if<Rng1>>;
0147 using single_pass = meta::or_c<single_pass_iterator_<iterator_t<R1>>,
0148 single_pass_iterator_<iterator_t<R2>>>;
0149
0150 set_difference_cursor() = default;
0151 set_difference_cursor(pred_ref_ pred, proj1_ref_ proj1, proj2_ref_ proj2,
0152 iterator_t<R1> it1, sentinel_t<R1> end1,
0153 iterator_t<R2> it2, sentinel_t<R2> end2)
0154 : pred_(std::move(pred))
0155 , proj1_(std::move(proj1))
0156 , proj2_(std::move(proj2))
0157 , it1_(std::move(it1))
0158 , end1_(std::move(end1))
0159 , it2_(std::move(it2))
0160 , end2_(std::move(end2))
0161 {
0162 satisfy();
0163 }
0164 template(bool Other)(
0165 requires IsConst && CPP_NOT(Other))
0166 set_difference_cursor(
0167 set_difference_cursor<Other, Rng1, Rng2, C, P1, P2> that)
0168 : pred_(std::move(that.pred_))
0169 , proj1_(std::move(that.proj1_))
0170 , proj2_(std::move(that.proj2_))
0171 , it1_(std::move(that.it1_))
0172 , end1_(std::move(that.end1_))
0173 , it2_(std::move(that.it2_))
0174 , end2_(std::move(that.end2_))
0175 {}
0176
0177 auto CPP_auto_fun(read)()(const)
0178 (
0179 return *it1_
0180 )
0181
0182 void next()
0183 {
0184 ++it1_;
0185 satisfy();
0186 }
0187 CPP_member
0188 auto equal(set_difference_cursor const & that) const
0189 -> CPP_ret(bool)(
0190 requires forward_range<Rng1>)
0191 {
0192
0193 return it1_ == that.it1_;
0194 }
0195 bool equal(default_sentinel_t) const
0196 {
0197 return it1_ == end1_;
0198 }
0199
0200 auto CPP_auto_fun(move)()(const)
0201 (
0202 return iter_move(it1_)
0203 )
0204
0205 };
0206
0207 constexpr cardinality set_difference_cardinality(cardinality c1, cardinality c2)
0208 {
0209 return (c1 == unknown)
0210 ? unknown
0211 : (c1 >= 0) || (c1 == finite) ? finite :
0212 (c2 >= 0) || (c2 == finite) ? infinite : unknown;
0213 }
0214 }
0215
0216
0217 template<typename Rng1, typename Rng2, typename C, typename P1, typename P2>
0218 using set_difference_view =
0219 detail::set_algorithm_view<Rng1, Rng2, C, P1, P2, detail::set_difference_cursor,
0220 detail::set_difference_cardinality(
0221 range_cardinality<Rng1>::value,
0222 range_cardinality<Rng2>::value)>;
0223
0224 namespace views
0225 {
0226 struct set_difference_base_fn
0227 {
0228 template(typename Rng1, typename Rng2, typename C = less,
0229 typename P1 = identity, typename P2 = identity)(
0230 requires
0231 viewable_range<Rng1> AND input_range<Rng1> AND
0232 viewable_range<Rng2> AND input_range<Rng2> AND
0233 indirect_relation<C,
0234 projected<iterator_t<Rng1>, P1>,
0235 projected<iterator_t<Rng2>, P2>>)
0236 set_difference_view<all_t<Rng1>, all_t<Rng2>, C, P1, P2>
0237 operator()(Rng1 && rng1,
0238 Rng2 && rng2,
0239 C pred = C{},
0240 P1 proj1 = P1{},
0241 P2 proj2 = P2{}) const
0242 {
0243 return {all(static_cast<Rng1 &&>(rng1)),
0244 all(static_cast<Rng2 &&>(rng2)),
0245 std::move(pred),
0246 std::move(proj1),
0247 std::move(proj2)};
0248 }
0249 };
0250
0251 struct set_difference_fn : set_difference_base_fn
0252 {
0253 using set_difference_base_fn::operator();
0254
0255 template(typename Rng2, typename C = less, typename P1 = identity,
0256 typename P2 = identity)(
0257 requires viewable_range<Rng2> AND input_range<Rng2> AND (!range<C>))
0258 constexpr auto operator()(Rng2 && rng2,
0259 C && pred = C{},
0260 P1 proj1 = P1{},
0261 P2 proj2 = P2{}) const
0262 {
0263 return make_view_closure(bind_back(set_difference_base_fn{},
0264 all(rng2),
0265 static_cast<C &&>(pred),
0266 std::move(proj1),
0267 std::move(proj2)));
0268 }
0269 };
0270
0271
0272 RANGES_INLINE_VARIABLE(set_difference_fn, set_difference)
0273 }
0274
0275
0276 namespace detail
0277 {
0278 template<bool IsConst, typename Rng1, typename Rng2, typename C, typename P1,
0279 typename P2>
0280 struct set_intersection_cursor
0281 {
0282 private:
0283 friend struct set_intersection_cursor<!IsConst, Rng1, Rng2, C, P1, P2>;
0284 using pred_ref_ = semiregular_box_ref_or_val_t<C, IsConst>;
0285 using proj1_ref_ = semiregular_box_ref_or_val_t<P1, IsConst>;
0286 using proj2_ref_ = semiregular_box_ref_or_val_t<P2, IsConst>;
0287 pred_ref_ pred_;
0288 proj1_ref_ proj1_;
0289 proj2_ref_ proj2_;
0290
0291 template<typename T>
0292 using constify_if = meta::const_if_c<IsConst, T>;
0293
0294 using R1 = constify_if<Rng1>;
0295 using R2 = constify_if<Rng2>;
0296
0297 iterator_t<R1> it1_;
0298 sentinel_t<R1> end1_;
0299
0300 iterator_t<R2> it2_;
0301 sentinel_t<R2> end2_;
0302
0303 void satisfy()
0304 {
0305 while(it1_ != end1_ && it2_ != end2_)
0306 {
0307 if(invoke(pred_, invoke(proj1_, *it1_), invoke(proj2_, *it2_)))
0308 ++it1_;
0309 else
0310 {
0311 if(!invoke(pred_, invoke(proj2_, *it2_), invoke(proj1_, *it1_)))
0312 return;
0313 ++it2_;
0314 }
0315 }
0316 }
0317
0318 public:
0319 using value_type = range_value_t<R1>;
0320 using single_pass = meta::or_c<single_pass_iterator_<iterator_t<R1>>,
0321 single_pass_iterator_<iterator_t<R2>>>;
0322
0323 set_intersection_cursor() = default;
0324 set_intersection_cursor(pred_ref_ pred, proj1_ref_ proj1, proj2_ref_ proj2,
0325 iterator_t<R1> it1, sentinel_t<R1> end1,
0326 iterator_t<R2> it2, sentinel_t<R2> end2)
0327 : pred_(std::move(pred))
0328 , proj1_(std::move(proj1))
0329 , proj2_(std::move(proj2))
0330 , it1_(std::move(it1))
0331 , end1_(std::move(end1))
0332 , it2_(std::move(it2))
0333 , end2_(std::move(end2))
0334 {
0335 satisfy();
0336 }
0337 template(bool Other)(
0338 requires IsConst && CPP_NOT(Other))
0339 set_intersection_cursor(
0340 set_intersection_cursor<Other, Rng1, Rng2, C, P1, P2> that)
0341 : pred_(std::move(that.pred_))
0342 , proj1_(std::move(that.proj1_))
0343 , proj2_(std::move(that.proj2_))
0344 , it1_(std::move(that.it1_))
0345 , end1_(std::move(that.end1_))
0346 , it2_(std::move(that.it2_))
0347 , end2_(std::move(that.end2_))
0348 {}
0349
0350 auto CPP_auto_fun(read)()(const)
0351 (
0352 return *it1_
0353 )
0354
0355 void next()
0356 {
0357 ++it1_;
0358 ++it2_;
0359 satisfy();
0360 }
0361 CPP_member
0362 auto equal(set_intersection_cursor const & that) const
0363 -> CPP_ret(bool)(
0364 requires forward_range<Rng1>)
0365 {
0366
0367 return it1_ == that.it1_;
0368 }
0369 bool equal(default_sentinel_t) const
0370 {
0371 return (it1_ == end1_) || (it2_ == end2_);
0372 }
0373
0374 auto CPP_auto_fun(move)()(const)
0375 (
0376 return iter_move(it1_)
0377 )
0378
0379 };
0380
0381 constexpr cardinality set_intersection_cardinality(cardinality c1, cardinality c2)
0382 {
0383 return (c1 == unknown) || (c2 == unknown)
0384 ? unknown
0385 : (c1 >= 0 || c1 == finite) || (c2 >= 0 || c2 == finite) ? finite
0386 : unknown;
0387 }
0388 }
0389
0390
0391 template<typename Rng1, typename Rng2, typename C, typename P1, typename P2>
0392 using set_intersection_view =
0393 detail::set_algorithm_view<Rng1, Rng2, C, P1, P2, detail::set_intersection_cursor,
0394 detail::set_intersection_cardinality(
0395 range_cardinality<Rng1>::value,
0396 range_cardinality<Rng2>::value)>;
0397
0398 namespace views
0399 {
0400 struct set_intersection_base_fn
0401 {
0402 template(typename Rng1, typename Rng2, typename C = less,
0403 typename P1 = identity, typename P2 = identity)(
0404 requires viewable_range<Rng1> AND input_range<Rng1> AND
0405 viewable_range<Rng2> AND input_range<Rng2> AND
0406 indirect_relation<
0407 C,
0408 projected<iterator_t<Rng1>, P1>,
0409 projected<iterator_t<Rng2>, P2>>)
0410 set_intersection_view<all_t<Rng1>, all_t<Rng2>, C, P1, P2>
0411 operator()(Rng1 && rng1,
0412 Rng2 && rng2,
0413 C pred = C{},
0414 P1 proj1 = P1{},
0415 P2 proj2 = P2{}) const
0416 {
0417 return {all(static_cast<Rng1 &&>(rng1)),
0418 all(static_cast<Rng2 &&>(rng2)),
0419 std::move(pred),
0420 std::move(proj1),
0421 std::move(proj2)};
0422 }
0423 };
0424
0425 struct set_intersection_fn : set_intersection_base_fn
0426 {
0427 using set_intersection_base_fn::operator();
0428
0429 template(typename Rng2, typename C = less, typename P1 = identity,
0430 typename P2 = identity)(
0431 requires viewable_range<Rng2> AND input_range<Rng2> AND (!range<C>))
0432 constexpr auto operator()(Rng2 && rng2,
0433 C && pred = C{},
0434 P1 proj1 = P1{},
0435 P2 proj2 = P2{}) const
0436 {
0437 return make_view_closure(bind_back(set_intersection_base_fn{},
0438 all(rng2),
0439 static_cast<C &&>(pred),
0440 std::move(proj1),
0441 std::move(proj2)));
0442 }
0443 };
0444
0445
0446 RANGES_INLINE_VARIABLE(set_intersection_fn, set_intersection)
0447 }
0448
0449
0450 namespace detail
0451 {
0452 template<bool IsConst, typename Rng1, typename Rng2, typename C, typename P1,
0453 typename P2>
0454 struct set_union_cursor
0455 {
0456 private:
0457 friend struct set_union_cursor<!IsConst, Rng1, Rng2, C, P1, P2>;
0458 using pred_ref_ = semiregular_box_ref_or_val_t<C, IsConst>;
0459 using proj1_ref_ = semiregular_box_ref_or_val_t<P1, IsConst>;
0460 using proj2_ref_ = semiregular_box_ref_or_val_t<P2, IsConst>;
0461 pred_ref_ pred_;
0462 proj1_ref_ proj1_;
0463 proj2_ref_ proj2_;
0464
0465 template<typename T>
0466 using constify_if = meta::const_if_c<IsConst, T>;
0467
0468 using R1 = constify_if<Rng1>;
0469 using R2 = constify_if<Rng2>;
0470
0471 iterator_t<R1> it1_;
0472 sentinel_t<R1> end1_;
0473
0474 iterator_t<R2> it2_;
0475 sentinel_t<R2> end2_;
0476
0477 enum class state_t
0478 {
0479 FIRST,
0480 SECOND
0481 } state;
0482
0483 void satisfy()
0484 {
0485 if(it1_ == end1_)
0486 {
0487 state = state_t::SECOND;
0488 return;
0489 }
0490
0491 if(it2_ == end2_)
0492 {
0493 state = state_t::FIRST;
0494 return;
0495 }
0496
0497 if(invoke(pred_, invoke(proj2_, *it2_), invoke(proj1_, *it1_)))
0498 {
0499 state = state_t::SECOND;
0500 return;
0501 }
0502
0503 if(!invoke(pred_, invoke(proj1_, *it1_), invoke(proj2_, *it2_)))
0504 ++it2_;
0505
0506 state = state_t::FIRST;
0507 }
0508
0509 public:
0510 using value_type = common_type_t<range_value_t<R1>, range_value_t<R2>>;
0511 using reference_type =
0512 common_reference_t<range_reference_t<R1>, range_reference_t<R2>>;
0513 using rvalue_reference_type =
0514 common_reference_t<range_rvalue_reference_t<R1>,
0515 range_rvalue_reference_t<R2>>;
0516 using single_pass = meta::or_c<single_pass_iterator_<iterator_t<R1>>,
0517 single_pass_iterator_<iterator_t<R2>>>;
0518
0519 set_union_cursor() = default;
0520 set_union_cursor(pred_ref_ pred, proj1_ref_ proj1, proj2_ref_ proj2,
0521 iterator_t<R1> it1, sentinel_t<R1> end1, iterator_t<R2> it2,
0522 sentinel_t<R2> end2)
0523 : pred_(std::move(pred))
0524 , proj1_(std::move(proj1))
0525 , proj2_(std::move(proj2))
0526 , it1_(std::move(it1))
0527 , end1_(std::move(end1))
0528 , it2_(std::move(it2))
0529 , end2_(std::move(end2))
0530 {
0531 satisfy();
0532 }
0533 template(bool Other)(
0534 requires IsConst AND CPP_NOT(Other))
0535 set_union_cursor(set_union_cursor<Other, Rng1, Rng2, C, P1, P2> that)
0536 : pred_(std::move(that.pred_))
0537 , proj1_(std::move(that.proj1_))
0538 , proj2_(std::move(that.proj2_))
0539 , it1_(std::move(that.it1_))
0540 , end1_(std::move(that.end1_))
0541 , it2_(std::move(that.it2_))
0542 , end2_(std::move(that.end2_))
0543 {}
0544 reference_type read() const noexcept(noexcept(*it1_) && noexcept(*it2_))
0545 {
0546 if(state == state_t::SECOND)
0547 return *it2_;
0548 else
0549 return *it1_;
0550 }
0551 void next()
0552 {
0553 if(state == state_t::FIRST)
0554 ++it1_;
0555 else
0556 ++it2_;
0557 satisfy();
0558 }
0559 CPP_member
0560 auto equal(set_union_cursor const & that) const
0561 -> CPP_ret(bool)(
0562 requires forward_range<Rng1> && forward_range<Rng2>)
0563 {
0564
0565 return (it1_ == that.it1_) && (it2_ == that.it2_);
0566 }
0567 bool equal(default_sentinel_t) const
0568 {
0569 return (it1_ == end1_) && (it2_ == end2_);
0570 }
0571 rvalue_reference_type move() const
0572 noexcept(noexcept(iter_move(it1_)) && noexcept(iter_move(it2_)))
0573 {
0574 if(state == state_t::SECOND)
0575 return iter_move(it2_);
0576 else
0577 return iter_move(it1_);
0578 }
0579 };
0580
0581 constexpr cardinality set_union_cardinality(cardinality c1, cardinality c2)
0582 {
0583 return (c1 == infinite) || (c2 == infinite)
0584 ? infinite
0585 : (c1 == unknown) || (c2 == unknown) ? unknown : finite;
0586 }
0587 }
0588
0589
0590 template<typename Rng1, typename Rng2, typename C, typename P1, typename P2>
0591 using set_union_view =
0592 detail::set_algorithm_view<Rng1, Rng2, C, P1, P2, detail::set_union_cursor,
0593 detail::set_union_cardinality(
0594 range_cardinality<Rng1>::value,
0595 range_cardinality<Rng2>::value)>;
0596
0597 namespace views
0598 {
0599 struct set_union_base_fn
0600 {
0601 public:
0602 template(typename Rng1, typename Rng2, typename C = less,
0603 typename P1 = identity, typename P2 = identity)(
0604 requires
0605 viewable_range<Rng1> AND input_range<Rng1> AND
0606 viewable_range<Rng2> AND input_range<Rng2> AND
0607 common_with<range_value_t<Rng1>, range_value_t<Rng2>> AND
0608 common_reference_with<range_reference_t<Rng1>,
0609 range_reference_t<Rng2>> AND
0610 common_reference_with<range_rvalue_reference_t<Rng1>,
0611 range_rvalue_reference_t<Rng2>> AND
0612 indirect_relation<C,
0613 projected<iterator_t<Rng1>, P1>,
0614 projected<iterator_t<Rng2>, P2>>)
0615 set_union_view<all_t<Rng1>, all_t<Rng2>, C, P1, P2>
0616 operator()(Rng1 && rng1,
0617 Rng2 && rng2,
0618 C pred = C{},
0619 P1 proj1 = P1{},
0620 P2 proj2 = P2{}) const
0621 {
0622 return {all(static_cast<Rng1 &&>(rng1)),
0623 all(static_cast<Rng2 &&>(rng2)),
0624 std::move(pred),
0625 std::move(proj1),
0626 std::move(proj2)};
0627 }
0628 };
0629
0630 struct set_union_fn : set_union_base_fn
0631 {
0632 using set_union_base_fn::operator();
0633
0634 template(typename Rng2, typename C = less, typename P1 = identity,
0635 typename P2 = identity)(
0636 requires viewable_range<Rng2> AND input_range<Rng2> AND (!range<C>))
0637 constexpr auto operator()(Rng2 && rng2,
0638 C && pred = C{},
0639 P1 proj1 = P1{},
0640 P2 proj2 = P2{}) const
0641 {
0642 return make_view_closure(bind_back(set_union_base_fn{},
0643 all(rng2),
0644 static_cast<C &&>(pred),
0645 std::move(proj1),
0646 std::move(proj2)));
0647 }
0648 };
0649
0650
0651 RANGES_INLINE_VARIABLE(set_union_fn, set_union)
0652 }
0653
0654
0655 namespace detail
0656 {
0657 template<bool IsConst, typename Rng1, typename Rng2, typename C, typename P1,
0658 typename P2>
0659 struct set_symmetric_difference_cursor
0660 {
0661 private:
0662 friend struct set_symmetric_difference_cursor<!IsConst, Rng1, Rng2, C, P1,
0663 P2>;
0664 using pred_ref_ = semiregular_box_ref_or_val_t<C, IsConst>;
0665 using proj1_ref_ = semiregular_box_ref_or_val_t<P1, IsConst>;
0666 using proj2_ref_ = semiregular_box_ref_or_val_t<P2, IsConst>;
0667 pred_ref_ pred_;
0668 proj1_ref_ proj1_;
0669 proj2_ref_ proj2_;
0670
0671 template<typename T>
0672 using constify_if = meta::const_if_c<IsConst, T>;
0673
0674 using R1 = constify_if<Rng1>;
0675 using R2 = constify_if<Rng2>;
0676
0677 iterator_t<R1> it1_;
0678 sentinel_t<R1> end1_;
0679
0680 iterator_t<R2> it2_;
0681 sentinel_t<R2> end2_;
0682
0683 enum class state_t
0684 {
0685 FIRST,
0686 SECOND,
0687 ONLY_FIRST,
0688 ONLY_SECOND
0689 } state;
0690
0691 void satisfy()
0692 {
0693 while(it1_ != end1_)
0694 {
0695 if(it2_ == end2_)
0696 {
0697 state = state_t::ONLY_FIRST;
0698 return;
0699 }
0700
0701 if(invoke(pred_, invoke(proj1_, *it1_), invoke(proj2_, *it2_)))
0702 {
0703 state = state_t::FIRST;
0704 return;
0705 }
0706 else
0707 {
0708 if(invoke(pred_, invoke(proj2_, *it2_), invoke(proj1_, *it1_)))
0709 {
0710 state = state_t::SECOND;
0711 return;
0712 }
0713 else
0714 {
0715 ++it1_;
0716 ++it2_;
0717 }
0718 }
0719 }
0720 state = state_t::ONLY_SECOND;
0721 }
0722
0723 public:
0724 using value_type = common_type_t<range_value_t<R1>, range_value_t<R2>>;
0725 using reference_type =
0726 common_reference_t<range_reference_t<R1>, range_reference_t<R2>>;
0727 using rvalue_reference_type =
0728 common_reference_t<range_rvalue_reference_t<R1>,
0729 range_rvalue_reference_t<R2>>;
0730 using single_pass = meta::or_c<single_pass_iterator_<iterator_t<R1>>,
0731 single_pass_iterator_<iterator_t<R2>>>;
0732
0733 set_symmetric_difference_cursor() = default;
0734 set_symmetric_difference_cursor(pred_ref_ pred, proj1_ref_ proj1,
0735 proj2_ref_ proj2, iterator_t<R1> it1,
0736 sentinel_t<R1> end1, iterator_t<R2> it2,
0737 sentinel_t<R2> end2)
0738 : pred_(std::move(pred))
0739 , proj1_(std::move(proj1))
0740 , proj2_(std::move(proj2))
0741 , it1_(std::move(it1))
0742 , end1_(std::move(end1))
0743 , it2_(std::move(it2))
0744 , end2_(std::move(end2))
0745 , state()
0746 {
0747 satisfy();
0748 }
0749 template(bool Other)(
0750 requires IsConst && CPP_NOT(Other))
0751 set_symmetric_difference_cursor(
0752 set_symmetric_difference_cursor<Other, Rng1, Rng2, C, P1, P2> that)
0753 : pred_(std::move(that.pred_))
0754 , proj1_(std::move(that.proj1_))
0755 , proj2_(std::move(that.proj2_))
0756 , it1_(std::move(that.it1_))
0757 , end1_(std::move(that.end1_))
0758 , it2_(std::move(that.it2_))
0759 , end2_(std::move(that.end2_))
0760 , state(that.state)
0761 {}
0762 reference_type read() const noexcept(noexcept(*it1_) && noexcept(*it2_))
0763 {
0764 if(state == state_t::SECOND || state == state_t::ONLY_SECOND)
0765 return *it2_;
0766 else
0767 return *it1_;
0768 }
0769 void next()
0770 {
0771 switch(state)
0772 {
0773 case state_t::FIRST:
0774 ++it1_;
0775 satisfy();
0776 break;
0777 case state_t::ONLY_FIRST:
0778 ++it1_;
0779 break;
0780 case state_t::SECOND:
0781 ++it2_;
0782 satisfy();
0783 break;
0784 case state_t::ONLY_SECOND:
0785 ++it2_;
0786 break;
0787 }
0788 }
0789 CPP_member
0790 auto equal(set_symmetric_difference_cursor const & that) const
0791 -> CPP_ret(bool)(
0792 requires forward_range<R1> && forward_range<R2>)
0793 {
0794
0795 return (it1_ == that.it1_) && (it2_ == that.it2_);
0796 }
0797 bool equal(default_sentinel_t) const
0798 {
0799 return (it1_ == end1_) && (it2_ == end2_);
0800 }
0801 rvalue_reference_type move() const
0802 noexcept(noexcept(iter_move(it1_)) && noexcept(iter_move(it2_)))
0803 {
0804 if(state == state_t::SECOND || state == state_t::ONLY_SECOND)
0805 return iter_move(it2_);
0806 else
0807 return iter_move(it1_);
0808 }
0809 };
0810
0811 constexpr cardinality set_symmetric_difference_cardinality(cardinality c1,
0812 cardinality c2)
0813 {
0814 return (c1 == unknown) || (c2 == unknown)
0815 ? unknown
0816 : (c1 == infinite) != (c2 == infinite)
0817 ? infinite
0818 : (c1 == infinite) && (c2 == infinite) ? unknown : finite;
0819 }
0820
0821 }
0822
0823
0824 template<typename Rng1, typename Rng2, typename C, typename P1, typename P2>
0825 using set_symmetric_difference_view = detail::set_algorithm_view<
0826 Rng1, Rng2, C, P1, P2, detail::set_symmetric_difference_cursor,
0827 detail::set_symmetric_difference_cardinality(range_cardinality<Rng1>::value,
0828 range_cardinality<Rng2>::value)>;
0829
0830 namespace views
0831 {
0832 struct set_symmetric_difference_base_fn
0833 {
0834 template(typename Rng1, typename Rng2, typename C = less,
0835 typename P1 = identity, typename P2 = identity)(
0836 requires
0837 viewable_range<Rng1> AND input_range<Rng1> AND
0838 viewable_range<Rng2> AND input_range<Rng2> AND
0839 common_with<range_value_t<Rng1>, range_value_t<Rng2>> AND
0840 common_reference_with<range_reference_t<Rng1>,
0841 range_reference_t<Rng2>> AND
0842 common_reference_with<range_rvalue_reference_t<Rng1>,
0843 range_rvalue_reference_t<Rng2>> AND
0844 indirect_relation<C,
0845 projected<iterator_t<Rng1>, P1>,
0846 projected<iterator_t<Rng2>, P2>>)
0847 set_symmetric_difference_view<all_t<Rng1>, all_t<Rng2>, C, P1, P2>
0848 operator()(Rng1 && rng1,
0849 Rng2 && rng2,
0850 C pred = C{},
0851 P1 proj1 = P1{},
0852 P2 proj2 = P2{}) const
0853 {
0854 return {all(static_cast<Rng1 &&>(rng1)),
0855 all(static_cast<Rng2 &&>(rng2)),
0856 std::move(pred),
0857 std::move(proj1),
0858 std::move(proj2)};
0859 }
0860 };
0861
0862 struct set_symmetric_difference_fn : set_symmetric_difference_base_fn
0863 {
0864 using set_symmetric_difference_base_fn::operator();
0865
0866 template(typename Rng2, typename C = less, typename P1 = identity,
0867 typename P2 = identity)(
0868 requires viewable_range<Rng2> AND input_range<Rng2> AND (!range<C>))
0869 constexpr auto operator()(Rng2 && rng2,
0870 C && pred = C{},
0871 P1 proj1 = P1{},
0872 P2 proj2 = P2{}) const
0873 {
0874 return make_view_closure(bind_back(set_symmetric_difference_base_fn{},
0875 all(rng2),
0876 static_cast<C &&>(pred),
0877 std::move(proj1),
0878 std::move(proj2)));
0879 }
0880 };
0881
0882
0883 RANGES_INLINE_VARIABLE(set_symmetric_difference_fn, set_symmetric_difference)
0884 }
0885
0886 }
0887
0888 #include <range/v3/detail/epilogue.hpp>
0889
0890 #endif
