Statistics
| Revision:

root / tmp / org.txm.statsengine.r.core.win32 / res / win32 / library / BH / include / boost / algorithm / cxx11 / partition_point.hpp @ 2486

History | View | Annotate | Download (2.1 kB)

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>
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