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/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)
31 /**************************************************************************************************/
33 \defgroup gather gather
34 \ingroup mutating_algorithm
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.
41 Given an sequence containing:
46 a call to gather ( arr, arr + 10, arr + 4, IsEven ()) will result in:
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
60 \par Storage Requirements:
62 The algorithm uses stable_partition, which will attempt to allocate temporary memory,
63 but will work in-situ if there is none available.
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>.
71 /**************************************************************************************************/
73 namespace boost { namespace algorithm {
75 /**************************************************************************************************/
79 \brief iterator-based gather implementation
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 )
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 )));
95 /**************************************************************************************************/
99 \brief range-based gather implementation
103 typename BidirectionalRange, //
104 typename Pred> // Pred models UnaryPredicate
106 typename boost::range_iterator<const BidirectionalRange>::type,
107 typename boost::range_iterator<const BidirectionalRange>::type>
109 const BidirectionalRange &range,
110 typename boost::range_iterator<const BidirectionalRange>::type pivot,
113 return boost::algorithm::gather ( boost::begin ( range ), boost::end ( range ), pivot, pred );
116 /**************************************************************************************************/
120 /**************************************************************************************************/