Horizon
subrange.hpp
Go to the documentation of this file.
1 // Range v3 library
3 //
4 // Copyright Eric Niebler 2013-present
5 // Copyright Casey Carter 2017
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_SUBRANGE_HPP
16 #define RANGES_V3_VIEW_SUBRANGE_HPP
17 
18 #include <tuple>
19 #include <type_traits>
20 #include <utility>
21 
22 #include <meta/meta.hpp>
23 
24 #include <concepts/concepts.hpp>
25 
31 #include <range/v3/utility/get.hpp>
33 
34 #include <range/v3/detail/prologue.hpp>
35 
36 namespace ranges
37 {
40  enum class subrange_kind : bool
41  {
42  unsized,
43  sized
44  };
45 
47  namespace detail
48  {
49  // clang-format off
52  template<typename From, typename To>
53  CPP_concept convertible_to_not_slicing_ =
54  convertible_to<From, To> &&
55  // A conversion is a slicing conversion if the source and the destination
56  // are both pointers, and if the pointed-to types differ after removing
57  // cv qualifiers.
58  (!(std::is_pointer<decay_t<From>>::value &&
59  std::is_pointer<decay_t<To>>::value &&
60  not_same_as_<std::remove_pointer_t<decay_t<From>>,
61  std::remove_pointer_t<decay_t<To>>>));
62 
63  template<std::size_t N, typename T>
64  using tuple_element_fun_t = void (*)(meta::_t<std::tuple_element<N, T>> const &);
65 
68  template<typename T>
69  CPP_requires(pair_like_impl_, //
70  requires(T t, tuple_element_fun_t<0, T> p0, tuple_element_fun_t<1, T> p1) //
71  (
72  p0( get<0>(t) ),
73  p1( get<1>(t) )
74  ));
77  template<typename T>
78  CPP_concept pair_like_impl_ = CPP_requires_ref(detail::pair_like_impl_, T);
79 
82  template(typename T)(
83  concept (is_complete_)(T),
84  0 != sizeof(T));
85 
88  template<typename T>
89  CPP_concept is_complete_ = //
90  CPP_concept_ref(is_complete_, T);
91 
92  template(typename T)( //
93  concept (pair_like_)(T), //
94  is_complete_<std::tuple_size<T>> AND
95  derived_from<std::tuple_size<T>, meta::size_t<2>> AND
96  detail::pair_like_impl_<T>);
97 
100  template<typename T>
101  CPP_concept pair_like = //
102  CPP_concept_ref(detail::pair_like_, T);
103 
104  // clang-format off
105  template(typename T, typename U, typename V)( //
106  concept (pair_like_convertible_from_helper_)(T, U, V), //
107  convertible_to_not_slicing_<U, meta::_t<std::tuple_element<0, T>>> AND
108  convertible_to<V, meta::_t<std::tuple_element<1, T>>>);
109 
112  template<typename T, typename U, typename V>
113  CPP_concept pair_like_convertible_from_helper_ = //
114  CPP_concept_ref(pair_like_convertible_from_helper_, T, U, V);
115 
116  template(typename T, typename U, typename V)( //
117  concept (pair_like_convertible_from_impl_)(T, U, V),
118  (!range<T>) AND
119  constructible_from<T, U, V> AND
120  pair_like<uncvref_t<T>> AND
121  pair_like_convertible_from_helper_<T, U, V>);
122 
125  template<typename T, typename U, typename V>
126  CPP_concept pair_like_convertible_from_ =
127  CPP_concept_ref(detail::pair_like_convertible_from_impl_, T, U, V);
128 
131  template(typename R, typename I, typename S)(
132  concept (range_convertible_to_impl_)(R, I, S),
133  convertible_to_not_slicing_<iterator_t<R>, I> AND
134  convertible_to<sentinel_t<R>, S>);
135 
138  template<typename R, typename I, typename S>
139  CPP_concept range_convertible_to_ =
140  borrowed_range<R> &&
141  CPP_concept_ref(detail::range_convertible_to_impl_, R, I, S);
142  // clang-format on
143 
144  template(typename S, typename I)(
145  requires sentinel_for<S, I>)
146  constexpr bool is_sized_sentinel_() noexcept
147  {
148  return (bool)sized_sentinel_for<S, I>;
149  }
150 
151  template<subrange_kind K, typename S, typename I>
152  constexpr bool store_size_() noexcept
153  {
154  return K == subrange_kind::sized && !(bool)sized_sentinel_for<S, I>;
155  }
156  } // namespace detail
158 
159  template< //
160  typename I, //
161  typename S = I, //
162  subrange_kind K = static_cast<subrange_kind>(detail::is_sized_sentinel_<S, I>())>
163  struct subrange;
164 
165  template<typename I, typename S, subrange_kind K>
166  RANGES_INLINE_VAR constexpr bool enable_borrowed_range<subrange<I, S, K>> = true;
167 
169  namespace _subrange_
170  {
171  struct adl_hook
172  {};
173 
174  template(std::size_t N, typename I, typename S, subrange_kind K)(
175  requires (N == 0)) //
176  constexpr I get(subrange<I, S, K> const & r)
177  {
178  return r.begin();
179  }
180  template(std::size_t N, typename I, typename S, subrange_kind K)(
181  requires (N == 1)) //
182  constexpr S get(subrange<I, S, K> const & r)
183  {
184  return r.end();
185  }
186  } // namespace _subrange_
188 
189  template<typename I, typename S, subrange_kind K>
190  struct subrange
192  same_as<S, unreachable_sentinel_t>
193  ? infinite
194  : K == subrange_kind::sized ? finite : unknown>
195  , private _subrange_::adl_hook
196  {
197  CPP_assert(input_or_output_iterator<I>);
198  CPP_assert(sentinel_for<S, I>);
199  CPP_assert(K == subrange_kind::sized || !sized_sentinel_for<S, I>);
200  CPP_assert(K != subrange_kind::sized || !same_as<S, unreachable_sentinel_t>);
201 
202  using size_type = detail::iter_size_t<I>;
203  using iterator = I;
204  using sentinel = S;
205 
206  subrange() = default;
207 
208  template(typename I2)(
209  requires detail::convertible_to_not_slicing_<I2, I> AND
210  (!detail::store_size_<K, S, I>())) //
211  constexpr subrange(I2 && i, S s)
212  : data_{static_cast<I2 &&>(i), std::move(s)}
213  {}
214 
215  template(typename I2)(
216  requires detail::convertible_to_not_slicing_<I2, I> AND
217  (detail::store_size_<K, S, I>())) //
218  constexpr subrange(I2 && i, S s, size_type n)
219  : data_{static_cast<I2 &&>(i), std::move(s), n}
220  {
221  if(RANGES_CONSTEXPR_IF((bool)random_access_iterator<I>))
222  {
223  using D = iter_difference_t<I>;
224  RANGES_EXPECT(n <= (size_type)std::numeric_limits<D>::max());
225  RANGES_EXPECT(ranges::next(first_(), (D)n) == last_());
226  }
227  }
228  template(typename I2)(
229  requires detail::convertible_to_not_slicing_<I2, I> AND
230  sized_sentinel_for<S, I>)
231  constexpr subrange(I2 && i, S s, size_type n)
232  : data_{static_cast<I2 &&>(i), std::move(s)}
233  {
234  RANGES_EXPECT(static_cast<size_type>(last_() - first_()) == n);
235  }
236 
237  template(typename R)(
238  requires (!same_as<detail::decay_t<R>, subrange>) AND
239  detail::range_convertible_to_<R, I, S> AND
240  (!detail::store_size_<K, S, I>()))
241  constexpr subrange(R && r)
242  : subrange{ranges::begin(r), ranges::end(r)}
243  {}
244 
245  template(typename R)(
246  requires (!same_as<detail::decay_t<R>, subrange>) AND
247  detail::range_convertible_to_<R, I, S> AND
248  (detail::store_size_<K, S, I>()) AND
249  sized_range<R>)
250  constexpr subrange(R && r)
251  : subrange{ranges::begin(r), ranges::end(r), ranges::size(r)}
252  {}
253 
254  template(typename R)(
255  requires (K == subrange_kind::sized) AND
256  detail::range_convertible_to_<R, I, S>)
257  constexpr subrange(R && r, size_type n) //
258  : subrange{ranges::begin(r), ranges::end(r), n}
259  {
260  if(RANGES_CONSTEXPR_IF((bool)sized_range<R>))
261  {
262  RANGES_EXPECT(n == ranges::size(r));
263  }
264  }
265 
266  template(typename PairLike)(
267  requires (!same_as<PairLike, subrange>) AND
268  detail::pair_like_convertible_from_<PairLike, I const &, S const &>)
269  constexpr operator PairLike() const
270  {
271  return PairLike(first_(), last_());
272  }
273 
274  constexpr I begin() const noexcept(std::is_nothrow_copy_constructible<I>::value)
275  {
276  return first_();
277  }
278  constexpr S end() const noexcept(std::is_nothrow_copy_constructible<S>::value)
279  {
280  return last_();
281  }
282  constexpr bool empty() const
283  {
284  return first_() == last_();
285  }
286 
287  CPP_member
288  constexpr auto size() const //
289  -> CPP_ret(size_type)(
290  requires (K == subrange_kind::sized))
291  {
292  return get_size_();
293  }
294 
295  RANGES_NODISCARD
296  constexpr subrange next(iter_difference_t<I> n = 1) const
297  {
298  auto tmp = *this;
299  tmp.advance(n);
300  return tmp;
301  }
302 
303  CPP_member
304  RANGES_NODISCARD constexpr auto prev(iter_difference_t<I> n = 1) const
305  -> CPP_ret(subrange)(
306  requires bidirectional_iterator<I>)
307  {
308  auto tmp = *this;
309  tmp.advance(-n);
310  return tmp;
311  }
312 
313  constexpr subrange & advance(iter_difference_t<I> n)
314  {
315  set_size_(get_size_() -
316  static_cast<size_type>(n - ranges::advance(first_(), n, last_())));
317  return *this;
318  }
319 
320  private:
321  using data_t =
323  detail::store_size_<K, S, I>(), //
324  std::tuple<I, S, size_type>, //
325  std::tuple<I, S>>;
326  data_t data_;
327 
328  constexpr I & first_() noexcept
329  {
330  return std::get<0>(data_);
331  }
332  constexpr const I & first_() const noexcept
333  {
334  return std::get<0>(data_);
335  }
336  constexpr S & last_() noexcept
337  {
338  return std::get<1>(data_);
339  }
340  constexpr const S & last_() const noexcept
341  {
342  return std::get<1>(data_);
343  }
344  CPP_member
345  constexpr auto get_size_() const //
346  -> CPP_ret(size_type)(
347  requires sized_sentinel_for<S, I>)
348  {
349  return static_cast<size_type>(last_() - first_());
350  }
351  CPP_member
352  constexpr auto get_size_() const noexcept //
353  -> CPP_ret(size_type)(
354  requires (detail::store_size_<K, S, I>()))
355  {
356  return std::get<2>(data_);
357  }
358  static constexpr void set_size_(...) noexcept
359  {}
360  CPP_member
361  constexpr auto set_size_(size_type n) noexcept //
362  -> CPP_ret(void)(
363  requires (detail::store_size_<K, S, I>()))
364  {
365  std::get<2>(data_) = n;
366  }
367  };
368 
369 #if RANGES_CXX_DEDUCTION_GUIDES >= RANGES_CXX_DEDUCTION_GUIDES_17
370  template<typename I, typename S>
371  subrange(I, S) //
372  -> subrange<I, S>;
373 
374  template(typename I, typename S)(
375  requires input_or_output_iterator<I> AND sentinel_for<S, I>)
376  subrange(I, S, detail::iter_size_t<I>)
378 
379  template(typename R)(
380  requires borrowed_range<R>)
381  subrange(R &&) //
382  -> subrange<iterator_t<R>, sentinel_t<R>,
383  (sized_range<R> ||
384  sized_sentinel_for<sentinel_t<R>, iterator_t<R>>)
385  ? subrange_kind::sized
386  : subrange_kind::unsized>;
387 
388  template(typename R)(
389  requires borrowed_range<R>)
390  subrange(R &&, detail::iter_size_t<iterator_t<R>>)
391  -> subrange<iterator_t<R>, sentinel_t<R>, subrange_kind::sized>;
392 #endif
393 
394  // in lieu of deduction guides, use make_subrange
396  {
397  template<typename I, typename S>
398  constexpr subrange<I, S> operator()(I i, S s) const
399  {
400  return {i, s};
401  }
402  template(typename I, typename S)(
403  requires input_or_output_iterator<I> AND sentinel_for<S, I>)
405  operator()(I i, S s, detail::iter_size_t<I> n) const
406  {
407  return {i, s, n};
408  }
409  template(typename R)(
410  requires borrowed_range<R>)
411  constexpr auto operator()(R && r) const
412  -> subrange<iterator_t<R>, sentinel_t<R>,
413  (sized_range<R> || sized_sentinel_for<sentinel_t<R>, iterator_t<R>>)
414  ? subrange_kind::sized
415  : subrange_kind::unsized>
416  {
417  return {(R &&) r};
418  }
419  template(typename R)(
420  requires borrowed_range<R>)
421  constexpr subrange<iterator_t<R>, sentinel_t<R>, subrange_kind::sized> //
422  operator()(R && r, detail::iter_size_t<iterator_t<R>> n) const
423  {
424  return {(R &&) r, n};
425  }
426  };
427 
431 
432  template<typename R>
433  using borrowed_subrange_t = detail::maybe_dangling_<R, subrange<iterator_t<R>>>;
434 
435  template<typename R>
436  using safe_subrange_t RANGES_DEPRECATED("Use borrowed_subrange_t instead.") =
437  borrowed_subrange_t<R>;
438 
439  namespace cpp20
440  {
441  using ranges::subrange_kind;
442 
443  template(typename I, //
444  typename S = I, //
445  subrange_kind K = //
446  static_cast<subrange_kind>( //
447  detail::is_sized_sentinel_<S, I>()))(
448  requires input_or_output_iterator<I> AND sentinel_for<S, I> AND
449  (K == subrange_kind::sized || !sized_sentinel_for<S, I>)) //
451 
452  using ranges::borrowed_subrange_t;
453 
454  template<typename R>
455  using safe_subrange_t RANGES_DEPRECATED("Use borrowed_subrange_t instead.") =
456  borrowed_subrange_t<R>;
457  } // namespace cpp20
459 } // namespace ranges
460 
461 RANGES_DIAGNOSTIC_PUSH
462 RANGES_DIAGNOSTIC_IGNORE_MISMATCHED_TAGS
463 
464 namespace std
465 {
466  template<typename I, typename S, ::ranges::subrange_kind K>
467  struct tuple_size<::ranges::subrange<I, S, K>> : std::integral_constant<size_t, 2>
468  {};
469  template<typename I, typename S, ::ranges::subrange_kind K>
470  struct tuple_element<0, ::ranges::subrange<I, S, K>>
471  {
472  using type = I;
473  };
474  template<typename I, typename S, ::ranges::subrange_kind K>
475  struct tuple_element<1, ::ranges::subrange<I, S, K>>
476  {
477  using type = S;
478  };
479 } // namespace std
480 
481 RANGES_DIAGNOSTIC_POP
482 
483 #include <range/v3/detail/epilogue.hpp>
484 
485 #endif
@ sized
satisfies ranges::concepts::sized_range
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
typename T::type _t
Type alias for T::type.
Definition: meta.hpp:141
meta::size_t< L::size()> size
An integral constant wrapper that is the size of the meta::list L.
Definition: meta.hpp:1696
bool_< 0==size< L >::type::value > empty
An Boolean integral constant wrapper around true if L is an empty type list; false,...
Definition: meta.hpp:2231
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
Tiny meta-programming library.
Definition: subrange.hpp:396
Definition: subrange.hpp:196
Definition: interface.hpp:129