summaryrefslogtreecommitdiff
path: root/boost/hana/detail/algorithm.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'boost/hana/detail/algorithm.hpp')
-rw-r--r--boost/hana/detail/algorithm.hpp184
1 files changed, 184 insertions, 0 deletions
diff --git a/boost/hana/detail/algorithm.hpp b/boost/hana/detail/algorithm.hpp
new file mode 100644
index 0000000000..d398659e2c
--- /dev/null
+++ b/boost/hana/detail/algorithm.hpp
@@ -0,0 +1,184 @@
+/*!
+@file
+Defines several `constexpr` algorithms.
+
+@copyright Louis Dionne 2013-2016
+Distributed under the Boost Software License, Version 1.0.
+(See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
+ */
+
+#ifndef BOOST_HANA_DETAIL_ALGORITHM_HPP
+#define BOOST_HANA_DETAIL_ALGORITHM_HPP
+
+#include <boost/hana/functional/placeholder.hpp>
+
+#include <boost/hana/config.hpp>
+
+#include <cstddef>
+#include <utility>
+
+
+BOOST_HANA_NAMESPACE_BEGIN namespace detail {
+ template <typename T>
+ constexpr void swap(T& x, T& y) {
+ auto tmp = x;
+ x = y;
+ y = std::move(tmp);
+ }
+
+ template <typename BidirIter>
+ constexpr void reverse(BidirIter first, BidirIter last) {
+ while (first != last) {
+ if (first == --last)
+ break;
+ detail::swap(*first, *last);
+ ++first;
+ }
+ }
+
+ template <typename BidirIter, typename BinaryPred>
+ constexpr bool next_permutation(BidirIter first, BidirIter last,
+ BinaryPred pred)
+ {
+ BidirIter i = last;
+ if (first == last || first == --i)
+ return false;
+ while (true) {
+ BidirIter ip1 = i;
+ if (pred(*--i, *ip1)) {
+ BidirIter j = last;
+ while (!pred(*i, *--j))
+ ;
+ detail::swap(*i, *j);
+ detail::reverse(ip1, last);
+ return true;
+ }
+ if (i == first) {
+ detail::reverse(first, last);
+ return false;
+ }
+ }
+ }
+
+ template <typename BidirIter>
+ constexpr bool next_permutation(BidirIter first, BidirIter last)
+ { return detail::next_permutation(first, last, hana::_ < hana::_); }
+
+
+ template <typename InputIter1, typename InputIter2, typename BinaryPred>
+ constexpr bool lexicographical_compare(InputIter1 first1, InputIter1 last1,
+ InputIter2 first2, InputIter2 last2,
+ BinaryPred pred)
+ {
+ for (; first2 != last2; ++first1, ++first2) {
+ if (first1 == last1 || pred(*first1, *first2))
+ return true;
+ else if (pred(*first2, *first1))
+ return false;
+ }
+ return false;
+ }
+
+ template <typename InputIter1, typename InputIter2>
+ constexpr bool lexicographical_compare(InputIter1 first1, InputIter1 last1,
+ InputIter2 first2, InputIter2 last2)
+ { return detail::lexicographical_compare(first1, last1, first2, last2, hana::_ < hana::_); }
+
+
+ template <typename InputIter1, typename InputIter2, typename BinaryPred>
+ constexpr bool equal(InputIter1 first1, InputIter1 last1,
+ InputIter2 first2, InputIter2 last2,
+ BinaryPred pred)
+ {
+ for (; first1 != last1 && first2 != last2; ++first1, ++first2)
+ if (!pred(*first1, *first2))
+ return false;
+ return first1 == last1 && first2 == last2;
+ }
+
+ template <typename InputIter1, typename InputIter2>
+ constexpr bool equal(InputIter1 first1, InputIter1 last1,
+ InputIter2 first2, InputIter2 last2)
+ { return detail::equal(first1, last1, first2, last2, hana::_ == hana::_); }
+
+
+ template <typename BidirIter, typename BinaryPred>
+ constexpr void sort(BidirIter first, BidirIter last, BinaryPred pred) {
+ if (first == last) return;
+
+ BidirIter i = first;
+ for (++i; i != last; ++i) {
+ BidirIter j = i;
+ auto t = *j;
+ for (BidirIter k = i; k != first && pred(t, *--k); --j)
+ *j = *k;
+ *j = t;
+ }
+ }
+
+ template <typename BidirIter>
+ constexpr void sort(BidirIter first, BidirIter last)
+ { detail::sort(first, last, hana::_ < hana::_); }
+
+
+ template <typename InputIter, typename T>
+ constexpr InputIter find(InputIter first, InputIter last, T const& value) {
+ for (; first != last; ++first)
+ if (*first == value)
+ return first;
+ return last;
+ }
+
+ template <typename InputIter, typename UnaryPred>
+ constexpr InputIter find_if(InputIter first, InputIter last, UnaryPred pred) {
+ for (; first != last; ++first)
+ if (pred(*first))
+ return first;
+ return last;
+ }
+
+ template <typename ForwardIter, typename T>
+ constexpr void iota(ForwardIter first, ForwardIter last, T value) {
+ while (first != last) {
+ *first++ = value;
+ ++value;
+ }
+ }
+
+ template <typename InputIt, typename T>
+ constexpr std::size_t
+ count(InputIt first, InputIt last, T const& value) {
+ std::size_t n = 0;
+ for (; first != last; ++first)
+ if (*first == value)
+ ++n;
+ return n;
+ }
+
+ template <typename InputIt, typename T, typename F>
+ constexpr T accumulate(InputIt first, InputIt last, T init, F f) {
+ for (; first != last; ++first)
+ init = f(init, *first);
+ return init;
+ }
+
+ template <typename InputIt, typename T>
+ constexpr T accumulate(InputIt first, InputIt last, T init) {
+ return detail::accumulate(first, last, init, hana::_ + hana::_);
+ }
+
+ template <typename ForwardIt>
+ constexpr ForwardIt min_element(ForwardIt first, ForwardIt last) {
+ if (first == last)
+ return last;
+
+ ForwardIt smallest = first;
+ ++first;
+ for (; first != last; ++first)
+ if (*first < *smallest)
+ smallest = first;
+ return smallest;
+ }
+} BOOST_HANA_NAMESPACE_END
+
+#endif // !BOOST_HANA_DETAIL_ALGORITHM_HPP