boost/algorithm/gather.hpp

   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/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)
  30
  31
  32 /**************************************************************************************************/
  33 /*!
  34     \defgroup gather gather
  35     \ingroup mutating_algorithm
  36
  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.
  41
  42     Given an sequence containing:
  43     <pre>
  44     0 1 2 3 4 5 6 7 8 9
  45     </pre>
  46
  47     a call to gather ( arr, arr + 10, arr + 4, IsEven ()) will result in:
  48
  49     <pre>
  50     1 3 0 2 4 6 8 5 7 9
  51         |---|-----|
  52       first |  second
  53           pivot
  54     </pre>
  55
  56
  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
  59     stable_partition.
  60
  61     \par Storage Requirements:
  62
  63     The algorithm uses stable_partition, which will attempt to allocate temporary memory,
  64     but will work in-situ if there is none available.
  65
  66     \par Time Complexity:
  67
  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>.
  70 */
  71
  72 /**************************************************************************************************/
  73
  74 namespace boost { namespace algorithm {
  75
  76 /**************************************************************************************************/
  77
  78 /*!
  79     \ingroup gather
  80     \brief iterator-based gather implementation
  81 */
  82
  83 template <
  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 )
  88 {
  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 )));
  94 }
  95
  96 /**************************************************************************************************/
  97
  98 /*!
  99     \ingroup gather
 100     \brief range-based gather implementation
 101 */
 102
 103 template <
 104     typename BidirectionalRange,    //
 105     typename Pred>                  // Pred models UnaryPredicate
 106 std::pair<
 107     typename boost::range_iterator<const BidirectionalRange>::type,
 108     typename boost::range_iterator<const BidirectionalRange>::type>
 109 gather (
 110     const BidirectionalRange &range,
 111     typename boost::range_iterator<const BidirectionalRange>::type pivot,
 112     Pred pred )
 113 {
 114     return boost::algorithm::gather ( boost::begin ( range ), boost::end ( range ), pivot, pred );
 115 }
 116
 117 /**************************************************************************************************/
 118
 119 }}  // namespace
 120
 121 /**************************************************************************************************/
 122
 123 #endif
 124