Chris@16: /* 
Chris@16:     Copyright 2008 Adobe Systems Incorporated
Chris@16: 
Chris@16:    Distributed under the Boost Software License, Version 1.0. (See accompanying
Chris@16:    file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16:  Revision history:
Chris@16:    January 2008 mtc Version for Adobe Source Library
Chris@16:    January 2013 mtc Version for Boost.Algorithm
Chris@16: 
Chris@16: */
Chris@16: 
Chris@16: /**************************************************************************************************/
Chris@16: 
Chris@16: /*!
Chris@16: \author Marshall Clow
Chris@16: \date    January 2008
Chris@16: */
Chris@16: 
Chris@16: #ifndef BOOST_ALGORITHM_GATHER_HPP
Chris@16: #define BOOST_ALGORITHM_GATHER_HPP
Chris@16: 
Chris@16: #include <algorithm>                // for std::stable_partition
Chris@16: #include <functional>
Chris@16: 
Chris@16: #include <boost/bind.hpp>           // for boost::bind
Chris@16: #include <boost/range/begin.hpp>    // for boost::begin(range)
Chris@16: #include <boost/range/end.hpp>      // for boost::end(range)
Chris@16: 
Chris@16: 
Chris@16: /**************************************************************************************************/
Chris@16: /*!
Chris@16:     \defgroup gather gather
Chris@16:     \ingroup mutating_algorithm
Chris@16: 
Chris@16:     \c gather() takes a collection of elements defined by a pair of iterators and moves
Chris@16:     the ones satisfying a predicate to them to a position (called the pivot) within
Chris@16:     the sequence. The algorithm is stable. The result is a pair of iterators that
Chris@16:     contains the items that satisfy the predicate.
Chris@16: 
Chris@16:     Given an sequence containing:
Chris@16:     <pre>
Chris@16:     0 1 2 3 4 5 6 7 8 9
Chris@16:     </pre>
Chris@16: 
Chris@16:     a call to gather ( arr, arr + 10, arr + 4, IsEven ()) will result in:
Chris@16: 
Chris@16:     <pre>
Chris@16:     1 3 0 2 4 6 8 5 7 9
Chris@16:         |---|-----|
Chris@16:       first |  second
Chris@16:           pivot
Chris@16:     </pre>
Chris@16: 
Chris@16: 
Chris@16:     The problem is broken down into two basic steps, namely, moving the items before the pivot
Chris@16:     and then moving the items from the pivot to the end. These "moves" are done with calls to
Chris@16:     stable_partition.
Chris@16: 
Chris@16:     \par Storage Requirements:
Chris@16: 
Chris@16:     The algorithm uses stable_partition, which will attempt to allocate temporary memory,
Chris@16:     but will work in-situ if there is none available.
Chris@16: 
Chris@16:     \par Time Complexity:
Chris@16: 
Chris@16:     If there is sufficient memory available, the run time is linear in <code>N</code>.
Chris@16:     If there is not any memory available, then the run time is <code>O(N log N)</code>.
Chris@16: */
Chris@16: 
Chris@16: /**************************************************************************************************/
Chris@16: 
Chris@16: namespace boost { namespace algorithm {
Chris@16: 
Chris@16: /**************************************************************************************************/
Chris@16: 
Chris@16: /*!
Chris@16:     \ingroup gather
Chris@16:     \brief iterator-based gather implementation
Chris@16: */
Chris@16: 
Chris@16: template <
Chris@16:     typename BidirectionalIterator,  // Iter models BidirectionalIterator
Chris@16:     typename Pred>                   // Pred models UnaryPredicate
Chris@16: std::pair<BidirectionalIterator, BidirectionalIterator> gather 
Chris@16:         ( BidirectionalIterator first, BidirectionalIterator last, BidirectionalIterator pivot, Pred pred )
Chris@16: {
Chris@16: //  The first call partitions everything up to (but not including) the pivot element,
Chris@16: //  while the second call partitions the rest of the sequence.
Chris@16:     return std::make_pair (
Chris@16:         std::stable_partition ( first, pivot, !boost::bind<bool> ( pred, _1 )),
Chris@16:         std::stable_partition ( pivot, last,   boost::bind<bool> ( pred, _1 )));
Chris@16: }
Chris@16: 
Chris@16: /**************************************************************************************************/
Chris@16: 
Chris@16: /*!
Chris@16:     \ingroup gather
Chris@16:     \brief range-based gather implementation
Chris@16: */
Chris@16: 
Chris@16: template <
Chris@16:     typename BidirectionalRange,    //
Chris@16:     typename Pred>                  // Pred models UnaryPredicate
Chris@16: std::pair<
Chris@16:     typename boost::range_iterator<const BidirectionalRange>::type,
Chris@16:     typename boost::range_iterator<const BidirectionalRange>::type>
Chris@16: gather (
Chris@16:     const BidirectionalRange &range,
Chris@16:     typename boost::range_iterator<const BidirectionalRange>::type pivot,
Chris@16:     Pred pred )
Chris@16: {
Chris@16:     return boost::algorithm::gather ( boost::begin ( range ), boost::end ( range ), pivot, pred );
Chris@16: }
Chris@16: 
Chris@16: /**************************************************************************************************/
Chris@16: 
Chris@16: }}  // namespace
Chris@16: 
Chris@16: /**************************************************************************************************/
Chris@16: 
Chris@16: #endif
Chris@16: