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

source code of boost/libs/algorithm/include/boost/algorithm/gather.hpp