Statistics
| Revision:

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

History | View | Annotate | Download (4 kB)

1
/* 
2
    Copyright 2008 Adobe Systems Incorporated
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
 Revision history:
8
   January 2008 mtc Version for Adobe Source Library
9
   January 2013 mtc Version for Boost.Algorithm
10

11
*/
12

    
13
/**************************************************************************************************/
14

    
15
/*!
16
\author Marshall Clow
17
\date    January 2008
18
*/
19

    
20
#ifndef BOOST_ALGORITHM_GATHER_HPP
21
#define BOOST_ALGORITHM_GATHER_HPP
22

    
23
#include <algorithm>                // for std::stable_partition
24
#include <functional>
25

    
26
#include <boost/bind.hpp>           // for boost::bind
27
#include <boost/range/begin.hpp>    // for boost::begin(range)
28
#include <boost/range/end.hpp>      // for boost::end(range)
29

    
30

    
31
/**************************************************************************************************/
32
/*!
33
    \defgroup gather gather
34
    \ingroup mutating_algorithm
35

36
    \c gather() takes a collection of elements defined by a pair of iterators and moves
37
    the ones satisfying a predicate to them to a position (called the pivot) within
38
    the sequence. The algorithm is stable. The result is a pair of iterators that
39
    contains the items that satisfy the predicate.
40

41
    Given an sequence containing:
42
    <pre>
43
    0 1 2 3 4 5 6 7 8 9
44
    </pre>
45

46
    a call to gather ( arr, arr + 10, arr + 4, IsEven ()) will result in:
47

48
    <pre>
49
    1 3 0 2 4 6 8 5 7 9
50
        |---|-----|
51
      first |  second
52
          pivot
53
    </pre>
54

55

56
    The problem is broken down into two basic steps, namely, moving the items before the pivot
57
    and then moving the items from the pivot to the end. These "moves" are done with calls to
58
    stable_partition.
59

60
    \par Storage Requirements:
61

62
    The algorithm uses stable_partition, which will attempt to allocate temporary memory,
63
    but will work in-situ if there is none available.
64

65
    \par Time Complexity:
66

67
    If there is sufficient memory available, the run time is linear in <code>N</code>.
68
    If there is not any memory available, then the run time is <code>O(N log N)</code>.
69
*/
70

    
71
/**************************************************************************************************/
72

    
73
namespace boost { namespace algorithm {
74

    
75
/**************************************************************************************************/
76

    
77
/*!
78
    \ingroup gather
79
    \brief iterator-based gather implementation
80
*/
81

    
82
template <
83
    typename BidirectionalIterator,  // Iter models BidirectionalIterator
84
    typename Pred>                   // Pred models UnaryPredicate
85
std::pair<BidirectionalIterator, BidirectionalIterator> gather 
86
        ( BidirectionalIterator first, BidirectionalIterator last, BidirectionalIterator pivot, Pred pred )
87
{
88
//  The first call partitions everything up to (but not including) the pivot element,
89
//  while the second call partitions the rest of the sequence.
90
    return std::make_pair (
91
        std::stable_partition ( first, pivot, !boost::bind<bool> ( pred, _1 )),
92
        std::stable_partition ( pivot, last,   boost::bind<bool> ( pred, _1 )));
93
}
94

    
95
/**************************************************************************************************/
96

    
97
/*!
98
    \ingroup gather
99
    \brief range-based gather implementation
100
*/
101

    
102
template <
103
    typename BidirectionalRange,    //
104
    typename Pred>                  // Pred models UnaryPredicate
105
std::pair<
106
    typename boost::range_iterator<const BidirectionalRange>::type,
107
    typename boost::range_iterator<const BidirectionalRange>::type>
108
gather (
109
    const BidirectionalRange &range,
110
    typename boost::range_iterator<const BidirectionalRange>::type pivot,
111
    Pred pred )
112
{
113
    return boost::algorithm::gather ( boost::begin ( range ), boost::end ( range ), pivot, pred );
114
}
115

    
116
/**************************************************************************************************/
117

    
118
}}  // namespace
119

    
120
/**************************************************************************************************/
121

    
122
#endif
123