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 <iterator> // for std::distance, advance
16
17#include <boost/config.hpp>
18#include <boost/range/begin.hpp>
19#include <boost/range/end.hpp>
20
21namespace boost { namespace algorithm {
22
23/// \fn partition_point ( ForwardIterator first, ForwardIterator last, Predicate p )
24/// \brief Given a partitioned range, returns the partition point, i.e, the first element
25/// that does not satisfy p
26///
27/// \param first The start of the input sequence
28/// \param last One past the end of the input sequence
29/// \param p The predicate to test the values with
30/// \note This function is part of the C++2011 standard library.
31template <typename ForwardIterator, typename Predicate>
32ForwardIterator partition_point ( ForwardIterator first, ForwardIterator last, Predicate p )
33{
34 std::size_t dist = std::distance ( first, last );
35 while ( first != last ) {
36 std::size_t d2 = dist / 2;
37 ForwardIterator ret_val = first;
38 std::advance (ret_val, d2);
39 if (p (*ret_val)) {
40 first = ++ret_val;
41 dist -= d2 + 1;
42 }
43 else {
44 last = ret_val;
45 dist = d2;
46 }
47 }
48 return first;
49}
50
51/// \fn partition_point ( Range &r, Predicate p )
52/// \brief Given a partitioned range, returns the partition point
53///
54/// \param r The input range
55/// \param p The predicate to test the values with
56///
57template <typename Range, typename Predicate>
58typename boost::range_iterator<Range>::type partition_point ( Range &r, Predicate p )
59{
60 return boost::algorithm::partition_point (boost::begin(r), boost::end(r), p);
61}
62
63
64}}
65
66#endif // BOOST_ALGORITHM_PARTITION_POINT_HPP
67

source code of boost/libs/algorithm/include/boost/algorithm/cxx11/partition_point.hpp