]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | ||
92f5a8d4 | 26 | #include <boost/config.hpp> |
7c673cae FG |
27 | #include <boost/bind.hpp> // for boost::bind |
28 | #include <boost/range/begin.hpp> // for boost::begin(range) | |
29 | #include <boost/range/end.hpp> // for boost::end(range) | |
30 | ||
31 | ||
32 | /**************************************************************************************************/ | |
33 | /*! | |
34 | \defgroup gather gather | |
35 | \ingroup mutating_algorithm | |
36 | ||
37 | \c gather() takes a collection of elements defined by a pair of iterators and moves | |
38 | the ones satisfying a predicate to them to a position (called the pivot) within | |
39 | the sequence. The algorithm is stable. The result is a pair of iterators that | |
40 | contains the items that satisfy the predicate. | |
41 | ||
42 | Given an sequence containing: | |
43 | <pre> | |
44 | 0 1 2 3 4 5 6 7 8 9 | |
45 | </pre> | |
46 | ||
47 | a call to gather ( arr, arr + 10, arr + 4, IsEven ()) will result in: | |
48 | ||
49 | <pre> | |
50 | 1 3 0 2 4 6 8 5 7 9 | |
51 | |---|-----| | |
52 | first | second | |
53 | pivot | |
54 | </pre> | |
55 | ||
56 | ||
57 | The problem is broken down into two basic steps, namely, moving the items before the pivot | |
58 | and then moving the items from the pivot to the end. These "moves" are done with calls to | |
59 | stable_partition. | |
60 | ||
61 | \par Storage Requirements: | |
62 | ||
63 | The algorithm uses stable_partition, which will attempt to allocate temporary memory, | |
64 | but will work in-situ if there is none available. | |
65 | ||
66 | \par Time Complexity: | |
67 | ||
68 | If there is sufficient memory available, the run time is linear in <code>N</code>. | |
69 | If there is not any memory available, then the run time is <code>O(N log N)</code>. | |
70 | */ | |
71 | ||
72 | /**************************************************************************************************/ | |
73 | ||
74 | namespace boost { namespace algorithm { | |
75 | ||
76 | /**************************************************************************************************/ | |
77 | ||
78 | /*! | |
79 | \ingroup gather | |
80 | \brief iterator-based gather implementation | |
81 | */ | |
82 | ||
83 | template < | |
84 | typename BidirectionalIterator, // Iter models BidirectionalIterator | |
85 | typename Pred> // Pred models UnaryPredicate | |
86 | std::pair<BidirectionalIterator, BidirectionalIterator> gather | |
87 | ( BidirectionalIterator first, BidirectionalIterator last, BidirectionalIterator pivot, Pred pred ) | |
88 | { | |
89 | // The first call partitions everything up to (but not including) the pivot element, | |
90 | // while the second call partitions the rest of the sequence. | |
91 | return std::make_pair ( | |
92 | std::stable_partition ( first, pivot, !boost::bind<bool> ( pred, _1 )), | |
93 | std::stable_partition ( pivot, last, boost::bind<bool> ( pred, _1 ))); | |
94 | } | |
95 | ||
96 | /**************************************************************************************************/ | |
97 | ||
98 | /*! | |
99 | \ingroup gather | |
100 | \brief range-based gather implementation | |
101 | */ | |
102 | ||
103 | template < | |
104 | typename BidirectionalRange, // | |
105 | typename Pred> // Pred models UnaryPredicate | |
106 | std::pair< | |
107 | typename boost::range_iterator<const BidirectionalRange>::type, | |
108 | typename boost::range_iterator<const BidirectionalRange>::type> | |
109 | gather ( | |
110 | const BidirectionalRange &range, | |
111 | typename boost::range_iterator<const BidirectionalRange>::type pivot, | |
112 | Pred pred ) | |
113 | { | |
114 | return boost::algorithm::gather ( boost::begin ( range ), boost::end ( range ), pivot, pred ); | |
115 | } | |
116 | ||
117 | /**************************************************************************************************/ | |
118 | ||
119 | }} // namespace | |
120 | ||
121 | /**************************************************************************************************/ | |
122 | ||
123 | #endif | |
124 |