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 <cassert>
9#include <functional>
10#include <iterator>
11#include <tuple>
12#include <type_traits>
13#include <utility>
14
15namespace view {
16namespace detail {
17
18template<typename Iterator>
19[[nodiscard]] constexpr Iterator safe_next(Iterator first, Iterator last, size_t n, std::input_iterator_tag)
20{
21 while (n-- && (first != last)) ++first;
22 return first;
23}
24
25template<typename Iterator>
26[[nodiscard]] constexpr Iterator safe_next(Iterator first, Iterator last, size_t n, std::random_access_iterator_tag)
27{
28 return first + std::min<size_t>(n, last - first);
29}
30
31template<typename Iterator>
32[[nodiscard]] constexpr Iterator safe_prev(Iterator first, Iterator last, size_t n, std::bidirectional_iterator_tag)
33{
34 while (n-- && (first != last)) --last;
35 return last;
36}
37
38template<typename Iterator>
39[[nodiscard]] constexpr Iterator safe_prev(Iterator first, Iterator last, size_t n, std::random_access_iterator_tag)
40{
41 return last - std::min<size_t>(n, last - first);
42}
43
44
45template<typename Range>
46class Drop
47{
48public:
49 constexpr Drop(Range&& range_, size_t n_)
50 : range(std::forward<Range>(range_))
51 , n(n_)
52 {
53 }
54
55 [[nodiscard]] constexpr auto begin() const {
56 using Iterator = decltype(std::begin(range));
57 return safe_next(std::begin(range), std::end(range), n,
58 typename std::iterator_traits<Iterator>::iterator_category());
59 }
60
61 [[nodiscard]] constexpr auto end() const {
62 return std::end(range);
63 }
64
65private:
66 Range range;
67 size_t n;
68};
69
70
71template<typename Range>
73{
74public:
75 constexpr DropBack(Range&& range_, size_t n_)
76 : range(std::forward<Range>(range_))
77 , n(n_)
78 {
79 }
80
81 [[nodiscard]] constexpr auto begin() const {
82 return std::begin(range);
83 }
84
85 [[nodiscard]] constexpr auto end() const {
86 using Iterator = decltype(std::begin(range));
87 return safe_prev(std::begin(range), std::end(range), n,
88 typename std::iterator_traits<Iterator>::iterator_category());
89 }
90
91private:
92 Range range;
93 size_t n;
94};
95
96
97template<typename Range>
99{
100public:
101 constexpr explicit Reverse(Range&& range_)
102 : range(std::forward<Range>(range_))
103 {
104 }
105
106 [[nodiscard]] constexpr auto begin() const { return range.rbegin(); }
107 [[nodiscard]] constexpr auto begin() { return range.rbegin(); }
108 [[nodiscard]] constexpr auto end() const { return range.rend(); }
109 [[nodiscard]] constexpr auto end() { return range.rend(); }
110 [[nodiscard]] constexpr auto rbegin() const { return range.begin(); }
111 [[nodiscard]] constexpr auto rbegin() { return range.begin(); }
112 [[nodiscard]] constexpr auto rend() const { return range.end(); }
113 [[nodiscard]] constexpr auto rend() { return range.end(); }
114
115private:
116 Range range;
117};
118
119
120template<typename Iterator, typename UnaryOp> class TransformIterator
121{
122public:
123 using return_type = std::invoke_result_t<UnaryOp, decltype(*std::declval<Iterator>())>;
124 using value_type = std::remove_reference_t<return_type>;
127 using difference_type = typename std::iterator_traits<Iterator>::difference_type;
128 using iterator_category = typename std::iterator_traits<Iterator>::iterator_category;
129
130public:
131 constexpr TransformIterator() = default;
132
133 constexpr TransformIterator(Iterator it_, UnaryOp op_)
134 : it(it_), op(op_)
135 {
136 }
137
138 // InputIterator, ForwardIterator
139
140 [[nodiscard]] constexpr return_type operator*() const { return std::invoke(op, *it); }
141
142 // pointer operator->() const not defined
143
145 {
146 ++it;
147 return *this;
148 }
149
151 {
152 auto copy = *this;
153 ++it;
154 return copy;
155 }
156
157 [[nodiscard]] constexpr friend bool operator==(const TransformIterator& x, const TransformIterator& y)
158 {
159 return x.it == y.it;
160 }
161
162 // BidirectionalIterator
163
165 {
166 --it;
167 return *this;
168 }
169
171 {
172 auto copy = *this;
173 --it;
174 return copy;
175 }
176
177 // RandomAccessIterator
178
180 {
181 it += n;
182 return *this;
183 }
184
186 {
187 it -= n;
188 return *this;
189 }
190
192 {
193 x += n;
194 return x;
195 }
197 {
198 x += n;
199 return x;
200 }
201
203 {
204 x -= n;
205 return x;
206 }
207
208 [[nodiscard]] constexpr friend difference_type operator-(const TransformIterator& x, const TransformIterator& y)
209 {
210 return x.it - y.it;
211 }
212
213 [[nodiscard]] constexpr reference operator[](difference_type n)
214 {
215 return *(*this + n);
216 }
217
218 [[nodiscard]] constexpr auto operator<=>(const TransformIterator& other) const
219 {
220 return it <=> other.it;
221 }
222
223private:
224 Iterator it;
225
226#ifndef _MSC_VER
227 // Wrapping in 'semiregular_t' is needed on libc++,
228 // see commit e81b34b5ed9f for more details.
229 using UO = semiregular_t<UnaryOp>;
230#else
231 // But it triggers compile errors on visual studio, though only in c++20
232 // mode. Hopefully we can remove this workaround in the future when we
233 // use std::views::transform().
234 using UO = UnaryOp;
235#endif
236 [[no_unique_address]] UO op;
237};
238
239template<typename Range, typename UnaryOp> class Transform
240{
241public:
242 constexpr Transform(Range&& range_, UnaryOp op_)
243 : range(std::forward<Range>(range_)), op(op_)
244 {
245 }
246
247 [[nodiscard]] constexpr auto begin() const
248 {
249 return TransformIterator(std::begin(range), op);
250 }
251 [[nodiscard]] constexpr auto end() const
252 {
253 return TransformIterator(std::end(range), op);
254 }
255 [[nodiscard]] constexpr auto rbegin() const
256 {
257 return TransformIterator(std::rbegin(range), op);
258 }
259 [[nodiscard]] constexpr auto rend() const
260 {
261 return TransformIterator(std::rend(range), op);
262 }
263
264 [[nodiscard]] constexpr auto size() const { return range.size(); }
265 [[nodiscard]] constexpr auto empty() const { return range.empty(); }
266
267 [[nodiscard]] constexpr auto front() const { return op(range.front()); }
268 [[nodiscard]] constexpr auto back() const { return op(range.back()); }
269
270 [[nodiscard]] constexpr auto operator[](size_t idx) const {
271 return std::invoke(op, range[idx]);
272 }
273
274private:
275 Range range;
276 [[no_unique_address]] UnaryOp op;
277};
278
279
280template<typename Iterator, typename Sentinel, typename Predicate>
282{
283public:
284 using value_type = typename std::iterator_traits<Iterator>::value_type;
285 using reference = typename std::iterator_traits<Iterator>::reference;
286 using pointer = typename std::iterator_traits<Iterator>::pointer;
287 using difference_type = typename std::iterator_traits<Iterator>::difference_type;
288 using iterator_category = std::forward_iterator_tag;
289
290 constexpr FilteredIterator(Iterator it_, Sentinel last_, Predicate pred_)
291 : it(it_), last(last_), pred(pred_)
292 {
293 while (isFiltered()) ++it;
294 }
295
296 [[nodiscard]] constexpr friend bool operator==(const FilteredIterator& x, const FilteredIterator& y)
297 {
298 return x.it == y.it;
299 }
300
301 [[nodiscard]] constexpr reference operator*() const { return *it; }
302 [[nodiscard]] constexpr pointer operator->() const { return &*it; }
303
305 {
306 do {
307 ++it;
308 } while (isFiltered());
309 return *this;
310 }
312 {
313 FilteredIterator result = *this;
314 ++(*this);
315 return result;
316 }
317
318private:
319 [[nodiscard]] constexpr bool isFiltered()
320 {
321 return (it != last) && !std::invoke(pred, *it);
322 }
323
324private:
325 Iterator it;
326 Sentinel last;
327 [[no_unique_address]] Predicate pred;
328};
329
330template<typename Range, typename Predicate>
332{
333public:
334 using Iterator = decltype(std::begin(std::declval<Range>()));
335 using Sentinel = decltype(std::end (std::declval<Range>()));
337
338 constexpr Filter(Range&& range_, Predicate pred_)
339 : range(std::forward<Range>(range_)), pred(pred_)
340 {
341 }
342
343 [[nodiscard]] constexpr F_Iterator begin() const
344 {
345 return {std::begin(range), std::end(range), pred};
346 }
347 [[nodiscard]] constexpr F_Iterator end() const
348 {
349 // TODO should be a 'FilteredSentinel', but that only works well
350 // in c++20 (and c++20 already has 'std::views::filter').
351 return {std::end(range), std::end(range), pred};
352 }
353
354private:
355 Range range;
356 [[no_unique_address]] Predicate pred;
357};
358
359
360template<typename Iterator, typename Sentinel> class TakeIterator
361{
362public:
363 using value_type = typename std::iterator_traits<Iterator>::value_type;
364 using difference_type = typename std::iterator_traits<Iterator>::difference_type;
365
366public:
367 constexpr TakeIterator(Iterator it_, size_t n_)
368 : it(it_), n(difference_type(n_)) {}
369
370 [[nodiscard]] constexpr auto operator*() const { return *it; }
371
373 ++it;
374 --n;
375 return *this;
376 }
377
378 constexpr TakeIterator operator++(int) {
379 auto copy = *this;
380 ++it;
381 --n;
382 return copy;
383 }
384
385 [[nodiscard]] constexpr friend bool operator==(const TakeIterator& x, const TakeIterator& y) {
386 return (x.it == y.it) || (x.n == 0 && y.n == 0);
387 }
388 [[nodiscard]] constexpr friend bool operator==(const TakeIterator& x, const Sentinel& y) {
389 return (x.it == y) || (x.n == 0);
390 }
391
392private:
393 Iterator it;
395};
396
397template<typename Range>
398class Take
399{
400public:
401 using Iterator = decltype(std::begin(std::declval<Range>()));
402 using Sentinel = decltype(std::end (std::declval<Range>()));
404
405 constexpr Take(Range&& range_, size_t n_)
406 : range(std::forward<Range>(range_)), n(n_) {}
407
408 [[nodiscard]] constexpr Take_Iterator begin() const {
409 return {std::begin(range), n};
410 }
411 [[nodiscard]] constexpr Sentinel end() const {
412 return std::end(range);
413 }
414
415private:
416 Range range;
417 size_t n;
418};
419
420
421template<typename... Ts>
422std::tuple<decltype(std::begin(std::declval<Ts>()))...>
423iterators_tuple_helper(const std::tuple<Ts...>&);
424
425template<typename... Ts>
426std::tuple<decltype(*std::begin(std::declval<Ts>()))...>
427iterators_deref_tuple_helper(const std::tuple<Ts...>&);
428
429template<bool CHECK_ALL, typename RangesTuple, size_t... Is>
430class Zip
431{
432 RangesTuple ranges;
433
434 using IteratorsTuple = decltype(iterators_tuple_helper (std::declval<RangesTuple>()));
435 using IteratorDerefTuple = decltype(iterators_deref_tuple_helper(std::declval<RangesTuple>()));
436
437 class Iterator {
438 public:
439 using iterator_category = std::input_iterator_tag;
440 using value_type = IteratorDerefTuple;
441 using difference_type = ptrdiff_t;
442 using pointer = value_type*;
443 using reference = value_type&;
444
445 Iterator(IteratorsTuple&& iterators_) : iterators(std::move(iterators_)) {}
446
447 Iterator& operator++() {
448 (++std::get<Is>(iterators), ...);
449 return *this;
450 }
451
452 Iterator operator++(int) {
453 auto r = *this;
454 ++(*this);
455 return r;
456 }
457
458 [[nodiscard]] bool operator==(const Iterator& other) const {
459 if (CHECK_ALL) {
460 return (... || (std::get<Is>(iterators) == std::get<Is>(other.iterators)));
461 } else {
462 return std::get<0>(iterators) == std::get<0>(other.iterators);
463 }
464 }
465
466 [[nodiscard]] auto operator*() {
467 return value_type((*std::get<Is>(iterators))...);
468 }
469
470 private:
471 IteratorsTuple iterators;
472 };
473
474public:
475 Zip(Zip&&) noexcept = default;
476 Zip(RangesTuple&& ranges_) : ranges(std::move(ranges_)) {}
477
478 [[nodiscard]] Iterator begin() const {
479 return {IteratorsTuple(std::begin(std::get<Is>(ranges))...)};
480 }
481 [[nodiscard]] Iterator end() const {
482 return {IteratorsTuple(std::end(std::get<Is>(ranges))...)};
483 }
484};
485
486template<typename RangesTuple, size_t ...Is>
487[[nodiscard]] Zip<true, RangesTuple, Is...> zip(RangesTuple&& ranges, std::index_sequence<Is...>){
488 return {std::forward<RangesTuple>(ranges)};
489}
490
491template<typename RangesTuple, size_t ...Is>
492[[nodiscard]] Zip<false, RangesTuple, Is...> zip_equal(RangesTuple&& ranges, std::index_sequence<Is...>)
493{
494 auto size0 = std::size(std::get<0>(ranges)); (void)size0;
495 assert((... && (std::size(std::get<Is>(ranges)) == size0)));
496 return {std::forward<RangesTuple>(ranges)};
497}
498
499} // namespace detail
500
501template<typename Range>
502[[nodiscard]] constexpr auto drop(Range&& range, size_t n)
503{
504 return detail::Drop<Range>(std::forward<Range>(range), n);
505}
506
507template<typename Range>
508[[nodiscard]] constexpr auto drop_back(Range&& range, size_t n)
509{
510 return detail::DropBack<Range>(std::forward<Range>(range), n);
511}
512
513template<typename Range>
514[[nodiscard]] constexpr auto reverse(Range&& range)
515{
516 return detail::Reverse<Range>(std::forward<Range>(range));
517}
518
519template<typename Range, typename UnaryOp>
520[[nodiscard]] constexpr auto transform(Range&& range, UnaryOp op)
521{
522 return detail::Transform<Range, UnaryOp>(std::forward<Range>(range), op);
523}
524
525template<typename Map> [[nodiscard]] constexpr auto keys(Map&& map)
526{
527 return transform(std::forward<Map>(map),
528 [](const auto& t) -> auto& { return std::get<0>(t); });
529}
530
531template<typename Map> [[nodiscard]] constexpr auto values(Map&& map)
532{
533 return transform(std::forward<Map>(map),
534 [](const auto& t) -> auto& { return std::get<1>(t); });
535}
536
537template<typename ForwardRange, typename Predicate>
538[[nodiscard]] auto filter(ForwardRange&& range, Predicate pred)
539{
540 return detail::Filter<ForwardRange, Predicate>{std::forward<ForwardRange>(range), pred};
541}
542
543template<typename ForwardRange>
544[[nodiscard]] constexpr auto take(ForwardRange&& range, size_t n)
545{
546 return detail::Take<ForwardRange>{std::forward<ForwardRange>(range), n};
547}
548
549// Similar to c++23 std::ranges::views::zip()
550template<typename ...Ranges>
551[[nodiscard]] auto zip(Ranges&&... ranges)
552{
553 return detail::zip(std::tuple<Ranges...>(std::forward<Ranges>(ranges)...),
554 std::index_sequence_for<Ranges...>());
555}
556
557// similar to zip() but with precondition: all ranges must have the size size
558template<typename ...Ranges>
559[[nodiscard]] auto zip_equal(Ranges&&... ranges)
560{
561 return detail::zip_equal(std::tuple<Ranges...>(std::forward<Ranges>(ranges)...),
562 std::index_sequence_for<Ranges...>());
563}
564
565} // namespace view
566
567#endif
TclObject t
constexpr DropBack(Range &&range_, size_t n_)
Definition view.hh:75
constexpr auto begin() const
Definition view.hh:81
constexpr auto end() const
Definition view.hh:85
constexpr Drop(Range &&range_, size_t n_)
Definition view.hh:49
constexpr auto begin() const
Definition view.hh:55
constexpr auto end() const
Definition view.hh:61
constexpr F_Iterator end() const
Definition view.hh:347
decltype(std::end(std::declval< Range >())) Sentinel
Definition view.hh:335
constexpr Filter(Range &&range_, Predicate pred_)
Definition view.hh:338
constexpr F_Iterator begin() const
Definition view.hh:343
decltype(std::begin(std::declval< Range >())) Iterator
Definition view.hh:334
constexpr pointer operator->() const
Definition view.hh:302
typename std::iterator_traits< Iterator >::value_type value_type
Definition view.hh:284
typename std::iterator_traits< Iterator >::difference_type difference_type
Definition view.hh:287
constexpr reference operator*() const
Definition view.hh:301
constexpr FilteredIterator operator++(int)
Definition view.hh:311
typename std::iterator_traits< Iterator >::pointer pointer
Definition view.hh:286
constexpr FilteredIterator & operator++()
Definition view.hh:304
typename std::iterator_traits< Iterator >::reference reference
Definition view.hh:285
constexpr friend bool operator==(const FilteredIterator &x, const FilteredIterator &y)
Definition view.hh:296
constexpr FilteredIterator(Iterator it_, Sentinel last_, Predicate pred_)
Definition view.hh:290
std::forward_iterator_tag iterator_category
Definition view.hh:288
constexpr auto rend() const
Definition view.hh:112
constexpr auto end()
Definition view.hh:109
constexpr auto rend()
Definition view.hh:113
constexpr auto end() const
Definition view.hh:108
constexpr auto begin() const
Definition view.hh:106
constexpr auto rbegin()
Definition view.hh:111
constexpr auto rbegin() const
Definition view.hh:110
constexpr auto begin()
Definition view.hh:107
constexpr Reverse(Range &&range_)
Definition view.hh:101
constexpr TakeIterator operator++(int)
Definition view.hh:378
constexpr friend bool operator==(const TakeIterator &x, const Sentinel &y)
Definition view.hh:388
typename std::iterator_traits< Iterator >::difference_type difference_type
Definition view.hh:364
constexpr TakeIterator(Iterator it_, size_t n_)
Definition view.hh:367
constexpr TakeIterator & operator++()
Definition view.hh:372
typename std::iterator_traits< Iterator >::value_type value_type
Definition view.hh:363
constexpr auto operator*() const
Definition view.hh:370
constexpr friend bool operator==(const TakeIterator &x, const TakeIterator &y)
Definition view.hh:385
decltype(std::begin(std::declval< Range >())) Iterator
Definition view.hh:401
constexpr Take_Iterator begin() const
Definition view.hh:408
constexpr Take(Range &&range_, size_t n_)
Definition view.hh:405
constexpr Sentinel end() const
Definition view.hh:411
decltype(std::end(std::declval< Range >())) Sentinel
Definition view.hh:402
constexpr auto operator<=>(const TransformIterator &other) const
Definition view.hh:218
std::invoke_result_t< UnaryOp, decltype(*std::declval< Iterator >())> return_type
Definition view.hh:123
constexpr TransformIterator(Iterator it_, UnaryOp op_)
Definition view.hh:133
constexpr TransformIterator & operator--()
Definition view.hh:164
constexpr friend difference_type operator-(const TransformIterator &x, const TransformIterator &y)
Definition view.hh:208
std::remove_reference_t< return_type > value_type
Definition view.hh:124
constexpr TransformIterator()=default
constexpr TransformIterator operator++(int)
Definition view.hh:150
constexpr return_type operator*() const
Definition view.hh:140
constexpr TransformIterator & operator-=(difference_type n)
Definition view.hh:185
constexpr TransformIterator & operator++()
Definition view.hh:144
constexpr TransformIterator operator--(int)
Definition view.hh:170
typename std::iterator_traits< Iterator >::difference_type difference_type
Definition view.hh:127
typename std::iterator_traits< Iterator >::iterator_category iterator_category
Definition view.hh:128
constexpr friend bool operator==(const TransformIterator &x, const TransformIterator &y)
Definition view.hh:157
constexpr friend TransformIterator operator+(difference_type n, TransformIterator x)
Definition view.hh:196
constexpr friend TransformIterator operator+(TransformIterator x, difference_type n)
Definition view.hh:191
constexpr friend TransformIterator operator-(TransformIterator x, difference_type n)
Definition view.hh:202
constexpr reference operator[](difference_type n)
Definition view.hh:213
constexpr TransformIterator & operator+=(difference_type n)
Definition view.hh:179
constexpr auto operator[](size_t idx) const
Definition view.hh:270
constexpr auto rbegin() const
Definition view.hh:255
constexpr auto back() const
Definition view.hh:268
constexpr auto begin() const
Definition view.hh:247
constexpr auto empty() const
Definition view.hh:265
constexpr Transform(Range &&range_, UnaryOp op_)
Definition view.hh:242
constexpr auto rend() const
Definition view.hh:259
constexpr auto size() const
Definition view.hh:264
constexpr auto front() const
Definition view.hh:267
constexpr auto end() const
Definition view.hh:251
Iterator begin() const
Definition view.hh:478
Zip(Zip &&) noexcept=default
Iterator end() const
Definition view.hh:481
Definition join.hh:10
STL namespace.
constexpr Iterator safe_next(Iterator first, Iterator last, size_t n, std::input_iterator_tag)
Definition view.hh:19
std::tuple< decltype(std::begin(std::declval< Ts >()))... > iterators_tuple_helper(const std::tuple< Ts... > &)
Zip< true, RangesTuple, Is... > zip(RangesTuple &&ranges, std::index_sequence< Is... >)
Definition view.hh:487
Zip< false, RangesTuple, Is... > zip_equal(RangesTuple &&ranges, std::index_sequence< Is... >)
Definition view.hh:492
constexpr Iterator safe_prev(Iterator first, Iterator last, size_t n, std::bidirectional_iterator_tag)
Definition view.hh:32
std::tuple< decltype(*std::begin(std::declval< Ts >()))... > iterators_deref_tuple_helper(const std::tuple< Ts... > &)
Definition view.hh:15
auto zip_equal(Ranges &&... ranges)
Definition view.hh:559
auto filter(ForwardRange &&range, Predicate pred)
Definition view.hh:538
constexpr auto transform(Range &&range, UnaryOp op)
Definition view.hh:520
constexpr auto take(ForwardRange &&range, size_t n)
Definition view.hh:544
constexpr auto reverse(Range &&range)
Definition view.hh:514
constexpr auto drop(Range &&range, size_t n)
Definition view.hh:502
constexpr auto drop_back(Range &&range, size_t n)
Definition view.hh:508
auto zip(Ranges &&... ranges)
Definition view.hh:551
constexpr auto keys(Map &&map)
Definition view.hh:525
constexpr auto values(Map &&map)
Definition view.hh:531
std::conditional_t< std::is_default_constructible_v< T > &&std::is_copy_assignable_v< T >, T, sreg_impl::semiregular< T > > semiregular_t
constexpr uint128 operator*(const uint128 &a, const uint128 &b)
Definition uint128.hh:191