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