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