1/*
2 Copyright (c) Marshall Clow 2011-2012.
3
4 Distributed under the Boost Software License, Version 1.0. (See accompanying
5 file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6*/
7
8/// \file partition_point.hpp
9/// \brief Find the partition point in a sequence
10/// \author Marshall Clow
11
12#ifndef BOOST_ALGORITHM_PARTITION_POINT_HPP
13#define BOOST_ALGORITHM_PARTITION_POINT_HPP
14
15#include <algorithm> // for std::partition_point, if available
16
17#include <boost/range/begin.hpp>
18#include <boost/range/end.hpp>
19
20namespace boost { namespace algorithm {
21
22/// \fn partition_point ( ForwardIterator first, ForwardIterator last, Predicate p )
23/// \brief Given a partitioned range, returns the partition point, i.e, the first element
24/// that does not satisfy p
25///
26/// \param first The start of the input sequence
27/// \param last One past the end of the input sequence
28/// \param p The predicate to test the values with
29/// \note This function is part of the C++2011 standard library.
30/// We will use the standard one if it is available,
31/// otherwise we have our own implementation.
32template <typename ForwardIterator, typename Predicate>
33ForwardIterator partition_point ( ForwardIterator first, ForwardIterator last, Predicate p )
34{
35 std::size_t dist = std::distance ( first, last );
36 while ( first != last ) {
37 std::size_t d2 = dist / 2;
38 ForwardIterator ret_val = first;
39 std::advance (ret_val, d2);
40 if (p (*ret_val)) {
41 first = ++ret_val;
42 dist -= d2 + 1;
43 }
44 else {
45 last = ret_val;
46 dist = d2;
47 }
48 }
49 return first;
50}
51
52/// \fn partition_point ( Range &r, Predicate p )
53/// \brief Given a partitioned range, returns the partition point
54///
55/// \param r The input range
56/// \param p The predicate to test the values with
57///
58template <typename Range, typename Predicate>
59typename boost::range_iterator<Range>::type partition_point ( Range &r, Predicate p )
60{
61 return boost::algorithm::partition_point (boost::begin(r), boost::end(r), p);
62}
63
64
65}}
66
67#endif // BOOST_ALGORITHM_PARTITION_POINT_HPP
68