openMSX
ranges.hh
Go to the documentation of this file.
1#ifndef RANGES_HH
2#define RANGES_HH
3
4#include <algorithm>
5#include <cassert>
6#include <functional>
7#include <iterator> // for std::begin(), std::end()
8#include <numeric>
9#include <span>
10#include <version> // for _LIBCPP_VERSION
11
12// Range based versions of the standard algorithms, these will likely become
13// part of c++20. For example see this post:
14// http://ericniebler.com/2018/12/05/standard-ranges/
15// In the future we can remove our implementation and instead use the standard
16// version (e.g. by a namespace alias like 'namespace ranges = std::ranges').
17//
18// All of the range algorithms below do nothing more than delegate to the
19// corresponding iterator-pair version of the algorithm.
20//
21// This list of algorithms is not complete. But it's easy to extend if/when we
22// need more.
23
24namespace ranges {
25
26// (Simplified) implementation of c++20 "range" and "sized_range" concepts.
27// * A "range" is something that has a begin() and end().
28// * A "sized_range" in addition has a size().
29template<typename T>
30concept range = requires(T& t) {
31 std::begin(t);
32 std::end (t);
33};
34
35template<typename T>
36concept sized_range = range<T> && requires(T& t) { std::size(t); };
37
38
39template<typename ForwardRange, typename Compare = std::less<>, typename Proj = std::identity>
40[[nodiscard]] bool is_sorted(ForwardRange&& range, Compare comp = {}, Proj proj = {})
41{
42 return std::is_sorted(std::begin(range), std::end(range),
43 [&](const auto& x, const auto& y) {
44 return comp(std::invoke(proj, x), std::invoke(proj, y));
45 });
46}
47
48template<typename RandomAccessRange>
49constexpr void sort(RandomAccessRange&& range)
50{
51 std::sort(std::begin(range), std::end(range));
52}
53
54template<typename RandomAccessRange, typename Compare>
55constexpr void sort(RandomAccessRange&& range, Compare comp)
56{
57 std::sort(std::begin(range), std::end(range), comp);
58}
59
60template<typename RAIter, typename Compare = std::less<>, typename Proj>
61constexpr void sort(RAIter first, RAIter last, Compare comp, Proj proj)
62{
63 std::sort(first, last,
64 [&](const auto& x, const auto& y) {
65 return comp(std::invoke(proj, x), std::invoke(proj, y));
66 });
67}
68
69template<typename RandomAccessRange, typename Compare = std::less<>, typename Proj>
70constexpr void sort(RandomAccessRange&& range, Compare comp, Proj proj)
71{
72 sort(std::begin(range), std::end(range), comp, proj);
73}
74
75template<typename RandomAccessRange>
76void stable_sort(RandomAccessRange&& range)
77{
78 std::stable_sort(std::begin(range), std::end(range));
79}
80
81template<typename RandomAccessRange, typename Compare>
82void stable_sort(RandomAccessRange&& range, Compare comp)
83{
84 std::stable_sort(std::begin(range), std::end(range), comp);
85}
86
87template<typename RAIter, typename Compare = std::less<>, typename Proj>
88void stable_sort(RAIter first, RAIter last, Compare comp, Proj proj)
89{
90 std::stable_sort(first, last,
91 [&](const auto& x, const auto& y) {
92 return comp(std::invoke(proj, x), std::invoke(proj, y));
93 });
94}
95
96template<typename RandomAccessRange, typename Compare = std::less<>, typename Proj>
97void stable_sort(RandomAccessRange&& range, Compare comp, Proj proj)
98{
99 stable_sort(std::begin(range), std::end(range), comp, proj);
100}
101
102template<typename ForwardRange, typename T>
103[[nodiscard]] bool binary_search(ForwardRange&& range, const T& value)
104{
105 return std::binary_search(std::begin(range), std::end(range), value);
106}
107
108template<typename ForwardRange, typename T, typename Compare>
109[[nodiscard]] bool binary_search(ForwardRange&& range, const T& value, Compare comp)
110{
111 return std::binary_search(std::begin(range), std::end(range), value, comp);
112}
113
114template<typename ForwardRange, typename T, typename Compare = std::less<>, typename Proj = std::identity>
115[[nodiscard]] auto lower_bound(ForwardRange&& range, const T& value, Compare comp = {}, Proj proj = {})
116{
117 auto comp2 = [&](const auto& x, const auto& y) {
118 return comp(std::invoke(proj, x), y);
119 };
120 return std::lower_bound(std::begin(range), std::end(range), value, comp2);
121}
122
123template<typename ForwardRange, typename T, typename Compare = std::less<>, typename Proj = std::identity>
124[[nodiscard]] auto upper_bound(ForwardRange&& range, const T& value, Compare comp = {}, Proj proj = {})
125{
126 auto comp2 = [&](const auto& x, const auto& y) {
127 return comp(x, std::invoke(proj, y));
128 };
129 return std::upper_bound(std::begin(range), std::end(range), value, comp2);
130}
131
132template<typename ForwardRange, typename T, typename Compare = std::less<>>
133[[nodiscard]] auto equal_range(ForwardRange&& range, const T& value, Compare comp = {})
134{
135 return std::equal_range(std::begin(range), std::end(range), value, comp);
136}
137template<typename ForwardRange, typename T, typename Compare = std::less<>, typename Proj = std::identity>
138[[nodiscard]] auto equal_range(ForwardRange&& range, const T& value, Compare comp, Proj proj)
139{
140 using Iter = decltype(std::begin(range));
141 using R = typename std::iterator_traits<Iter>::value_type;
142 struct Comp2 {
143 Compare comp;
144 Proj proj;
145
146 bool operator()(const R& x, const R& y) const {
147 return comp(std::invoke(proj, x), std::invoke(proj, y));
148 }
149 bool operator()(const R& x, const T& y) const {
150 return comp(std::invoke(proj, x), y);
151 }
152 bool operator()(const T& x, const R& y) const {
153 return comp(x, std::invoke(proj, y));
154 }
155 };
156 return std::equal_range(std::begin(range), std::end(range), value, Comp2{comp, proj});
157}
158
159template<typename InputRange, typename T>
160[[nodiscard]] auto find(InputRange&& range, const T& value)
161{
162 return std::find(std::begin(range), std::end(range), value);
163}
164
165template<typename InputRange, typename T, typename Proj>
166[[nodiscard]] auto find(InputRange&& range, const T& value, Proj proj)
167{
168 return find_if(std::forward<InputRange>(range),
169 [&](const auto& e) { return std::invoke(proj, e) == value; });
170}
171
172template<typename InputRange, typename UnaryPredicate>
173[[nodiscard]] auto find_if(InputRange&& range, UnaryPredicate pred)
174{
175 auto it = std::begin(range);
176 auto et = std::end(range);
177 for (; it != et; ++it) {
178 if (std::invoke(pred, *it)) {
179 return it;
180 }
181 }
182 return it;
183}
184
185template<typename InputRange, typename UnaryPredicate>
186[[nodiscard]] bool all_of(InputRange&& range, UnaryPredicate pred)
187{
188 //return std::all_of(std::begin(range), std::end(range), pred);
189 auto it = std::begin(range);
190 auto et = std::end(range); // allow 'it' and 'et' to have different types
191 for (; it != et; ++it) {
192 if (!std::invoke(pred, *it)) return false;
193 }
194 return true;
195}
196
197template<typename InputRange, typename UnaryPredicate>
198[[nodiscard]] bool any_of(InputRange&& range, UnaryPredicate pred)
199{
200 //return std::any_of(std::begin(range), std::end(range), pred);
201 auto it = std::begin(range);
202 auto et = std::end(range); // allow 'it' and 'et' to have different types
203 for (; it != et; ++it) {
204 if (std::invoke(pred, *it)) return true;
205 }
206 return false;
207}
208
209template<typename InputRange, typename UnaryPredicate>
210[[nodiscard]] bool none_of(InputRange&& range, UnaryPredicate pred)
211{
212 //return std::none_of(std::begin(range), std::end(range), pred);
213 auto it = std::begin(range);
214 auto et = std::end(range); // allow 'it' and 'et' to have different types
215 for (; it != et; ++it) {
216 if (std::invoke(pred, *it)) return false;
217 }
218 return true;
219}
220
221template<typename ForwardRange>
222[[nodiscard]] auto unique(ForwardRange&& range)
223{
224 return std::unique(std::begin(range), std::end(range));
225}
226
227template<typename ForwardRange, typename BinaryPredicate>
228[[nodiscard]] auto unique(ForwardRange&& range, BinaryPredicate pred)
229{
230 return std::unique(std::begin(range), std::end(range), pred);
231}
232
233template<typename RAIter, typename Compare = std::equal_to<>, typename Proj>
234[[nodiscard]] auto unique(RAIter first, RAIter last, Compare comp, Proj proj)
235{
236 return std::unique(first, last,
237 [&](const auto& x, const auto& y) {
238 return comp(std::invoke(proj, x), std::invoke(proj, y));
239 });
240}
241
242template<typename RandomAccessRange, typename Compare = std::equal_to<>, typename Proj>
243[[nodiscard]] auto unique(RandomAccessRange&& range, Compare comp, Proj proj)
244{
245 return unique(std::begin(range), std::end(range), comp, proj);
246}
247
248template<typename InputRange, typename OutputIter>
249 requires(!range<OutputIter>)
250auto copy(InputRange&& range, OutputIter out)
251{
252 return std::copy(std::begin(range), std::end(range), out);
253}
254
255template<sized_range Input, sized_range Output>
256auto copy(Input&& in, Output&& out)
257{
258 assert(std::size(in) <= std::size(out));
259 return std::copy(std::begin(in), std::end(in), std::begin(out));
260}
261
262template<typename InputRange, typename OutputIter, typename UnaryPredicate>
263auto copy_if(InputRange&& range, OutputIter out, UnaryPredicate pred)
264{
265 return std::copy_if(std::begin(range), std::end(range), out, pred);
266}
267
268template<typename InputRange, typename OutputIter, typename UnaryOperation>
269auto transform(InputRange&& range, OutputIter out, UnaryOperation op)
270{
271 return std::transform(std::begin(range), std::end(range), out, op);
272}
273
274template<typename ForwardRange, typename Generator>
275void generate(ForwardRange&& range, Generator&& g)
276{
277 std::generate(std::begin(range), std::end(range), std::forward<Generator>(g));
278}
279
280template<typename ForwardRange, typename T>
281[[nodiscard]] auto remove(ForwardRange&& range, const T& value)
282{
283 return std::remove(std::begin(range), std::end(range), value);
284}
285
286template<typename ForwardRange, typename UnaryPredicate>
287[[nodiscard]] auto remove_if(ForwardRange&& range, UnaryPredicate pred)
288{
289 return std::remove_if(std::begin(range), std::end(range), pred);
290}
291
292template<typename ForwardRange, typename T>
293constexpr void replace(ForwardRange&& range, const T& old_value, const T& new_value)
294{
295 std::replace(std::begin(range), std::end(range), old_value, new_value);
296}
297
298template<typename ForwardRange, typename UnaryPredicate, typename T>
299void replace_if(ForwardRange&& range, UnaryPredicate pred, const T& new_value)
300{
301 std::replace_if(std::begin(range), std::end(range), pred, new_value);
302}
303
304template<typename ForwardRange, typename T>
305constexpr void fill(ForwardRange&& range, const T& value)
306{
307 std::fill(std::begin(range), std::end(range), value);
308}
309
310// part of c++20
311template<typename ForwardIt, typename T>
312constexpr void iota(ForwardIt first, ForwardIt last, T value)
313{
314 while (first != last) {
315 *first++ = value;
316 ++value;
317 }
318}
319
320template<typename ForwardRange, typename T>
321constexpr void iota(ForwardRange&& range, T&& value)
322{
323 ::ranges::iota(std::begin(range), std::end(range), std::forward<T>(value));
324}
325
326template<typename InputRange, typename T>
327[[nodiscard]] T accumulate(InputRange&& range, T init)
328{
329 return std::accumulate(std::begin(range), std::end(range), init);
330}
331
332template<typename InputRange, typename T, typename BinaryOperation>
333[[nodiscard]] T accumulate(InputRange&& range, T init, BinaryOperation op)
334{
335 return std::accumulate(std::begin(range), std::end(range), init, op);
336}
337
338template<typename InputRange, typename T>
339[[nodiscard]] auto count(InputRange&& range, const T& value)
340{
341 return std::count(std::begin(range), std::end(range), value);
342}
343
344template<typename InputRange, typename UnaryPredicate>
345[[nodiscard]] auto count_if(InputRange&& range, UnaryPredicate pred)
346{
347 auto first = std::begin(range);
348 auto last = std::end(range);
349 typename std::iter_difference_t<decltype(first)> count = 0;
350 while (first != last) {
351 if (std::invoke(pred, *first++)) ++count;
352 }
353 return count;
354 //return std::count_if(std::begin(range), std::end(range), pred);
355}
356
357template<typename InputRange1, typename InputRange2, typename OutputIter>
358auto set_difference(InputRange1&& range1, InputRange2&& range2, OutputIter out)
359{
360 return std::set_difference(std::begin(range1), std::end(range1),
361 std::begin(range2), std::end(range2),
362 out);
363}
364
365template<range InputRange1, range InputRange2,
366 typename Pred = std::equal_to<void>,
367 typename Proj1 = std::identity, typename Proj2 = std::identity>
368bool equal(InputRange1&& range1, InputRange2&& range2, Pred pred = {},
369 Proj1 proj1 = {}, Proj2 proj2 = {})
370{
371 auto it1 = std::begin(range1);
372 auto it2 = std::begin(range2);
373 auto et1 = std::end(range1);
374 auto et2 = std::end(range2);
375 for (; (it1 != et1) && (it2 != et2); ++it1, ++it2) {
376 if (!std::invoke(pred, std::invoke(proj1, *it1), std::invoke(proj2, *it2))) {
377 return false;
378 }
379 }
380 return (it1 == et1) && (it2 == et2);
381}
382
383template<sized_range SizedRange1, sized_range SizedRange2,
384 typename Pred = std::equal_to<void>,
385 typename Proj1 = std::identity, typename Proj2 = std::identity>
386bool equal(SizedRange1&& range1, SizedRange2&& range2, Pred pred = {},
387 Proj1 proj1 = {}, Proj2 proj2 = {})
388{
389 if (std::size(range1) != std::size(range2)) return false;
390
391 auto it1 = std::begin(range1);
392 auto it2 = std::begin(range2);
393 auto et1 = std::end(range1);
394 for (; it1 != et1; ++it1, ++it2) {
395 if (!std::invoke(pred, std::invoke(proj1, *it1), std::invoke(proj2, *it2))) {
396 return false;
397 }
398 }
399 return true;
400}
401
402// Test whether all elements in the given range are equal to each other (after
403// applying a projection).
404template<typename InputRange, typename Proj = std::identity>
405bool all_equal(InputRange&& range, Proj proj = {})
406{
407 auto it = std::begin(range);
408 auto et = std::end(range);
409 if (it == et) return true;
410
411 auto val = std::invoke(proj, *it);
412 for (++it; it != et; ++it) {
413 if (std::invoke(proj, *it) != val) {
414 return false;
415 }
416 }
417 return true;
418}
419
420} // namespace ranges
421
422// Perform a binary-search in a sorted range.
423// The given 'range' must be sorted according to 'comp'.
424// We search for 'value' after applying 'proj' to the elements in the range.
425// Returns a pointer to the element in 'range', or nullptr if not found.
426//
427// This helper function is typically used to simplify code like:
428// auto it = ranges::lower_bound(myMap, name, {}, &Element::name);
429// if ((it != myMap.end()) && (it->name == name)) {
430// ... use *it
431// }
432// Note that this code needs to check both for the end-iterator and that the
433// element was actually found. By using binary_find() this complexity is hidden:
434// if (auto m = binary_find(myMap, name, {}, &Element::name)) {
435// ... use *m
436// }
437template<typename ForwardRange, typename T, typename Compare = std::less<>, typename Proj = std::identity>
438[[nodiscard]] auto* binary_find(ForwardRange&& range, const T& value, Compare comp = {}, Proj proj = {})
439{
440 auto it = ranges::lower_bound(range, value, comp, proj);
441 return ((it != std::end(range)) && (!std::invoke(comp, value, std::invoke(proj, *it))))
442 ? &*it
443 : nullptr;
444}
445
446// Convenience function to convert part of an array (or vector, ...) into a
447// span. These are not part of the c++ ranges namespace, but often these results
448// are then further used in range algorithms, that's why I placed them in this
449// header.
450
451template<typename Range>
452constexpr auto make_span(Range&& range)
453{
454#ifndef _LIBCPP_VERSION
455 // C++20 version, works with gcc/visual studio
456 // Simple enough that we don't actually need this helper function.
457 return std::span(range);
458#else
459 // Unfortunately we do need a workaround for clang/libc++, version 14 and 15
460 // return std::span(std::begin(range), std::end(range));
461
462 // Further workaround for Xcode-14, clang-13
463 // Don't always use this workaround, because '&*begin()' is actually
464 // undefined behavior when the range is empty. It works fine in
465 // practice, except when using a DEBUG-STL version.
466 return std::span(&*std::begin(range), std::size(range));
467#endif
468}
469
470template<typename Range>
471constexpr auto subspan(Range&& range, size_t offset, size_t count = std::dynamic_extent)
472{
473 return make_span(std::forward<Range>(range)).subspan(offset, count);
474}
475
476template<size_t Count, typename Range>
477constexpr auto subspan(Range&& range, size_t offset = 0)
478{
479 return make_span(std::forward<Range>(range)).subspan(offset).template first<Count>();
480}
481
482#endif
int g
TclObject t
bool comp(const uint8_t *p, const uint8_t *q)
bool is_sorted(ForwardRange &&range, Compare comp={}, Proj proj={})
Definition ranges.hh:40
bool binary_search(ForwardRange &&range, const T &value)
Definition ranges.hh:103
bool any_of(InputRange &&range, UnaryPredicate pred)
Definition ranges.hh:198
auto unique(ForwardRange &&range)
Definition ranges.hh:222
bool all_of(InputRange &&range, UnaryPredicate pred)
Definition ranges.hh:186
constexpr void fill(ForwardRange &&range, const T &value)
Definition ranges.hh:305
auto remove(ForwardRange &&range, const T &value)
Definition ranges.hh:281
void replace_if(ForwardRange &&range, UnaryPredicate pred, const T &new_value)
Definition ranges.hh:299
bool all_equal(InputRange &&range, Proj proj={})
Definition ranges.hh:405
auto find_if(InputRange &&range, UnaryPredicate pred)
Definition ranges.hh:173
bool none_of(InputRange &&range, UnaryPredicate pred)
Definition ranges.hh:210
auto copy(InputRange &&range, OutputIter out)
Definition ranges.hh:250
auto count(InputRange &&range, const T &value)
Definition ranges.hh:339
auto remove_if(ForwardRange &&range, UnaryPredicate pred)
Definition ranges.hh:287
constexpr void iota(ForwardIt first, ForwardIt last, T value)
Definition ranges.hh:312
T accumulate(InputRange &&range, T init)
Definition ranges.hh:327
void stable_sort(RandomAccessRange &&range)
Definition ranges.hh:76
auto find(InputRange &&range, const T &value)
Definition ranges.hh:160
bool equal(InputRange1 &&range1, InputRange2 &&range2, Pred pred={}, Proj1 proj1={}, Proj2 proj2={})
Definition ranges.hh:368
auto upper_bound(ForwardRange &&range, const T &value, Compare comp={}, Proj proj={})
Definition ranges.hh:124
auto equal_range(ForwardRange &&range, const T &value, Compare comp={})
Definition ranges.hh:133
auto set_difference(InputRange1 &&range1, InputRange2 &&range2, OutputIter out)
Definition ranges.hh:358
void generate(ForwardRange &&range, Generator &&g)
Definition ranges.hh:275
auto transform(InputRange &&range, OutputIter out, UnaryOperation op)
Definition ranges.hh:269
auto copy_if(InputRange &&range, OutputIter out, UnaryPredicate pred)
Definition ranges.hh:263
constexpr void replace(ForwardRange &&range, const T &old_value, const T &new_value)
Definition ranges.hh:293
constexpr void sort(RandomAccessRange &&range)
Definition ranges.hh:49
auto lower_bound(ForwardRange &&range, const T &value, Compare comp={}, Proj proj={})
Definition ranges.hh:115
auto count_if(InputRange &&range, UnaryPredicate pred)
Definition ranges.hh:345
constexpr auto make_span(Range &&range)
Definition ranges.hh:452
constexpr auto subspan(Range &&range, size_t offset, size_t count=std::dynamic_extent)
Definition ranges.hh:471
auto * binary_find(ForwardRange &&range, const T &value, Compare comp={}, Proj proj={})
Definition ranges.hh:438