Horizon
drop_last.hpp
Go to the documentation of this file.
1 // Range v3 library
3 //
4 // Copyright Andrey Diduh 2019
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_DROP_LAST_HPP
15 #define RANGES_V3_VIEW_DROP_LAST_HPP
16 
17 #include <type_traits>
18 
19 #include <meta/meta.hpp>
20 
29 #include <range/v3/utility/static_const.hpp>
31 #include <range/v3/view/all.hpp>
33 #include <range/v3/view/view.hpp>
34 
35 #include <range/v3/detail/prologue.hpp>
36 
37 namespace ranges
38 {
41 
43  namespace detail
44  {
45  namespace drop_last_view
46  {
47  template<typename Rng>
48  range_size_t<Rng> get_size(Rng & rng, range_difference_t<Rng> n_)
49  {
50  RANGES_EXPECT(n_ >= 0);
51  range_size_t<Rng> const initial_size = ranges::size(rng);
52  range_size_t<Rng> const n = static_cast<range_size_t<Rng>>(n_);
53  return initial_size > n ? initial_size - n : 0;
54  }
55 
56  template(typename Rng)(
57  requires random_access_range<Rng> AND sized_range<Rng>)
58  iterator_t<Rng> get_end(Rng & rng, range_difference_t<Rng> n, int)
59  {
60  return begin(rng) + static_cast<range_difference_t<Rng>>(
61  drop_last_view::get_size(rng, n));
62  }
63  template(typename Rng)(
64  requires bidirectional_range<Rng> AND common_range<Rng>)
65  iterator_t<Rng> get_end(Rng & rng, range_difference_t<Rng> n, long)
66  {
67  return prev(end(rng), n, begin(rng));
68  }
69 
70  enum class mode_enum
71  {
72  bidi,
73  forward,
74  sized,
75  invalid
76  };
77 
78  template<mode_enum Mode>
79  using mode_t = std::integral_constant<mode_enum, Mode>;
80 
81  using mode_bidi = mode_t<mode_enum::bidi>;
82  using mode_forward = mode_t<mode_enum::forward>;
83  using mode_sized = mode_t<mode_enum::sized>;
84  using mode_invalid = mode_t<mode_enum::invalid>;
85 
86  template<typename Rng>
87  constexpr mode_enum get_mode() noexcept
88  {
89  // keep range bound
90  // Sized Bidi O(N)
91  return (random_access_range<Rng> && view_<Rng> && sized_range<Rng>) ||
92  (bidirectional_range<Rng> && view_<Rng> &&
93  common_range<Rng>)
94  ? mode_enum::bidi //
95  : sized_range<Rng> && view_<Rng> //
96  ? mode_enum::sized //
97  : forward_range<Rng> && view_<Rng> //
98  ? mode_enum::forward //
99  : mode_enum::invalid; //
100 
101  // max performance
102  // Sized Bidi O(1)
103  // Sized Bidi use mode::sized instead of mode::bidi - thus become unbound.
104  /*return (random_access_range<Rng> && view_<Rng> && sized_range<Rng> &&
105  view_<Rng>) || (bidirectional_range<Rng> && view_<Rng> &&
106  common_range<Rng> && view_<Rng>) ? mode::bidi : sized_range<Rng> &&
107  view_<Rng> ? mode::sized : bidirectional_range<Rng> && view_<Rng> &&
108  common_range<Rng> && view_<Rng> ? mode::bidi : forward_range<Rng> &&
109  view_<Rng> ? mode::forward : mode::invalid;*/
110  }
111 
112  template<typename Rng>
113  using mode_of = mode_t<drop_last_view::get_mode<Rng>()>;
114  } // namespace drop_last_view
115  } // namespace detail
117 
118  template<typename Rng, typename = detail::drop_last_view::mode_of<Rng>>
120  {};
121 
122  template<typename Rng>
123  struct drop_last_view<Rng, detail::drop_last_view::mode_bidi>
124  : view_interface<drop_last_view<Rng, detail::drop_last_view::mode_bidi>,
125  is_finite<Rng>::value
126  ? finite
127  : range_cardinality<Rng>::value> // finite at best
128  {
129  CPP_assert(
130  (random_access_range<Rng> && view_<Rng> && sized_range<Rng>) ||
131  (bidirectional_range<Rng> && view_<Rng> && common_range<Rng>));
132 
133  private:
134  friend range_access;
135  using difference_t = range_difference_t<Rng>;
136 
137  Rng rng_;
138  difference_t n_;
139  detail::non_propagating_cache<iterator_t<Rng>> end_;
140 
141  public:
142  drop_last_view() = default;
143  constexpr drop_last_view(Rng rng, difference_t n)
144  : rng_(std::move(rng))
145  , n_(n)
146  {
147  RANGES_EXPECT(n >= 0);
148  }
149 
150  iterator_t<Rng> begin()
151  {
152  return ranges::begin(rng_);
153  }
154  sentinel_t<Rng> end()
155  {
156  if(!end_)
157  end_ = detail::drop_last_view::get_end(rng_, n_, 0);
158  return *end_;
159  }
160  template(typename CRng = Rng const)(
161  requires random_access_range<CRng> AND sized_range<CRng>)
162  iterator_t<CRng> begin() const
163  {
164  return ranges::begin(rng_);
165  }
166  template(typename CRng = Rng const)(
167  requires random_access_range<CRng> AND sized_range<CRng>)
168  iterator_t<CRng> end() const
169  {
170  return detail::drop_last_view::get_end(rng_, n_, 0);
171  }
172 
173  CPP_auto_member
174  auto CPP_fun(size)()(
175  requires sized_range<Rng>)
176  {
177  return detail::drop_last_view::get_size(rng_, n_);
178  }
179  CPP_auto_member
180  auto CPP_fun(size)()(const //
181  requires sized_range<Rng const>)
182  {
183  return detail::drop_last_view::get_size(rng_, n_);
184  }
185 
186  Rng & base()
187  {
188  return rng_;
189  }
190  Rng const & base() const
191  {
192  return rng_;
193  }
194  };
195 
196  template<typename Rng>
199  is_finite<Rng>::value
200  ? finite
201  : range_cardinality<Rng>::value> // finite at best (but
202  // unknown is expected)
203  {
204  CPP_assert(forward_range<Rng> && view_<Rng>);
205 
206  private:
207  friend range_access;
208 
209  using difference_t = range_difference_t<Rng>;
210  difference_t n_;
211  detail::non_propagating_cache<iterator_t<Rng>> probe_begin;
212 
213  struct adaptor : adaptor_base
214  {
215  iterator_t<Rng> probe_;
216 
217  adaptor() = default;
218  adaptor(iterator_t<Rng> probe_first)
219  : probe_(std::move(probe_first))
220  {}
221  void next(iterator_t<Rng> & it)
222  {
223  ++it;
224  ++probe_;
225  }
226  };
227 
228  struct sentinel_adaptor : adaptor_base
229  {
230  template<typename I, typename S>
231  bool empty(I const &, adaptor const & ia, S const & s) const
232  {
233  return ia.probe_ == s;
234  }
235  };
236 
237  adaptor begin_adaptor()
238  {
239  if(!probe_begin)
240  probe_begin = next(begin(this->base()), n_, end(this->base()));
241  return {*probe_begin};
242  }
243  sentinel_adaptor end_adaptor()
244  {
245  return {};
246  }
247 
248  public:
249  drop_last_view() = default;
250  constexpr drop_last_view(Rng rng, difference_t n)
251  : drop_last_view::view_adaptor(std::move(rng))
252  , n_(n)
253  {
254  RANGES_EXPECT(n >= 0);
255  }
256 
257  CPP_auto_member
258  auto CPP_fun(size)()(
259  requires sized_range<Rng>)
260  {
261  return detail::drop_last_view::get_size(this->base(), n_);
262  }
263  CPP_auto_member
264  auto CPP_fun(size)()(const //
265  requires sized_range<Rng const>)
266  {
267  return detail::drop_last_view::get_size(this->base(), n_);
268  }
269  };
270 
271  template<typename Rng>
272  struct drop_last_view<Rng, detail::drop_last_view::mode_sized>
273  : view_interface<drop_last_view<Rng, detail::drop_last_view::mode_sized>, finite>
274  {
275  CPP_assert(sized_range<Rng> && view_<Rng>);
276 
277  private:
278  friend range_access;
279 
280  using difference_t = range_difference_t<Rng>;
281  Rng rng_;
282  difference_t n_;
283 
284  public:
285  drop_last_view() = default;
286  constexpr drop_last_view(Rng rng, difference_t n)
287  : rng_(std::move(rng))
288  , n_(n)
289  {
290  RANGES_EXPECT(n >= 0);
291  }
292 
293  counted_iterator<iterator_t<Rng>> begin()
294  {
295  return {ranges::begin(rng_), static_cast<difference_t>(size())};
296  }
297  template(typename CRng = Rng const)(
298  requires sized_range<CRng>)
299  counted_iterator<iterator_t<CRng>> begin() const
300  {
301  return {ranges::begin(rng_), static_cast<difference_t>(size())};
302  }
303  default_sentinel_t end() const
304  {
305  return {};
306  }
307  range_size_t<Rng> size()
308  {
309  return detail::drop_last_view::get_size(this->base(), n_);
310  }
311  CPP_auto_member
312  auto CPP_fun(size)()(const //
313  requires sized_range<Rng const>)
314  {
315  return detail::drop_last_view::get_size(this->base(), n_);
316  }
317 
318  Rng & base()
319  {
320  return rng_;
321  }
322  Rng const & base() const
323  {
324  return rng_;
325  }
326  };
327 
328  template<typename Rng, typename T>
329  RANGES_INLINE_VAR constexpr bool enable_borrowed_range<drop_last_view<Rng, T>> = //
330  enable_borrowed_range<Rng>;
331 
332 #if RANGES_CXX_DEDUCTION_GUIDES >= RANGES_CXX_DEDUCTION_GUIDES_17
333  template<typename Rng>
334  drop_last_view(Rng &&, range_difference_t<Rng>)
336 #endif
337 
338  namespace views
339  {
341  {
342  template(typename Rng)(
343  requires sized_range<Rng> || forward_range<Rng>)
344  constexpr auto operator()(Rng && rng, range_difference_t<Rng> n) const
346  {
347  return {all(static_cast<Rng &&>(rng)), n};
348  }
349  };
350 
352  {
353  using drop_last_base_fn::operator();
354 
355  template(typename Int)(
356  requires detail::integer_like_<Int>)
357  constexpr auto operator()(Int n) const
358  {
359  return make_view_closure(bind_back(drop_last_base_fn{}, n));
360  }
361  };
362 
364  } // namespace views
365 
367 } // namespace ranges
368 
369 #include <range/v3/detail/epilogue.hpp>
370 #include <range/v3/detail/satisfy_boost_range.hpp>
371 RANGES_SATISFY_BOOST_RANGE(::ranges::drop_last_view)
372 
373 #endif
@ sized
satisfies ranges::concepts::sized_range
@ forward
satisfies ranges::concepts::forward_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
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
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
Tiny meta-programming library.
Definition: adaptor.hpp:110
Definition: default_sentinel.hpp:26
Definition: drop_last.hpp:120
Definition: traits.hpp:128
Definition: adaptor.hpp:475
Definition: interface.hpp:129
Definition: drop_last.hpp:341
Definition: drop_last.hpp:352