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