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