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 2486 sjacqu01
/*
2 2486 sjacqu01
    Copyright 2008 Adobe Systems Incorporated
3 2486 sjacqu01

4 2486 sjacqu01
   Distributed under the Boost Software License, Version 1.0. (See accompanying
5 2486 sjacqu01
   file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6 2486 sjacqu01

7 2486 sjacqu01
 Revision history:
8 2486 sjacqu01
   January 2008 mtc Version for Adobe Source Library
9 2486 sjacqu01
   January 2013 mtc Version for Boost.Algorithm
10 2486 sjacqu01

11 2486 sjacqu01
*/
12 2486 sjacqu01
13 2486 sjacqu01
/**************************************************************************************************/
14 2486 sjacqu01
15 2486 sjacqu01
/*!
16 2486 sjacqu01
\author Marshall Clow
17 2486 sjacqu01
\date    January 2008
18 2486 sjacqu01
*/
19 2486 sjacqu01
20 2486 sjacqu01
#ifndef BOOST_ALGORITHM_GATHER_HPP
21 2486 sjacqu01
#define BOOST_ALGORITHM_GATHER_HPP
22 2486 sjacqu01
23 2486 sjacqu01
#include <algorithm>                // for std::stable_partition
24 2486 sjacqu01
#include <functional>
25 2486 sjacqu01
26 2486 sjacqu01
#include <boost/bind.hpp>           // for boost::bind
27 2486 sjacqu01
#include <boost/range/begin.hpp>    // for boost::begin(range)
28 2486 sjacqu01
#include <boost/range/end.hpp>      // for boost::end(range)
29 2486 sjacqu01
30 2486 sjacqu01
31 2486 sjacqu01
/**************************************************************************************************/
32 2486 sjacqu01
/*!
33 2486 sjacqu01
    \defgroup gather gather
34 2486 sjacqu01
    \ingroup mutating_algorithm
35 2486 sjacqu01

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

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

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

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

55 2486 sjacqu01

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

60 2486 sjacqu01
    \par Storage Requirements:
61 2486 sjacqu01

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

65 2486 sjacqu01
    \par Time Complexity:
66 2486 sjacqu01

67 2486 sjacqu01
    If there is sufficient memory available, the run time is linear in <code>N</code>.
68 2486 sjacqu01
    If there is not any memory available, then the run time is <code>O(N log N)</code>.
69 2486 sjacqu01
*/
70 2486 sjacqu01
71 2486 sjacqu01
/**************************************************************************************************/
72 2486 sjacqu01
73 2486 sjacqu01
namespace boost { namespace algorithm {
74 2486 sjacqu01
75 2486 sjacqu01
/**************************************************************************************************/
76 2486 sjacqu01
77 2486 sjacqu01
/*!
78 2486 sjacqu01
    \ingroup gather
79 2486 sjacqu01
    \brief iterator-based gather implementation
80 2486 sjacqu01
*/
81 2486 sjacqu01
82 2486 sjacqu01
template <
83 2486 sjacqu01
    typename BidirectionalIterator,  // Iter models BidirectionalIterator
84 2486 sjacqu01
    typename Pred>                   // Pred models UnaryPredicate
85 2486 sjacqu01
std::pair<BidirectionalIterator, BidirectionalIterator> gather
86 2486 sjacqu01
        ( BidirectionalIterator first, BidirectionalIterator last, BidirectionalIterator pivot, Pred pred )
87 2486 sjacqu01
{
88 2486 sjacqu01
//  The first call partitions everything up to (but not including) the pivot element,
89 2486 sjacqu01
//  while the second call partitions the rest of the sequence.
90 2486 sjacqu01
    return std::make_pair (
91 2486 sjacqu01
        std::stable_partition ( first, pivot, !boost::bind<bool> ( pred, _1 )),
92 2486 sjacqu01
        std::stable_partition ( pivot, last,   boost::bind<bool> ( pred, _1 )));
93 2486 sjacqu01
}
94 2486 sjacqu01
95 2486 sjacqu01
/**************************************************************************************************/
96 2486 sjacqu01
97 2486 sjacqu01
/*!
98 2486 sjacqu01
    \ingroup gather
99 2486 sjacqu01
    \brief range-based gather implementation
100 2486 sjacqu01
*/
101 2486 sjacqu01
102 2486 sjacqu01
template <
103 2486 sjacqu01
    typename BidirectionalRange,    //
104 2486 sjacqu01
    typename Pred>                  // Pred models UnaryPredicate
105 2486 sjacqu01
std::pair<
106 2486 sjacqu01
    typename boost::range_iterator<const BidirectionalRange>::type,
107 2486 sjacqu01
    typename boost::range_iterator<const BidirectionalRange>::type>
108 2486 sjacqu01
gather (
109 2486 sjacqu01
    const BidirectionalRange &range,
110 2486 sjacqu01
    typename boost::range_iterator<const BidirectionalRange>::type pivot,
111 2486 sjacqu01
    Pred pred )
112 2486 sjacqu01
{
113 2486 sjacqu01
    return boost::algorithm::gather ( boost::begin ( range ), boost::end ( range ), pivot, pred );
114 2486 sjacqu01
}
115 2486 sjacqu01
116 2486 sjacqu01
/**************************************************************************************************/
117 2486 sjacqu01
118 2486 sjacqu01
}}  // namespace
119 2486 sjacqu01
120 2486 sjacqu01
/**************************************************************************************************/
121 2486 sjacqu01
122 2486 sjacqu01
#endif