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
359template<typename... Ts>
360std::tuple<decltype(std::begin(std::declval<Ts>()))...>
361iterators_tuple_helper(const std::tuple<Ts...>&);
362
363template<typename... Ts>
364std::tuple<decltype(*std::begin(std::declval<Ts>()))...>
365iterators_deref_tuple_helper(const std::tuple<Ts...>&);
366
367template<bool CHECK_ALL, typename RangesTuple, size_t... Is>
368class Zip
369{
370 RangesTuple ranges;
371
372 using IteratorsTuple = decltype(iterators_tuple_helper (std::declval<RangesTuple>()));
373 using IteratorDerefTuple = decltype(iterators_deref_tuple_helper(std::declval<RangesTuple>()));
374
375 class Iterator {
376 public:
377 using iterator_category = std::input_iterator_tag;
378 using value_type = IteratorDerefTuple;
379 using difference_type = ptrdiff_t;
380 using pointer = value_type*;
381 using reference = value_type&;
382
383 Iterator(IteratorsTuple&& iterators_) : iterators(std::move(iterators_)) {}
384
385 Iterator& operator++() {
386 (++std::get<Is>(iterators), ...);
387 return *this;
388 }
389
390 Iterator operator++(int) {
391 auto r = *this;
392 ++(*this);
393 return r;
394 }
395
396 [[nodiscard]] bool operator==(const Iterator& other) const {
397 if (CHECK_ALL) {
398 return (... || (std::get<Is>(iterators) == std::get<Is>(other.iterators)));
399 } else {
400 return std::get<0>(iterators) == std::get<0>(other.iterators);
401 }
402 }
403
404 [[nodiscard]] auto operator*() {
405 return value_type((*std::get<Is>(iterators))...);
406 }
407
408 private:
409 IteratorsTuple iterators;
410 };
411
412public:
413 Zip(Zip&&) noexcept = default;
414 Zip(RangesTuple&& ranges_) : ranges(std::move(ranges_)) {}
415
416 [[nodiscard]] Iterator begin() const {
417 return {IteratorsTuple(std::begin(std::get<Is>(ranges))...)};
418 }
419 [[nodiscard]] Iterator end() const {
420 return {IteratorsTuple(std::end(std::get<Is>(ranges))...)};
421 }
422};
423
424template<typename RangesTuple, size_t ...Is>
425[[nodiscard]] Zip<true, RangesTuple, Is...> zip(RangesTuple&& ranges, std::index_sequence<Is...>){
426 return {std::forward<RangesTuple>(ranges)};
427}
428
429template<typename RangesTuple, size_t ...Is>
430[[nodiscard]] Zip<false, RangesTuple, Is...> zip_equal(RangesTuple&& ranges, std::index_sequence<Is...>)
431{
432 auto size0 = std::size(std::get<0>(ranges)); (void)size0;
433 assert((... && (std::size(std::get<Is>(ranges)) == size0)));
434 return {std::forward<RangesTuple>(ranges)};
435}
436
437} // namespace detail
438
439template<typename Range>
440[[nodiscard]] constexpr auto drop(Range&& range, size_t n)
441{
442 return detail::Drop<Range>(std::forward<Range>(range), n);
443}
444
445template<typename Range>
446[[nodiscard]] constexpr auto drop_back(Range&& range, size_t n)
447{
448 return detail::DropBack<Range>(std::forward<Range>(range), n);
449}
450
451template<typename Range>
452[[nodiscard]] constexpr auto reverse(Range&& range)
453{
454 return detail::Reverse<Range>(std::forward<Range>(range));
455}
456
457template<typename Range, typename UnaryOp>
458[[nodiscard]] constexpr auto transform(Range&& range, UnaryOp op)
459{
460 return detail::Transform<Range, UnaryOp>(std::forward<Range>(range), op);
461}
462
463template<typename Map> [[nodiscard]] constexpr auto keys(Map&& map)
464{
465 return transform(std::forward<Map>(map),
466 [](const auto& t) -> auto& { return std::get<0>(t); });
467}
468
469template<typename Map> [[nodiscard]] constexpr auto values(Map&& map)
470{
471 return transform(std::forward<Map>(map),
472 [](const auto& t) -> auto& { return std::get<1>(t); });
473}
474
475template<typename ForwardRange, typename Predicate>
476[[nodiscard]] auto filter(ForwardRange&& range, Predicate pred)
477{
478 return detail::Filter<ForwardRange, Predicate>{std::forward<ForwardRange>(range), pred};
479}
480
481// Similar to c++23 std::ranges::views::zip()
482template<typename ...Ranges>
483[[nodiscard]] auto zip(Ranges&&... ranges)
484{
485 return detail::zip(std::tuple<Ranges...>(std::forward<Ranges>(ranges)...),
486 std::index_sequence_for<Ranges...>());
487}
488
489// similar to zip() but with precondition: all ranges must have the size size
490template<typename ...Ranges>
491[[nodiscard]] auto zip_equal(Ranges&&... ranges)
492{
493 return detail::zip_equal(std::tuple<Ranges...>(std::forward<Ranges>(ranges)...),
494 std::index_sequence_for<Ranges...>());
495}
496
497} // namespace view
498
499#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 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:416
Zip(Zip &&) noexcept=default
Iterator end() const
Definition: view.hh:419
Definition: join.hh:10
bool operator==(const Event &x, const Event &y)
Definition: Event.cc:11
Definition: ranges.hh:24
auto copy(InputRange &&range, OutputIter out)
Definition: ranges.hh:232
STL namespace.
size_t size(std::string_view utf8)
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:425
Zip< false, RangesTuple, Is... > zip_equal(RangesTuple &&ranges, std::index_sequence< Is... >)
Definition: view.hh:430
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:491
auto filter(ForwardRange &&range, Predicate pred)
Definition: view.hh:476
constexpr auto transform(Range &&range, UnaryOp op)
Definition: view.hh:458
constexpr auto reverse(Range &&range)
Definition: view.hh:452
constexpr auto drop(Range &&range, size_t n)
Definition: view.hh:440
constexpr auto drop_back(Range &&range, size_t n)
Definition: view.hh:446
auto zip(Ranges &&... ranges)
Definition: view.hh:483
constexpr auto keys(Map &&map)
Definition: view.hh:463
constexpr auto values(Map &&map)
Definition: view.hh:469
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 uint128 operator*(const uint128 &a, const uint128 &b)
Definition: uint128.hh:191
constexpr auto begin(const zstring_view &x)
constexpr auto end(const zstring_view &x)