Horizon
sliding.hpp
Go to the documentation of this file.
1 // Range v3 library
3 //
4 // Copyright Eric Niebler 2013-present
5 // Copyright Tobias Mayer 2016
6 // Copyright Casey Carter 2016
7 //
8 // Use, modification and distribution is subject to the
9 // Boost Software License, Version 1.0. (See accompanying
10 // file LICENSE_1_0.txt or copy at
11 // http://www.boost.org/LICENSE_1_0.txt)
12 //
13 // Project home: https://github.com/ericniebler/range-v3
14 //
15 
16 #ifndef RANGES_V3_VIEW_SLIDING_HPP
17 #define RANGES_V3_VIEW_SLIDING_HPP
18 
19 #include <utility>
20 
21 #include <meta/meta.hpp>
22 
23 #include <range/v3/range_fwd.hpp>
24 
31 #include <range/v3/utility/static_const.hpp>
33 #include <range/v3/view/all.hpp>
35 #include <range/v3/view/view.hpp>
36 
37 #include <range/v3/detail/prologue.hpp>
38 
39 namespace ranges
40 {
42  namespace sliding_view_detail
43  {
44  enum class cache
45  {
46  none,
47  first,
48  last
49  };
50 
51  template<typename Rng>
52  using caching = std::integral_constant<
53  cache, random_access_range<Rng> && sized_range<Rng>
54  ? cache::none
55  : bidirectional_range<Rng> && common_range<Rng> ? cache::last
56  : cache::first>;
57  } // namespace sliding_view_detail
59 
60  template<typename Rng,
61  sliding_view_detail::cache = sliding_view_detail::caching<Rng>::value>
62  struct sliding_view;
63 
65  namespace sliding_view_detail
66  {
67  template<typename Rng>
68  using uncounted_t =
69  decltype(ranges::uncounted(std::declval<iterator_t<Rng> &>()));
70 
71  template<typename Rng, bool = (bool)random_access_range<Rng>>
72  struct trailing
73  {
74  trailing() = default;
75  constexpr trailing(Rng & rng)
76  : it_{uncounted(ranges::begin(rng))}
77  {}
78  constexpr uncounted_t<Rng> get(iterator_t<Rng> const &,
79  range_difference_t<Rng>) const
80  {
81  return it_;
82  }
83  void next()
84  {
85  ++it_;
86  }
87  CPP_member
88  auto prev() //
89  -> CPP_ret(void)(
90  requires bidirectional_range<Rng>)
91  {
92  --it_;
93  }
94 
95  private:
96  uncounted_t<Rng> it_;
97  };
98 
99  template<typename Rng>
100  struct trailing<Rng, true>
101  {
102  trailing() = default;
103  constexpr trailing(Rng &) noexcept
104  {}
105  constexpr uncounted_t<Rng> get(iterator_t<Rng> const & it,
106  range_difference_t<Rng> n) const
107  {
108  return uncounted(it - (n - 1));
109  }
110  void next()
111  {}
112  void prev()
113  {}
114  };
115 
116  template<typename Rng>
117  struct RANGES_EMPTY_BASES sv_base
118  : view_adaptor<sliding_view<Rng>, Rng,
119  is_finite<Rng>::value ? finite : range_cardinality<Rng>::value>
120  , private detail::non_propagating_cache<iterator_t<Rng>, sv_base<Rng>,
121  caching<Rng>::value != cache::none>
122  {
123  CPP_assert(forward_range<Rng>);
124  sv_base() = default;
125  sv_base(Rng rng, range_difference_t<Rng> n)
126  : sv_base::view_adaptor(std::move(rng))
127  , n_(n)
128  {
129  RANGES_ASSERT(0 < n_);
130  }
131  CPP_auto_member
132  auto CPP_fun(size)()(const //
133  requires sized_range<Rng const>)
134  {
135  auto const count = ranges::size(this->base());
136  auto const n = static_cast<range_size_t<Rng const>>(n_);
137  return count < n ? 0 : count - n + 1;
138  }
139  CPP_auto_member
140  auto CPP_fun(size)()(
141  requires sized_range<Rng>)
142  {
143  auto const count = ranges::size(this->base());
144  auto const n = static_cast<range_size_t<Rng>>(n_);
145  return count < n ? 0 : count - n + 1;
146  }
147 
148  protected:
149  range_difference_t<Rng> n_;
150 
151  optional<iterator_t<Rng>> & cache() &
152  {
153  return static_cast<cache_t &>(*this);
154  }
155  optional<iterator_t<Rng>> const & cache() const &
156  {
157  return static_cast<cache_t const &>(*this);
158  }
159 
160  private:
161  using cache_t = detail::non_propagating_cache<iterator_t<Rng>, sv_base<Rng>>;
162  };
163  } // namespace sliding_view_detail
165 
168  template<typename Rng>
169  struct sliding_view<Rng, sliding_view_detail::cache::first>
170  : sliding_view_detail::sv_base<Rng>
171  {
172  private:
173  friend range_access;
174 
175  iterator_t<Rng> get_first()
176  {
177  auto & first = this->cache();
178  if(!first)
179  {
180  first = ranges::next(
181  ranges::begin(this->base()), this->n_ - 1, ranges::end(this->base()));
182  }
183  return *first;
184  }
185 
186  struct RANGES_EMPTY_BASES adaptor
187  : adaptor_base
188  , sliding_view_detail::trailing<Rng>
189  {
190  private:
191  using base_t = sliding_view_detail::trailing<Rng>;
192  range_difference_t<Rng> n_ = {};
193 
194  public:
195  adaptor() = default;
196  adaptor(sliding_view * v)
197  : base_t{v->base()}
198  , n_{v->n_}
199  {}
200  iterator_t<Rng> begin(sliding_view & v)
201  {
202  return v.get_first();
203  }
204  auto read(iterator_t<Rng> const & it) const
205  -> decltype(views::counted(uncounted(it), n_))
206  {
207  return views::counted(base_t::get(it, n_), n_);
208  }
209  void next(iterator_t<Rng> & it)
210  {
211  ++it;
212  base_t::next();
213  }
214  CPP_member
215  auto prev(iterator_t<Rng> & it) //
216  -> CPP_ret(void)(
217  requires bidirectional_range<Rng>)
218  {
219  base_t::prev();
220  --it;
221  }
222  CPP_member
223  auto advance(iterator_t<Rng> & it, range_difference_t<Rng> n)
224  -> CPP_ret(void)(
225  requires random_access_range<Rng>)
226  {
227  it += n;
228  }
229  };
230 
231  adaptor begin_adaptor()
232  {
233  return {this};
234  }
235  meta::if_c<common_range<Rng>, adaptor, adaptor_base> end_adaptor()
236  {
237  return {this};
238  }
239 
240  public:
241  using sliding_view::sv_base::sv_base;
242  };
243 
244  template<typename Rng>
245  struct sliding_view<Rng, sliding_view_detail::cache::last>
246  : sliding_view_detail::sv_base<Rng>
247  {
248  private:
249  friend range_access;
250 
251  iterator_t<Rng> get_last()
252  {
253  auto & last = this->cache();
254  if(!last)
255  {
256  last = ranges::prev(
257  ranges::end(this->base()), this->n_ - 1, ranges::begin(this->base()));
258  }
259  return *last;
260  }
261 
262  struct adaptor : adaptor_base
263  {
264  private:
265  range_difference_t<Rng> n_ = {};
266 
267  public:
268  adaptor() = default;
269  adaptor(sliding_view * v)
270  : n_{v->n_}
271  {}
273  {
274  return v.get_last();
275  }
276  auto read(iterator_t<Rng> const & it) const
277  -> decltype(views::counted(uncounted(it), n_))
278  {
279  return views::counted(uncounted(it), n_);
280  }
281  };
282 
283  adaptor begin_adaptor()
284  {
285  return {this};
286  }
287  adaptor end_adaptor()
288  {
289  return {this};
290  }
291 
292  public:
293  using sliding_view::sv_base::sv_base;
294  };
295 
296  template<typename Rng>
297  struct sliding_view<Rng, sliding_view_detail::cache::none>
298  : sliding_view_detail::sv_base<Rng>
299  {
300  private:
301  friend range_access;
302 
303  template<bool Const>
304  struct adaptor : adaptor_base
305  {
306  private:
307  friend adaptor<!Const>;
308  using CRng = meta::const_if_c<Const, Rng>;
309  range_difference_t<Rng> n_ = 0;
310 
311  public:
312  adaptor() = default;
313  adaptor(range_difference_t<Rng> n)
314  : n_(n)
315  {}
316  template(bool Other)(
317  requires Const AND CPP_NOT(Other)) //
318  adaptor(adaptor<Other> that)
319  : n_(that.n_)
320  {}
321  iterator_t<CRng> end(meta::const_if_c<Const, sliding_view> & v) const
322  {
323  auto const sz = ranges::distance(v.base());
324  auto const offset = n_ - 1 < sz ? n_ - 1 : sz;
325  return ranges::begin(v.base()) + (sz - offset);
326  }
327  auto read(iterator_t<CRng> const & it) const
328  -> decltype(views::counted(uncounted(it), n_))
329  {
330  return views::counted(uncounted(it), n_);
331  }
332  };
333 
334  adaptor<simple_view<Rng>()> begin_adaptor()
335  {
336  return {this->n_};
337  }
338  CPP_member
339  auto begin_adaptor() const //
340  -> CPP_ret(adaptor<true>)(
341  requires range<Rng const>)
342  {
343  return {this->n_};
344  }
345  adaptor<simple_view<Rng>()> end_adaptor()
346  {
347  return {this->n_};
348  }
349  CPP_member
350  auto end_adaptor() const //
351  -> CPP_ret(adaptor<true>)(
352  requires range<Rng const>)
353  {
354  return {this->n_};
355  }
356 
357  public:
358  using sliding_view::sv_base::sv_base;
359  };
360 
361  template<typename Rng>
362  RANGES_INLINE_VAR constexpr bool enable_borrowed_range<sliding_view<Rng>> = //
363  enable_borrowed_range<Rng>;
364 
365 #if RANGES_CXX_DEDUCTION_GUIDES >= RANGES_CXX_DEDUCTION_GUIDES_17
366  template<typename Rng>
367  sliding_view(Rng &&, range_difference_t<Rng>)
369 #endif
370 
371  namespace views
372  {
373  // In: range<T>
374  // Out: range<range<T>>, where each inner range has $n$ elements.
376  {
377  template(typename Rng)(
378  requires viewable_range<Rng> AND forward_range<Rng>)
379  constexpr sliding_view<all_t<Rng>> //
380  operator()(Rng && rng, range_difference_t<Rng> n) const
381  {
382  return {all(static_cast<Rng &&>(rng)), n};
383  }
384  };
385 
387  {
388  using sliding_base_fn::operator();
389 
390  template<typename Int>
391  constexpr auto CPP_fun(operator())(Int n)(const //
392  requires detail::integer_like_<Int>)
393  {
394  return make_view_closure(bind_back(sliding_base_fn{}, n));
395  }
396  };
397 
401  } // namespace views
403 } // namespace ranges
404 
405 #include <range/v3/detail/epilogue.hpp>
406 
407 #endif
@ none
No concepts met.
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
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::count_< L, T > > count
Count the number of times a type T appears in the list L.
Definition: meta.hpp:2725
Tiny meta-programming library.
Definition: adaptor.hpp:110
Definition: sliding.hpp:62
Definition: sliding.hpp:376
Definition: sliding.hpp:387