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
20 namespace 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.
32 template <typename ForwardIterator, typename Predicate>
33 ForwardIterator 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 ///
58 template <typename Range, typename Predicate>
partition_point(Range & r,Predicate p)59 typename 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