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