3 Defines several `constexpr` algorithms.
5 @copyright Louis Dionne 2013-2017
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)
10 #ifndef BOOST_HANA_DETAIL_ALGORITHM_HPP
11 #define BOOST_HANA_DETAIL_ALGORITHM_HPP
13 #include <boost/hana/functional/placeholder.hpp>
15 #include <boost/hana/config.hpp>
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).
25 constexpr void constexpr_swap(T& x, T& y) {
31 template <typename BidirIter>
32 constexpr void reverse(BidirIter first, BidirIter last) {
33 while (first != last) {
36 detail::constexpr_swap(*first, *last);
41 template <typename BidirIter, typename BinaryPred>
42 constexpr bool next_permutation(BidirIter first, BidirIter last,
46 if (first == last || first == --i)
50 if (pred(*--i, *ip1)) {
52 while (!pred(*i, *--j))
54 detail::constexpr_swap(*i, *j);
55 detail::reverse(ip1, last);
59 detail::reverse(first, last);
65 template <typename BidirIter>
66 constexpr bool next_permutation(BidirIter first, BidirIter last)
67 { return detail::next_permutation(first, last, hana::_ < hana::_); }
70 template <typename InputIter1, typename InputIter2, typename BinaryPred>
71 constexpr bool lexicographical_compare(InputIter1 first1, InputIter1 last1,
72 InputIter2 first2, InputIter2 last2,
75 for (; first2 != last2; ++first1, ++first2) {
76 if (first1 == last1 || pred(*first1, *first2))
78 else if (pred(*first2, *first1))
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::_); }
90 template <typename InputIter1, typename InputIter2, typename BinaryPred>
91 constexpr bool equal(InputIter1 first1, InputIter1 last1,
92 InputIter2 first2, InputIter2 last2,
95 for (; first1 != last1 && first2 != last2; ++first1, ++first2)
96 if (!pred(*first1, *first2))
98 return first1 == last1 && first2 == last2;
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::_); }
107 template <typename BidirIter, typename BinaryPred>
108 constexpr void sort(BidirIter first, BidirIter last, BinaryPred pred) {
109 if (first == last) return;
112 for (++i; i != last; ++i) {
115 for (BidirIter k = i; k != first && pred(t, *--k); --j)
121 template <typename BidirIter>
122 constexpr void sort(BidirIter first, BidirIter last)
123 { detail::sort(first, last, hana::_ < hana::_); }
126 template <typename InputIter, typename T>
127 constexpr InputIter find(InputIter first, InputIter last, T const& value) {
128 for (; first != last; ++first)
134 template <typename InputIter, typename UnaryPred>
135 constexpr InputIter find_if(InputIter first, InputIter last, UnaryPred pred) {
136 for (; first != last; ++first)
142 template <typename ForwardIter, typename T>
143 constexpr void iota(ForwardIter first, ForwardIter last, T value) {
144 while (first != last) {
150 template <typename InputIt, typename T>
151 constexpr std::size_t
152 count(InputIt first, InputIt last, T const& value) {
154 for (; first != last; ++first)
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);
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::_);
172 template <typename ForwardIt>
173 constexpr ForwardIt min_element(ForwardIt first, ForwardIt last) {
177 ForwardIt smallest = first;
179 for (; first != last; ++first)
180 if (*first < *smallest)
184 } BOOST_HANA_NAMESPACE_END
186 #endif // !BOOST_HANA_DETAIL_ALGORITHM_HPP