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 } // namespace cpp20
131 
132 /*!
133  * \ingroup UtilitiesGroup
134  * \brief Utility functions wrapping STL algorithms and additional algorithms.
135  */
136 namespace alg {
137 /// Convenience wrapper around std::all_of
138 template <class Container, class UnaryPredicate>
139 decltype(auto) all_of(const Container& c, UnaryPredicate&& unary_predicate) {
140  using std::begin;
141  using std::end;
142  return std::all_of(begin(c), end(c),
143  std::forward<UnaryPredicate>(unary_predicate));
144 }
145 
146 /// Convenience wrapper around std::any_of
147 template <class Container, class UnaryPredicate>
148 decltype(auto) any_of(const Container& c, UnaryPredicate&& unary_predicate) {
149  using std::begin;
150  using std::end;
151  return std::any_of(begin(c), end(c),
152  std::forward<UnaryPredicate>(unary_predicate));
153 }
154 
155 /// Convenience wrapper around std::none_of
156 template <class Container, class UnaryPredicate>
157 decltype(auto) none_of(const Container& c, UnaryPredicate&& unary_predicate) {
158  using std::begin;
159  using std::end;
160  return std::none_of(begin(c), end(c),
161  std::forward<UnaryPredicate>(unary_predicate));
162 }
163 
164 /// Convenience wrapper around std::count
165 template <class Container, class T>
166 decltype(auto) count(const Container& c, const T& value) {
167  using std::begin;
168  using std::end;
169  return std::count(begin(c), end(c), value);
170 }
171 
172 /// Convenience wrapper around std::count_if
173 template <class Container, class UnaryPredicate>
174 decltype(auto) count_if(const Container& c, UnaryPredicate&& unary_predicate) {
175  using std::begin;
176  using std::end;
177  return std::count_if(begin(c), end(c),
178  std::forward<UnaryPredicate>(unary_predicate));
179 }
180 
181 /// Convenience wrapper around std::find
182 template <class Container, class T>
183 decltype(auto) find(const Container& c, const T& value) {
184  using std::begin;
185  using std::end;
186  return std::find(begin(c), end(c), value);
187 }
188 
189 /// Convenience wrapper around std::find_if
190 template <class Container, class UnaryPredicate>
191 decltype(auto) find_if(const Container& c, UnaryPredicate&& unary_predicate) {
192  using std::begin;
193  using std::end;
194  return std::find_if(begin(c), end(c),
195  std::forward<UnaryPredicate>(unary_predicate));
196 }
197 
198 /// Convenience wrapper around std::find_if_not
199 template <class Container, class UnaryPredicate>
200 decltype(auto) find_if_not(const Container& c,
201  UnaryPredicate&& unary_predicate) {
202  using std::begin;
203  using std::end;
204  return std::find_if_not(begin(c), end(c),
205  std::forward<UnaryPredicate>(unary_predicate));
206 }
207 
208 /// Convenience wrapper around std::find, returns `true` if `value` is in `c`.
209 template <class Container, class T>
210 bool found(const Container& c, const T& value) {
211  using std::begin;
212  using std::end;
213  return std::find(begin(c), end(c), value) != end(c);
214 }
215 
216 /// Convenience wrapper around std::find_if, returns `true` if the result of
217 /// `std::find_if` is not equal to `end(c)`.
218 template <class Container, class UnaryPredicate>
219 bool found_if(const Container& c, UnaryPredicate&& unary_predicate) {
220  using std::begin;
221  using std::end;
222  return std::find_if(begin(c), end(c),
223  std::forward<UnaryPredicate>(unary_predicate)) != end(c);
224 }
225 
226 /// Convenience wrapper around std::find_if_not, returns `true` if the result of
227 /// `std::find_if_not` is not equal to `end(c)`.
228 template <class Container, class UnaryPredicate>
229 bool found_if_not(const Container& c, UnaryPredicate&& unary_predicate) {
230  using std::begin;
231  using std::end;
232  return std::find_if_not(begin(c), end(c),
233  std::forward<UnaryPredicate>(unary_predicate)) !=
234  end(c);
235 }
236 
237 /// Convenience wrapper around std::for_each, returns the result of
238 /// `std::for_each(begin(c), end(c), f)`.
239 template <class Container, class UnaryFunction>
240 decltype(auto) for_each(const Container& c, UnaryFunction&& f) {
241  using std::begin;
242  using std::end;
243  return std::for_each(begin(c), end(c), std::forward<UnaryFunction>(f));
244 }
245 
246 /// Convenience wrapper around std::equal, assumes containers `lhs` has at least
247 /// as many elements as `rhs`.
248 template <class Container, class Container2>
249 decltype(auto) equal(const Container& lhs, const Container2& rhs) {
250  using std::begin;
251  using std::end;
252  return std::equal(begin(lhs), end(lhs), begin(rhs));
253 }
254 
255 /// Convenience wrapper around std::equal, assumes containers `lhs` has at least
256 /// as many elements as `rhs`.
257 template <class Container, class Container2, class BinaryPredicate>
258 decltype(auto) equal(const Container& lhs, const Container2& rhs,
259  BinaryPredicate&& p) {
260  using std::begin;
261  using std::end;
262  return std::equal(begin(lhs), end(lhs), begin(rhs),
263  std::forward<BinaryPredicate>(p));
264 }
265 
266 /// Convenience wrapper around std::max_element
267 template <class Container>
268 decltype(auto) max_element(const Container& c) {
269  using std::begin;
270  using std::end;
271  return std::max_element(begin(c), end(c));
272 }
273 
274 /// Convenience wrapper around std::max_element
275 template <class Container, class Compare>
276 decltype(auto) max_element(const Container& c, Compare&& comp) {
277  using std::begin;
278  using std::end;
279  return std::max_element(begin(c), end(c), std::forward<Compare>(comp));
280 }
281 
282 /// Convenience wrapper around std::min_element
283 template <class Container>
284 decltype(auto) min_element(const Container& c) {
285  using std::begin;
286  using std::end;
287  return std::min_element(begin(c), end(c));
288 }
289 
290 /// Convenience wrapper around std::min_element
291 template <class Container, class Compare>
292 decltype(auto) min_element(const Container& c, Compare&& comp) {
293  using std::begin;
294  using std::end;
295  return std::min_element(begin(c), end(c), std::forward<Compare>(comp));
296 }
297 
298 /// Convenience wrapper around std::remove
299 template <class Container, class T>
300 decltype(auto) remove(Container& c, const T& value) {
301  using std::begin;
302  using std::end;
303  return std::remove(begin(c), end(c), value);
304 }
305 
306 /// Convenience wrapper around std::remove_if
307 template <class Container, class UnaryPredicate>
308 decltype(auto) remove_if(Container& c, UnaryPredicate&& unary_predicate) {
309  using std::begin;
310  using std::end;
311  return std::remove_if(begin(c), end(c),
312  std::forward<UnaryPredicate>(unary_predicate));
313 }
314 } // namespace alg
bool found_if_not(const Container &c, UnaryPredicate &&unary_predicate)
Convenience wrapper around std::find_if_not, returns true if the result of std::find_if_not is not eq...
Definition: Algorithm.hpp:229
C++ STL code present in C++20.
Definition: Algorithm.hpp:11
constexpr bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp)
Definition: Algorithm.hpp:93
constexpr void iter_swap(ForwardIt1 a, ForwardIt2 b)
Definition: Algorithm.hpp:32
Definition: Determinant.hpp:11
Utility functions wrapping STL algorithms and additional algorithms.
Definition: Algorithm.hpp:136
constexpr void reverse(BidirectionalIterator first, BidirectionalIterator last)
Definition: Algorithm.hpp:79
bool found(const Container &c, const T &value)
Convenience wrapper around std::find, returns true if value is in c.
Definition: Algorithm.hpp:210
constexpr void swap(T &a, T &b) noexcept
Definition: Algorithm.hpp:19
Defines functions and classes from the GSL.
bool found_if(const Container &c, UnaryPredicate &&unary_predicate)
Convenience wrapper around std::find_if, returns true if the result of std::find_if is not equal to e...
Definition: Algorithm.hpp:219