Line data Source code
1 0 : // Distributed under the MIT License.
2 : // See LICENSE.txt for details.
3 : #pragma once
4 :
5 : #include <algorithm>
6 : #include <functional>
7 : #include <iterator>
8 :
9 : #include "Utilities/Gsl.hpp"
10 :
11 1 : namespace cpp20 {
12 : /*!
13 : * \ingroup UtilitiesGroup
14 : * Reimplementation of std::swap that is constexpr;
15 : * taken from the LLVM source at
16 : * https://github.com/llvm-mirror/libcxx/blob/master/include/type_traits
17 : */
18 : template <class T>
19 1 : constexpr void swap(T& a, T& b) {
20 : T c(std::move(a));
21 : a = std::move(b);
22 : b = std::move(c);
23 : }
24 :
25 : /*!
26 : * \ingroup UtilitiesGroup
27 : * Reimplementation of std::iter_swap that is constexpr;
28 : * taken from the LLVM source at
29 : * https://github.com/llvm-mirror/libcxx/blob/master/include/type_traits
30 : */
31 : template <class ForwardIt1, class ForwardIt2>
32 1 : constexpr void iter_swap(ForwardIt1 a, ForwardIt2 b) {
33 : swap(*a, *b);
34 : }
35 :
36 : namespace detail {
37 : /*!
38 : * \ingroup UtilitiesGroup
39 : * Reimplementation of std::reverse that is constexpr, for bidirectional
40 : * iterators; taken from the LLVM source at
41 : * https://github.com/llvm-mirror/libcxx/blob/master/include/algorithm
42 : */
43 : template <class BidirIt>
44 : constexpr void reverse(BidirIt first, BidirIt last,
45 : std::bidirectional_iterator_tag /* unused */) {
46 : while (first != last) {
47 : if (first == --last) {
48 : break;
49 : }
50 : cpp20::iter_swap(first, last);
51 : ++first;
52 : }
53 : }
54 :
55 : /*!
56 : * \ingroup UtilitiesGroup
57 : * Reimplementation of std::reverse that is constexpr, for random access
58 : * iterators; taken from the LLVM source at
59 : * https://github.com/llvm-mirror/libcxx/blob/master/include/algorithm
60 : */
61 : template <class RandomAccessIterator>
62 : constexpr void reverse(RandomAccessIterator first, RandomAccessIterator last,
63 : std::random_access_iterator_tag /* unused */) {
64 : if (first != last) {
65 : for (; first < --last; ++first) {
66 : cpp20::iter_swap(first, last);
67 : }
68 : }
69 : }
70 : } // namespace detail
71 :
72 : /*!
73 : * \ingroup UtilitiesGroup
74 : * Reimplementation of std::reverse that is constexpr;
75 : * taken from the LLVM source at
76 : * https://github.com/llvm-mirror/libcxx/blob/master/include/algorithm
77 : */
78 : template <class BidirectionalIterator>
79 1 : constexpr void reverse(BidirectionalIterator first,
80 : BidirectionalIterator last) {
81 : cpp20::detail::reverse(first, last,
82 : typename std::iterator_traits<
83 : BidirectionalIterator>::iterator_category());
84 : }
85 :
86 : /*!
87 : * \ingroup UtilitiesGroup
88 : * Reimplementation of std::next_permutation that is constexpr,
89 : * for a generic comparator; taken from the LLVM source at
90 : * https://github.com/llvm-mirror/libcxx/blob/master/include/algorithm
91 : */
92 : template <class Compare, class BidirectionalIterator>
93 1 : constexpr bool next_permutation(BidirectionalIterator first,
94 : BidirectionalIterator last, Compare comp) {
95 : BidirectionalIterator i = last;
96 : if (first == last || first == --i) {
97 : return false;
98 : }
99 : while (true) {
100 : BidirectionalIterator ip1 = i;
101 : if (comp(*--i, *ip1)) {
102 : BidirectionalIterator j = last;
103 : while (!comp(*i, *--j)) {
104 : }
105 : cpp20::swap(*i, *j);
106 : cpp20::reverse(ip1, last);
107 : return true;
108 : }
109 : if (i == first) {
110 : cpp20::reverse(first, last);
111 : return false;
112 : }
113 : }
114 : }
115 :
116 : /*!
117 : * \ingroup UtilitiesGroup
118 : * Reimplementation of std::next_permutation that is constexpr,
119 : * with less as the comparator; taken from the LLVM source at
120 : * https://github.com/llvm-mirror/libcxx/blob/master/include/algorithm
121 : */
122 : template <class BidirectionalIterator>
123 1 : constexpr bool next_permutation(BidirectionalIterator first,
124 : BidirectionalIterator last) {
125 : return cpp20::next_permutation(
126 : first, last,
127 : std::less<
128 : typename std::iterator_traits<BidirectionalIterator>::value_type>());
129 : }
130 :
131 : /*!
132 : * \ingroup UtilitiesGroup
133 : * Reimplementation of std::find that is constexpr
134 : */
135 : template <class InputIt, class T>
136 1 : constexpr InputIt find(InputIt first, InputIt last, const T& value) {
137 : for (; first != last; ++first) {
138 : if (*first == value) {
139 : return first;
140 : }
141 : }
142 : return last;
143 : }
144 :
145 : /*!
146 : * \ingroup UtilitiesGroup
147 : * Reimplementation of std::find_if that is constexpr
148 : */
149 : template <class InputIt, class UnaryPredicate>
150 1 : constexpr InputIt find_if(InputIt first, InputIt last, UnaryPredicate p) {
151 : for (; first != last; ++first) {
152 : if (p(*first)) {
153 : return first;
154 : }
155 : }
156 : return last;
157 : }
158 :
159 : /*!
160 : * \ingroup UtilitiesGroup
161 : * Reimplementation of std::find_if_not that is constexpr
162 : */
163 : template <class InputIt, class UnaryPredicate>
164 1 : constexpr InputIt find_if_not(InputIt first, InputIt last, UnaryPredicate q) {
165 : for (; first != last; ++first) {
166 : if (!q(*first)) {
167 : return first;
168 : }
169 : }
170 : return last;
171 : }
172 : } // namespace cpp20
173 :
174 : /*!
175 : * \ingroup UtilitiesGroup
176 : * \brief Utility functions wrapping STL algorithms and additional algorithms.
177 : */
178 1 : namespace alg {
179 : /// Convenience wrapper around std::all_of
180 : template <class Container, class UnaryPredicate>
181 1 : decltype(auto) all_of(const Container& c, UnaryPredicate&& unary_predicate) {
182 : using std::begin;
183 : using std::end;
184 : return std::all_of(begin(c), end(c),
185 : std::forward<UnaryPredicate>(unary_predicate));
186 : }
187 :
188 : /// Convenience wrapper around std::any_of
189 : template <class Container, class UnaryPredicate>
190 1 : decltype(auto) any_of(const Container& c, UnaryPredicate&& unary_predicate) {
191 : using std::begin;
192 : using std::end;
193 : return std::any_of(begin(c), end(c),
194 : std::forward<UnaryPredicate>(unary_predicate));
195 : }
196 :
197 : /// Convenience wrapper around std::none_of
198 : template <class Container, class UnaryPredicate>
199 1 : decltype(auto) none_of(const Container& c, UnaryPredicate&& unary_predicate) {
200 : using std::begin;
201 : using std::end;
202 : return std::none_of(begin(c), end(c),
203 : std::forward<UnaryPredicate>(unary_predicate));
204 : }
205 :
206 : /// Convenience wrapper around std::count
207 : template <class Container, class T>
208 1 : decltype(auto) count(const Container& c, const T& value) {
209 : using std::begin;
210 : using std::end;
211 : return std::count(begin(c), end(c), value);
212 : }
213 :
214 : /// Convenience wrapper around std::count_if
215 : template <class Container, class UnaryPredicate>
216 1 : decltype(auto) count_if(const Container& c, UnaryPredicate&& unary_predicate) {
217 : using std::begin;
218 : using std::end;
219 : return std::count_if(begin(c), end(c),
220 : std::forward<UnaryPredicate>(unary_predicate));
221 : }
222 :
223 : /// Convenience wrapper around constexpr reimplementation of std::find
224 : template <class Container, class T>
225 1 : constexpr decltype(auto) find(Container&& c, const T& value) {
226 : using std::begin;
227 : using std::end;
228 : return cpp20::find(begin(std::forward<Container>(c)),
229 : end(std::forward<Container>(c)), value);
230 : }
231 :
232 : /// Convenience wrapper around constexpr reimplementation of std::find_if
233 : template <class Container, class UnaryPredicate>
234 1 : constexpr decltype(auto) find_if(Container&& c,
235 : UnaryPredicate&& unary_predicate) {
236 : using std::begin;
237 : using std::end;
238 : return cpp20::find_if(begin(std::forward<Container>(c)),
239 : end(std::forward<Container>(c)),
240 : std::forward<UnaryPredicate>(unary_predicate));
241 : }
242 :
243 : /// Convenience wrapper around constexpr reimplementation of std::find_if_not
244 : template <class Container, class UnaryPredicate>
245 1 : constexpr decltype(auto) find_if_not(Container&& c,
246 : UnaryPredicate&& unary_predicate) {
247 : using std::begin;
248 : using std::end;
249 : return cpp20::find_if_not(begin(std::forward<Container>(c)),
250 : end(std::forward<Container>(c)),
251 : std::forward<UnaryPredicate>(unary_predicate));
252 : }
253 :
254 : /// Convenience wrapper around constexpr reimplementation of std::find, returns
255 : /// `true` if `value` is in `c`.
256 : template <class Container, class T>
257 1 : constexpr bool found(const Container& c, const T& value) {
258 : using std::begin;
259 : using std::end;
260 : return cpp20::find(begin(c), end(c), value) != end(c);
261 : }
262 :
263 : /// Convenience wrapper around constexpr reimplementation of std::find_if,
264 : /// returns `true` if the result of `cpp20::find_if` is not equal to `end(c)`.
265 : template <class Container, class UnaryPredicate>
266 1 : constexpr bool found_if(const Container& c, UnaryPredicate&& unary_predicate) {
267 : using std::begin;
268 : using std::end;
269 : return cpp20::find_if(begin(c), end(c),
270 : std::forward<UnaryPredicate>(unary_predicate)) !=
271 : end(c);
272 : }
273 :
274 : /// Convenience wrapper around constexpr reimplementation of std::find_if_not,
275 : /// returns `true` if the result of `cpp20::find_if_not` is not equal to
276 : /// `end(c)`.
277 : template <class Container, class UnaryPredicate>
278 1 : constexpr bool found_if_not(const Container& c,
279 : UnaryPredicate&& unary_predicate) {
280 : using std::begin;
281 : using std::end;
282 : return cpp20::find_if_not(begin(c), end(c),
283 : std::forward<UnaryPredicate>(unary_predicate)) !=
284 : end(c);
285 : }
286 :
287 : /// @{
288 : /// Convenience wrapper around std::for_each, returns the result of
289 : /// `std::for_each(begin(c), end(c), f)`.
290 : template <class Container, class UnaryFunction>
291 1 : decltype(auto) for_each(const Container& c, UnaryFunction&& f) {
292 : using std::begin;
293 : using std::end;
294 : return std::for_each(begin(c), end(c), std::forward<UnaryFunction>(f));
295 : }
296 :
297 : template <class Container, class UnaryFunction>
298 1 : decltype(auto) for_each(Container& c, UnaryFunction&& f) {
299 : using std::begin;
300 : using std::end;
301 : return std::for_each(begin(c), end(c), std::forward<UnaryFunction>(f));
302 : }
303 : /// @}
304 :
305 : /// Convenience wrapper around std::equal, assumes containers `lhs` has at least
306 : /// as many elements as `rhs`.
307 : template <class Container, class Container2>
308 1 : decltype(auto) equal(const Container& lhs, const Container2& rhs) {
309 : using std::begin;
310 : using std::end;
311 : return std::equal(begin(lhs), end(lhs), begin(rhs));
312 : }
313 :
314 : /// Convenience wrapper around std::equal, assumes containers `lhs` has at least
315 : /// as many elements as `rhs`.
316 : template <class Container, class Container2, class BinaryPredicate>
317 1 : decltype(auto) equal(const Container& lhs, const Container2& rhs,
318 : BinaryPredicate&& p) {
319 : using std::begin;
320 : using std::end;
321 : return std::equal(begin(lhs), end(lhs), begin(rhs),
322 : std::forward<BinaryPredicate>(p));
323 : }
324 :
325 : /// Convenience wrapper around std::max_element
326 : template <class Container>
327 1 : constexpr decltype(auto) max_element(const Container& c) {
328 : using std::begin;
329 : using std::end;
330 : return std::max_element(begin(c), end(c));
331 : }
332 :
333 : /// Convenience wrapper around std::max_element
334 : template <class Container, class Compare>
335 1 : constexpr decltype(auto) max_element(const Container& c, Compare&& comp) {
336 : using std::begin;
337 : using std::end;
338 : return std::max_element(begin(c), end(c), std::forward<Compare>(comp));
339 : }
340 :
341 : /// Convenience wrapper around std::min_element
342 : template <class Container>
343 1 : constexpr decltype(auto) min_element(const Container& c) {
344 : using std::begin;
345 : using std::end;
346 : return std::min_element(begin(c), end(c));
347 : }
348 :
349 : /// Convenience wrapper around std::min_element
350 : template <class Container, class Compare>
351 1 : constexpr decltype(auto) min_element(const Container& c, Compare&& comp) {
352 : using std::begin;
353 : using std::end;
354 : return std::min_element(begin(c), end(c), std::forward<Compare>(comp));
355 : }
356 :
357 : /// Convenience wrapper around std::minmax_element
358 : template <class Container>
359 1 : constexpr decltype(auto) minmax_element(const Container& c) {
360 : using std::begin;
361 : using std::end;
362 : return std::minmax_element(begin(c), end(c));
363 : }
364 :
365 : /// Convenience wrapper around std::minmax_element
366 : template <class Container, class Compare>
367 1 : constexpr decltype(auto) minmax_element(const Container& c, Compare&& comp) {
368 : using std::begin;
369 : using std::end;
370 : return std::minmax_element(begin(c), end(c), std::forward<Compare>(comp));
371 : }
372 :
373 : /// Convenience wrapper around std::remove
374 : template <class Container, class T>
375 1 : decltype(auto) remove(Container& c, const T& value) {
376 : using std::begin;
377 : using std::end;
378 : return std::remove(begin(c), end(c), value);
379 : }
380 :
381 : /// Convenience wrapper around std::remove_if
382 : template <class Container, class UnaryPredicate>
383 1 : decltype(auto) remove_if(Container& c, UnaryPredicate&& unary_predicate) {
384 : using std::begin;
385 : using std::end;
386 : return std::remove_if(begin(c), end(c),
387 : std::forward<UnaryPredicate>(unary_predicate));
388 : }
389 :
390 : /// Convience wrapper around std::sample
391 : template <class Container, class OutputIt, class Distance, class URBG>
392 1 : decltype(auto) sample(Container& c, OutputIt out, Distance n, URBG&& g) {
393 : using std::begin;
394 : using std::end;
395 : return std::sample(begin(c), end(c), out, n, g);
396 : }
397 :
398 : /// Convenience wrapper around std::sort
399 : template <class Container>
400 1 : decltype(auto) sort(Container& c) {
401 : using std::begin;
402 : using std::end;
403 : return std::sort(begin(c), end(c));
404 : }
405 :
406 : /// Convenience wrapper around std::sort
407 : template <class Container, class Compare>
408 1 : decltype(auto) sort(Container& c, Compare&& comp) {
409 : using std::begin;
410 : using std::end;
411 : return std::sort(begin(c), end(c), std::forward<Compare>(comp));
412 : }
413 :
414 : /// Convenience wrapper around std::transform
415 : template <class Container, class OutputIt, class UnaryOp>
416 1 : decltype(auto) transform(const Container& c, OutputIt output_first,
417 : UnaryOp&& unary_op) {
418 : using std::begin;
419 : using std::end;
420 : return std::transform(begin(c), end(c), output_first,
421 : std::forward<UnaryOp>(unary_op));
422 : }
423 :
424 : /// Convenience wrapper around std::transform
425 : template <class Container1, class Container2, class OutputIt, class BinaryOp>
426 1 : decltype(auto) transform(const Container1& c1, const Container2& c2,
427 : OutputIt output_first, BinaryOp&& binary_op) {
428 : using std::begin;
429 : using std::end;
430 : return std::transform(begin(c1), end(c1), begin(c2), output_first,
431 : std::forward<BinaryOp>(binary_op));
432 : }
433 : } // namespace alg
|
