Algorithm.hpp
1 // 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 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 constexpr void swap(T& a, T& b) noexcept {
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 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 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 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 constexpr bool next_permutation(BidirectionalIterator first,
124  BidirectionalIterator last) {
126  first, last,
127  std::less<
129 }
130 
131 /*!
132  * \ingroup UtilitiesGroup
133  * Reimplementation of std::find that is constexpr
134  */
135 template <class InputIt, class T>
136 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 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 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 namespace alg {
179 /// Convenience wrapper around std::all_of
180 template <class Container, class UnaryPredicate>
181 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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::remove
358 template <class Container, class T>
359 decltype(auto) remove(Container& c, const T& value) {
360  using std::begin;
361  using std::end;
362  return std::remove(begin(c), end(c), value);
363 }
364 
365 /// Convenience wrapper around std::remove_if
366 template <class Container, class UnaryPredicate>
367 decltype(auto) remove_if(Container& c, UnaryPredicate&& unary_predicate) {
368  using std::begin;
369  using std::end;
370  return std::remove_if(begin(c), end(c),
371  std::forward<UnaryPredicate>(unary_predicate));
372 }
373 
374 /// Convenience wrapper around std::sort
375 template <class Container>
376 decltype(auto) sort(Container& c) {
377  using std::begin;
378  using std::end;
379  return std::sort(begin(c), end(c));
380 }
381 
382 /// Convenience wrapper around std::sort
383 template <class Container, class Compare>
384 decltype(auto) sort(Container& c, Compare&& comp) {
385  using std::begin;
386  using std::end;
387  return std::sort(begin(c), end(c), std::forward<Compare>(comp));
388 }
389 
390 /// Convenience wrapper around std::transform
391 template <class Container, class OutputIt, class UnaryOp>
392 decltype(auto) transform(const Container& c, OutputIt output_first,
393  UnaryOp&& unary_op) {
394  using std::begin;
395  using std::end;
396  return std::transform(begin(c), end(c), output_first,
397  std::forward<UnaryOp>(unary_op));
398 }
399 
400 /// Convenience wrapper around std::transform
401 template <class Container1, class Container2, class OutputIt, class BinaryOp>
402 decltype(auto) transform(const Container1& c1, const Container2& c2,
403  OutputIt output_first, BinaryOp&& binary_op) {
404  using std::begin;
405  using std::end;
406  return std::transform(begin(c1), end(c1), begin(c2), output_first,
407  std::forward<BinaryOp>(binary_op));
408 }
409 } // namespace alg
alg::find_if_not
constexpr decltype(auto) find_if_not(Container &&c, UnaryPredicate &&unary_predicate)
Convenience wrapper around constexpr reimplementation of std::find_if_not.
Definition: Algorithm.hpp:245
alg::any_of
decltype(auto) any_of(const Container &c, UnaryPredicate &&unary_predicate)
Convenience wrapper around std::any_of.
Definition: Algorithm.hpp:190
cpp20
Definition: Algorithm.hpp:11
functional
alg::remove
decltype(auto) remove(Container &c, const T &value)
Convenience wrapper around std::remove.
Definition: Algorithm.hpp:359
alg
Utility functions wrapping STL algorithms and additional algorithms.
Definition: Algorithm.hpp:178
iterator
std::bidirectional_iterator_tag
cpp20::iter_swap
constexpr void iter_swap(ForwardIt1 a, ForwardIt2 b)
Definition: Algorithm.hpp:32
cpp20::next_permutation
constexpr bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp)
Definition: Algorithm.hpp:93
std::less
algorithm
alg::found_if
constexpr bool found_if(const Container &c, UnaryPredicate &&unary_predicate)
Convenience wrapper around constexpr reimplementation of std::find_if, returns true if the result of ...
Definition: Algorithm.hpp:266
alg::found
constexpr bool found(const Container &c, const T &value)
Convenience wrapper around constexpr reimplementation of std::find, returns true if value is in c.
Definition: Algorithm.hpp:257
alg::remove_if
decltype(auto) remove_if(Container &c, UnaryPredicate &&unary_predicate)
Convenience wrapper around std::remove_if.
Definition: Algorithm.hpp:367
std::iterator_traits
alg::count_if
decltype(auto) count_if(const Container &c, UnaryPredicate &&unary_predicate)
Convenience wrapper around std::count_if.
Definition: Algorithm.hpp:216
cpp20::find_if
constexpr InputIt find_if(InputIt first, InputIt last, UnaryPredicate p)
Definition: Algorithm.hpp:150
alg::min_element
decltype(auto) min_element(const Container &c)
Convenience wrapper around std::min_element.
Definition: Algorithm.hpp:343
cpp20::reverse
constexpr void reverse(BidirectionalIterator first, BidirectionalIterator last)
Definition: Algorithm.hpp:79
alg::equal
decltype(auto) equal(const Container &lhs, const Container2 &rhs)
Convenience wrapper around std::equal, assumes containers lhs has at least as many elements as rhs.
Definition: Algorithm.hpp:308
alg::for_each
decltype(auto) for_each(const Container &c, UnaryFunction &&f)
Convenience wrapper around std::for_each, returns the result of std::for_each(begin(c),...
Definition: Algorithm.hpp:291
alg::max_element
decltype(auto) max_element(const Container &c)
Convenience wrapper around std::max_element.
Definition: Algorithm.hpp:327
alg::count
decltype(auto) count(const Container &c, const T &value)
Convenience wrapper around std::count.
Definition: Algorithm.hpp:208
alg::sort
decltype(auto) sort(Container &c)
Convenience wrapper around std::sort.
Definition: Algorithm.hpp:376
alg::none_of
decltype(auto) none_of(const Container &c, UnaryPredicate &&unary_predicate)
Convenience wrapper around std::none_of.
Definition: Algorithm.hpp:199
Gsl.hpp
cpp20::find_if_not
constexpr InputIt find_if_not(InputIt first, InputIt last, UnaryPredicate q)
Definition: Algorithm.hpp:164
alg::find
constexpr decltype(auto) find(Container &&c, const T &value)
Convenience wrapper around constexpr reimplementation of std::find.
Definition: Algorithm.hpp:225
alg::found_if_not
constexpr bool found_if_not(const Container &c, UnaryPredicate &&unary_predicate)
Convenience wrapper around constexpr reimplementation of std::find_if_not, returns true if the result...
Definition: Algorithm.hpp:278
cpp20::swap
constexpr void swap(T &a, T &b) noexcept
Definition: Algorithm.hpp:19
alg::transform
decltype(auto) transform(const Container &c, OutputIt output_first, UnaryOp &&unary_op)
Convenience wrapper around std::transform.
Definition: Algorithm.hpp:392
alg::find_if
constexpr decltype(auto) find_if(Container &&c, UnaryPredicate &&unary_predicate)
Convenience wrapper around constexpr reimplementation of std::find_if.
Definition: Algorithm.hpp:234
alg::all_of
decltype(auto) all_of(const Container &c, UnaryPredicate &&unary_predicate)
Convenience wrapper around std::all_of.
Definition: Algorithm.hpp:181
cpp20::find
constexpr InputIt find(InputIt first, InputIt last, const T &value)
Definition: Algorithm.hpp:136