openMSX
view.hh
Go to the documentation of this file.
1 #ifndef VIEW_HH
2 #define VIEW_HH
3 
4 #include "semiregular.hh"
5 #include <algorithm>
6 #include <functional>
7 #include <iterator>
8 #include <tuple>
9 #include <type_traits>
10 
11 namespace view {
12 namespace detail {
13 
14 template<typename Iterator>
15 [[nodiscard]] constexpr Iterator safe_next(Iterator first, Iterator last, size_t n, std::input_iterator_tag)
16 {
17  while (n-- && (first != last)) ++first;
18  return first;
19 }
20 
21 template<typename Iterator>
22 [[nodiscard]] constexpr Iterator safe_next(Iterator first, Iterator last, size_t n, std::random_access_iterator_tag)
23 {
24  return first + std::min<size_t>(n, last - first);
25 }
26 
27 template<typename Iterator>
28 [[nodiscard]] constexpr Iterator safe_prev(Iterator first, Iterator last, size_t n, std::bidirectional_iterator_tag)
29 {
30  while (n-- && (first != last)) --last;
31  return last;
32 }
33 
34 template<typename Iterator>
35 [[nodiscard]] constexpr Iterator safe_prev(Iterator first, Iterator last, size_t n, std::random_access_iterator_tag)
36 {
37  return last - std::min<size_t>(n, last - first);
38 }
39 
40 
41 template<typename Range>
42 class Drop
43 {
44 public:
45  constexpr Drop(Range&& range_, size_t n_)
46  : range(std::forward<Range>(range_))
47  , n(n_)
48  {
49  }
50 
51  [[nodiscard]] constexpr auto begin() const {
52  using Iterator = decltype(std::begin(range));
53  return safe_next(std::begin(range), std::end(range), n,
54  typename std::iterator_traits<Iterator>::iterator_category());
55  }
56 
57  [[nodiscard]] constexpr auto end() const {
58  return std::end(range);
59  }
60 
61 private:
62  Range range;
63  size_t n;
64 };
65 
66 
67 template<typename Range>
68 class DropBack
69 {
70 public:
71  constexpr DropBack(Range&& range_, size_t n_)
72  : range(std::forward<Range>(range_))
73  , n(n_)
74  {
75  }
76 
77  [[nodiscard]] constexpr auto begin() const {
78  return std::begin(range);
79  }
80 
81  [[nodiscard]] constexpr auto end() const {
82  using Iterator = decltype(std::begin(range));
83  return safe_prev(std::begin(range), std::end(range), n,
84  typename std::iterator_traits<Iterator>::iterator_category());
85  }
86 
87 private:
88  Range range;
89  size_t n;
90 };
91 
92 
93 template<typename Range>
94 class Reverse
95 {
96 public:
97  constexpr explicit Reverse(Range&& range_)
98  : range(std::forward<Range>(range_))
99  {
100  }
101 
102  [[nodiscard]] constexpr auto begin() const { return range.rbegin(); }
103  [[nodiscard]] constexpr auto begin() { return range.rbegin(); }
104  [[nodiscard]] constexpr auto end() const { return range.rend(); }
105  [[nodiscard]] constexpr auto end() { return range.rend(); }
106  [[nodiscard]] constexpr auto rbegin() const { return range.begin(); }
107  [[nodiscard]] constexpr auto rbegin() { return range.begin(); }
108  [[nodiscard]] constexpr auto rend() const { return range.end(); }
109  [[nodiscard]] constexpr auto rend() { return range.end(); }
110 
111 private:
112  Range range;
113 };
114 
115 
116 template<typename Iterator, typename UnaryOp> class TransformIterator
117 {
118 public:
119  using return_type = std::invoke_result_t<UnaryOp, decltype(*std::declval<Iterator>())>;
120  using value_type = std::remove_reference_t<return_type>;
122  using pointer = value_type*;
123  using difference_type = typename std::iterator_traits<Iterator>::difference_type;
124  using iterator_category = typename std::iterator_traits<Iterator>::iterator_category;
125 
126 public:
127  constexpr TransformIterator() = default;
128 
129  constexpr TransformIterator(Iterator it_, UnaryOp op_)
130  : storage(it_, op_)
131  {
132  }
133 
134  // InputIterator, ForwardIterator
135 
136  [[nodiscard]] constexpr return_type operator*() const { return std::invoke(op(), *it()); }
137 
138  // pointer operator->() const not defined
139 
141  {
142  ++it();
143  return *this;
144  }
145 
147  {
148  auto copy = *this;
149  ++it();
150  return copy;
151  }
152 
153  [[nodiscard]] constexpr friend bool operator==(const TransformIterator& x, const TransformIterator& y)
154  {
155  return x.it() == y.it();
156  }
157 
158  [[nodiscard]] constexpr friend bool operator!=(const TransformIterator& x, const TransformIterator& y)
159  {
160  return x.it() != y.it();
161  }
162 
163  // BidirectionalIterator
164 
166  {
167  --it();
168  return *this;
169  }
170 
172  {
173  auto copy = *this;
174  --it();
175  return copy;
176  }
177 
178  // RandomAccessIterator
179 
181  {
182  it() += n;
183  return *this;
184  }
185 
187  {
188  it() -= n;
189  return *this;
190  }
191 
192  [[nodiscard]] constexpr friend TransformIterator operator+(TransformIterator x, difference_type n)
193  {
194  x += n;
195  return x;
196  }
197  [[nodiscard]] constexpr friend TransformIterator operator+(difference_type n, TransformIterator x)
198  {
199  x += n;
200  return x;
201  }
202 
203  [[nodiscard]] constexpr friend TransformIterator operator-(TransformIterator x, difference_type n)
204  {
205  x -= n;
206  return x;
207  }
208 
209  [[nodiscard]] constexpr friend difference_type operator-(const TransformIterator& x, const TransformIterator& y)
210  {
211  return x.it() - y.it();
212  }
213 
214  [[nodiscard]] constexpr reference operator[](difference_type n)
215  {
216  return *(*this + n);
217  }
218 
219  [[nodiscard]] constexpr friend bool operator<(const TransformIterator& x, const TransformIterator& y)
220  {
221  return x.it() < y.it();
222  }
223  [[nodiscard]] constexpr friend bool operator<=(const TransformIterator& x, const TransformIterator& y)
224  {
225  return x.it() <= y.it();
226  }
227  [[nodiscard]] constexpr friend bool operator>(const TransformIterator& x, const TransformIterator& y)
228  {
229  return x.it() > y.it();
230  }
231  [[nodiscard]] constexpr friend bool operator>=(const TransformIterator& x, const TransformIterator& y)
232  {
233  return x.it() >= y.it();
234  }
235 
236 private:
237  std::tuple<Iterator, semiregular_t<UnaryOp>> storage;
238 
239  [[nodiscard]] constexpr Iterator& it() { return std::get<0>(storage); }
240  [[nodiscard]] constexpr const Iterator& it() const { return std::get<0>(storage); }
241  [[nodiscard]] constexpr UnaryOp& op() { return std::get<1>(storage); }
242  [[nodiscard]] constexpr const UnaryOp& op() const { return std::get<1>(storage); }
243 };
244 
245 template<typename Range, typename UnaryOp> class Transform
246 {
247 public:
248  constexpr Transform(Range&& range_, UnaryOp op_)
249  : storage(std::forward<Range>(range_), op_)
250  {
251  }
252 
253  [[nodiscard]] constexpr auto begin() const
254  {
255  return TransformIterator(std::begin(range()), op());
256  }
257  [[nodiscard]] constexpr auto end() const
258  {
259  return TransformIterator(std::end(range()), op());
260  }
261  [[nodiscard]] constexpr auto rbegin() const
262  {
263  return TransformIterator(std::rbegin(range()), op());
264  }
265  [[nodiscard]] constexpr auto rend() const
266  {
267  return TransformIterator(std::rend(range()), op());
268  }
269 
270  [[nodiscard]] constexpr auto size() const { return range().size(); }
271  [[nodiscard]] constexpr auto empty() const { return range().empty(); }
272 
273  [[nodiscard]] constexpr auto front() const { return op()(range().front()); }
274  [[nodiscard]] constexpr auto back() const { return op()(range().back()); }
275 
276  [[nodiscard]] constexpr auto operator[](size_t idx) const {
277  return std::invoke(op(), range()[idx]);
278  }
279 
280 private:
281  std::tuple<Range, UnaryOp> storage;
282 
283  [[nodiscard]] constexpr const Range& range() const { return std::get<0>(storage); }
284  [[nodiscard]] constexpr const UnaryOp& op() const { return std::get<1>(storage); }
285 };
286 
287 
288 template<typename Iterator, typename Sentinel, typename Predicate>
290 {
291 public:
292  using value_type = typename std::iterator_traits<Iterator>::value_type;
293  using reference = typename std::iterator_traits<Iterator>::reference;
294  using pointer = typename std::iterator_traits<Iterator>::pointer;
295  using difference_type = typename std::iterator_traits<Iterator>::difference_type;
296  using iterator_category = std::forward_iterator_tag;
297 
298  constexpr FilteredIterator(Iterator it_, Sentinel last_, Predicate pred_)
299  : it(it_), last(last_), pred(pred_)
300  {
301  while (isFiltered()) ++it;
302  }
303 
304  [[nodiscard]] constexpr friend bool operator==(const FilteredIterator& x, const FilteredIterator& y)
305  {
306  return x.it == y.it;
307  }
308  [[nodiscard]] constexpr friend bool operator!=(const FilteredIterator& x, const FilteredIterator& y)
309  {
310  return !(x == y);
311  }
312 
313  [[nodiscard]] constexpr reference operator*() const { return *it; }
314  [[nodiscard]] constexpr pointer operator->() const { return &*it; }
315 
317  {
318  do {
319  ++it;
320  } while (isFiltered());
321  return *this;
322  }
324  {
325  FilteredIterator result = *this;
326  ++(*this);
327  return result;
328  }
329 
330 private:
331  [[nodiscard]] constexpr bool isFiltered()
332  {
333  return (it != last) && !std::invoke(pred, *it);
334  }
335 
336 private:
337  Iterator it;
338  Sentinel last;
339  Predicate pred;
340 };
341 
342 template<typename Range, typename Predicate>
343 class Filter
344 {
345 public:
346  using Iterator = decltype(std::begin(std::declval<Range>()));
347  using Sentinel = decltype(std::end (std::declval<Range>()));
349 
350  constexpr Filter(Range&& range_, Predicate pred_)
351  : range(std::forward<Range>(range_)), pred(pred_)
352  {
353  }
354 
355  [[nodiscard]] constexpr F_Iterator begin() const
356  {
357  return {std::begin(range), std::end(range), pred};
358  }
359  [[nodiscard]] constexpr F_Iterator end() const
360  {
361  // TODO should be a 'FilteredSentinel', but that only works well
362  // in c++20 (and c++20 already has 'std::views::filter').
363  return {std::end(range), std::end(range), pred};
364  }
365 
366 private:
367  Range range;
368  Predicate pred;
369 };
370 
371 } // namespace detail
372 
373 template<typename Range>
374 [[nodiscard]] constexpr auto drop(Range&& range, size_t n)
375 {
376  return detail::Drop<Range>(std::forward<Range>(range), n);
377 }
378 
379 template<typename Range>
380 [[nodiscard]] constexpr auto drop_back(Range&& range, size_t n)
381 {
382  return detail::DropBack<Range>(std::forward<Range>(range), n);
383 }
384 
385 template<typename Range>
386 [[nodiscard]] constexpr auto reverse(Range&& range)
387 {
388  return detail::Reverse<Range>(std::forward<Range>(range));
389 }
390 
391 template<typename Range, typename UnaryOp>
392 [[nodiscard]] constexpr auto transform(Range&& range, UnaryOp op)
393 {
394  return detail::Transform<Range, UnaryOp>(std::forward<Range>(range), op);
395 }
396 
397 template<typename Map> [[nodiscard]] constexpr auto keys(Map&& map)
398 {
399  return transform(std::forward<Map>(map),
400  [](const auto& t) -> auto& { return std::get<0>(t); });
401 }
402 
403 template<typename Map> [[nodiscard]] constexpr auto values(Map&& map)
404 {
405  return transform(std::forward<Map>(map),
406  [](const auto& t) -> auto& { return std::get<1>(t); });
407 }
408 
409 template<typename ForwardRange, typename Predicate>
410 [[nodiscard]] auto filter(ForwardRange&& range, Predicate pred)
411 {
412  return detail::Filter<ForwardRange, Predicate>{std::forward<ForwardRange>(range), pred};
413 }
414 
415 } // namespace view
416 
417 #endif
TclObject t
constexpr DropBack(Range &&range_, size_t n_)
Definition: view.hh:71
constexpr auto begin() const
Definition: view.hh:77
constexpr auto end() const
Definition: view.hh:81
constexpr Drop(Range &&range_, size_t n_)
Definition: view.hh:45
constexpr auto begin() const
Definition: view.hh:51
constexpr auto end() const
Definition: view.hh:57
constexpr F_Iterator end() const
Definition: view.hh:359
decltype(std::end(std::declval< Range >())) Sentinel
Definition: view.hh:347
constexpr Filter(Range &&range_, Predicate pred_)
Definition: view.hh:350
constexpr F_Iterator begin() const
Definition: view.hh:355
decltype(std::begin(std::declval< Range >())) Iterator
Definition: view.hh:346
constexpr pointer operator->() const
Definition: view.hh:314
typename std::iterator_traits< Iterator >::value_type value_type
Definition: view.hh:292
constexpr friend bool operator!=(const FilteredIterator &x, const FilteredIterator &y)
Definition: view.hh:308
typename std::iterator_traits< Iterator >::difference_type difference_type
Definition: view.hh:295
constexpr reference operator*() const
Definition: view.hh:313
constexpr FilteredIterator & operator++()
Definition: view.hh:316
constexpr FilteredIterator operator++(int)
Definition: view.hh:323
typename std::iterator_traits< Iterator >::pointer pointer
Definition: view.hh:294
typename std::iterator_traits< Iterator >::reference reference
Definition: view.hh:293
constexpr friend bool operator==(const FilteredIterator &x, const FilteredIterator &y)
Definition: view.hh:304
constexpr FilteredIterator(Iterator it_, Sentinel last_, Predicate pred_)
Definition: view.hh:298
std::forward_iterator_tag iterator_category
Definition: view.hh:296
constexpr auto rend() const
Definition: view.hh:108
constexpr auto end()
Definition: view.hh:105
constexpr auto rend()
Definition: view.hh:109
constexpr auto end() const
Definition: view.hh:104
constexpr auto begin() const
Definition: view.hh:102
constexpr auto rbegin()
Definition: view.hh:107
constexpr auto rbegin() const
Definition: view.hh:106
constexpr auto begin()
Definition: view.hh:103
constexpr Reverse(Range &&range_)
Definition: view.hh:97
constexpr TransformIterator & operator+=(difference_type n)
Definition: view.hh:180
std::invoke_result_t< UnaryOp, decltype(*std::declval< Iterator >())> return_type
Definition: view.hh:119
constexpr TransformIterator(Iterator it_, UnaryOp op_)
Definition: view.hh:129
constexpr friend difference_type operator-(const TransformIterator &x, const TransformIterator &y)
Definition: view.hh:209
std::remove_reference_t< return_type > value_type
Definition: view.hh:120
constexpr TransformIterator & operator++()
Definition: view.hh:140
constexpr TransformIterator & operator-=(difference_type n)
Definition: view.hh:186
constexpr TransformIterator()=default
constexpr TransformIterator operator++(int)
Definition: view.hh:146
constexpr return_type operator*() const
Definition: view.hh:136
constexpr TransformIterator operator--(int)
Definition: view.hh:171
typename std::iterator_traits< Iterator >::difference_type difference_type
Definition: view.hh:123
typename std::iterator_traits< Iterator >::iterator_category iterator_category
Definition: view.hh:124
constexpr friend bool operator!=(const TransformIterator &x, const TransformIterator &y)
Definition: view.hh:158
constexpr friend bool operator>=(const TransformIterator &x, const TransformIterator &y)
Definition: view.hh:231
constexpr friend bool operator==(const TransformIterator &x, const TransformIterator &y)
Definition: view.hh:153
constexpr friend bool operator<=(const TransformIterator &x, const TransformIterator &y)
Definition: view.hh:223
constexpr friend TransformIterator operator+(difference_type n, TransformIterator x)
Definition: view.hh:197
constexpr friend bool operator>(const TransformIterator &x, const TransformIterator &y)
Definition: view.hh:227
constexpr friend TransformIterator operator+(TransformIterator x, difference_type n)
Definition: view.hh:192
constexpr friend TransformIterator operator-(TransformIterator x, difference_type n)
Definition: view.hh:203
constexpr friend bool operator<(const TransformIterator &x, const TransformIterator &y)
Definition: view.hh:219
constexpr reference operator[](difference_type n)
Definition: view.hh:214
constexpr TransformIterator & operator--()
Definition: view.hh:165
constexpr auto operator[](size_t idx) const
Definition: view.hh:276
constexpr auto rbegin() const
Definition: view.hh:261
constexpr auto back() const
Definition: view.hh:274
constexpr auto begin() const
Definition: view.hh:253
constexpr auto empty() const
Definition: view.hh:271
constexpr Transform(Range &&range_, UnaryOp op_)
Definition: view.hh:248
constexpr auto rend() const
Definition: view.hh:265
constexpr auto size() const
Definition: view.hh:270
constexpr auto front() const
Definition: view.hh:273
constexpr auto end() const
Definition: view.hh:257
Definition: join.hh:10
constexpr KeyMatrixPosition x
Keyboard bindings.
Definition: Keyboard.cc:118
auto copy(InputRange &&range, OutputIter out)
Definition: ranges.hh:179
constexpr Iterator safe_next(Iterator first, Iterator last, size_t n, std::input_iterator_tag)
Definition: view.hh:15
constexpr Iterator safe_prev(Iterator first, Iterator last, size_t n, std::bidirectional_iterator_tag)
Definition: view.hh:28
Definition: view.hh:11
auto filter(ForwardRange &&range, Predicate pred)
Definition: view.hh:410
constexpr auto transform(Range &&range, UnaryOp op)
Definition: view.hh:392
constexpr auto reverse(Range &&range)
Definition: view.hh:386
constexpr auto drop(Range &&range, size_t n)
Definition: view.hh:374
constexpr auto drop_back(Range &&range, size_t n)
Definition: view.hh:380
constexpr auto keys(Map &&map)
Definition: view.hh:397
constexpr auto values(Map &&map)
Definition: view.hh:403
constexpr auto begin(const zstring_view &x)
Definition: zstring_view.hh:83
constexpr auto end(const zstring_view &x)
Definition: zstring_view.hh:84