2 Copyright 2008 Adobe Systems Incorporated
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)
8 January 2008 mtc Version for Adobe Source Library
9 January 2013 mtc Version for Boost.Algorithm
13 /**************************************************************************************************/
20 #ifndef BOOST_ALGORITHM_GATHER_HPP
21 #define BOOST_ALGORITHM_GATHER_HPP
23 #include <algorithm> // for std::stable_partition
26 #include <boost/config.hpp>
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)
32 /**************************************************************************************************/
34 \defgroup gather gather
35 \ingroup mutating_algorithm
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.
42 Given an sequence containing:
47 a call to gather ( arr, arr + 10, arr + 4, IsEven ()) will result in:
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
61 \par Storage Requirements:
63 The algorithm uses stable_partition, which will attempt to allocate temporary memory,
64 but will work in-situ if there is none available.
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>.
72 /**************************************************************************************************/
74 namespace boost { namespace algorithm {
76 /**************************************************************************************************/
80 \brief iterator-based gather implementation
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 )
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 )));
96 /**************************************************************************************************/
100 \brief range-based gather implementation
104 typename BidirectionalRange, //
105 typename Pred> // Pred models UnaryPredicate
107 typename boost::range_iterator<const BidirectionalRange>::type,
108 typename boost::range_iterator<const BidirectionalRange>::type>
110 const BidirectionalRange &range,
111 typename boost::range_iterator<const BidirectionalRange>::type pivot,
114 return boost::algorithm::gather ( boost::begin ( range ), boost::end ( range ), pivot, pred );
117 /**************************************************************************************************/
121 /**************************************************************************************************/