1 /*! 2 @file 3 Defines several `constexpr` algorithms. 4 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) 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> constexpr_swap(T & x,T & y)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> reverse(BidirIter first,BidirIter last)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> next_permutation(BidirIter first,BidirIter last,BinaryPred pred)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> next_permutation(BidirIter first,BidirIter last)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> lexicographical_compare(InputIter1 first1,InputIter1 last1,InputIter2 first2,InputIter2 last2,BinaryPred pred)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> lexicographical_compare(InputIter1 first1,InputIter1 last1,InputIter2 first2,InputIter2 last2)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> equal(InputIter1 first1,InputIter1 last1,InputIter2 first2,InputIter2 last2,BinaryPred pred)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> equal(InputIter1 first1,InputIter1 last1,InputIter2 first2,InputIter2 last2)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> sort(BidirIter first,BidirIter last,BinaryPred pred)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> sort(BidirIter first,BidirIter last)122 constexpr void sort(BidirIter first, BidirIter last) 123 { detail::sort(first, last, hana::_ < hana::_); } 124 125 126 template <typename InputIter, typename T> find(InputIter first,InputIter last,T const & value)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> find_if(InputIter first,InputIter last,UnaryPred pred)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> iota(ForwardIter first,ForwardIter last,T value)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 count(InputIt first,InputIt last,T const & value)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> accumulate(InputIt first,InputIt last,T init,F 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> accumulate(InputIt first,InputIt last,T init)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> min_element(ForwardIt first,ForwardIt last)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 187