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
73namespace boost { namespace algorithm {
74
75/**************************************************************************************************/
76
77/*!
78 \ingroup gather
79 \brief iterator-based gather implementation
80*/
81
82template <
83 typename BidirectionalIterator, // Iter models BidirectionalIterator
84 typename Pred> // Pred models UnaryPredicate
85std::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
102template <
103 typename BidirectionalRange, //
104 typename Pred> // Pred models UnaryPredicate
105std::pair<
106 typename boost::range_iterator<const BidirectionalRange>::type,
107 typename boost::range_iterator<const BidirectionalRange>::type>
108gather (
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