boost/algorithm/gather.hpp

0001 /*
0002     Copyright 2008 Adobe Systems Incorporated
0003
0004    Distributed under the Boost Software License, Version 1.0. (See accompanying
0005    file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0006
0007  Revision history:
0008    January 2008 mtc Version for Adobe Source Library
0009    January 2013 mtc Version for Boost.Algorithm
0010
0011 */
0012
0013 /**************************************************************************************************/
0014
0015 /*!
0016 \author Marshall Clow
0017 \date    January 2008
0018 */
0019
0020 #ifndef BOOST_ALGORITHM_GATHER_HPP
0021 #define BOOST_ALGORITHM_GATHER_HPP
0022
0023 #include <algorithm>                // for std::stable_partition
0024 #include <functional>
0025 #include <utility>                  // for std::make_pair
0026
0027 #include <boost/config.hpp>
0028 #include <boost/bind/bind.hpp>      // for boost::bind
0029 #include <boost/range/begin.hpp>    // for boost::begin(range)
0030 #include <boost/range/end.hpp>      // for boost::end(range)
0031
0032
0033 /**************************************************************************************************/
0034 /*!
0035     \defgroup gather gather
0036     \ingroup mutating_algorithm
0037
0038     \c gather() takes a collection of elements defined by a pair of iterators and moves
0039     the ones satisfying a predicate to them to a position (called the pivot) within
0040     the sequence. The algorithm is stable. The result is a pair of iterators that
0041     contains the items that satisfy the predicate.
0042
0043     Given an sequence containing:
0044     <pre>
0045     0 1 2 3 4 5 6 7 8 9
0046     </pre>
0047
0048     a call to gather ( arr, arr + 10, arr + 4, IsEven ()) will result in:
0049
0050     <pre>
0051     1 3 0 2 4 6 8 5 7 9
0052         |---|-----|
0053       first |  second
0054           pivot
0055     </pre>
0056
0057
0058     The problem is broken down into two basic steps, namely, moving the items before the pivot
0059     and then moving the items from the pivot to the end. These "moves" are done with calls to
0060     stable_partition.
0061
0062     \par Storage Requirements:
0063
0064     The algorithm uses stable_partition, which will attempt to allocate temporary memory,
0065     but will work in-situ if there is none available.
0066
0067     \par Time Complexity:
0068
0069     If there is sufficient memory available, the run time is linear in <code>N</code>.
0070     If there is not any memory available, then the run time is <code>O(N log N)</code>.
0071 */
0072
0073 /**************************************************************************************************/
0074
0075 namespace boost { namespace algorithm {
0076
0077 /**************************************************************************************************/
0078
0079 /*!
0080     \ingroup gather
0081     \brief iterator-based gather implementation
0082 */
0083
0084 template <
0085     typename BidirectionalIterator,  // models BidirectionalIterator
0086     typename Pred>                   // models UnaryPredicate
0087 std::pair<BidirectionalIterator, BidirectionalIterator> gather
0088         ( BidirectionalIterator first, BidirectionalIterator last, BidirectionalIterator pivot, Pred pred )
0089 {
0090 //  The first call partitions everything up to (but not including) the pivot element,
0091 //  while the second call partitions the rest of the sequence.
0092     using namespace boost::placeholders;
0093     return std::make_pair (
0094         std::stable_partition ( first, pivot, !boost::bind<bool> ( pred, _1 )),
0095         std::stable_partition ( pivot, last,   boost::bind<bool> ( pred, _1 )));
0096 }
0097
0098 /**************************************************************************************************/
0099
0100 /*!
0101     \ingroup gather
0102     \brief range-based gather implementation
0103 */
0104
0105 template <
0106     typename BidirectionalRange,    //
0107     typename Pred>                  // Pred models UnaryPredicate
0108 std::pair<
0109     typename boost::range_iterator<BidirectionalRange>::type,
0110     typename boost::range_iterator<BidirectionalRange>::type>
0111 gather (
0112     BidirectionalRange &range,
0113     typename boost::range_iterator<BidirectionalRange>::type pivot,
0114     Pred pred )
0115 {
0116     return boost::algorithm::gather ( boost::begin ( range ), boost::end ( range ), pivot, pred );
0117 }
0118
0119 /**************************************************************************************************/
0120
0121 }}  // namespace
0122
0123 /**************************************************************************************************/
0124
0125 #endif
0126