openMSX
ranges.hh
Go to the documentation of this file.
1#ifndef RANGES_HH
2#define RANGES_HH
3
4#include <algorithm>
5#include <functional>
6#include <iterator> // for std::begin(), std::end()
7#include <numeric>
8
9// Range based versions of the standard algorithms, these will likely become
10// part of c++20. For example see this post:
11// http://ericniebler.com/2018/12/05/standard-ranges/
12// In the future we can remove our implementation and instead use the standard
13// version (e.g. by a namespace alias like 'namespace ranges = std::ranges').
14//
15// All of the range algorithms below do nothing more than delegate to the
16// corresponding iterator-pair version of the algorithm.
17//
18// This list of algorithms is not complete. But it's easy to extend if/when we
19// need more.
20
21namespace ranges {
22
23template<typename ForwardRange, typename Compare = std::less<>, typename Proj = std::identity>
24[[nodiscard]] bool is_sorted(ForwardRange&& range, Compare comp = {}, Proj proj = {})
25{
26 return std::is_sorted(std::begin(range), std::end(range),
27 [&](const auto& x, const auto& y) {
28 return comp(std::invoke(proj, x), std::invoke(proj, y));
29 });
30}
31
32template<typename RandomAccessRange>
33constexpr void sort(RandomAccessRange&& range)
34{
35 std::sort(std::begin(range), std::end(range));
36}
37
38template<typename RandomAccessRange, typename Compare>
39constexpr void sort(RandomAccessRange&& range, Compare comp)
40{
41 std::sort(std::begin(range), std::end(range), comp);
42}
43
44template<typename RAIter, typename Compare = std::less<>, typename Proj>
45void sort(RAIter first, RAIter last, Compare comp, Proj proj)
46{
47 std::sort(first, last,
48 [&](const auto& x, const auto& y) {
49 return comp(std::invoke(proj, x), std::invoke(proj, y));
50 });
51}
52
53template<typename RandomAccessRange, typename Compare = std::less<>, typename Proj>
54void sort(RandomAccessRange&& range, Compare comp, Proj proj)
55{
56 sort(std::begin(range), std::end(range), comp, proj);
57}
58
59template<typename RandomAccessRange>
60void stable_sort(RandomAccessRange&& range)
61{
62 std::stable_sort(std::begin(range), std::end(range));
63}
64
65template<typename RandomAccessRange, typename Compare>
66void stable_sort(RandomAccessRange&& range, Compare comp)
67{
69}
70
71template<typename RAIter, typename Compare = std::less<>, typename Proj>
72void stable_sort(RAIter first, RAIter last, Compare comp, Proj proj)
73{
74 std::stable_sort(first, last,
75 [&](const auto& x, const auto& y) {
76 return comp(std::invoke(proj, x), std::invoke(proj, y));
77 });
78}
79
80template<typename RandomAccessRange, typename Compare = std::less<>, typename Proj>
81void stable_sort(RandomAccessRange&& range, Compare comp, Proj proj)
82{
83 stable_sort(std::begin(range), std::end(range), comp, proj);
84}
85
86template<typename ForwardRange, typename T>
87[[nodiscard]] bool binary_search(ForwardRange&& range, const T& value)
88{
89 return std::binary_search(std::begin(range), std::end(range), value);
90}
91
92template<typename ForwardRange, typename T, typename Compare>
93[[nodiscard]] bool binary_search(ForwardRange&& range, const T& value, Compare comp)
94{
95 return std::binary_search(std::begin(range), std::end(range), value, comp);
96}
97
98template<typename ForwardRange, typename T, typename Compare = std::less<>, typename Proj = std::identity>
99[[nodiscard]] auto lower_bound(ForwardRange&& range, const T& value, Compare comp = {}, Proj proj = {})
100{
101 auto comp2 = [&](const auto& x, const auto& y) {
102 return comp(std::invoke(proj, x), y);
103 };
104 return std::lower_bound(std::begin(range), std::end(range), value, comp2);
105}
106
107template<typename ForwardRange, typename T, typename Compare = std::less<>, typename Proj = std::identity>
108[[nodiscard]] auto upper_bound(ForwardRange&& range, const T& value, Compare comp = {}, Proj proj = {})
109{
110 auto comp2 = [&](const auto& x, const auto& y) {
111 return comp(x, std::invoke(proj, y));
112 };
113 return std::upper_bound(std::begin(range), std::end(range), value, comp2);
114}
115
116template<typename ForwardRange, typename T, typename Compare = std::less<>>
117[[nodiscard]] auto equal_range(ForwardRange&& range, const T& value, Compare comp = {})
118{
119 return std::equal_range(std::begin(range), std::end(range), value, comp);
120}
121template<typename ForwardRange, typename T, typename Compare = std::less<>, typename Proj = std::identity>
122[[nodiscard]] auto equal_range(ForwardRange&& range, const T& value, Compare comp, Proj proj)
123{
124 using Iter = decltype(std::begin(range));
125 using R = typename std::iterator_traits<Iter>::value_type;
126 struct Comp2 {
127 Compare comp;
128 Proj proj;
129
130 bool operator()(const R& x, const R& y) const {
131 return comp(std::invoke(proj, x), std::invoke(proj, y));
132 }
133 bool operator()(const R& x, const T& y) const {
134 return comp(std::invoke(proj, x), y);
135 }
136 bool operator()(const T& x, const R& y) const {
137 return comp(x, std::invoke(proj, y));
138 }
139 };
140 return std::equal_range(std::begin(range), std::end(range), value, Comp2{comp, proj});
141}
142
143template<typename InputRange, typename T>
144[[nodiscard]] auto find(InputRange&& range, const T& value)
145{
146 return std::find(std::begin(range), std::end(range), value);
147}
148
149template<typename InputRange, typename T, typename Proj>
150[[nodiscard]] auto find(InputRange&& range, const T& value, Proj proj)
151{
152 return find_if(std::forward<InputRange>(range),
153 [&](const auto& e) { return std::invoke(proj, e) == value; });
154}
155
156template<typename InputRange, typename UnaryPredicate>
157[[nodiscard]] auto find_if(InputRange&& range, UnaryPredicate pred)
158{
159 return std::find_if(std::begin(range), std::end(range), pred);
160}
161
162template<typename InputRange, typename UnaryPredicate>
163[[nodiscard]] bool all_of(InputRange&& range, UnaryPredicate pred)
164{
165 return std::all_of(std::begin(range), std::end(range), pred);
166}
167
168template<typename InputRange, typename UnaryPredicate>
169[[nodiscard]] bool any_of(InputRange&& range, UnaryPredicate pred)
170{
171 return std::any_of(std::begin(range), std::end(range), pred);
172}
173
174template<typename InputRange, typename UnaryPredicate>
175[[nodiscard]] bool none_of(InputRange&& range, UnaryPredicate pred)
176{
177 return std::none_of(std::begin(range), std::end(range), pred);
178}
179
180template<typename ForwardRange>
181[[nodiscard]] auto unique(ForwardRange&& range)
182{
183 return std::unique(std::begin(range), std::end(range));
184}
185
186template<typename ForwardRange, typename BinaryPredicate>
187[[nodiscard]] auto unique(ForwardRange&& range, BinaryPredicate pred)
188{
189 return std::unique(std::begin(range), std::end(range), pred);
190}
191
192template<typename RAIter, typename Compare = std::equal_to<>, typename Proj>
193[[nodiscard]] auto unique(RAIter first, RAIter last, Compare comp, Proj proj)
194{
195 return std::unique(first, last,
196 [&](const auto& x, const auto& y) {
197 return comp(std::invoke(proj, x), std::invoke(proj, y));
198 });
199}
200
201template<typename RandomAccessRange, typename Compare = std::equal_to<>, typename Proj>
202[[nodiscard]] auto unique(RandomAccessRange&& range, Compare comp, Proj proj)
203{
204 return unique(std::begin(range), std::end(range), comp, proj);
205}
206
207template<typename InputRange, typename OutputIter>
208auto copy(InputRange&& range, OutputIter out)
209{
210 return std::copy(std::begin(range), std::end(range), out);
211}
212
213template<typename InputRange, typename OutputIter, typename UnaryPredicate>
214auto copy_if(InputRange&& range, OutputIter out, UnaryPredicate pred)
215{
216 return std::copy_if(std::begin(range), std::end(range), out, pred);
217}
218
219template<typename InputRange, typename OutputIter, typename UnaryOperation>
220auto transform(InputRange&& range, OutputIter out, UnaryOperation op)
221{
222 return std::transform(std::begin(range), std::end(range), out, op);
223}
224
225template<typename ForwardRange, typename Generator>
226void generate(ForwardRange&& range, Generator&& g)
227{
228 std::generate(std::begin(range), std::end(range), std::forward<Generator>(g));
229}
230
231template<typename ForwardRange, typename T>
232[[nodiscard]] auto remove(ForwardRange&& range, const T& value)
233{
234 return std::remove(std::begin(range), std::end(range), value);
235}
236
237template<typename ForwardRange, typename UnaryPredicate>
238[[nodiscard]] auto remove_if(ForwardRange&& range, UnaryPredicate pred)
239{
240 return std::remove_if(std::begin(range), std::end(range), pred);
241}
242
243template<typename ForwardRange, typename T>
244constexpr void replace(ForwardRange&& range, const T& old_value, const T& new_value)
245{
246 std::replace(std::begin(range), std::end(range), old_value, new_value);
247}
248
249template<typename ForwardRange, typename UnaryPredicate, typename T>
250void replace_if(ForwardRange&& range, UnaryPredicate pred, const T& new_value)
251{
252 std::replace_if(std::begin(range), std::end(range), pred, new_value);
253}
254
255template<typename ForwardRange, typename T>
256constexpr void fill(ForwardRange&& range, const T& value)
257{
258 std::fill(std::begin(range), std::end(range), value);
259}
260
261// part of c++20
262template<typename ForwardIt, typename T>
263constexpr void iota(ForwardIt first, ForwardIt last, T value)
264{
265 while (first != last) {
266 *first++ = value;
267 ++value;
268 }
269}
270
271template<typename ForwardRange, typename T>
272constexpr void iota(ForwardRange&& range, T&& value)
273{
274 iota(std::begin(range), std::end(range), std::forward<T>(value));
275}
276
277template<typename InputRange, typename T>
278[[nodiscard]] T accumulate(InputRange&& range, T init)
279{
280 return std::accumulate(std::begin(range), std::end(range), init);
281}
282
283template<typename InputRange, typename T, typename BinaryOperation>
284[[nodiscard]] T accumulate(InputRange&& range, T init, BinaryOperation op)
285{
286 return std::accumulate(std::begin(range), std::end(range), init, op);
287}
288
289template<typename InputRange, typename T>
290[[nodiscard]] auto count(InputRange&& range, const T& value)
291{
292 return std::count(std::begin(range), std::end(range), value);
293}
294
295template<typename InputRange, typename UnaryPredicate>
296[[nodiscard]] auto count_if(InputRange&& range, UnaryPredicate pred)
297{
298 return std::count_if(std::begin(range), std::end(range), pred);
299}
300
301template<typename InputRange1, typename InputRange2, typename OutputIter>
302auto set_difference(InputRange1&& range1, InputRange2&& range2, OutputIter out)
303{
304 return std::set_difference(std::begin(range1), std::end(range1),
305 std::begin(range2), std::end(range2),
306 out);
307}
308
309} // namespace ranges
310
311#endif
int g
constexpr double e
Definition: Math.hh:18
bool comp(const uint8_t *p, const uint8_t *q)
constexpr auto R
Definition: MSXMixer.cc:298
constexpr KeyMatrixPosition x
Keyboard bindings.
Definition: Keyboard.cc:127
Definition: ranges.hh:21
bool is_sorted(ForwardRange &&range, Compare comp={}, Proj proj={})
Definition: ranges.hh:24
bool binary_search(ForwardRange &&range, const T &value)
Definition: ranges.hh:87
bool any_of(InputRange &&range, UnaryPredicate pred)
Definition: ranges.hh:169
auto unique(ForwardRange &&range)
Definition: ranges.hh:181
bool all_of(InputRange &&range, UnaryPredicate pred)
Definition: ranges.hh:163
constexpr void fill(ForwardRange &&range, const T &value)
Definition: ranges.hh:256
auto remove(ForwardRange &&range, const T &value)
Definition: ranges.hh:232
void replace_if(ForwardRange &&range, UnaryPredicate pred, const T &new_value)
Definition: ranges.hh:250
void stable_sort(RandomAccessRange &&range, Compare comp, Proj proj)
Definition: ranges.hh:81
void sort(RandomAccessRange &&range, Compare comp, Proj proj)
Definition: ranges.hh:54
auto find_if(InputRange &&range, UnaryPredicate pred)
Definition: ranges.hh:157
bool binary_search(ForwardRange &&range, const T &value, Compare comp)
Definition: ranges.hh:93
bool none_of(InputRange &&range, UnaryPredicate pred)
Definition: ranges.hh:175
auto count(InputRange &&range, const T &value)
Definition: ranges.hh:290
auto find(InputRange &&range, const T &value, Proj proj)
Definition: ranges.hh:150
auto equal_range(ForwardRange &&range, const T &value, Compare comp, Proj proj)
Definition: ranges.hh:122
auto remove_if(ForwardRange &&range, UnaryPredicate pred)
Definition: ranges.hh:238
constexpr void iota(ForwardIt first, ForwardIt last, T value)
Definition: ranges.hh:263
T accumulate(InputRange &&range, T init)
Definition: ranges.hh:278
void stable_sort(RandomAccessRange &&range)
Definition: ranges.hh:60
auto find(InputRange &&range, const T &value)
Definition: ranges.hh:144
auto unique(RandomAccessRange &&range, Compare comp, Proj proj)
Definition: ranges.hh:202
auto upper_bound(ForwardRange &&range, const T &value, Compare comp={}, Proj proj={})
Definition: ranges.hh:108
auto equal_range(ForwardRange &&range, const T &value, Compare comp={})
Definition: ranges.hh:117
auto set_difference(InputRange1 &&range1, InputRange2 &&range2, OutputIter out)
Definition: ranges.hh:302
void generate(ForwardRange &&range, Generator &&g)
Definition: ranges.hh:226
auto transform(InputRange &&range, OutputIter out, UnaryOperation op)
Definition: ranges.hh:220
auto copy_if(InputRange &&range, OutputIter out, UnaryPredicate pred)
Definition: ranges.hh:214
auto copy(InputRange &&range, OutputIter out)
Definition: ranges.hh:208
constexpr void replace(ForwardRange &&range, const T &old_value, const T &new_value)
Definition: ranges.hh:244
T accumulate(InputRange &&range, T init, BinaryOperation op)
Definition: ranges.hh:284
constexpr void sort(RandomAccessRange &&range)
Definition: ranges.hh:33
auto lower_bound(ForwardRange &&range, const T &value, Compare comp={}, Proj proj={})
Definition: ranges.hh:99
auto count_if(InputRange &&range, UnaryPredicate pred)
Definition: ranges.hh:296
constexpr auto begin(const zstring_view &x)
constexpr auto end(const zstring_view &x)