]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | /*! |
2 | @file | |
3 | Defines several `constexpr` algorithms. | |
4 | ||
5 | @copyright Louis Dionne 2013-2016 | |
6 | Distributed under the Boost Software License, Version 1.0. | |
7 | (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt) | |
8 | */ | |
9 | ||
10 | #ifndef BOOST_HANA_DETAIL_ALGORITHM_HPP | |
11 | #define BOOST_HANA_DETAIL_ALGORITHM_HPP | |
12 | ||
13 | #include <boost/hana/functional/placeholder.hpp> | |
14 | ||
15 | #include <boost/hana/config.hpp> | |
16 | ||
17 | #include <cstddef> | |
18 | #include <utility> | |
19 | ||
20 | ||
21 | BOOST_HANA_NAMESPACE_BEGIN namespace detail { | |
22 | // Do not call this swap, otherwise it can get picked up by ADL and conflict | |
23 | // with std::swap (see https://github.com/boostorg/hana/issues/297). | |
24 | template <typename T> | |
25 | constexpr void constexpr_swap(T& x, T& y) { | |
26 | auto tmp = x; | |
27 | x = y; | |
28 | y = std::move(tmp); | |
29 | } | |
30 | ||
31 | template <typename BidirIter> | |
32 | constexpr void reverse(BidirIter first, BidirIter last) { | |
33 | while (first != last) { | |
34 | if (first == --last) | |
35 | break; | |
36 | detail::constexpr_swap(*first, *last); | |
37 | ++first; | |
38 | } | |
39 | } | |
40 | ||
41 | template <typename BidirIter, typename BinaryPred> | |
42 | constexpr bool next_permutation(BidirIter first, BidirIter last, | |
43 | BinaryPred pred) | |
44 | { | |
45 | BidirIter i = last; | |
46 | if (first == last || first == --i) | |
47 | return false; | |
48 | while (true) { | |
49 | BidirIter ip1 = i; | |
50 | if (pred(*--i, *ip1)) { | |
51 | BidirIter j = last; | |
52 | while (!pred(*i, *--j)) | |
53 | ; | |
54 | detail::constexpr_swap(*i, *j); | |
55 | detail::reverse(ip1, last); | |
56 | return true; | |
57 | } | |
58 | if (i == first) { | |
59 | detail::reverse(first, last); | |
60 | return false; | |
61 | } | |
62 | } | |
63 | } | |
64 | ||
65 | template <typename BidirIter> | |
66 | constexpr bool next_permutation(BidirIter first, BidirIter last) | |
67 | { return detail::next_permutation(first, last, hana::_ < hana::_); } | |
68 | ||
69 | ||
70 | template <typename InputIter1, typename InputIter2, typename BinaryPred> | |
71 | constexpr bool lexicographical_compare(InputIter1 first1, InputIter1 last1, | |
72 | InputIter2 first2, InputIter2 last2, | |
73 | BinaryPred pred) | |
74 | { | |
75 | for (; first2 != last2; ++first1, ++first2) { | |
76 | if (first1 == last1 || pred(*first1, *first2)) | |
77 | return true; | |
78 | else if (pred(*first2, *first1)) | |
79 | return false; | |
80 | } | |
81 | return false; | |
82 | } | |
83 | ||
84 | template <typename InputIter1, typename InputIter2> | |
85 | constexpr bool lexicographical_compare(InputIter1 first1, InputIter1 last1, | |
86 | InputIter2 first2, InputIter2 last2) | |
87 | { return detail::lexicographical_compare(first1, last1, first2, last2, hana::_ < hana::_); } | |
88 | ||
89 | ||
90 | template <typename InputIter1, typename InputIter2, typename BinaryPred> | |
91 | constexpr bool equal(InputIter1 first1, InputIter1 last1, | |
92 | InputIter2 first2, InputIter2 last2, | |
93 | BinaryPred pred) | |
94 | { | |
95 | for (; first1 != last1 && first2 != last2; ++first1, ++first2) | |
96 | if (!pred(*first1, *first2)) | |
97 | return false; | |
98 | return first1 == last1 && first2 == last2; | |
99 | } | |
100 | ||
101 | template <typename InputIter1, typename InputIter2> | |
102 | constexpr bool equal(InputIter1 first1, InputIter1 last1, | |
103 | InputIter2 first2, InputIter2 last2) | |
104 | { return detail::equal(first1, last1, first2, last2, hana::_ == hana::_); } | |
105 | ||
106 | ||
107 | template <typename BidirIter, typename BinaryPred> | |
108 | constexpr void sort(BidirIter first, BidirIter last, BinaryPred pred) { | |
109 | if (first == last) return; | |
110 | ||
111 | BidirIter i = first; | |
112 | for (++i; i != last; ++i) { | |
113 | BidirIter j = i; | |
114 | auto t = *j; | |
115 | for (BidirIter k = i; k != first && pred(t, *--k); --j) | |
116 | *j = *k; | |
117 | *j = t; | |
118 | } | |
119 | } | |
120 | ||
121 | template <typename BidirIter> | |
122 | constexpr void sort(BidirIter first, BidirIter last) | |
123 | { detail::sort(first, last, hana::_ < hana::_); } | |
124 | ||
125 | ||
126 | template <typename InputIter, typename T> | |
127 | constexpr InputIter find(InputIter first, InputIter last, T const& value) { | |
128 | for (; first != last; ++first) | |
129 | if (*first == value) | |
130 | return first; | |
131 | return last; | |
132 | } | |
133 | ||
134 | template <typename InputIter, typename UnaryPred> | |
135 | constexpr InputIter find_if(InputIter first, InputIter last, UnaryPred pred) { | |
136 | for (; first != last; ++first) | |
137 | if (pred(*first)) | |
138 | return first; | |
139 | return last; | |
140 | } | |
141 | ||
142 | template <typename ForwardIter, typename T> | |
143 | constexpr void iota(ForwardIter first, ForwardIter last, T value) { | |
144 | while (first != last) { | |
145 | *first++ = value; | |
146 | ++value; | |
147 | } | |
148 | } | |
149 | ||
150 | template <typename InputIt, typename T> | |
151 | constexpr std::size_t | |
152 | count(InputIt first, InputIt last, T const& value) { | |
153 | std::size_t n = 0; | |
154 | for (; first != last; ++first) | |
155 | if (*first == value) | |
156 | ++n; | |
157 | return n; | |
158 | } | |
159 | ||
160 | template <typename InputIt, typename T, typename F> | |
161 | constexpr T accumulate(InputIt first, InputIt last, T init, F f) { | |
162 | for (; first != last; ++first) | |
163 | init = f(init, *first); | |
164 | return init; | |
165 | } | |
166 | ||
167 | template <typename InputIt, typename T> | |
168 | constexpr T accumulate(InputIt first, InputIt last, T init) { | |
169 | return detail::accumulate(first, last, init, hana::_ + hana::_); | |
170 | } | |
171 | ||
172 | template <typename ForwardIt> | |
173 | constexpr ForwardIt min_element(ForwardIt first, ForwardIt last) { | |
174 | if (first == last) | |
175 | return last; | |
176 | ||
177 | ForwardIt smallest = first; | |
178 | ++first; | |
179 | for (; first != last; ++first) | |
180 | if (*first < *smallest) | |
181 | smallest = first; | |
182 | return smallest; | |
183 | } | |
184 | } BOOST_HANA_NAMESPACE_END | |
185 | ||
186 | #endif // !BOOST_HANA_DETAIL_ALGORITHM_HPP |