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