Horizon
set_algorithm.hpp
Go to the documentation of this file.
1 // Range v3 library
3 //
4 // Copyright Eric Niebler 2013-present
5 // Copyright Tomislav Ivek 2015-2016
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_SET_ALGORITHM_HPP
16 #define RANGES_V3_VIEW_SET_ALGORITHM_HPP
17 
18 #include <algorithm>
19 #include <iterator>
20 #include <type_traits>
21 #include <utility>
22 
23 #include <meta/meta.hpp>
24 
25 #include <range/v3/range_fwd.hpp>
26 
36 #include <range/v3/utility/static_const.hpp>
37 #include <range/v3/view/all.hpp>
38 #include <range/v3/view/facade.hpp>
39 #include <range/v3/view/view.hpp>
40 
41 #include <range/v3/detail/prologue.hpp>
42 
43 namespace ranges
44 {
47 
49  namespace detail
50  {
51  template<typename Rng1, typename Rng2, typename C, typename P1, typename P2,
52  template<bool, typename...> class Cursor, cardinality Cardinality>
53  struct set_algorithm_view
54  : view_facade<set_algorithm_view<Rng1, Rng2, C, P1, P2, Cursor, Cardinality>,
55  Cardinality>
56  {
57  private:
58  friend range_access;
59  semiregular_box_t<C> pred_;
60  semiregular_box_t<P1> proj1_;
61  semiregular_box_t<P2> proj2_;
62  Rng1 rng1_;
63  Rng2 rng2_;
64 
65  template<bool IsConst>
66  using cursor = Cursor<IsConst, Rng1, Rng2, C, P1, P2>;
67 
68  cursor<simple_view<Rng1>() && simple_view<Rng2>()> begin_cursor()
69  {
70  return {pred_,
71  proj1_,
72  proj2_,
73  ranges::begin(rng1_),
74  ranges::end(rng1_),
75  ranges::begin(rng2_),
76  ranges::end(rng2_)};
77  }
78  CPP_member
79  auto begin_cursor() const //
80  -> CPP_ret(cursor<true>)(
81  requires range<Rng1 const> && range<Rng2 const>)
82  {
83  return {pred_,
84  proj1_,
85  proj2_,
86  ranges::begin(rng1_),
87  ranges::end(rng1_),
88  ranges::begin(rng2_),
89  ranges::end(rng2_)};
90  }
91 
92  public:
93  set_algorithm_view() = default;
94  set_algorithm_view(Rng1 rng1, Rng2 rng2, C pred, P1 proj1, P2 proj2)
95  : pred_(std::move(pred))
96  , proj1_(std::move(proj1))
97  , proj2_(std::move(proj2))
98  , rng1_(std::move(rng1))
99  , rng2_(std::move(rng2))
100  {}
101  };
102 
103  template<bool IsConst, typename Rng1, typename Rng2, typename C, typename P1,
104  typename P2>
105  struct set_difference_cursor
106  {
107  private:
108  friend struct set_difference_cursor<!IsConst, Rng1, Rng2, C, P1, P2>;
109  using pred_ref_ = semiregular_box_ref_or_val_t<C, IsConst>;
110  using proj1_ref_ = semiregular_box_ref_or_val_t<P1, IsConst>;
111  using proj2_ref_ = semiregular_box_ref_or_val_t<P2, IsConst>;
112  pred_ref_ pred_;
113  proj1_ref_ proj1_;
114  proj2_ref_ proj2_;
115 
116  template<typename T>
117  using constify_if = meta::const_if_c<IsConst, T>;
118 
119  using R1 = constify_if<Rng1>;
120  using R2 = constify_if<Rng2>;
121 
122  iterator_t<R1> it1_;
123  sentinel_t<R1> end1_;
124 
125  iterator_t<R2> it2_;
126  sentinel_t<R2> end2_;
127 
128  void satisfy()
129  {
130  while(it1_ != end1_)
131  {
132  if(it2_ == end2_)
133  return;
134 
135  if(invoke(pred_, invoke(proj1_, *it1_), invoke(proj2_, *it2_)))
136  return;
137 
138  if(!invoke(pred_, invoke(proj2_, *it2_), invoke(proj1_, *it1_)))
139  ++it1_;
140 
141  ++it2_;
142  }
143  }
144 
145  public:
146  using value_type = range_value_t<constify_if<Rng1>>;
148  single_pass_iterator_<iterator_t<R2>>>;
149 
150  set_difference_cursor() = default;
151  set_difference_cursor(pred_ref_ pred, proj1_ref_ proj1, proj2_ref_ proj2,
152  iterator_t<R1> it1, sentinel_t<R1> end1,
153  iterator_t<R2> it2, sentinel_t<R2> end2)
154  : pred_(std::move(pred))
155  , proj1_(std::move(proj1))
156  , proj2_(std::move(proj2))
157  , it1_(std::move(it1))
158  , end1_(std::move(end1))
159  , it2_(std::move(it2))
160  , end2_(std::move(end2))
161  {
162  satisfy();
163  }
164  template(bool Other)(
165  requires IsConst && CPP_NOT(Other)) //
166  set_difference_cursor(
167  set_difference_cursor<Other, Rng1, Rng2, C, P1, P2> that)
168  : pred_(std::move(that.pred_))
169  , proj1_(std::move(that.proj1_))
170  , proj2_(std::move(that.proj2_))
171  , it1_(std::move(that.it1_))
172  , end1_(std::move(that.end1_))
173  , it2_(std::move(that.it2_))
174  , end2_(std::move(that.end2_))
175  {}
176  // clang-format off
177  auto CPP_auto_fun(read)()(const)
178  (
179  return *it1_
180  )
181  // clang-format on
182  void next()
183  {
184  ++it1_;
185  satisfy();
186  }
187  CPP_member
188  auto equal(set_difference_cursor const & that) const //
189  -> CPP_ret(bool)(
190  requires forward_range<Rng1>)
191  {
192  // does not support comparing iterators from different ranges
193  return it1_ == that.it1_;
194  }
195  bool equal(default_sentinel_t) const
196  {
197  return it1_ == end1_;
198  }
199  // clang-format off
200  auto CPP_auto_fun(move)()(const)
201  (
202  return iter_move(it1_)
203  )
204  // clang-format on
205  };
206 
207  constexpr cardinality set_difference_cardinality(cardinality c1, cardinality c2)
208  {
209  return (c1 == unknown)
210  ? unknown
211  : (c1 >= 0) || (c1 == finite) ? finite : // else, c1 == infinite
212  (c2 >= 0) || (c2 == finite) ? infinite : unknown;
213  }
214  } // namespace detail
216 
217  template<typename Rng1, typename Rng2, typename C, typename P1, typename P2>
218  using set_difference_view =
219  detail::set_algorithm_view<Rng1, Rng2, C, P1, P2, detail::set_difference_cursor,
220  detail::set_difference_cardinality(
221  range_cardinality<Rng1>::value,
222  range_cardinality<Rng2>::value)>;
223 
224  namespace views
225  {
227  {
228  template(typename Rng1, typename Rng2, typename C = less,
229  typename P1 = identity, typename P2 = identity)(
230  requires //
231  viewable_range<Rng1> AND input_range<Rng1> AND
232  viewable_range<Rng2> AND input_range<Rng2> AND
234  projected<iterator_t<Rng1>, P1>,
235  projected<iterator_t<Rng2>, P2>>)
236  set_difference_view<all_t<Rng1>, all_t<Rng2>, C, P1, P2> //
237  operator()(Rng1 && rng1,
238  Rng2 && rng2,
239  C pred = C{},
240  P1 proj1 = P1{},
241  P2 proj2 = P2{}) const
242  {
243  return {all(static_cast<Rng1 &&>(rng1)),
244  all(static_cast<Rng2 &&>(rng2)),
245  std::move(pred),
246  std::move(proj1),
247  std::move(proj2)};
248  }
249  };
250 
252  {
253  using set_difference_base_fn::operator();
254 
255  template(typename Rng2, typename C = less, typename P1 = identity,
256  typename P2 = identity)(
257  requires viewable_range<Rng2> AND input_range<Rng2> AND (!range<C>))
258  constexpr auto operator()(Rng2 && rng2,
259  C && pred = C{},
260  P1 proj1 = P1{},
261  P2 proj2 = P2{}) const
262  {
263  return make_view_closure(bind_back(set_difference_base_fn{},
264  all(rng2),
265  static_cast<C &&>(pred),
266  std::move(proj1),
267  std::move(proj2)));
268  }
269  };
270 
273  } // namespace views
274 
276  namespace detail
277  {
278  template<bool IsConst, typename Rng1, typename Rng2, typename C, typename P1,
279  typename P2>
280  struct set_intersection_cursor
281  {
282  private:
283  friend struct set_intersection_cursor<!IsConst, Rng1, Rng2, C, P1, P2>;
284  using pred_ref_ = semiregular_box_ref_or_val_t<C, IsConst>;
285  using proj1_ref_ = semiregular_box_ref_or_val_t<P1, IsConst>;
286  using proj2_ref_ = semiregular_box_ref_or_val_t<P2, IsConst>;
287  pred_ref_ pred_;
288  proj1_ref_ proj1_;
289  proj2_ref_ proj2_;
290 
291  template<typename T>
292  using constify_if = meta::const_if_c<IsConst, T>;
293 
294  using R1 = constify_if<Rng1>;
295  using R2 = constify_if<Rng2>;
296 
297  iterator_t<R1> it1_;
298  sentinel_t<R1> end1_;
299 
300  iterator_t<R2> it2_;
301  sentinel_t<R2> end2_;
302 
303  void satisfy()
304  {
305  while(it1_ != end1_ && it2_ != end2_)
306  {
307  if(invoke(pred_, invoke(proj1_, *it1_), invoke(proj2_, *it2_)))
308  ++it1_;
309  else
310  {
311  if(!invoke(pred_, invoke(proj2_, *it2_), invoke(proj1_, *it1_)))
312  return;
313  ++it2_;
314  }
315  }
316  }
317 
318  public:
319  using value_type = range_value_t<R1>;
321  single_pass_iterator_<iterator_t<R2>>>;
322 
323  set_intersection_cursor() = default;
324  set_intersection_cursor(pred_ref_ pred, proj1_ref_ proj1, proj2_ref_ proj2,
325  iterator_t<R1> it1, sentinel_t<R1> end1,
326  iterator_t<R2> it2, sentinel_t<R2> end2)
327  : pred_(std::move(pred))
328  , proj1_(std::move(proj1))
329  , proj2_(std::move(proj2))
330  , it1_(std::move(it1))
331  , end1_(std::move(end1))
332  , it2_(std::move(it2))
333  , end2_(std::move(end2))
334  {
335  satisfy();
336  }
337  template(bool Other)(
338  requires IsConst && CPP_NOT(Other)) //
339  set_intersection_cursor(
340  set_intersection_cursor<Other, Rng1, Rng2, C, P1, P2> that)
341  : pred_(std::move(that.pred_))
342  , proj1_(std::move(that.proj1_))
343  , proj2_(std::move(that.proj2_))
344  , it1_(std::move(that.it1_))
345  , end1_(std::move(that.end1_))
346  , it2_(std::move(that.it2_))
347  , end2_(std::move(that.end2_))
348  {}
349  // clang-format off
350  auto CPP_auto_fun(read)()(const)
351  (
352  return *it1_
353  )
354  // clang-format on
355  void next()
356  {
357  ++it1_;
358  ++it2_;
359  satisfy();
360  }
361  CPP_member
362  auto equal(set_intersection_cursor const & that) const //
363  -> CPP_ret(bool)(
364  requires forward_range<Rng1>)
365  {
366  // does not support comparing iterators from different ranges
367  return it1_ == that.it1_;
368  }
369  bool equal(default_sentinel_t) const
370  {
371  return (it1_ == end1_) || (it2_ == end2_);
372  }
373  // clang-format off
374  auto CPP_auto_fun(move)()(const)
375  (
376  return iter_move(it1_)
377  )
378  // clang-format on
379  };
380 
381  constexpr cardinality set_intersection_cardinality(cardinality c1, cardinality c2)
382  {
383  return (c1 == unknown) || (c2 == unknown)
384  ? unknown
385  : (c1 >= 0 || c1 == finite) || (c2 >= 0 || c2 == finite) ? finite
386  : unknown;
387  }
388  } // namespace detail
390 
391  template<typename Rng1, typename Rng2, typename C, typename P1, typename P2>
392  using set_intersection_view =
393  detail::set_algorithm_view<Rng1, Rng2, C, P1, P2, detail::set_intersection_cursor,
394  detail::set_intersection_cardinality(
395  range_cardinality<Rng1>::value,
396  range_cardinality<Rng2>::value)>;
397 
398  namespace views
399  {
401  {
402  template(typename Rng1, typename Rng2, typename C = less,
403  typename P1 = identity, typename P2 = identity)(
404  requires viewable_range<Rng1> AND input_range<Rng1> AND
405  viewable_range<Rng2> AND input_range<Rng2> AND
407  C,
408  projected<iterator_t<Rng1>, P1>,
409  projected<iterator_t<Rng2>, P2>>)
410  set_intersection_view<all_t<Rng1>, all_t<Rng2>, C, P1, P2>
411  operator()(Rng1 && rng1,
412  Rng2 && rng2,
413  C pred = C{},
414  P1 proj1 = P1{},
415  P2 proj2 = P2{}) const
416  {
417  return {all(static_cast<Rng1 &&>(rng1)),
418  all(static_cast<Rng2 &&>(rng2)),
419  std::move(pred),
420  std::move(proj1),
421  std::move(proj2)};
422  }
423  };
424 
426  {
427  using set_intersection_base_fn::operator();
428 
429  template(typename Rng2, typename C = less, typename P1 = identity,
430  typename P2 = identity)(
431  requires viewable_range<Rng2> AND input_range<Rng2> AND (!range<C>))
432  constexpr auto operator()(Rng2 && rng2,
433  C && pred = C{},
434  P1 proj1 = P1{},
435  P2 proj2 = P2{}) const
436  {
437  return make_view_closure(bind_back(set_intersection_base_fn{},
438  all(rng2),
439  static_cast<C &&>(pred),
440  std::move(proj1),
441  std::move(proj2)));
442  }
443  };
444 
447  } // namespace views
448 
450  namespace detail
451  {
452  template<bool IsConst, typename Rng1, typename Rng2, typename C, typename P1,
453  typename P2>
454  struct set_union_cursor
455  {
456  private:
457  friend struct set_union_cursor<!IsConst, Rng1, Rng2, C, P1, P2>;
458  using pred_ref_ = semiregular_box_ref_or_val_t<C, IsConst>;
459  using proj1_ref_ = semiregular_box_ref_or_val_t<P1, IsConst>;
460  using proj2_ref_ = semiregular_box_ref_or_val_t<P2, IsConst>;
461  pred_ref_ pred_;
462  proj1_ref_ proj1_;
463  proj2_ref_ proj2_;
464 
465  template<typename T>
466  using constify_if = meta::const_if_c<IsConst, T>;
467 
468  using R1 = constify_if<Rng1>;
469  using R2 = constify_if<Rng2>;
470 
471  iterator_t<R1> it1_;
472  sentinel_t<R1> end1_;
473 
474  iterator_t<R2> it2_;
475  sentinel_t<R2> end2_;
476 
477  enum class state_t
478  {
479  FIRST,
480  SECOND
481  } state;
482 
483  void satisfy()
484  {
485  if(it1_ == end1_)
486  {
487  state = state_t::SECOND;
488  return;
489  }
490 
491  if(it2_ == end2_)
492  {
493  state = state_t::FIRST;
494  return;
495  }
496 
497  if(invoke(pred_, invoke(proj2_, *it2_), invoke(proj1_, *it1_)))
498  {
499  state = state_t::SECOND;
500  return;
501  }
502 
503  if(!invoke(pred_, invoke(proj1_, *it1_), invoke(proj2_, *it2_)))
504  ++it2_;
505 
506  state = state_t::FIRST;
507  }
508 
509  public:
510  using value_type = common_type_t<range_value_t<R1>, range_value_t<R2>>;
511  using reference_type =
512  common_reference_t<range_reference_t<R1>, range_reference_t<R2>>;
513  using rvalue_reference_type =
514  common_reference_t<range_rvalue_reference_t<R1>,
515  range_rvalue_reference_t<R2>>;
517  single_pass_iterator_<iterator_t<R2>>>;
518 
519  set_union_cursor() = default;
520  set_union_cursor(pred_ref_ pred, proj1_ref_ proj1, proj2_ref_ proj2,
521  iterator_t<R1> it1, sentinel_t<R1> end1, iterator_t<R2> it2,
522  sentinel_t<R2> end2)
523  : pred_(std::move(pred))
524  , proj1_(std::move(proj1))
525  , proj2_(std::move(proj2))
526  , it1_(std::move(it1))
527  , end1_(std::move(end1))
528  , it2_(std::move(it2))
529  , end2_(std::move(end2))
530  {
531  satisfy();
532  }
533  template(bool Other)(
534  requires IsConst AND CPP_NOT(Other))
535  set_union_cursor(set_union_cursor<Other, Rng1, Rng2, C, P1, P2> that)
536  : pred_(std::move(that.pred_))
537  , proj1_(std::move(that.proj1_))
538  , proj2_(std::move(that.proj2_))
539  , it1_(std::move(that.it1_))
540  , end1_(std::move(that.end1_))
541  , it2_(std::move(that.it2_))
542  , end2_(std::move(that.end2_))
543  {}
544  reference_type read() const noexcept(noexcept(*it1_) && noexcept(*it2_))
545  {
546  if(state == state_t::SECOND)
547  return *it2_;
548  else
549  return *it1_;
550  }
551  void next()
552  {
553  if(state == state_t::FIRST)
554  ++it1_;
555  else
556  ++it2_;
557  satisfy();
558  }
559  CPP_member
560  auto equal(set_union_cursor const & that) const //
561  -> CPP_ret(bool)(
562  requires forward_range<Rng1> && forward_range<Rng2>)
563  {
564  // does not support comparing iterators from different ranges
565  return (it1_ == that.it1_) && (it2_ == that.it2_);
566  }
567  bool equal(default_sentinel_t) const
568  {
569  return (it1_ == end1_) && (it2_ == end2_);
570  }
571  rvalue_reference_type move() const
572  noexcept(noexcept(iter_move(it1_)) && noexcept(iter_move(it2_)))
573  {
574  if(state == state_t::SECOND)
575  return iter_move(it2_);
576  else
577  return iter_move(it1_);
578  }
579  };
580 
581  constexpr cardinality set_union_cardinality(cardinality c1, cardinality c2)
582  {
583  return (c1 == infinite) || (c2 == infinite)
584  ? infinite
585  : (c1 == unknown) || (c2 == unknown) ? unknown : finite;
586  }
587  } // namespace detail
589 
590  template<typename Rng1, typename Rng2, typename C, typename P1, typename P2>
591  using set_union_view =
592  detail::set_algorithm_view<Rng1, Rng2, C, P1, P2, detail::set_union_cursor,
593  detail::set_union_cardinality(
594  range_cardinality<Rng1>::value,
595  range_cardinality<Rng2>::value)>;
596 
597  namespace views
598  {
600  {
601  public:
602  template(typename Rng1, typename Rng2, typename C = less,
603  typename P1 = identity, typename P2 = identity)(
604  requires //
605  viewable_range<Rng1> AND input_range<Rng1> AND
606  viewable_range<Rng2> AND input_range<Rng2> AND
607  common_with<range_value_t<Rng1>, range_value_t<Rng2>> AND
608  common_reference_with<range_reference_t<Rng1>,
609  range_reference_t<Rng2>> AND
610  common_reference_with<range_rvalue_reference_t<Rng1>,
611  range_rvalue_reference_t<Rng2>> AND
613  projected<iterator_t<Rng1>, P1>,
614  projected<iterator_t<Rng2>, P2>>)
615  set_union_view<all_t<Rng1>, all_t<Rng2>, C, P1, P2> //
616  operator()(Rng1 && rng1,
617  Rng2 && rng2,
618  C pred = C{},
619  P1 proj1 = P1{},
620  P2 proj2 = P2{}) const
621  {
622  return {all(static_cast<Rng1 &&>(rng1)),
623  all(static_cast<Rng2 &&>(rng2)),
624  std::move(pred),
625  std::move(proj1),
626  std::move(proj2)};
627  }
628  };
629 
631  {
632  using set_union_base_fn::operator();
633 
634  template(typename Rng2, typename C = less, typename P1 = identity,
635  typename P2 = identity)(
636  requires viewable_range<Rng2> AND input_range<Rng2> AND (!range<C>))
637  constexpr auto operator()(Rng2 && rng2,
638  C && pred = C{},
639  P1 proj1 = P1{},
640  P2 proj2 = P2{}) const
641  {
642  return make_view_closure(bind_back(set_union_base_fn{},
643  all(rng2),
644  static_cast<C &&>(pred),
645  std::move(proj1),
646  std::move(proj2)));
647  }
648  };
649 
652  } // namespace views
653 
655  namespace detail
656  {
657  template<bool IsConst, typename Rng1, typename Rng2, typename C, typename P1,
658  typename P2>
659  struct set_symmetric_difference_cursor
660  {
661  private:
662  friend struct set_symmetric_difference_cursor<!IsConst, Rng1, Rng2, C, P1,
663  P2>;
664  using pred_ref_ = semiregular_box_ref_or_val_t<C, IsConst>;
665  using proj1_ref_ = semiregular_box_ref_or_val_t<P1, IsConst>;
666  using proj2_ref_ = semiregular_box_ref_or_val_t<P2, IsConst>;
667  pred_ref_ pred_;
668  proj1_ref_ proj1_;
669  proj2_ref_ proj2_;
670 
671  template<typename T>
672  using constify_if = meta::const_if_c<IsConst, T>;
673 
674  using R1 = constify_if<Rng1>;
675  using R2 = constify_if<Rng2>;
676 
677  iterator_t<R1> it1_;
678  sentinel_t<R1> end1_;
679 
680  iterator_t<R2> it2_;
681  sentinel_t<R2> end2_;
682 
683  enum class state_t
684  {
685  FIRST,
686  SECOND,
687  ONLY_FIRST,
688  ONLY_SECOND
689  } state;
690 
691  void satisfy()
692  {
693  while(it1_ != end1_)
694  {
695  if(it2_ == end2_)
696  {
697  state = state_t::ONLY_FIRST;
698  return;
699  }
700 
701  if(invoke(pred_, invoke(proj1_, *it1_), invoke(proj2_, *it2_)))
702  {
703  state = state_t::FIRST;
704  return;
705  }
706  else
707  {
708  if(invoke(pred_, invoke(proj2_, *it2_), invoke(proj1_, *it1_)))
709  {
710  state = state_t::SECOND;
711  return;
712  }
713  else
714  {
715  ++it1_;
716  ++it2_;
717  }
718  }
719  }
720  state = state_t::ONLY_SECOND;
721  }
722 
723  public:
724  using value_type = common_type_t<range_value_t<R1>, range_value_t<R2>>;
725  using reference_type =
726  common_reference_t<range_reference_t<R1>, range_reference_t<R2>>;
727  using rvalue_reference_type =
728  common_reference_t<range_rvalue_reference_t<R1>,
729  range_rvalue_reference_t<R2>>;
731  single_pass_iterator_<iterator_t<R2>>>;
732 
733  set_symmetric_difference_cursor() = default;
734  set_symmetric_difference_cursor(pred_ref_ pred, proj1_ref_ proj1,
735  proj2_ref_ proj2, iterator_t<R1> it1,
736  sentinel_t<R1> end1, iterator_t<R2> it2,
737  sentinel_t<R2> end2)
738  : pred_(std::move(pred))
739  , proj1_(std::move(proj1))
740  , proj2_(std::move(proj2))
741  , it1_(std::move(it1))
742  , end1_(std::move(end1))
743  , it2_(std::move(it2))
744  , end2_(std::move(end2))
745  , state()
746  {
747  satisfy();
748  }
749  template(bool Other)(
750  requires IsConst && CPP_NOT(Other)) //
751  set_symmetric_difference_cursor(
752  set_symmetric_difference_cursor<Other, Rng1, Rng2, C, P1, P2> that)
753  : pred_(std::move(that.pred_))
754  , proj1_(std::move(that.proj1_))
755  , proj2_(std::move(that.proj2_))
756  , it1_(std::move(that.it1_))
757  , end1_(std::move(that.end1_))
758  , it2_(std::move(that.it2_))
759  , end2_(std::move(that.end2_))
760  , state(that.state)
761  {}
762  reference_type read() const noexcept(noexcept(*it1_) && noexcept(*it2_))
763  {
764  if(state == state_t::SECOND || state == state_t::ONLY_SECOND)
765  return *it2_;
766  else
767  return *it1_;
768  }
769  void next()
770  {
771  switch(state)
772  {
773  case state_t::FIRST:
774  ++it1_;
775  satisfy();
776  break;
777  case state_t::ONLY_FIRST:
778  ++it1_;
779  break;
780  case state_t::SECOND:
781  ++it2_;
782  satisfy();
783  break;
784  case state_t::ONLY_SECOND:
785  ++it2_;
786  break;
787  }
788  }
789  CPP_member
790  auto equal(set_symmetric_difference_cursor const & that) const
791  -> CPP_ret(bool)(
792  requires forward_range<R1> && forward_range<R2>)
793  {
794  // does not support comparing iterators from different ranges:
795  return (it1_ == that.it1_) && (it2_ == that.it2_);
796  }
797  bool equal(default_sentinel_t) const
798  {
799  return (it1_ == end1_) && (it2_ == end2_);
800  }
801  rvalue_reference_type move() const
802  noexcept(noexcept(iter_move(it1_)) && noexcept(iter_move(it2_)))
803  {
804  if(state == state_t::SECOND || state == state_t::ONLY_SECOND)
805  return iter_move(it2_);
806  else
807  return iter_move(it1_);
808  }
809  };
810 
811  constexpr cardinality set_symmetric_difference_cardinality(cardinality c1,
812  cardinality c2)
813  {
814  return (c1 == unknown) || (c2 == unknown)
815  ? unknown
816  : (c1 == infinite) != (c2 == infinite)
817  ? infinite
818  : (c1 == infinite) && (c2 == infinite) ? unknown : finite;
819  }
820 
821  } // namespace detail
823 
824  template<typename Rng1, typename Rng2, typename C, typename P1, typename P2>
825  using set_symmetric_difference_view = detail::set_algorithm_view<
826  Rng1, Rng2, C, P1, P2, detail::set_symmetric_difference_cursor,
827  detail::set_symmetric_difference_cardinality(range_cardinality<Rng1>::value,
828  range_cardinality<Rng2>::value)>;
829 
830  namespace views
831  {
833  {
834  template(typename Rng1, typename Rng2, typename C = less,
835  typename P1 = identity, typename P2 = identity)(
836  requires //
837  viewable_range<Rng1> AND input_range<Rng1> AND
838  viewable_range<Rng2> AND input_range<Rng2> AND
839  common_with<range_value_t<Rng1>, range_value_t<Rng2>> AND
840  common_reference_with<range_reference_t<Rng1>,
841  range_reference_t<Rng2>> AND
842  common_reference_with<range_rvalue_reference_t<Rng1>,
843  range_rvalue_reference_t<Rng2>> AND
845  projected<iterator_t<Rng1>, P1>,
846  projected<iterator_t<Rng2>, P2>>)
847  set_symmetric_difference_view<all_t<Rng1>, all_t<Rng2>, C, P1, P2>
848  operator()(Rng1 && rng1,
849  Rng2 && rng2,
850  C pred = C{},
851  P1 proj1 = P1{},
852  P2 proj2 = P2{}) const
853  {
854  return {all(static_cast<Rng1 &&>(rng1)),
855  all(static_cast<Rng2 &&>(rng2)),
856  std::move(pred),
857  std::move(proj1),
858  std::move(proj2)};
859  }
860  };
861 
863  {
864  using set_symmetric_difference_base_fn::operator();
865 
866  template(typename Rng2, typename C = less, typename P1 = identity,
867  typename P2 = identity)(
868  requires viewable_range<Rng2> AND input_range<Rng2> AND (!range<C>))
869  constexpr auto operator()(Rng2 && rng2,
870  C && pred = C{},
871  P1 proj1 = P1{},
872  P2 proj2 = P2{}) const
873  {
874  return make_view_closure(bind_back(set_symmetric_difference_base_fn{},
875  all(rng2),
876  static_cast<C &&>(pred),
877  std::move(proj1),
878  std::move(proj2)));
879  }
880  };
881 
883  RANGES_INLINE_VARIABLE(set_symmetric_difference_fn, set_symmetric_difference)
884  } // namespace views
886 } // namespace ranges
887 
888 #include <range/v3/detail/epilogue.hpp>
889 
890 #endif
CPP_concept indirect_relation
\concept indirect_relation
Definition: concepts.hpp:670
CPP_concept range
\concept range
Definition: concepts.hpp:69
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
typename Fn::template invoke< Args... > invoke
Evaluate the invocable Fn with the arguments Args.
Definition: meta.hpp:541
defer< bind_back, Fn, Ts... > bind_back
Definition: meta.hpp:994
bool_<(T::type::value< U::type::value)> less
A Boolean integral constant wrapper around true if T::type::value is less than U::type::value; false,...
Definition: meta.hpp:255
Tiny meta-programming library.
Logically OR together all the Boolean parameters.
Definition: meta.hpp:1432
Definition: identity.hpp:25
Definition: set_algorithm.hpp:227
Definition: set_algorithm.hpp:252
Definition: set_algorithm.hpp:401
Definition: set_algorithm.hpp:426
Definition: set_algorithm.hpp:833
Definition: set_algorithm.hpp:863
Definition: set_algorithm.hpp:600
Definition: set_algorithm.hpp:631