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