Horizon
join.hpp
Go to the documentation of this file.
1 // 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 
22 #include <range/v3/range_fwd.hpp>
23 
29 #include <range/v3/range_for.hpp>
30 #include <range/v3/utility/static_const.hpp>
32 #include <range/v3/view/all.hpp>
33 #include <range/v3/view/facade.hpp>
34 #include <range/v3/view/single.hpp>
35 #include <range/v3/view/view.hpp>
36 
37 #include <range/v3/detail/prologue.hpp>
38 
39 namespace 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) &&
165  forward_range<Rng> &&
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 && //
264  bidirectional_range<COuter> && //
265  bidirectional_range<CInner> && //
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 =
329  forward_range<Rng> && forward_range<range_reference_t<Rng>> &&
330  common_range<Rng> && common_range<range_reference_t<Rng>>>;
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 =
342  forward_range<CRng> &&
343  forward_range<range_reference_t<CRng>> &&
344  common_range<CRng> && common_range<range_reference_t<CRng>>>;
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) &&
379  (range_cardinality<Rng>::value >= 0) && forward_range<Rng> &&
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
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 =
512  viewable_range<Rng> && input_range<Rng> &&
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> &&
538  viewable_range<ValRng> && forward_range<ValRng> &&
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 
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  {
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>
646 RANGES_SATISFY_BOOST_RANGE(::ranges::join_view)
647 RANGES_SATISFY_BOOST_RANGE(::ranges::join_with_view)
648 
649 #endif
CPP_concept sized_range
\concept sized_range
Definition: concepts.hpp:208
CPP_concept input_range
\concept input_range
Definition: concepts.hpp:103
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
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
defer< bind_back, Fn, Ts... > bind_back
Definition: meta.hpp:994
meta::size_t< L::size()> size
An integral constant wrapper that is the size of the meta::list L.
Definition: meta.hpp:1696
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
apply< quote< concat >, ListOfLists > join
Joins a list of lists into a single list.
Definition: meta.hpp:1786
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