1/*!
2@file
3Defines several `constexpr` algorithms.
4
5Copyright Louis Dionne 2013-2022
6Distributed 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
21namespace boost { namespace hana { 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} }} // end namespace boost::hana
185
186#endif // !BOOST_HANA_DETAIL_ALGORITHM_HPP
187

source code of boost/libs/hana/include/boost/hana/detail/algorithm.hpp