range.hpp
Go to the documentation of this file.
1 
14 #ifndef CORE_RANGE_HPP
15 #define CORE_RANGE_HPP
16 
17 #include <istream>
18 #include <utility>
19 #include <memory>
20 
21 #include <cstdlib>
22 
23 #include "type_traits.hpp"
24 #include "iterator.hpp"
25 
26 namespace core {
27 inline namespace v2 {
28 namespace impl {
29 
30 using ::std::begin;
31 using ::std::end;
32 
33 template <class T> using adl_begin_t = decltype(begin(::std::declval<T>()));
34 template <class T> using adl_end_t = decltype(end(::std::declval<T>()));
35 
36 template <class T>
38  using ::std::begin;
39  return begin(::core::forward<T>(t));
40 }
41 
42 template <class T>
44  using ::std::end;
45  return end(::core::forward<T>(t));
46 }
47 
48 } /* namespace impl */
49 
50 template <class R>
52  is_detected<impl::adl_begin_t, R>::value,
53  is_detected<impl::adl_end_t, R>::value
54 > { };
55 
56 template <class Iterator>
57 struct range {
58  using traits = ::std::iterator_traits<Iterator>;
59 
60  using iterator_category = typename traits::iterator_category;
61 
62  using difference_type = typename traits::difference_type;
63  using value_type = typename traits::value_type;
64 
65  using reference = typename traits::reference;
66  using pointer = typename traits::pointer;
67 
68  using iterator = Iterator;
69 
70  static constexpr bool is_input = ::std::is_convertible<
72  ::std::input_iterator_tag
73  >::value;
74 
75  static constexpr bool is_output = ::std::is_convertible<
76  iterator_category,
77  ::std::output_iterator_tag
78  >::value;
79 
80  static constexpr bool is_forward = ::std::is_convertible<
81  iterator_category,
82  ::std::forward_iterator_tag
83  >::value;
84 
85  static constexpr bool is_bidirectional = ::std::is_convertible<
86  iterator_category,
87  ::std::bidirectional_iterator_tag
88  >::value;
89 
90  static constexpr bool is_random_access = ::std::is_convertible<
91  iterator_category,
92  ::std::random_access_iterator_tag
93  >::value;
94 
95  template <
96  class Range,
97  class=meta::when<
98  meta::all<
99  meta::none<
100  ::std::is_pointer<iterator>::value,
101  ::std::is_same<decay_t<Range>, range>::value
102  >(),
105  >()
106  >
107  > explicit range (Range&& r) noexcept :
108  begin_ { impl::adl_begin(::core::forward<Range>(r)) },
109  end_ { impl::adl_end(::core::forward<Range>(r)) }
110  { }
111 
112  range (::std::pair<iterator, iterator> pair) noexcept :
113  range { ::std::get<0>(pair), ::std::get<1>(pair) }
114  { }
115 
116  range (iterator begin_, iterator end_) noexcept :
117  begin_ { begin_ },
118  end_ { end_ }
119  { }
120 
121  range (range const& that) :
122  range { that.begin_, that.end_ }
123  { }
124 
125  range (range&& that) noexcept :
126  range { ::core::move(that.begin_), ::core::move(that.end_) }
127  { that.begin_ = that.end_; }
128 
129  range () = default;
130  ~range () = default;
131 
132  range& operator = (range const& that) {
133  return *this = range { that };
134  }
135 
136  range& operator = (range&& that) {
137  range { ::std::move(that) }.swap(*this);
138  return *this;
139  }
140 
141  reference operator [](difference_type idx) const {
142  static_assert(is_random_access, "can only subscript into random-access");
143  return idx < 0 ? this->end()[idx] : this->begin()[idx];
144  }
145 
146  iterator begin () const { return this->begin_; }
147  iterator end () const { return this->end_; }
148 
149  reference front () const { return *this->begin(); }
150  reference back () const {
151  static_assert(is_bidirectional, "can only get back of bidirectional");
152  return *::std::prev(this->end());
153  }
154 
155  bool empty () const { return this->begin() == this->end(); }
156 
158  static_assert(is_forward, "can only get size of forward-range");
159  return ::std::distance(this->begin(), this->end());
160  }
161 
162  /* Creates an open-ended range of [start, stop) */
164  static_assert(is_forward, "can only slice forward-range");
165  /* Behavior is:
166  * if start is negative, the begin marker is this->end() - start
167  * if stop is negative, the end marker is this->end() - stop
168  * if start is positive, the begin marker is this->begin() + start
169  * if stop is positive, the end marker is this->begin() + stop
170  *
171  * if start and stop are positive, and stop is less than or equal to start,
172  * an empty range is returned.
173  *
174  * if start and stop are negative and stop is less than or equal to start,
175  * an empty range is returned.
176  *
177  * if start is positive and stop is negative and abs(stop) + start is
178  * greater than or equal to this->size(), an empty range is returned.
179  *
180  * if start is negative and stop is positive and this->size() + start is
181  * greater or equal to stop, an empty range is returned.
182  *
183  * The first two conditions can be computed cheaply, while the third and
184  * fourth are a bit more expensive, but WILL be required no matter what
185  * iterator type we are. However we don't compute the size until after
186  * we've checked the first two conditions
187  *
188  * An example with python style slicing for each would be:
189  * [4:3] -> empty range
190  * [-4:-4] -> empty range
191  * [7:-4] -> empty range for string of size 11 or more
192  * [-4:15] -> empty range for a string of size 19 or less.
193  */
194  bool const start_positive = start > 0;
195  bool const stop_positive = stop > 0;
196  bool const stop_less = stop < start;
197  bool const first_return_empty = start_positive == stop_positive and stop_less;
198  if (first_return_empty) { return range { }; }
199 
200  /* now safe to compute size */
201  auto const size = this->size();
202  auto const third_empty = ::std::abs(stop) + start;
203 
204  bool const second_return_empty =
205  (start_positive and not stop_positive and third_empty >= size) or
206  (not start_positive and stop_positive and size + start >= stop);
207  if (second_return_empty) { return range { }; }
208 
209  /* While the code below technically works for all iterators it is
210  * ineffecient in some cases for bidirectional ranges, where either of
211  * start or stop are negative.
212  * TODO: Specialize for bidirectional operators
213  */
214  if (not start_positive) { start += size; }
215  if (not stop_positive) { stop += size; }
216 
217  auto begin = this->begin();
218  ::std::advance(begin, start);
219 
220  auto end = begin;
221  ::std::advance(end, stop - start);
222 
223  return range { begin, end };
224  }
225 
226  /* Creates an open-ended range of [start, end()) */
227  range slice (difference_type start) const {
228  static_assert(is_forward, "can only slice forward-range");
229  return range { split(start).second };
230  }
231 
232  ::std::pair<range, range> split (difference_type idx) const {
233  static_assert(is_forward,"can only split a forward-range");
234  if (idx >= 0) {
235  range second { *this };
236  second.pop_front_upto(idx);
237  return ::std::make_pair(range { this->begin(), second.begin() }, second);
238  }
239 
240  range first { *this };
241  first.pop_back_upto(-idx);
242  return ::std::make_pair(first, range { first.end(), this->end() });
243  }
244 
245  /* mutates range */
246  void pop_front (difference_type n) { ::std::advance(this->begin_, n); }
247  void pop_front () { ++this->begin_; }
248 
250  static_assert(is_bidirectional, "can only pop-back bidirectional-range");
251  ::std::advance(this->end_, -n);
252  }
253 
254  void pop_back () {
255  static_assert(is_bidirectional, "can only pop-back bidirectional-range");
256  --this->end_;
257  }
258 
259  /* Negative argument causes no change */
261  ::std::advance(
262  this->begin_,
263  ::std::min(::std::max<difference_type>(0, n), this->size())
264  );
265  }
266 
267  /* Negative argument causes no change */
269  static_assert(is_bidirectional, "can only pop-back-upto bidirectional");
270  ::std::advance(
271  this->end_,
272  -::std::min(::std::max<difference_type>(0, n), this->size())
273  );
274  }
275 
278  swap(this->begin_, that.begin_);
279  swap(this->end_, that.end_);
280  }
281 
282 private:
283  iterator begin_;
284  iterator end_;
285 };
286 
287 template <class T>
288 auto make_range (T* ptr, ::std::size_t n) -> range<T*> {
289  return range<T*> { ptr, ptr + n };
290 }
291 
292 template <class Iterator>
293 auto make_range (Iterator begin, Iterator end) -> range<Iterator> {
294  return range<Iterator> { begin, end };
295 }
296 
297 template <class Range>
299  using ::std::begin;
300  using ::std::end;
301  return make_range(begin(value), end(value));
302 }
303 
304 /* Used like: core::make_range<char>(::std::cin) */
305 template <
306  class T,
307  class CharT,
308  class Traits=::std::char_traits<CharT>
309 > auto make_range (::std::basic_istream<CharT, Traits>& stream) -> range<
310  ::std::istream_iterator<T, CharT, Traits>
311 > {
312  using iterator = ::std::istream_iterator<T, CharT, Traits>;
313  return make_range(iterator { stream }, iterator { });
314 }
315 
316 template <class CharT, class Traits=::std::char_traits<CharT>>
317 auto make_range (::std::basic_streambuf<CharT, Traits>* buffer) -> range<
318  ::std::istreambuf_iterator<CharT, Traits>
319 > {
320  using iterator = ::std::istreambuf_iterator<CharT, Traits>;
321  return make_range(iterator { buffer }, iterator { });
322 }
323 
324 template <class Iter>
326  return make_range(
327  ::std::make_move_iterator(start),
328  ::std::make_move_iterator(stop));
329 }
330 
331 template <class T>
333  return make_move_range(ptr, ptr + n);
334 }
335 
336 template <class T>
337 range<number_iterator<T>> make_number_range(T start, T stop, T step) noexcept {
338  auto begin = make_number_iterator(start, step);
339  auto end = make_number_iterator(stop, step);
340  return make_range(begin, end);
341 }
342 
343 template <class T>
344 range<number_iterator<T>> make_number_range (T start, T stop) noexcept {
346 }
347 
348 template <class Iterator>
349 void swap (range<Iterator>& lhs, range<Iterator>& rhs) noexcept(
350  noexcept(lhs.swap(rhs))
351 ) { lhs.swap(rhs); }
352 
353 }} /* namespace core::v2 */
354 
355 #endif /* CORE_RANGE_HPP */
typename traits::difference_type difference_type
Definition: range.hpp:62
bool empty() const
Definition: range.hpp:155
range slice(difference_type start) const
Definition: range.hpp:227
number_iterator< T > make_number_iterator(T value, T step) noexcept
Definition: iterator.hpp:261
reference back() const
Definition: range.hpp:150
iterator end() const
Definition: range.hpp:147
constexpr auto size(Container const &container) noexcept -> decltype(container.size())
Definition: iterator.hpp:29
void pop_front(difference_type n)
Definition: range.hpp:246
::std::iterator_traits< Iterator > traits
Definition: range.hpp:58
auto make_range(T *ptr, ::std::size_t n) -> range< T *>
Definition: range.hpp:288
range(range &&that) noexcept
Definition: range.hpp:125
constexpr bool none() noexcept
Definition: meta.hpp:276
void pop_back()
Definition: range.hpp:254
Copyright © 2013 - 2015 MNMLSTC.
Definition: algorithm.hpp:23
adl_end_t< T > adl_end(T &&t)
Definition: range.hpp:43
iterator begin() const
Definition: range.hpp:146
::std::is_convertible< detected_t< T, Args... >, To > is_detected_convertible
Definition: type_traits.hpp:88
::std::pair< range, range > split(difference_type idx) const
Definition: range.hpp:232
constexpr bool all() noexcept
Definition: meta.hpp:279
RangeType< double > Range
3.0.0 TODO: break reverse-compatibility by changing RangeType to Range.
Definition: range.hpp:19
range(Range &&r) noexcept
Definition: range.hpp:107
void pop_back_upto(difference_type n)
Definition: range.hpp:268
decltype(end(::std::declval< T >())) adl_end_t
Definition: range.hpp:34
range(iterator begin_, iterator end_) noexcept
Definition: range.hpp:116
typename traits::iterator_category iterator_category
Definition: range.hpp:60
void pop_front_upto(difference_type n)
Definition: range.hpp:260
void pop_front()
Definition: range.hpp:247
adl_begin_t< T > adl_begin(T &&t)
Definition: range.hpp:37
typename ::std::enable_if< B, T >::type when
Definition: meta.hpp:193
difference_type size() const
Definition: range.hpp:157
void swap(any &lhs, any &rhs) noexcept
Definition: any.hpp:333
typename traits::reference reference
Definition: range.hpp:65
decltype(begin(::std::declval< T >())) adl_begin_t
Definition: range.hpp:33
range< number_iterator< T > > make_number_range(T start, T stop, T step) noexcept
Definition: range.hpp:337
void swap(range &that) noexcept(is_nothrow_swappable< iterator >::value)
Definition: range.hpp:276
Iterator iterator
Definition: range.hpp:68
range<::std::move_iterator< Iter > > make_move_range(Iter start, Iter stop)
Definition: range.hpp:325
constexpr T const & min(T const &lhs, T const &rhs)
Definition: algorithm.hpp:69
range(::std::pair< iterator, iterator > pair) noexcept
Definition: range.hpp:112
range slice(difference_type start, difference_type stop) const
Definition: range.hpp:163
range(range const &that)
Definition: range.hpp:121
auto move(Range &&rng, OutputIt &&it) -> enable_if_t< is_range< Range >::value, decay_t< OutputIt > >
Definition: algorithm.hpp:736
void pop_back(difference_type n)
Definition: range.hpp:249
reference front() const
Definition: range.hpp:149
void swap(range< Iterator > &lhs, range< Iterator > &rhs) noexcept(noexcept(lhs.swap(rhs)))
Definition: range.hpp:349
typename traits::value_type value_type
Definition: range.hpp:63
typename traits::pointer pointer
Definition: range.hpp:66