Horizon
concat.hpp
Go to the documentation of this file.
1 // Range v3 library
3 //
4 // Copyright Eric Niebler 2013-2014.
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_CONCAT_HPP
15 #define RANGES_V3_VIEW_CONCAT_HPP
16 
17 #include <tuple>
18 #include <type_traits>
19 #include <utility>
20 
21 #include <meta/meta.hpp>
22 
23 #include <range/v3/range_fwd.hpp>
24 
32 #include <range/v3/utility/static_const.hpp>
35 #include <range/v3/view/all.hpp>
36 #include <range/v3/view/facade.hpp>
37 #include <range/v3/view/view.hpp>
38 
39 #include <range/v3/detail/prologue.hpp>
40 
41 namespace ranges
42 {
44  namespace detail
45  {
46  template<typename State, typename Value>
47  using concat_cardinality_ = std::integral_constant<
48  cardinality,
49  State::value == infinite || Value::value == infinite
50  ? infinite
51  : State::value == unknown || Value::value == unknown
52  ? unknown
53  : State::value == finite || Value::value == finite
54  ? finite
55  : static_cast<cardinality>(State::value + Value::value)>;
56 
57  template<typename... Rngs>
58  using concat_cardinality =
60  std::integral_constant<cardinality, static_cast<cardinality>(0)>,
62  } // namespace detail
64 
67  template<typename... Rngs>
68  struct concat_view
69  : view_facade<concat_view<Rngs...>, detail::concat_cardinality<Rngs...>::value>
70  {
71  private:
72  friend range_access;
73  using difference_type_ = common_type_t<range_difference_t<Rngs>...>;
74  static constexpr std::size_t cranges{sizeof...(Rngs)};
75  std::tuple<Rngs...> rngs_;
76 
77  template<bool IsConst>
78  struct cursor;
79 
80  template<bool IsConst>
81  struct sentinel
82  {
83  private:
84  friend struct sentinel<!IsConst>;
85  friend struct cursor<IsConst>;
86  template<typename T>
87  using constify_if = meta::const_if_c<IsConst, T>;
88  using concat_view_t = constify_if<concat_view>;
89  sentinel_t<constify_if<meta::back<meta::list<Rngs...>>>> end_;
90 
91  public:
92  sentinel() = default;
93  sentinel(concat_view_t * rng, end_tag)
94  : end_(end(std::get<cranges - 1>(rng->rngs_)))
95  {}
96  template(bool Other)(
97  requires IsConst AND CPP_NOT(Other)) //
98  sentinel(sentinel<Other> that)
99  : end_(std::move(that.end_))
100  {}
101  };
102 
103  template<bool IsConst>
104  struct cursor
105  {
106  using difference_type = common_type_t<range_difference_t<Rngs>...>;
107 
108  private:
109  friend struct cursor<!IsConst>;
110  template<typename T>
111  using constify_if = meta::const_if_c<IsConst, T>;
112  using concat_view_t = constify_if<concat_view>;
113  concat_view_t * rng_;
115 
116  template<std::size_t N>
117  void satisfy(meta::size_t<N>)
118  {
119  RANGES_EXPECT(its_.index() == N);
120  if(ranges::get<N>(its_) == end(std::get<N>(rng_->rngs_)))
121  {
122  ranges::emplace<N + 1>(its_, begin(std::get<N + 1>(rng_->rngs_)));
123  this->satisfy(meta::size_t<N + 1>{});
124  }
125  }
126  void satisfy(meta::size_t<cranges - 1>)
127  {
128  RANGES_EXPECT(its_.index() == cranges - 1);
129  }
130  struct next_fun
131  {
132  cursor * pos;
133  template(typename I, std::size_t N)(
134  requires input_iterator<I>)
135  void operator()(indexed_element<I, N> it) const
136  {
137  RANGES_ASSERT(it.get() != end(std::get<N>(pos->rng_->rngs_)));
138  ++it.get();
139  pos->satisfy(meta::size_t<N>{});
140  }
141  };
142  struct prev_fun
143  {
144  cursor * pos;
145  template(typename I)(
146  requires bidirectional_iterator<I>)
147  void operator()(indexed_element<I, 0> it) const
148  {
149  RANGES_ASSERT(it.get() != begin(std::get<0>(pos->rng_->rngs_)));
150  --it.get();
151  }
152  template(typename I, std::size_t N)(
153  requires (N != 0) AND bidirectional_iterator<I>)
154  void operator()(indexed_element<I, N> it) const
155  {
156  if(it.get() == begin(std::get<N>(pos->rng_->rngs_)))
157  {
158  auto && rng = std::get<N - 1>(pos->rng_->rngs_);
159  ranges::emplace<N - 1>(
160  pos->its_,
161  ranges::next(ranges::begin(rng), ranges::end(rng)));
162  pos->its_.visit_i(*this);
163  }
164  else
165  --it.get();
166  }
167  };
168  struct advance_fwd_fun
169  {
170  cursor * pos;
171  difference_type n;
172  template(typename I)(
173  requires random_access_iterator<I>)
174  void operator()(indexed_element<I, cranges - 1> it) const
175  {
176  ranges::advance(it.get(), n);
177  }
178  template(typename I, std::size_t N)(
179  requires random_access_iterator<I>)
180  void operator()(indexed_element<I, N> it) const
181  {
182  auto last = ranges::end(std::get<N>(pos->rng_->rngs_));
183  // BUGBUG If distance(it, last) > n, then using bounded advance
184  // is O(n) when it need not be since the last iterator position
185  // is actually not interesting. Only the "rest" is needed, which
186  // can sometimes be O(1).
187  auto rest = ranges::advance(it.get(), n, std::move(last));
188  pos->satisfy(meta::size_t<N>{});
189  if(rest != 0)
190  pos->its_.visit_i(advance_fwd_fun{pos, rest});
191  }
192  };
193  struct advance_rev_fun
194  {
195  cursor * pos;
196  difference_type n;
197  template(typename I)(
198  requires random_access_iterator<I>)
199  void operator()(indexed_element<I, 0> it) const
200  {
201  ranges::advance(it.get(), n);
202  }
203  template(typename I, std::size_t N)(
204  requires random_access_iterator<I>)
205  void operator()(indexed_element<I, N> it) const
206  {
207  auto first = ranges::begin(std::get<N>(pos->rng_->rngs_));
208  if(it.get() == first)
209  {
210  auto && rng = std::get<N - 1>(pos->rng_->rngs_);
211  ranges::emplace<N - 1>(
212  pos->its_,
213  ranges::next(ranges::begin(rng), ranges::end(rng)));
214  pos->its_.visit_i(*this);
215  }
216  else
217  {
218  auto rest = ranges::advance(it.get(), n, std::move(first));
219  if(rest != 0)
220  pos->its_.visit_i(advance_rev_fun{pos, rest});
221  }
222  }
223  };
224  [[noreturn]] static difference_type distance_to_(meta::size_t<cranges>,
225  cursor const &,
226  cursor const &)
227  {
228  RANGES_EXPECT(false);
229  }
230  template<std::size_t N>
231  static difference_type distance_to_(meta::size_t<N>, cursor const & from,
232  cursor const & to)
233  {
234  if(from.its_.index() > N)
235  return cursor::distance_to_(meta::size_t<N + 1>{}, from, to);
236  if(from.its_.index() == N)
237  {
238  if(to.its_.index() == N)
239  return distance(ranges::get<N>(from.its_),
240  ranges::get<N>(to.its_));
241  return distance(ranges::get<N>(from.its_),
242  end(std::get<N>(from.rng_->rngs_))) +
243  cursor::distance_to_(meta::size_t<N + 1>{}, from, to);
244  }
245  if(from.its_.index() < N && to.its_.index() > N)
246  return distance(std::get<N>(from.rng_->rngs_)) +
247  cursor::distance_to_(meta::size_t<N + 1>{}, from, to);
248  RANGES_EXPECT(to.its_.index() == N);
249  return distance(begin(std::get<N>(from.rng_->rngs_)),
250  ranges::get<N>(to.its_));
251  }
252 
253  public:
254  // BUGBUG what about rvalue_reference and common_reference?
255  using reference = common_reference_t<range_reference_t<constify_if<Rngs>>...>;
256  using single_pass = meta::or_c<single_pass_iterator_<iterator_t<Rngs>>...>;
257  cursor() = default;
258  cursor(concat_view_t * rng, begin_tag)
259  : rng_(rng)
260  , its_{emplaced_index<0>, begin(std::get<0>(rng->rngs_))}
261  {
262  this->satisfy(meta::size_t<0>{});
263  }
264  cursor(concat_view_t * rng, end_tag)
265  : rng_(rng)
266  , its_{emplaced_index<cranges - 1>, end(std::get<cranges - 1>(rng->rngs_))}
267  {}
268  template(bool Other)(
269  requires IsConst && CPP_NOT(Other)) //
270  cursor(cursor<Other> that)
271  : rng_(that.rng_)
272  , its_(std::move(that.its_))
273  {}
274  reference read() const
275  {
276  // Kind of a dumb implementation. Surely there's a better way.
277  return ranges::get<0>(unique_variant(its_.visit(
278  compose(convert_to<reference>{}, detail::dereference_fn{}))));
279  }
280  void next()
281  {
282  its_.visit_i(next_fun{this});
283  }
284  CPP_member
285  auto equal(cursor const & pos) const //
286  -> CPP_ret(bool)(
287  requires //
288  equality_comparable<variant<iterator_t<constify_if<Rngs>>...>>)
289  {
290  return its_ == pos.its_;
291  }
292  bool equal(sentinel<IsConst> const & pos) const
293  {
294  return its_.index() == cranges - 1 &&
295  ranges::get<cranges - 1>(its_) == pos.end_;
296  }
297  CPP_member
298  auto prev() //
299  -> CPP_ret(void)(
300  requires and_v<bidirectional_range<Rngs>...>)
301  {
302  its_.visit_i(prev_fun{this});
303  }
304  CPP_member
305  auto advance(difference_type n) //
306  -> CPP_ret(void)(
307  requires and_v<random_access_range<Rngs>...>)
308  {
309  if(n > 0)
310  its_.visit_i(advance_fwd_fun{this, n});
311  else if(n < 0)
312  its_.visit_i(advance_rev_fun{this, n});
313  }
314  CPP_member
315  auto distance_to(cursor const & that) const //
316  -> CPP_ret(difference_type)(
317  requires and_v<sized_sentinel_for<iterator_t<Rngs>,
318  iterator_t<Rngs>>...>)
319  {
320  if(its_.index() <= that.its_.index())
321  return cursor::distance_to_(meta::size_t<0>{}, *this, that);
322  return -cursor::distance_to_(meta::size_t<0>{}, that, *this);
323  }
324  };
325  cursor<meta::and_c<simple_view<Rngs>()...>::value> begin_cursor()
326  {
327  return {this, begin_tag{}};
328  }
329  meta::if_<meta::and_c<(bool)common_range<Rngs>...>,
330  cursor<meta::and_c<simple_view<Rngs>()...>::value>,
331  sentinel<meta::and_c<simple_view<Rngs>()...>::value>>
332  end_cursor()
333  {
334  return {this, end_tag{}};
335  }
336  CPP_member
337  auto begin_cursor() const //
338  -> CPP_ret(cursor<true>)(
339  requires and_v<range<Rngs const>...>)
340  {
341  return {this, begin_tag{}};
342  }
343  CPP_member
344  auto end_cursor() const //
345  -> CPP_ret(
346  meta::if_<meta::and_c<(bool)common_range<Rngs const>...>, //
347  cursor<true>, //
348  sentinel<true>>)(
349  requires and_v<range<Rngs const>...>)
350  {
351  return {this, end_tag{}};
352  }
353 
354  public:
355  concat_view() = default;
356  explicit concat_view(Rngs... rngs)
357  : rngs_{std::move(rngs)...}
358  {}
359  CPP_member
360  constexpr auto size() const //
361  -> CPP_ret(std::size_t)(
362  requires (detail::concat_cardinality<Rngs...>::value >= 0))
363  {
364  return static_cast<std::size_t>(detail::concat_cardinality<Rngs...>::value);
365  }
366  CPP_auto_member
367  constexpr auto CPP_fun(size)()(const //
368  requires(detail::concat_cardinality<Rngs...>::value < 0) &&
369  and_v<sized_range<Rngs const>...>)
370  {
371  using size_type = common_type_t<range_size_t<Rngs const>...>;
372  return tuple_foldl(
373  tuple_transform(rngs_,
374  [](auto && r) -> size_type { return ranges::size(r); }),
375  size_type{0},
376  plus{});
377  }
378  CPP_auto_member
379  constexpr auto CPP_fun(size)()(
380  requires (detail::concat_cardinality<Rngs...>::value < 0) &&
381  and_v<sized_range<Rngs>...>)
382  {
383  using size_type = common_type_t<range_size_t<Rngs>...>;
384  return tuple_foldl(
385  tuple_transform(rngs_,
386  [](auto && r) -> size_type { return ranges::size(r); }),
387  size_type{0},
388  plus{});
389  }
390  };
391 
392 #if RANGES_CXX_DEDUCTION_GUIDES >= RANGES_CXX_DEDUCTION_GUIDES_17
393  template<typename... Rng>
394  concat_view(Rng &&...) //
396 #endif
397 
398  namespace views
399  {
400  struct concat_fn
401  {
402  template(typename... Rngs)(
403  requires and_v<(viewable_range<Rngs> && input_range<Rngs>)...>)
404  concat_view<all_t<Rngs>...> operator()(Rngs &&... rngs) const
405  {
406  return concat_view<all_t<Rngs>...>{all(static_cast<Rngs &&>(rngs))...};
407  }
408  template(typename Rng)(
409  requires viewable_range<Rng> AND input_range<Rng>)
410  all_t<Rng> operator()(Rng && rng) const //
411  {
412  return all(static_cast<Rng &&>(rng));
413  }
414  // MSVC doesn't like variadics in operator() for some reason
415 #if defined(_MSC_VER)
416  template(typename Rng0, typename Rng1)(
417  requires viewable_range<Rng0> AND input_range<Rng0> AND
418  viewable_range<Rng1> AND input_range<Rng1>)
419  concat_view<all_t<Rng0>, all_t<Rng1>> operator()(Rng0 && rng0, Rng1 && rng1)
420  const
421  {
422  return concat_view<all_t<Rng0>, all_t<Rng1>>{
423  all(static_cast<Rng0 &&>(rng0)),
424  all(static_cast<Rng1 &&>(rng1))};
425  }
426  template(typename Rng0, typename Rng1, typename Rng2)(
427  requires viewable_range<Rng0> AND input_range<Rng0> AND
428  viewable_range<Rng1> AND input_range<Rng1> AND
429  viewable_range<Rng2> AND input_range<Rng2>)
430  concat_view<all_t<Rng0>, all_t<Rng1>, all_t<Rng2>> //
431  operator()(Rng0 && rng0, Rng1 && rng1, Rng2 && rng2) const
432  {
433  return concat_view<all_t<Rng0>, all_t<Rng1>, all_t<Rng2>>{
434  all(static_cast<Rng0 &&>(rng0)),
435  all(static_cast<Rng1 &&>(rng1)),
436  all(static_cast<Rng2 &&>(rng2))};
437  }
438 #endif
439  };
440 
444  } // namespace views
446 } // namespace ranges
447 
448 #include <range/v3/detail/epilogue.hpp>
449 #include <range/v3/detail/satisfy_boost_range.hpp>
450 RANGES_SATISFY_BOOST_RANGE(::ranges::concat_view)
451 
452 #endif
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< std::size_t, N > size_t
An integral constant wrapper for std::size_t.
Definition: meta.hpp:163
front< Pair > first
Retrieve the first element of the pair Pair.
Definition: meta.hpp:2251
meta::size_t< L::size()> size
An integral constant wrapper that is the size of the meta::list L.
Definition: meta.hpp:1696
_t< detail::back_< L > > back
Return the last element in meta::list L.
Definition: meta.hpp:2103
_t< detail::_if_< list< Args... > >> if_
Select one type or another depending on a compile-time Boolean.
Definition: meta.hpp:1247
_t< detail::fold_< L, id< State >, Fn > > fold
Return a new meta::list constructed by doing a left fold of the list L using binary invocable Fn and ...
Definition: meta.hpp:1589
Tiny meta-programming library.
Definition: meta.hpp:1383
A list of types.
Definition: meta.hpp:1684
Logically OR together all the Boolean parameters.
Definition: meta.hpp:1432
Turn a template C into an invocable.
Definition: meta.hpp:913
Definition: range_fwd.hpp:488
Definition: concat.hpp:70
Definition: arithmetic.hpp:66
Definition: range_fwd.hpp:490
Definition: variant.hpp:71
Definition: arithmetic.hpp:25
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: concat.hpp:401