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 <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 
21 namespace ranges {
22 
23 template<typename ForwardRange, typename Compare = std::less<>, typename Proj = 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 
32 template<typename RandomAccessRange>
33 void sort(RandomAccessRange&& range)
34 {
35  std::sort(std::begin(range), std::end(range));
36 }
37 
38 template<typename RandomAccessRange, typename Compare>
39 void sort(RandomAccessRange&& range, Compare comp)
40 {
41  std::sort(std::begin(range), std::end(range), comp);
42 }
43 
44 template<typename RAIter, typename Compare = std::less<>, typename Proj>
45 void 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 
53 template<typename RandomAccessRange, typename Compare = std::less<>, typename Proj>
54 void sort(RandomAccessRange&& range, Compare comp, Proj proj)
55 {
56  sort(std::begin(range), std::end(range), comp, proj);
57 }
58 
59 template<typename RandomAccessRange>
60 void stable_sort(RandomAccessRange&& range)
61 {
62  std::stable_sort(std::begin(range), std::end(range));
63 }
64 
65 template<typename RandomAccessRange, typename Compare>
66 void stable_sort(RandomAccessRange&& range, Compare comp)
67 {
68  std::stable_sort(std::begin(range), std::end(range), comp);
69 }
70 
71 template<typename ForwardRange, typename T>
72 [[nodiscard]] bool binary_search(ForwardRange&& range, const T& value)
73 {
74  return std::binary_search(std::begin(range), std::end(range), value);
75 }
76 
77 template<typename ForwardRange, typename T, typename Compare>
78 [[nodiscard]] bool binary_search(ForwardRange&& range, const T& value, Compare comp)
79 {
80  return std::binary_search(std::begin(range), std::end(range), value, comp);
81 }
82 
83 template<typename ForwardRange, typename T, typename Compare = std::less<>, typename Proj = identity>
84 [[nodiscard]] auto lower_bound(ForwardRange&& range, const T& value, Compare comp = {}, Proj proj = {})
85 {
86  auto comp2 = [&](const auto& x, const auto& y) {
87  return comp(std::invoke(proj, x), y);
88  };
89  return std::lower_bound(std::begin(range), std::end(range), value, comp2);
90 }
91 
92 template<typename ForwardRange, typename T, typename Compare = std::less<>, typename Proj = identity>
93 [[nodiscard]] auto upper_bound(ForwardRange&& range, const T& value, Compare comp = {}, Proj proj = {})
94 {
95  auto comp2 = [&](const auto& x, const auto& y) {
96  return comp(x, std::invoke(proj, y));
97  };
98  return std::upper_bound(std::begin(range), std::end(range), value, comp2);
99 }
100 
101 template<typename ForwardRange, typename T, typename Compare = std::less<>>
102 [[nodiscard]] auto equal_range(ForwardRange&& range, const T& value, Compare comp = {})
103 {
104  return std::equal_range(std::begin(range), std::end(range), value, comp);
105 }
106 template<typename ForwardRange, typename T, typename Compare = std::less<>, typename Proj = identity>
107 [[nodiscard]] auto equal_range(ForwardRange&& range, const T& value, Compare comp, Proj proj)
108 {
109  using Iter = decltype(std::begin(range));
110  using R = typename std::iterator_traits<Iter>::value_type;
111  struct Comp2 {
112  Compare comp;
113  Proj proj;
114 
115  bool operator()(const R& x, const R& y) const {
116  return comp(std::invoke(proj, x), std::invoke(proj, y));
117  }
118  bool operator()(const R& x, const T& y) const {
119  return comp(std::invoke(proj, x), y);
120  }
121  bool operator()(const T& x, const R& y) const {
122  return comp(x, std::invoke(proj, y));
123  }
124  };
125  return std::equal_range(std::begin(range), std::end(range), value, Comp2{comp, proj});
126 }
127 
128 template<typename InputRange, typename T>
129 [[nodiscard]] auto find(InputRange&& range, const T& value)
130 {
131  return std::find(std::begin(range), std::end(range), value);
132 }
133 
134 template<typename InputRange, typename T, typename Proj>
135 [[nodiscard]] auto find(InputRange&& range, const T& value, Proj proj)
136 {
137  return find_if(std::forward<InputRange>(range),
138  [&](const auto& e) { return std::invoke(proj, e) == value; });
139 }
140 
141 template<typename InputRange, typename UnaryPredicate>
142 [[nodiscard]] auto find_if(InputRange&& range, UnaryPredicate pred)
143 {
144  return std::find_if(std::begin(range), std::end(range), pred);
145 }
146 
147 template<typename InputRange, typename UnaryPredicate>
148 [[nodiscard]] bool all_of(InputRange&& range, UnaryPredicate pred)
149 {
150  return std::all_of(std::begin(range), std::end(range), pred);
151 }
152 
153 template<typename InputRange, typename UnaryPredicate>
154 [[nodiscard]] bool any_of(InputRange&& range, UnaryPredicate pred)
155 {
156  return std::any_of(std::begin(range), std::end(range), pred);
157 }
158 
159 template<typename InputRange, typename UnaryPredicate>
160 [[nodiscard]] bool none_of(InputRange&& range, UnaryPredicate pred)
161 {
162  return std::none_of(std::begin(range), std::end(range), pred);
163 }
164 
165 template<typename ForwardRange>
166 [[nodiscard]] auto unique(ForwardRange&& range)
167 {
168  return std::unique(std::begin(range), std::end(range));
169 }
170 
171 template<typename ForwardRange, typename BinaryPredicate>
172 [[nodiscard]] auto unique(ForwardRange&& range, BinaryPredicate pred)
173 {
174  return std::unique(std::begin(range), std::end(range), pred);
175 }
176 
177 template<typename InputRange, typename OutputIter>
178 auto copy(InputRange&& range, OutputIter out)
179 {
180  return std::copy(std::begin(range), std::end(range), out);
181 }
182 
183 template<typename InputRange, typename OutputIter, typename UnaryPredicate>
184 auto copy_if(InputRange&& range, OutputIter out, UnaryPredicate pred)
185 {
186  return std::copy_if(std::begin(range), std::end(range), out, pred);
187 }
188 
189 template<typename InputRange, typename OutputIter, typename UnaryOperation>
190 auto transform(InputRange&& range, OutputIter out, UnaryOperation op)
191 {
192  return std::transform(std::begin(range), std::end(range), out, op);
193 }
194 
195 template<typename ForwardRange, typename Generator>
196 void generate(ForwardRange&& range, Generator&& g)
197 {
198  std::generate(std::begin(range), std::end(range), std::forward<Generator>(g));
199 }
200 
201 template<typename ForwardRange, typename T>
202 [[nodiscard]] auto remove(ForwardRange&& range, const T& value)
203 {
204  return std::remove(std::begin(range), std::end(range), value);
205 }
206 
207 template<typename ForwardRange, typename UnaryPredicate>
208 [[nodiscard]] auto remove_if(ForwardRange&& range, UnaryPredicate pred)
209 {
210  return std::remove_if(std::begin(range), std::end(range), pred);
211 }
212 
213 template<typename ForwardRange, typename T>
214 void replace(ForwardRange&& range, const T& old_value, const T& new_value)
215 {
216  std::replace(std::begin(range), std::end(range), old_value, new_value);
217 }
218 
219 template<typename ForwardRange, typename UnaryPredicate, typename T>
220 void replace_if(ForwardRange&& range, UnaryPredicate pred, const T& new_value)
221 {
222  std::replace_if(std::begin(range), std::end(range), pred, new_value);
223 }
224 
225 template<typename ForwardRange, typename T>
226 void fill(ForwardRange&& range, const T& value)
227 {
228  std::fill(std::begin(range), std::end(range), value);
229 }
230 
231 // part of c++20
232 template<typename ForwardIt, typename T>
233 constexpr void iota(ForwardIt first, ForwardIt last, T value)
234 {
235  while (first != last) {
236  *first++ = value;
237  ++value;
238  }
239 }
240 
241 template<typename ForwardRange, typename T>
242 constexpr void iota(ForwardRange&& range, T&& value)
243 {
244  iota(std::begin(range), std::end(range), std::forward<T>(value));
245 }
246 
247 template<typename InputRange, typename T>
248 [[nodiscard]] T accumulate(InputRange&& range, T init)
249 {
250  return std::accumulate(std::begin(range), std::end(range), init);
251 }
252 
253 template<typename InputRange, typename T, typename BinaryOperation>
254 [[nodiscard]] T accumulate(InputRange&& range, T init, BinaryOperation op)
255 {
256  return std::accumulate(std::begin(range), std::end(range), init, op);
257 }
258 
259 template<typename InputRange, typename T>
260 [[nodiscard]] auto count(InputRange&& range, const T& value)
261 {
262  return std::count(std::begin(range), std::end(range), value);
263 }
264 
265 template<typename InputRange, typename UnaryPredicate>
266 [[nodiscard]] auto count_if(InputRange&& range, UnaryPredicate pred)
267 {
268  return std::count_if(std::begin(range), std::end(range), pred);
269 }
270 
271 template<typename InputRange1, typename InputRange2, typename OutputIter>
272 auto set_difference(InputRange1&& range1, InputRange2&& range2, OutputIter out)
273 {
274  return std::set_difference(std::begin(range1), std::end(range1),
275  std::begin(range2), std::end(range2),
276  out);
277 }
278 
279 } // namespace ranges
280 
281 #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:89
Definition: ranges.hh:21
bool is_sorted(ForwardRange &&range, Compare comp={}, Proj proj={})
Definition: ranges.hh:24
void fill(ForwardRange &&range, const T &value)
Definition: ranges.hh:226
bool binary_search(ForwardRange &&range, const T &value)
Definition: ranges.hh:72
bool any_of(InputRange &&range, UnaryPredicate pred)
Definition: ranges.hh:154
auto unique(ForwardRange &&range)
Definition: ranges.hh:166
bool all_of(InputRange &&range, UnaryPredicate pred)
Definition: ranges.hh:148
auto unique(ForwardRange &&range, BinaryPredicate pred)
Definition: ranges.hh:172
auto remove(ForwardRange &&range, const T &value)
Definition: ranges.hh:202
void replace(ForwardRange &&range, const T &old_value, const T &new_value)
Definition: ranges.hh:214
void replace_if(ForwardRange &&range, UnaryPredicate pred, const T &new_value)
Definition: ranges.hh:220
void sort(RandomAccessRange &&range, Compare comp, Proj proj)
Definition: ranges.hh:54
auto find_if(InputRange &&range, UnaryPredicate pred)
Definition: ranges.hh:142
bool binary_search(ForwardRange &&range, const T &value, Compare comp)
Definition: ranges.hh:78
bool none_of(InputRange &&range, UnaryPredicate pred)
Definition: ranges.hh:160
auto count(InputRange &&range, const T &value)
Definition: ranges.hh:260
auto find(InputRange &&range, const T &value, Proj proj)
Definition: ranges.hh:135
auto equal_range(ForwardRange &&range, const T &value, Compare comp, Proj proj)
Definition: ranges.hh:107
auto remove_if(ForwardRange &&range, UnaryPredicate pred)
Definition: ranges.hh:208
constexpr void iota(ForwardIt first, ForwardIt last, T value)
Definition: ranges.hh:233
T accumulate(InputRange &&range, T init)
Definition: ranges.hh:248
void stable_sort(RandomAccessRange &&range)
Definition: ranges.hh:60
auto find(InputRange &&range, const T &value)
Definition: ranges.hh:129
auto upper_bound(ForwardRange &&range, const T &value, Compare comp={}, Proj proj={})
Definition: ranges.hh:93
auto equal_range(ForwardRange &&range, const T &value, Compare comp={})
Definition: ranges.hh:102
void stable_sort(RandomAccessRange &&range, Compare comp)
Definition: ranges.hh:66
auto set_difference(InputRange1 &&range1, InputRange2 &&range2, OutputIter out)
Definition: ranges.hh:272
void generate(ForwardRange &&range, Generator &&g)
Definition: ranges.hh:196
auto transform(InputRange &&range, OutputIter out, UnaryOperation op)
Definition: ranges.hh:190
auto copy_if(InputRange &&range, OutputIter out, UnaryPredicate pred)
Definition: ranges.hh:184
auto copy(InputRange &&range, OutputIter out)
Definition: ranges.hh:178
void sort(RandomAccessRange &&range)
Definition: ranges.hh:33
T accumulate(InputRange &&range, T init, BinaryOperation op)
Definition: ranges.hh:254
auto lower_bound(ForwardRange &&range, const T &value, Compare comp={}, Proj proj={})
Definition: ranges.hh:84
auto count_if(InputRange &&range, UnaryPredicate pred)
Definition: ranges.hh:266
constexpr auto begin(const zstring_view &x)
Definition: zstring_view.hh:83
constexpr auto end(const zstring_view &x)
Definition: zstring_view.hh:84