Subject: [Boost-commit] svn:boost r77060 - in trunk: boost/algorithm/cxx11 libs/algorithm/test
From: marshall_at_[hidden]
Date: 2012-02-18 02:17:42
Author: marshall
Date: 2012-02-18 02:17:39 EST (Sat, 18 Feb 2012)
New Revision: 77060
URL: http://svn.boost.org/trac/boost/changeset/77060
Log:
Added c++11 algorithms to Boost.Algorithm
Added:
trunk/boost/algorithm/cxx11/
trunk/boost/algorithm/cxx11/all_of.hpp (contents, props changed)
trunk/boost/algorithm/cxx11/any_of.hpp (contents, props changed)
trunk/boost/algorithm/cxx11/copy_if.hpp (contents, props changed)
trunk/boost/algorithm/cxx11/copy_n.hpp (contents, props changed)
trunk/boost/algorithm/cxx11/find_if_not.hpp (contents, props changed)
trunk/boost/algorithm/cxx11/iota.hpp (contents, props changed)
trunk/boost/algorithm/cxx11/is_partitioned.hpp (contents, props changed)
trunk/boost/algorithm/cxx11/is_permutation.hpp (contents, props changed)
trunk/boost/algorithm/cxx11/none_of.hpp (contents, props changed)
trunk/boost/algorithm/cxx11/one_of.hpp (contents, props changed)
trunk/boost/algorithm/cxx11/ordered.hpp (contents, props changed)
trunk/boost/algorithm/cxx11/partition_copy.hpp (contents, props changed)
trunk/boost/algorithm/cxx11/partition_point.hpp (contents, props changed)
trunk/libs/algorithm/test/all_of_test.cpp (contents, props changed)
trunk/libs/algorithm/test/any_of_test.cpp (contents, props changed)
trunk/libs/algorithm/test/copy_n_test1.cpp (contents, props changed)
trunk/libs/algorithm/test/find_if_not_test1.cpp (contents, props changed)
trunk/libs/algorithm/test/iota_test1.cpp (contents, props changed)
trunk/libs/algorithm/test/is_partitioned_test1.cpp (contents, props changed)
trunk/libs/algorithm/test/is_permutation_test1.cpp (contents, props changed)
trunk/libs/algorithm/test/none_of_test.cpp (contents, props changed)
trunk/libs/algorithm/test/one_of_test.cpp (contents, props changed)
trunk/libs/algorithm/test/ordered_test.cpp (contents, props changed)
trunk/libs/algorithm/test/partition_copy_test1.cpp (contents, props changed)
trunk/libs/algorithm/test/partition_point_test1.cpp (contents, props changed)
Text files modified:
trunk/libs/algorithm/test/Jamfile.v2 | 17 +++++++++++++++++
1 files changed, 17 insertions(+), 0 deletions(-)
Added: trunk/boost/algorithm/cxx11/all_of.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/algorithm/cxx11/all_of.hpp 2012-02-18 02:17:39 EST (Sat, 18 Feb 2012)
@@ -0,0 +1,90 @@
+/*
+ Copyright (c) Marshall Clow 2008-2012.
+
+ 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)
+*/
+
+/// \file all_of.hpp
+/// \brief Test ranges to see if all elements match a value or predicate.
+/// \author Marshall Clow
+
+#ifndef BOOST_ALGORITHM_ALL_OF_HPP
+#define BOOST_ALGORITHM_ALL_OF_HPP
+
+#include <boost/range/begin.hpp>
+#include <boost/range/end.hpp>
+
+namespace boost { namespace algorithm {
+
+#if __cplusplus >= 201103L
+// Use the C++11 versions of all_of if it is available
+using std::all_of; // Section 25.2.1
+#else
+/// \fn all_of ( InputIterator first, InputIterator last, Predicate p )
+/// \return true if all elements in [first, last) satisfy the predicate 'p'
+/// \note returns true on an empty range
+///
+/// \param first The start of the input sequence
+/// \param last One past the end of the input sequence
+/// \param p A predicate for testing the elements of the sequence
+///
+/// \note This function is part of the C++2011 standard library.
+/// We will use the standard one if it is available,
+/// otherwise we have our own implementation.
+template<typename InputIterator, typename Predicate>
+bool all_of ( InputIterator first, InputIterator last, Predicate p )
+{
+ for ( ; first != last; ++first )
+ if ( !p(*first))
+ return false;
+ return true;
+}
+#endif
+
+/// \fn all_of ( const Range &r, Predicate p )
+/// \return true if all elements in the range satisfy the predicate 'p'
+/// \note returns true on an empty range
+///
+/// \param r The input range
+/// \param p A predicate for testing the elements of the range
+///
+template<typename Range, typename Predicate>
+bool all_of ( const Range &r, Predicate p )
+{
+ return boost::algorithm::all_of ( boost::begin (r), boost::end (r), p );
+}
+
+/// \fn all_of_equal ( InputIterator first, InputIterator last, const T &val )
+/// \return true if all elements in [first, last) are equal to 'val'
+/// \note returns true on an empty range
+///
+/// \param first The start of the input sequence
+/// \param last One past the end of the input sequence
+/// \param val A value to compare against
+///
+template<typename InputIterator, typename T>
+bool all_of_equal ( InputIterator first, InputIterator last, const T &val )
+{
+ for ( ; first != last; ++first )
+ if ( val != *first )
+ return false;
+ return true;
+}
+
+/// \fn all_of_equal ( const Range &r, const T &val )
+/// \return true if all elements in the range are equal to 'val'
+/// \note returns true on an empty range
+///
+/// \param r The input range
+/// \param val A value to compare against
+///
+template<typename Range, typename T>
+bool all_of_equal ( const Range &r, const T &val )
+{
+ return boost::algorithm::all_of_equal ( boost::begin (r), boost::end (r), val );
+}
+
+}} // namespace boost and algorithm
+
+#endif // BOOST_ALGORITHM_ALL_OF_HPP
Added: trunk/boost/algorithm/cxx11/any_of.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/algorithm/cxx11/any_of.hpp 2012-02-18 02:17:39 EST (Sat, 18 Feb 2012)
@@ -0,0 +1,89 @@
+/*
+ Copyright (c) Marshall Clow 2008-2012.
+
+ 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)
+
+ For more information, see http://www.boost.org
+*/
+
+/// \file
+/// \brief Test ranges to see if any elements match a value or predicate.
+/// \author Marshall Clow
+
+#ifndef BOOST_ALGORITHM_ANY_OF_HPP
+#define BOOST_ALGORITHM_ANY_OF_HPP
+
+#include <boost/range/begin.hpp>
+#include <boost/range/end.hpp>
+
+namespace boost { namespace algorithm {
+
+// Use the C++11 versions of any_of if it is available
+#if __cplusplus >= 201103L
+using std::any_of; // Section 25.2.2
+#else
+/// \fn any_of ( InputIterator first, InputIterator last, Predicate p )
+/// \return true if any of the elements in [first, last) satisfy the predicate
+/// \note returns false on an empty range
+///
+/// \param first The start of the input sequence
+/// \param last One past the end of the input sequence
+/// \param p A predicate for testing the elements of the sequence
+///
+template<typename InputIterator, typename Predicate>
+bool any_of ( InputIterator first, InputIterator last, Predicate p )
+{
+ for ( ; first != last; ++first )
+ if ( p(*first))
+ return true;
+ return false;
+}
+#endif
+
+/// \fn any_of ( const Range &r, Predicate p )
+/// \return true if any elements in the range satisfy the predicate 'p'
+/// \note returns false on an empty range
+///
+/// \param r The input range
+/// \param p A predicate for testing the elements of the range
+///
+template<typename Range, typename Predicate>
+bool any_of ( const Range &r, Predicate p )
+{
+ return boost::algorithm::any_of (boost::begin (r), boost::end (r), p);
+}
+
+/// \fn any_of_equal ( InputIterator first, InputIterator last, const V &val )
+/// \return true if any of the elements in [first, last) are equal to 'val'
+/// \note returns false on an empty range
+///
+/// \param first The start of the input sequence
+/// \param last One past the end of the input sequence
+/// \param val A value to compare against
+///
+template<typename InputIterator, typename V>
+bool any_of_equal ( InputIterator first, InputIterator last, const V &val )
+{
+ for ( ; first != last; ++first )
+ if ( val == *first )
+ return true;
+ return false;
+}
+
+/// \fn any_of_equal ( const Range &r, const V &val )
+/// \return true if any of the elements in the range are equal to 'val'
+/// \note returns false on an empty range
+///
+/// \param r The input range
+/// \param val A value to compare against
+///
+template<typename Range, typename V>
+bool any_of_equal ( const Range &r, const V &val )
+{
+ return boost::algorithm::any_of_equal (boost::begin (r), boost::end (r), val);
+}
+
+}} // namespace boost and algorithm
+
+#endif // BOOST_ALGORITHM_ANY_OF_HPP
Added: trunk/boost/algorithm/cxx11/copy_if.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/algorithm/cxx11/copy_if.hpp 2012-02-18 02:17:39 EST (Sat, 18 Feb 2012)
@@ -0,0 +1,133 @@
+/*
+ Copyright (c) Marshall Clow 2008-2012.
+
+ 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)
+*/
+
+/// \file copy_if.hpp
+/// \brief Copy a subset of a sequence to a new sequence
+/// \author Marshall Clow
+
+#ifndef BOOST_ALGORITHM_COPY_IF_HPP
+#define BOOST_ALGORITHM_COPY_IF_HPP
+
+#include <algorithm> // for std::copy_if, if available
+#include <boost/range/begin.hpp>
+#include <boost/range/end.hpp>
+
+namespace boost { namespace algorithm {
+
+#if __cplusplus >= 201103L
+// Use the C++11 versions of copy_if if it is available
+using std::copy_if; // Section 25.3.1
+#else
+/// \fn copy_if ( InputIterator first, InputIterator last, OutputIterator result, Predicate p )
+/// \brief Copies all the elements from the input range that satisfy the
+/// predicate to the output range.
+/// \return The updated output iterator
+///
+/// \param first The start of the input sequence
+/// \param last One past the end of the input sequence
+/// \param result An output iterator to write the results into
+/// \param p A predicate for testing the elements of the range
+/// \note This function is part of the C++2011 standard library.
+/// We will use the standard one if it is available,
+/// otherwise we have our own implementation.
+template<typename InputIterator, typename OutputIterator, typename Predicate>
+OutputIterator copy_if ( InputIterator first, InputIterator last, OutputIterator result, Predicate p )
+{
+ for ( ; first != last; ++first )
+ if (p(*first))
+ *result++ = first;
+ return result;
+}
+#endif
+
+/// \fn copy_if ( const Range &r, OutputIterator result, Predicate p )
+/// \brief Copies all the elements from the input range that satisfy the
+/// predicate to the output range.
+/// \return The updated output iterator
+///
+/// \param r The input range
+/// \param result An output iterator to write the results into
+/// \param p A predicate for testing the elements of the range
+///
+template<typename Range, typename OutputIterator, typename Predicate>
+OutputIterator copy_if ( const Range &r, OutputIterator result, Predicate p )
+{
+ return boost::algorithm::copy_if (boost::begin (r), boost::end(r), result, p);
+}
+
+
+/// \fn copy_while ( InputIterator first, InputIterator last, OutputIterator result, Predicate p )
+/// \brief Copies all the elements at the start of the input range that
+/// satisfy the predicate to the output range.
+/// \return The updated output iterator
+///
+/// \param first The start of the input sequence
+/// \param last One past the end of the input sequence
+/// \param result An output iterator to write the results into
+/// \param p A predicate for testing the elements of the range
+///
+template<typename InputIterator, typename OutputIterator, typename Predicate>
+OutputIterator copy_while ( InputIterator first, InputIterator last,
+ OutputIterator result, Predicate p )
+{
+ for ( ; first != last && p(*first); ++first )
+ *result++ = first;
+ return result;
+}
+
+/// \fn copy_while ( const Range &r, OutputIterator result, Predicate p )
+/// \brief Copies all the elements at the start of the input range that
+/// satisfy the predicate to the output range.
+/// \return The updated output iterator
+///
+/// \param r The input range
+/// \param result An output iterator to write the results into
+/// \param p A predicate for testing the elements of the range
+///
+template<typename Range, typename OutputIterator, typename Predicate>
+OutputIterator copy_while ( const Range &r, OutputIterator result, Predicate p )
+{
+ return boost::algorithm::copy_while (boost::begin (r), boost::end(r), result, p);
+}
+
+
+/// \fn copy_until ( InputIterator first, InputIterator last, OutputIterator result, Predicate p )
+/// \brief Copies all the elements at the start of the input range that do not
+/// satisfy the predicate to the output range.
+/// \return The updated output iterator
+///
+/// \param first The start of the input sequence
+/// \param last One past the end of the input sequence
+/// \param result An output iterator to write the results into
+/// \param p A predicate for testing the elements of the range
+///
+template<typename InputIterator, typename OutputIterator, typename Predicate>
+OutputIterator copy_until ( InputIterator first, InputIterator last, OutputIterator result, Predicate p )
+{
+ for ( ; first != last && !p(*first); ++first )
+ *result++ = first;
+ return result;
+}
+
+/// \fn copy_until ( const Range &r, OutputIterator result, Predicate p )
+/// \brief Copies all the elements at the start of the input range that do not
+/// satisfy the predicate to the output range.
+/// \return The updated output iterator
+///
+/// \param r The input range
+/// \param result An output iterator to write the results into
+/// \param p A predicate for testing the elements of the range
+///
+template<typename Range, typename OutputIterator, typename Predicate>
+OutputIterator copy_until ( const Range &r, OutputIterator result, Predicate p )
+{
+ return boost::algorithm::copy_until (boost::begin (r), boost::end(r), result, p);
+}
+
+}} // namespace boost and algorithm
+
+#endif // BOOST_ALGORITHM_COPY_IF_HPP
Added: trunk/boost/algorithm/cxx11/copy_n.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/algorithm/cxx11/copy_n.hpp 2012-02-18 02:17:39 EST (Sat, 18 Feb 2012)
@@ -0,0 +1,44 @@
+/*
+ Copyright (c) Marshall Clow 2011-2012.
+
+ 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)
+*/
+
+/// \file copy_n.hpp
+/// \brief Copy n items from one sequence to another
+/// \author Marshall Clow
+
+#ifndef BOOST_ALGORITHM_COPY_N_HPP
+#define BOOST_ALGORITHM_COPY_N_HPP
+
+#include <algorithm> // for std::copy_n, if available
+
+namespace boost { namespace algorithm {
+
+#if __cplusplus >= 201103L
+// Use the C++11 versions of copy_n if it is available
+using std::copy_n; // Section 25.3.1
+#else
+/// \fn copy_n ( InputIterator first, Size n, OutputIterator result )
+/// \brief Copies exactly n (n > 0) elements from the range starting at first to
+/// the range starting at result.
+/// \return The updated output iterator
+///
+/// \param first The start of the input sequence
+/// \param n The number of elements to copy
+/// \param result An output iterator to write the results into
+/// \note This function is part of the C++2011 standard library.
+/// We will use the standard one if it is available,
+/// otherwise we have our own implementation.
+template <typename InputIterator, typename Size, typename OutputIterator>
+OutputIterator copy_n ( InputIterator first, Size n, OutputIterator result )
+{
+ for ( ; n > 0; --n, ++first, ++result )
+ *result = *first;
+ return result;
+}
+#endif
+}} // namespace boost and algorithm
+
+#endif // BOOST_ALGORITHM_COPY_IF_HPP
Added: trunk/boost/algorithm/cxx11/find_if_not.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/algorithm/cxx11/find_if_not.hpp 2012-02-18 02:17:39 EST (Sat, 18 Feb 2012)
@@ -0,0 +1,60 @@
+/*
+ Copyright (c) Marshall Clow 2011-2012.
+
+ 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)
+*/
+
+/// \file find_if_not.hpp
+/// \brief Find the first element in a sequence that does not satisfy a predicate.
+/// \author Marshall Clow
+
+#ifndef BOOST_ALGORITHM_FIND_IF_NOT_HPP
+#define BOOST_ALGORITHM_FIND_IF_NOT_HPP
+
+#include <algorithm> // for std::find_if_not, if it exists
+
+#include <boost/range/begin.hpp>
+#include <boost/range/end.hpp>
+
+namespace boost { namespace algorithm {
+
+#if __cplusplus >= 201103L
+// Use the C++11 versions of find_if_not if it is available
+using std::find_if_not; // Section 25.2.5
+#else
+/// \fn find_if_not(InputIterator first, InputIterator last, Predicate p)
+/// \brief Finds the first element in the sequence that does not satisfy the predicate.
+/// \return The iterator pointing to the desired element.
+///
+/// \param first The start of the input sequence
+/// \param last One past the end of the input sequence
+/// \param p A predicate for testing the elements of the range
+/// \note This function is part of the C++2011 standard library.
+/// We will use the standard one if it is available,
+/// otherwise we have our own implementation.
+template<typename InputIterator, typename Predicate>
+InputIterator find_if_not ( InputIterator first, InputIterator last, Predicate p )
+{
+ for ( ; first != last; ++first )
+ if ( !p(*first))
+ break;
+ return first;
+}
+#endif
+
+/// \fn find_if_not ( const Range &r, Predicate p )
+/// \brief Finds the first element in the sequence that does not satisfy the predicate.
+/// \return The iterator pointing to the desired element.
+///
+/// \param r The input range
+/// \param p A predicate for testing the elements of the range
+///
+template<typename Range, typename Predicate>
+typename boost::range_iterator<const Range>::type find_if_not ( const Range &r, Predicate p )
+{
+ return boost::algorithm::find_if_not (boost::begin (r), boost::end(r), p);
+}
+
+}}
+#endif // BOOST_ALGORITHM_FIND_IF_NOT_HPP
Added: trunk/boost/algorithm/cxx11/iota.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/algorithm/cxx11/iota.hpp 2012-02-18 02:17:39 EST (Sat, 18 Feb 2012)
@@ -0,0 +1,74 @@
+/*
+ Copyright (c) Marshall Clow 2008-2012.
+
+ 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)
+*/
+
+/// \file iota.hpp
+/// \brief Generate an increasing series
+/// \author Marshall Clow
+
+#ifndef BOOST_ALGORITHM_IOTA_HPP
+#define BOOST_ALGORITHM_IOTA_HPP
+
+#include <numeric>
+
+#include <boost/range/begin.hpp>
+#include <boost/range/end.hpp>
+
+namespace boost { namespace algorithm {
+
+#if __cplusplus >= 201103L
+// Use the C++11 versions of iota if it is available
+using std::iota; // Section 26.7.6
+#else
+/// \fn iota ( ForwardIterator first, ForwardIterator last, T value )
+/// \brief Generates an increasing sequence of values, and stores them in [first, last)
+///
+/// \param first The start of the input sequence
+/// \param last One past the end of the input sequence
+/// \param value The initial value of the sequence to be generated
+/// \note This function is part of the C++2011 standard library.
+/// We will use the standard one if it is available,
+/// otherwise we have our own implementation.
+template <typename ForwardIterator, typename T>
+void iota ( ForwardIterator first, ForwardIterator last, T value )
+{
+ for ( ; first != last; ++first, ++value )
+ *first = value;
+}
+#endif
+
+/// \fn iota ( Range &r, T value )
+/// \brief Generates an increasing sequence of values, and stores them in the input Range.
+///
+/// \param r The input range
+/// \param value The initial value of the sequence to be generated
+///
+template <typename Range, typename T>
+void iota ( Range &r, T value )
+{
+ boost::algorithm::iota (boost::begin(r), boost::end(r), value);
+}
+
+
+/// \fn iota_n ( OutputIterator out, T value, std::size_t n )
+/// \brief Generates an increasing sequence of values, and stores them in the input Range.
+///
+/// \param out An output iterator to write the results into
+/// \param value The initial value of the sequence to be generated
+/// \param n The number of items to write
+///
+template <typename OutputIterator, typename T>
+OutputIterator iota_n ( OutputIterator out, T value, std::size_t n )
+{
+ while ( n-- > 0 )
+ *out++ = value++;
+
+ return out;
+}
+
+}}
+
+#endif // BOOST_ALGORITHM_IOTA_HPP
\ No newline at end of file
Added: trunk/boost/algorithm/cxx11/is_partitioned.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/algorithm/cxx11/is_partitioned.hpp 2012-02-18 02:17:39 EST (Sat, 18 Feb 2012)
@@ -0,0 +1,65 @@
+/*
+ Copyright (c) Marshall Clow 2011-2012.
+
+ 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)
+*/
+
+/// \file is_partitioned.hpp
+/// \brief Tell if a sequence is partitioned
+/// \author Marshall Clow
+
+#ifndef BOOST_ALGORITHM_IS_PARTITIONED_HPP
+#define BOOST_ALGORITHM_IS_PARTITIONED_HPP
+
+#include <algorithm> // for std::is_partitioned, if available
+
+#include <boost/range/begin.hpp>
+#include <boost/range/end.hpp>
+
+namespace boost { namespace algorithm {
+
+#if __cplusplus >= 201103L
+// Use the C++11 versions of iota if it is available
+using std::is_partitioned; // Section 25.3.13
+#else
+/// \fn is_partitioned ( InputIterator first, InputIterator last, UnaryPredicate p )
+/// \brief Tests to see if a sequence is partititioned according to a predicate
+///
+/// \param first The start of the input sequence
+/// \param last One past the end of the input sequence
+/// \param p The predicicate to test the values with
+/// \note This function is part of the C++2011 standard library.
+/// We will use the standard one if it is available,
+/// otherwise we have our own implementation.
+template <typename InputIterator, typename UnaryPredicate>
+bool is_partitioned ( InputIterator first, InputIterator last, UnaryPredicate p )
+{
+// Run through the part that satisfy the predicate
+ for ( ; first != last; ++first )
+ if ( !p (*first))
+ break;
+// Now the part that does not satisfy the predicate
+ for ( ; first != last; ++first )
+ if ( p (*first))
+ return false;
+ return true;
+}
+#endif
+
+/// \fn is_partitioned ( const Range &r, UnaryPredicate p )
+/// \brief Generates an increasing sequence of values, and stores them in the input Range.
+///
+/// \param r The input range
+/// \param p The predicicate to test the values with
+///
+template <typename Range, typename UnaryPredicate>
+bool is_partitioned ( const Range &r, UnaryPredicate p )
+{
+ return boost::algorithm::is_partitioned (boost::begin(r), boost::end(r), p);
+}
+
+
+}}
+
+#endif // BOOST_ALGORITHM_IS_PARTITIONED_HPP
\ No newline at end of file
Added: trunk/boost/algorithm/cxx11/is_permutation.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/algorithm/cxx11/is_permutation.hpp 2012-02-18 02:17:39 EST (Sat, 18 Feb 2012)
@@ -0,0 +1,140 @@
+/*
+ Copyright (c) Marshall Clow 2011-2012.
+
+ 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)
+*/
+
+/// \file is_permutation.hpp
+/// \brief Is a sequence a permutation of another sequence
+/// \author Marshall Clow
+
+#ifndef BOOST_ALGORITHM_IS_PERMUTATION_HPP
+#define BOOST_ALGORITHM_IS_PERMUTATION_HPP
+
+#include <algorithm> // for std::less, tie, mismatch and is_permutation (if available)
+#include <utility> // for std::make_pair
+#include <iterator>
+#include <iostream>
+
+#include <boost/range/begin.hpp>
+#include <boost/range/end.hpp>
+#include <boost/utility/enable_if.hpp>
+#include <boost/type_traits/is_same.hpp>
+#include <boost/tr1/tr1/tuple> // for tie
+
+namespace boost { namespace algorithm {
+
+#if __cplusplus >= 201103L
+// Use the C++11 versions of is_permutation if it is available
+using std::is_permutation; // Section 25.2.12
+#else
+/// \cond DOXYGEN_HIDE
+namespace detail {
+ template <typename Predicate, typename Iterator>
+ struct value_predicate {
+ value_predicate ( Predicate p, Iterator it ) : p_ ( p ), it_ ( it ) {}
+
+ template <typename T1>
+ bool operator () ( const T1 &t1 ) const { return p_ ( *it_, t1 ); }
+ private:
+ Predicate &p_;
+ Iterator it_;
+ };
+}
+/// \endcond
+
+
+/// \fn is_permutation ( ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 first2, BinaryPredicate p )
+/// \brief Tests to see if a the sequence [first,last) is a permutation of the sequence starting at first2
+///
+/// \param first The start of the input sequence
+/// \param last One past the end of the input sequence
+/// \param first2 The start of the second sequence
+/// \param p The predicate to compare elements with
+///
+/// \note This function is part of the C++2011 standard library.
+/// We will use the standard one if it is available,
+/// otherwise we have our own implementation.
+template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate >
+bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1,
+ ForwardIterator2 first2, BinaryPredicate p )
+{
+// Skip the common prefix (if any)
+// std::tie (first1, first2) = std::mismatch (first1, last1, first2, p);
+ std::pair<ForwardIterator1, ForwardIterator2> eq = std::mismatch (first1, last1, first2, p);
+ first1 = eq.first;
+ first2 = eq.second;
+ if ( first1 != last1 ) {
+ // Create last2
+ ForwardIterator2 last2 = first2;
+ std::advance ( last2, std::distance (first1, last1));
+
+ // for each unique value in the sequence [first1,last1), count how many times
+ // it occurs, and make sure it occurs the same number of times in [first2, last2)
+ for ( ForwardIterator1 iter = first1; iter != last1; ++iter ) {
+ detail::value_predicate<BinaryPredicate, ForwardIterator1> pred ( p, iter );
+
+ /* For each value we haven't seen yet... */
+ if ( std::find_if ( first1, iter, pred ) == iter ) {
+ std::size_t dest_count = std::count_if ( first2, last2, pred );
+ if ( dest_count == 0 || dest_count != (std::size_t) std::count_if ( iter, last1, pred ))
+ return false;
+ }
+ }
+ }
+
+ return true;
+}
+
+/// \fn is_permutation ( ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 first2 )
+/// \brief Tests to see if a the sequence [first,last) is a permutation of the sequence starting at first2
+///
+/// \param first The start of the input sequence
+/// \param last One past the end of the input sequence
+/// \param first2 The start of the second sequence
+/// \note This function is part of the C++2011 standard library.
+/// We will use the standard one if it is available,
+/// otherwise we have our own implementation.
+template< class ForwardIterator1, class ForwardIterator2 >
+bool is_permutation ( ForwardIterator1 first, ForwardIterator1 last,
+ ForwardIterator2 first2 )
+{
+// How should I deal with the idea that ForwardIterator1::value_type
+// and ForwardIterator2::value_type could be different? Define my own comparison predicate?
+ return boost::algorithm::is_permutation ( first, last, first2,
+ std::equal_to<typename ForwardIterator1::value_type> ());
+}
+
+#endif
+
+/// \fn is_permutation ( const Range &r, ForwardIterator first2 )
+/// \brief Tests to see if a the sequence [first,last) is a permutation of the sequence starting at first2
+///
+/// \param r The input range
+/// \param first2 The start of the second sequence
+template <typename Range, typename ForwardIterator>
+bool is_permutation ( const Range &r, ForwardIterator first2 )
+{
+ return boost::algorithm::is_permutation (boost::begin (r), boost::end (r), first2 );
+}
+
+/// \fn is_permutation ( const Range &r, ForwardIterator first2, BinaryPredicate pred )
+/// \brief Tests to see if a the sequence [first,last) is a permutation of the sequence starting at first2
+///
+/// \param r The input range
+/// \param first2 The start of the second sequence
+/// \param pred The predicate to compare elements with
+///
+// Disable this template when the first two parameters are the same type
+// That way the non-range version will be chosen.
+template <typename Range, typename ForwardIterator, typename BinaryPredicate>
+typename boost::disable_if_c<boost::is_same<Range, ForwardIterator>::value, bool>::type
+is_permutation ( const Range &r, ForwardIterator first2, BinaryPredicate pred )
+{
+ return boost::algorithm::is_permutation (boost::begin (r), boost::end (r), first2, pred );
+}
+
+}}
+
+#endif // BOOST_ALGORITHM_IS_PERMUTATION_HPP
\ No newline at end of file
Added: trunk/boost/algorithm/cxx11/none_of.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/algorithm/cxx11/none_of.hpp 2012-02-18 02:17:39 EST (Sat, 18 Feb 2012)
@@ -0,0 +1,87 @@
+/*
+ Copyright (c) Marshall Clow 2008-2012.
+
+ 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)
+*/
+
+/// \file none_of.hpp
+/// \brief Test ranges to see if no elements match a value or predicate.
+/// \author Marshall Clow
+
+#ifndef BOOST_ALGORITHM_NONE_OF_HPP
+#define BOOST_ALGORITHM_NONE_OF_HPP
+
+#include <boost/range/begin.hpp>
+#include <boost/range/end.hpp>
+
+namespace boost { namespace algorithm {
+
+// Use the C++11 versions of the none_of if it is available
+#if __cplusplus >= 201103L
+using std::none_of; // Section 25.2.3
+#else
+/// \fn none_of ( InputIterator first, InputIterator last, Predicate p )
+/// \return true if none of the elements in [first, last) satisfy the predicate 'p'
+/// \note returns true on an empty range
+///
+/// \param first The start of the input sequence
+/// \param last One past the end of the input sequence
+/// \param p A predicate for testing the elements of the sequence
+///
+template<typename InputIterator, typename Predicate>
+bool none_of ( InputIterator first, InputIterator last, Predicate p )
+{
+for ( ; first != last; ++first )
+ if ( p(*first))
+ return false;
+ return true;
+}
+#endif
+
+/// \fn none_of ( const Range &r, Predicate p )
+/// \return true if none of the elements in the range satisfy the predicate 'p'
+/// \note returns true on an empty range
+///
+/// \param r The input range
+/// \param p A predicate for testing the elements of the range
+///
+template<typename Range, typename Predicate>
+bool none_of ( const Range &r, Predicate p )
+{
+ return boost::algorithm::none_of (boost::begin (r), boost::end (r), p );
+}
+
+/// \fn none_of_equal ( InputIterator first, InputIterator last, const V &val )
+/// \return true if none of the elements in [first, last) are equal to 'val'
+/// \note returns true on an empty range
+///
+/// \param first The start of the input sequence
+/// \param last One past the end of the input sequence
+/// \param val A value to compare against
+///
+template<typename InputIterator, typename V>
+bool none_of_equal ( InputIterator first, InputIterator last, const V &val )
+{
+ for ( ; first != last; ++first )
+ if ( val == *first )
+ return false;
+ return true;
+}
+
+/// \fn none_of_equal ( const Range &r, const V &val )
+/// \return true if none of the elements in the range are equal to 'val'
+/// \note returns true on an empty range
+///
+/// \param r The input range
+/// \param val A value to compare against
+///
+template<typename Range, typename V>
+bool none_of_equal ( const Range &r, const V & val )
+{
+ return boost::algorithm::none_of_equal (boost::begin (r), boost::end (r), val);
+}
+
+}} // namespace boost and algorithm
+
+#endif // BOOST_ALGORITHM_NONE_OF_HPP
Added: trunk/boost/algorithm/cxx11/one_of.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/algorithm/cxx11/one_of.hpp 2012-02-18 02:17:39 EST (Sat, 18 Feb 2012)
@@ -0,0 +1,82 @@
+/*
+ Copyright (c) Marshall Clow 2008-2012.
+
+ 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)
+*/
+
+/// \file one_of.hpp
+/// \brief Test ranges to see if only one element matches a value or predicate.
+/// \author Marshall Clow
+
+#ifndef BOOST_ALGORITHM_ONE_OF_HPP
+#define BOOST_ALGORITHM_ONE_OF_HPP
+
+#include <algorithm> // for std::find and std::find_if
+#include <boost/algorithm/cxx11/none_of.hpp>
+
+#include <boost/range/begin.hpp>
+#include <boost/range/end.hpp>
+
+namespace boost { namespace algorithm {
+
+/// \fn one_of ( InputIterator first, InputIterator last, Predicate p )
+/// \return true if the predicate 'p' is true for exactly one item in [first, last).
+///
+/// \param first The start of the input sequence
+/// \param last One past the end of the input sequence
+/// \param p A predicate for testing the elements of the sequence
+///
+template<typename InputIterator, typename Predicate>
+bool one_of ( InputIterator first, InputIterator last, Predicate p )
+{
+ InputIterator i = std::find_if (first, last, p);
+ if (i == last)
+ return false; // Didn't occur at all
+ return boost::algorithm::none_of (++i, last, p);
+}
+
+/// \fn one_of ( const Range &r, Predicate p )
+/// \return true if the predicate 'p' is true for exactly one item in the range.
+///
+/// \param r The input range
+/// \param p A predicate for testing the elements of the range
+///
+template<typename Range, typename Predicate>
+bool one_of ( const Range &r, Predicate p )
+{
+ return boost::algorithm::one_of ( boost::begin (r), boost::end (r), p );
+}
+
+
+/// \fn one_of_equal ( InputIterator first, InputIterator last, const V &val )
+/// \return true if the value 'val' exists only once in [first, last).
+///
+/// \param first The start of the input sequence
+/// \param last One past the end of the input sequence
+/// \param val A value to compare against
+///
+template<typename InputIterator, typename V>
+bool one_of_equal ( InputIterator first, InputIterator last, const V &val )
+{
+ InputIterator i = std::find (first, last, val); // find first occurrence of 'val'
+ if (i == last)
+ return false; // Didn't occur at all
+ return boost::algorithm::none_of_equal (++i, last, val);
+}
+
+/// \fn one_of_equal ( const Range &r, const V &val )
+/// \return true if the value 'val' exists only once in the range.
+///
+/// \param r The input range
+/// \param val A value to compare against
+///
+template<typename Range, typename V>
+bool one_of_equal ( const Range &r, const V &val )
+{
+ return boost::algorithm::one_of_equal ( boost::begin (r), boost::end (r), val );
+}
+
+}} // namespace boost and algorithm
+
+#endif // BOOST_ALGORITHM_ALL_HPP
Added: trunk/boost/algorithm/cxx11/ordered.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/algorithm/cxx11/ordered.hpp 2012-02-18 02:17:39 EST (Sat, 18 Feb 2012)
@@ -0,0 +1,286 @@
+// Copyright (c) 2010 Nuovation System Designs, LLC
+// Grant Erickson <gerickson_at_[hidden]>
+//
+// Reworked somewhat by Marshall Clow; August 2010
+//
+// 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)
+//
+// See http://www.boost.org/ for latest version.
+//
+
+#ifndef BOOST_ALGORITHM_ORDERED_HPP
+#define BOOST_ALGORITHM_ORDERED_HPP
+
+#include <algorithm>
+#include <functional>
+#include <iterator>
+
+#include <boost/range/begin.hpp>
+#include <boost/range/end.hpp>
+
+#include <boost/utility/enable_if.hpp>
+#include <boost/type_traits/is_same.hpp>
+
+namespace boost { namespace algorithm {
+
+#if __cplusplus >= 201103L
+// Use the C++11 versions of iota if it is available
+using std::is_sorted_until; // Section 25.4.1.5
+using std::is_sorted; // Section 25.4.1.5
+#else
+/// \fn is_sorted_until ( ForwardIterator first, ForwardIterator last, Pred p )
+/// \return the point in the sequence [first, last) where the elements are unordered
+/// (according to the comparison predicate 'p').
+///
+/// \param first The start of the sequence to be tested.
+/// \param last One past the end of the sequence
+/// \param p A binary predicate that returns true if two elements are ordered.
+///
+ template <typename ForwardIterator, typename Pred>
+ ForwardIterator is_sorted_until ( ForwardIterator first, ForwardIterator last, Pred p )
+ {
+ if ( first == last ) return last; // the empty sequence is ordered
+ ForwardIterator next = first;
+ while ( ++next != last )
+ {
+ if ( !p ( *first, *next ))
+ return next;
+ first = next;
+ }
+ return last;
+ }
+
+/// \fn is_sorted_until ( ForwardIterator first, ForwardIterator last )
+/// \return the point in the sequence [first, last) where the elements are unordered
+///
+/// \param first The start of the sequence to be tested.
+/// \param last One past the end of the sequence
+///
+ template <typename ForwardIterator>
+ ForwardIterator is_sorted_until ( ForwardIterator first, ForwardIterator last )
+ {
+ typedef typename std::iterator_traits<ForwardIterator>::value_type value_type;
+ return is_sorted_until ( first, last, std::less_equal<value_type>());
+ }
+
+
+/// \fn is_sorted ( ForwardIterator first, ForwardIterator last, Pred p )
+/// \return whether or not the entire sequence is sorted
+///
+/// \param first The start of the sequence to be tested.
+/// \param last One past the end of the sequence
+/// \param p A binary predicate that returns true if two elements are ordered.
+///
+ template <typename ForwardIterator, typename Pred>
+ bool is_sorted ( ForwardIterator first, ForwardIterator last, Pred p )
+ {
+ return is_sorted_until (first, last, p) == last;
+ }
+
+/// \fn is_sorted ( ForwardIterator first, ForwardIterator last )
+/// \return whether or not the entire sequence is sorted
+///
+/// \param first The start of the sequence to be tested.
+/// \param last One past the end of the sequence
+///
+ template <typename ForwardIterator>
+ bool is_sorted ( ForwardIterator first, ForwardIterator last )
+ {
+ return is_sorted_until (first, last) == last;
+ }
+#endif
+
+///
+/// -- Range based versions of the C++11 functions
+///
+
+/// \fn is_sorted_until ( const R &range, Pred p )
+/// \return the point in the range R where the elements are unordered
+/// (according to the comparison predicate 'p').
+///
+/// \param range The range to be tested.
+/// \param p A binary predicate that returns true if two elements are ordered.
+///
+ template <typename R, typename Pred>
+ typename boost::lazy_disable_if_c<
+ boost::is_same<R, Pred>::value,
+ typename boost::range_iterator<const R>
+ >::type is_sorted_until ( const R &range, Pred p )
+ {
+ return is_sorted_until ( boost::begin ( range ), boost::end ( range ), p );
+ }
+
+
+/// \fn is_sorted_until ( const R &range )
+/// \return the point in the range R where the elements are unordered
+///
+/// \param range The range to be tested.
+///
+ template <typename R>
+ typename boost::range_iterator<const R>::type is_sorted_until ( const R &range )
+ {
+ return is_sorted_until ( boost::begin ( range ), boost::end ( range ));
+ }
+
+
+/// \fn is_sorted ( const R &range, Pred p )
+/// \return whether or not the entire range R is sorted
+/// (according to the comparison predicate 'p').
+///
+/// \param range The range to be tested.
+/// \param p A binary predicate that returns true if two elements are ordered.
+///
+ template <typename R, typename Pred>
+ bool is_sorted ( const R &range, Pred p )
+ {
+ return is_sorted ( boost::begin ( range ), boost::end ( range ), p );
+ }
+
+
+/// \fn is_sorted ( const R &range )
+/// \return whether or not the entire range R is sorted
+///
+/// \param range The range to be tested.
+///
+ template <typename R, typename Pred>
+ bool is_sorted ( const R &range )
+ {
+ return is_sorted ( boost::begin ( range ), boost::end ( range ));
+ }
+
+
+///
+/// -- Range based versions of the C++11 functions
+///
+
+/// \fn is_increasing ( ForwardIterator first, ForwardIterator last )
+/// \return true if the entire sequence is increasing; i.e, each item is greater than or
+/// equal to the previous one.
+///
+/// \param first The start of the sequence to be tested.
+/// \param last One past the end of the sequence
+///
+/// \note This function will return true for sequences that contain items that compare
+/// equal. If that is not what you intended, you should use is_strictly_increasing instead.
+ template <typename ForwardIterator>
+ bool is_increasing ( ForwardIterator first, ForwardIterator last )
+ {
+ typedef typename std::iterator_traits<ForwardIterator>::value_type value_type;
+ return is_sorted (first, last, std::less_equal<value_type>());
+ }
+
+
+/// \fn is_increasing ( const R &range )
+/// \return true if the entire sequence is increasing; i.e, each item is greater than or
+/// equal to the previous one.
+///
+/// \param range The range to be tested.
+///
+/// \note This function will return true for sequences that contain items that compare
+/// equal. If that is not what you intended, you should use is_strictly_increasing instead.
+ template <typename R>
+ bool is_increasing ( const R &range )
+ {
+ return is_increasing ( boost::begin ( range ), boost::end ( range ));
+ }
+
+
+
+/// \fn is_decreasing ( ForwardIterator first, ForwardIterator last )
+/// \return true if the entire sequence is decreasing; i.e, each item is less than
+/// or equal to the previous one.
+///
+/// \param first The start of the sequence to be tested.
+/// \param last One past the end of the sequence
+///
+/// \note This function will return true for sequences that contain items that compare
+/// equal. If that is not what you intended, you should use is_strictly_decreasing instead.
+ template <typename ForwardIterator>
+ bool is_decreasing ( ForwardIterator first, ForwardIterator last )
+ {
+ typedef typename std::iterator_traits<ForwardIterator>::value_type value_type;
+ return is_sorted (first, last, std::greater_equal<value_type>());
+ }
+
+/// \fn is_decreasing ( const R &range )
+/// \return true if the entire sequence is decreasing; i.e, each item is less than
+/// or equal to the previous one.
+///
+/// \param range The range to be tested.
+///
+/// \note This function will return true for sequences that contain items that compare
+/// equal. If that is not what you intended, you should use is_strictly_decreasing instead.
+ template <typename R>
+ bool is_decreasing ( const R &range )
+ {
+ return is_decreasing ( boost::begin ( range ), boost::end ( range ));
+ }
+
+
+
+/// \fn is_strictly_increasing ( ForwardIterator first, ForwardIterator last )
+/// \return true if the entire sequence is strictly increasing; i.e, each item is greater
+/// than the previous one
+///
+/// \param first The start of the sequence to be tested.
+/// \param last One past the end of the sequence
+///
+/// \note This function will return false for sequences that contain items that compare
+/// equal. If that is not what you intended, you should use is_increasing instead.
+ template <typename ForwardIterator>
+ bool is_strictly_increasing ( ForwardIterator first, ForwardIterator last )
+ {
+ typedef typename std::iterator_traits<ForwardIterator>::value_type value_type;
+ return is_sorted (first, last, std::less<value_type>());
+ }
+
+/// \fn is_strictly_increasing ( const R &range )
+/// \return true if the entire sequence is strictly increasing; i.e, each item is greater
+/// than the previous one
+///
+/// \param range The range to be tested.
+///
+/// \note This function will return false for sequences that contain items that compare
+/// equal. If that is not what you intended, you should use is_increasing instead.
+ template <typename R>
+ bool is_strictly_increasing ( const R &range )
+ {
+ return is_strictly_increasing ( boost::begin ( range ), boost::end ( range ));
+ }
+
+
+/// \fn is_strictly_decreasing ( ForwardIterator first, ForwardIterator last )
+/// \return true if the entire sequence is strictly decreasing; i.e, each item is less than
+/// the previous one
+///
+/// \param first The start of the sequence to be tested.
+/// \param last One past the end of the sequence
+///
+/// \note This function will return false for sequences that contain items that compare
+/// equal. If that is not what you intended, you should use is_decreasing instead.
+ template <typename ForwardIterator>
+ bool is_strictly_decreasing ( ForwardIterator first, ForwardIterator last )
+ {
+ typedef typename std::iterator_traits<ForwardIterator>::value_type value_type;
+ return is_sorted (first, last, std::greater<value_type>());
+ }
+
+/// \fn is_strictly_decreasing ( const R &range )
+/// \return true if the entire sequence is strictly decreasing; i.e, each item is less than
+/// the previous one
+///
+/// \param range The range to be tested.
+///
+/// \note This function will return false for sequences that contain items that compare
+/// equal. If that is not what you intended, you should use is_decreasing instead.
+ template <typename R>
+ bool is_strictly_decreasing ( const R &range )
+ {
+ return is_strictly_decreasing ( boost::begin ( range ), boost::end ( range ));
+ }
+
+}} // namespace boost
+
+#endif // BOOST_ALGORITHM_ORDERED_HPP
Added: trunk/boost/algorithm/cxx11/partition_copy.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/algorithm/cxx11/partition_copy.hpp 2012-02-18 02:17:39 EST (Sat, 18 Feb 2012)
@@ -0,0 +1,75 @@
+/*
+ Copyright (c) Marshall Clow 2011-2012.
+
+ 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)
+*/
+
+/// \file partition_copy.hpp
+/// \brief Copy a subset of a sequence to a new sequence
+/// \author Marshall Clow
+
+#ifndef BOOST_ALGORITHM_PARTITION_COPY_HPP
+#define BOOST_ALGORITHM_PARTITION_COPY_HPP
+
+#include <boost/range/begin.hpp>
+#include <boost/range/end.hpp>
+
+namespace boost { namespace algorithm {
+
+#if __cplusplus >= 201103L
+// Use the C++11 versions of partition_copy if it is available
+using std::partition_copy; // Section 25.3.13
+#else
+/// \fn partition_copy ( InputIterator first, InputIterator last,
+/// OutputIterator1 out_true, OutputIterator2 out_false, UnaryPredicate p )
+/// \brief Copies the elements that satisfy the predicate p from the range [first, last)
+/// to the range beginning at d_first_true, and
+/// copies the elements that do not satisfy p to the range beginning at d_first_false.
+///
+///
+/// \param first The start of the input sequence
+/// \param last One past the end of the input sequence
+/// \param out_true An output iterator to write the elements that satisfy the predicate into
+/// \param out_false An output iterator to write the elements that do not satisfy the predicate into
+/// \param p A predicate for dividing the elements of the input sequence.
+///
+/// \note This function is part of the C++2011 standard library.
+/// We will use the standard one if it is available,
+/// otherwise we have our own implementation.
+template <typename InputIterator,
+ typename OutputIterator1, typename OutputIterator2, typename UnaryPredicate>
+std::pair<OutputIterator1, OutputIterator2>
+partition_copy ( InputIterator first, InputIterator last,
+ OutputIterator1 out_true, OutputIterator2 out_false, UnaryPredicate p )
+{
+ for ( ; first != last; ++first )
+ if ( p (*first))
+ *out_true++ = *first;
+ else
+ *out_false++ = *first;
+ return std::make_pair<OutputIterator1, OutputIterator2> ( out_true, out_false );
+}
+#endif
+
+/// \fn partition_copy ( const Range &r,
+/// OutputIterator1 out_true, OutputIterator2 out_false, UnaryPredicate p )
+///
+/// \param r The input range
+/// \param out_true An output iterator to write the elements that satisfy the predicate into
+/// \param out_false An output iterator to write the elements that do not satisfy the predicate into
+/// \param p A predicate for dividing the elements of the input sequence.
+///
+template <typename Range, typename OutputIterator1, typename OutputIterator2,
+ typename UnaryPredicate>
+std::pair<OutputIterator1, OutputIterator2>
+partition_copy ( const Range &r, OutputIterator1 out_true, OutputIterator2 out_false,
+ UnaryPredicate p )
+{
+ return boost::algorithm::partition_copy
+ (boost::begin(r), boost::end(r), out_true, out_false, p );
+}
+
+}} // namespace boost and algorithm
+
+#endif // BOOST_ALGORITHM_PARTITION_COPY_HPP
Added: trunk/boost/algorithm/cxx11/partition_point.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/algorithm/cxx11/partition_point.hpp 2012-02-18 02:17:39 EST (Sat, 18 Feb 2012)
@@ -0,0 +1,72 @@
+/*
+ Copyright (c) Marshall Clow 2011-2012.
+
+ 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)
+*/
+
+/// \file partition_point.hpp
+/// \brief Find the partition point in a sequence
+/// \author Marshall Clow
+
+#ifndef BOOST_ALGORITHM_PARTITION_POINT_HPP
+#define BOOST_ALGORITHM_PARTITION_POINT_HPP
+
+#include <algorithm> // for std::partition_point, if available
+
+#include <boost/range/begin.hpp>
+#include <boost/range/end.hpp>
+
+namespace boost { namespace algorithm {
+
+#if __cplusplus >= 201103L
+// Use the C++11 versions of iota if it is available
+using std::partition_point; // Section 25.3.13
+#else
+/// \fn partition_point ( ForwardIterator first, ForwardIterator last, Predicate p )
+/// \brief Given a partitioned range, returns the partition point, i.e, the first element
+/// that does not satisfy p
+///
+/// \param first The start of the input sequence
+/// \param last One past the end of the input sequence
+/// \param p The predicate to test the values with
+/// \note This function is part of the C++2011 standard library.
+/// We will use the standard one if it is available,
+/// otherwise we have our own implementation.
+template <typename ForwardIterator, typename Predicate>
+ForwardIterator partition_point ( ForwardIterator first, ForwardIterator last, Predicate p )
+{
+ std::size_t dist = std::distance ( first, last );
+ while ( first != last ) {
+ std::size_t d2 = dist / 2;
+ ForwardIterator ret_val = first;
+ std::advance (ret_val, d2);
+ if (p (*ret_val)) {
+ first = ++ret_val;
+ dist -= d2 + 1;
+ }
+ else {
+ last = ret_val;
+ dist = d2;
+ }
+ }
+ return first;
+}
+#endif
+
+/// \fn partition_point ( Range &r, Predicate p )
+/// \brief Given a partitioned range, returns the partition point
+///
+/// \param r The input range
+/// \param p The predicate to test the values with
+///
+template <typename Range, typename Predicate>
+typename boost::range_iterator<Range> partition_point ( Range &r, Predicate p )
+{
+ return boost::algorithm::partition_point (boost::begin(r), boost::end(r), p);
+}
+
+
+}}
+
+#endif // BOOST_ALGORITHM_PARTITION_POINT_HPP
\ No newline at end of file
Modified: trunk/libs/algorithm/test/Jamfile.v2
==============================================================================
--- trunk/libs/algorithm/test/Jamfile.v2 (original)
+++ trunk/libs/algorithm/test/Jamfile.v2 2012-02-18 02:17:39 EST (Sat, 18 Feb 2012)
@@ -22,6 +22,23 @@
# Clamp tests
[ run clamp_test.cpp : : : : clamp_test ]
+
+# Cxx11 tests
+ [ run all_of_test.cpp : : : : all_of_test ]
+ [ run any_of_test.cpp : : : : any_of_test ]
+ [ run none_of_test.cpp : : : : none_of_test ]
+ [ run one_of_test.cpp : : : : one_of_test ]
+
+ [ run ordered_test.cpp : : : : ordered_test ]
+ [ run find_if_not_test1.cpp : : : : find_if_not_test1 ]
+ [ run copy_n_test1.cpp : : : : copy_n_test1 ]
+ [ run iota_test1.cpp : : : : iota_test1 ]
+
+ [ run is_permutation_test1.cpp : : : : is_permutation_test1 ]
+ [ run partition_point_test1.cpp : : : : partition_point_test1 ]
+ [ run is_partitioned_test1.cpp : : : : is_partitioned_test1 ]
+ [ run partition_copy_test1.cpp : : : : partition_copy_test1 ]
+
;
}
Added: trunk/libs/algorithm/test/all_of_test.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/algorithm/test/all_of_test.cpp 2012-02-18 02:17:39 EST (Sat, 18 Feb 2012)
@@ -0,0 +1,86 @@
+/*
+ Copyright (c) Marshall Clow 2010-2012.
+
+ 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)
+
+ For more information, see http://www.boost.org
+*/
+
+#include <boost/config.hpp>
+#include <boost/algorithm/cxx11/all_of.hpp>
+#include <boost/test/included/test_exec_monitor.hpp>
+
+#include <functional>
+#include <vector>
+#include <list>
+
+template<typename T>
+struct is_ : public std::unary_function<T, bool> {
+ is_ ( T v ) : val_ ( v ) {}
+ ~is_ () {}
+ bool operator () ( T comp ) const { return val_ == comp; }
+private:
+ is_ (); // need a value
+
+ T val_;
+ };
+
+namespace ba = boost::algorithm;
+
+void test_all ()
+{
+// Note: The literal values here are tested against directly, careful if you change them:
+ int some_numbers[] = { 1, 1, 1, 18, 10 };
+ std::vector<int> vi(some_numbers, some_numbers + 5);
+ std::list<int> li(vi.begin(), vi.end ());
+
+ int some_letters[] = { 'a', 'q', 'n', 'y', 'n' };
+ std::vector<char> vc(some_letters, some_letters + 5);
+
+
+ BOOST_CHECK (!ba::all_of_equal ( vi, 1 ));
+ BOOST_CHECK (!ba::all_of ( vi, is_<int> ( 1 )));
+ BOOST_CHECK (!ba::all_of_equal ( vi.begin(), vi.end(), 1 ));
+ BOOST_CHECK (!ba::all_of ( vi.begin(), vi.end(), is_<int> ( 1 )));
+
+ BOOST_CHECK (!ba::all_of_equal ( vi, 0 ));
+ BOOST_CHECK (!ba::all_of ( vi, is_<int> ( 0 )));
+ BOOST_CHECK (!ba::all_of_equal ( vi.begin(), vi.end(), 0 ));
+ BOOST_CHECK (!ba::all_of ( vi.begin(), vi.end(), is_<int> ( 0 )));
+
+ BOOST_CHECK ( ba::all_of_equal ( vi.end(), vi.end(), 0 ));
+ BOOST_CHECK ( ba::all_of ( vi.end(), vi.end(), is_<int> ( 0 )));
+
+ BOOST_CHECK ( ba::all_of_equal ( vi.begin(), vi.begin () + 3, 1 ));
+ BOOST_CHECK ( ba::all_of ( vi.begin(), vi.begin () + 3, is_<int> ( 1 )));
+
+ BOOST_CHECK ( ba::all_of_equal ( vc.begin() + 1, vc.begin() + 2, 'q' ));
+ BOOST_CHECK ( ba::all_of ( vc.begin() + 1, vc.begin() + 2, is_<char> ( 'q' )));
+
+ BOOST_CHECK (!ba::all_of_equal ( vc, '!' ));
+ BOOST_CHECK (!ba::all_of ( vc, is_<char> ( '!' )));
+
+ BOOST_CHECK ( ba::all_of_equal ( vi.begin(), vi.begin(), 1 ));
+ BOOST_CHECK ( ba::all_of_equal ( vc.begin(), vc.begin(), 'a' ));
+ BOOST_CHECK ( ba::all_of ( vi.begin(), vi.begin(), is_<int> ( 1 )));
+ BOOST_CHECK ( ba::all_of ( vc.begin(), vc.begin(), is_<char> ( 'a' )));
+
+ BOOST_CHECK (!ba::all_of_equal ( li, 1 ));
+ BOOST_CHECK (!ba::all_of ( li, is_<int> ( 1 )));
+ BOOST_CHECK (!ba::all_of_equal ( li.begin(), li.end(), 1 ));
+ BOOST_CHECK (!ba::all_of ( li.begin(), li.end(), is_<int> ( 1 )));
+
+ std::list<int>::iterator l_iter = li.begin ();
+ l_iter++; l_iter++; l_iter++;
+ BOOST_CHECK ( ba::all_of_equal ( li.begin(), l_iter, 1 ));
+ BOOST_CHECK ( ba::all_of ( li.begin(), l_iter, is_<int> ( 1 )));
+
+}
+
+
+int test_main( int , char* [] )
+{
+ test_all ();
+ return 0;
+}
Added: trunk/libs/algorithm/test/any_of_test.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/algorithm/test/any_of_test.cpp 2012-02-18 02:17:39 EST (Sat, 18 Feb 2012)
@@ -0,0 +1,105 @@
+/*
+ Copyright (c) Marshall Clow 2010-2012.
+
+ 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)
+
+ For more information, see http://www.boost.org
+*/
+
+#include <boost/config.hpp>
+#include <boost/algorithm/cxx11/any_of.hpp>
+#include <boost/test/included/test_exec_monitor.hpp>
+
+#include <functional>
+#include <vector>
+#include <list>
+
+template<typename T>
+struct is_ : public std::unary_function<T, bool> {
+ is_ ( T v ) : val_ ( v ) {}
+ ~is_ () {}
+ bool operator () ( T comp ) const { return val_ == comp; }
+private:
+ is_ (); // need a value
+
+ T val_;
+ };
+
+namespace ba = boost::algorithm;
+
+void test_any ()
+{
+// Note: The literal values here are tested against directly, careful if you change them:
+ int some_numbers[] = { 1, 5, 0, 18, 10 };
+ std::vector<int> vi(some_numbers, some_numbers + 5);
+ std::list<int> li(vi.begin(), vi.end ());
+
+ int some_letters[] = { 'a', 'q', 'n', 'y', 'n' };
+ std::vector<char> vc(some_letters, some_letters + 5);
+
+ BOOST_CHECK ( ba::any_of_equal ( vi, 1 ));
+ BOOST_CHECK ( ba::any_of ( vi, is_<int> ( 1 )));
+ BOOST_CHECK ( ba::any_of_equal ( vi.begin(), vi.end(), 1 ));
+ BOOST_CHECK ( ba::any_of ( vi.begin(), vi.end(), is_<int> ( 1 )));
+
+ BOOST_CHECK (!ba::any_of_equal ( vi, 9 ));
+ BOOST_CHECK (!ba::any_of ( vi, is_<int> ( 9 )));
+ BOOST_CHECK (!ba::any_of_equal ( vi.begin(), vi.end(), 9 ));
+ BOOST_CHECK (!ba::any_of ( vi.begin(), vi.end(), is_<int> ( 9 )));
+
+ BOOST_CHECK ( ba::any_of_equal ( vi, 10 ));
+ BOOST_CHECK ( ba::any_of ( vi, is_<int> ( 10 )));
+ BOOST_CHECK (!ba::any_of_equal ( vi, 4 ));
+ BOOST_CHECK (!ba::any_of ( vi, is_<int> ( 4 )));
+
+ BOOST_CHECK (!ba::any_of_equal ( vi.end(), vi.end(), 0 ));
+ BOOST_CHECK (!ba::any_of ( vi.end(), vi.end(), is_<int> ( 0 )));
+
+// 5 is not in { 0, 18, 10 }, but 10 is
+ BOOST_CHECK ( ba::any_of_equal ( vi.begin() + 2, vi.end(), 10 ));
+ BOOST_CHECK ( ba::any_of ( vi.begin() + 2, vi.end(), is_<int> ( 10 )));
+
+ BOOST_CHECK (!ba::any_of_equal ( vi.begin() + 2, vi.end(), 5 ));
+ BOOST_CHECK (!ba::any_of ( vi.begin() + 2, vi.end(), is_<int> ( 5 )));
+
+// 18 is not in { 1, 5, 0 }, but 5 is
+ BOOST_CHECK ( ba::any_of_equal ( vi.begin(), vi.begin() + 3, 5 ));
+ BOOST_CHECK ( ba::any_of ( vi.begin(), vi.begin() + 3, is_<int> ( 5 )));
+
+ BOOST_CHECK (!ba::any_of_equal ( vi.begin(), vi.begin() + 3, 18 ));
+ BOOST_CHECK (!ba::any_of ( vi.begin(), vi.begin() + 3, is_<int> ( 18 )));
+
+ BOOST_CHECK ( ba::any_of_equal ( vc, 'q' ));
+ BOOST_CHECK ( ba::any_of ( vc, is_<char> ( 'q' )));
+
+ BOOST_CHECK (!ba::any_of_equal ( vc, '!' ));
+ BOOST_CHECK (!ba::any_of ( vc, is_<char> ( '!' )));
+
+ BOOST_CHECK ( ba::any_of_equal ( vc, 'n' ));
+ BOOST_CHECK ( ba::any_of ( vc, is_<char> ( 'n' )));
+
+ BOOST_CHECK (!ba::any_of_equal ( vi.begin(), vi.begin(), 1 ));
+ BOOST_CHECK (!ba::any_of_equal ( vc.begin(), vc.begin(), 'a' ));
+ BOOST_CHECK (!ba::any_of ( vi.begin(), vi.begin(), is_<int> ( 1 )));
+ BOOST_CHECK (!ba::any_of ( vc.begin(), vc.begin(), is_<char> ( 'a' )));
+
+ BOOST_CHECK ( ba::any_of_equal ( li, 1 ));
+ BOOST_CHECK ( ba::any_of ( li, is_<int> ( 1 )));
+ BOOST_CHECK ( ba::any_of_equal ( li.begin(), li.end(), 1 ));
+ BOOST_CHECK ( ba::any_of ( li.begin(), li.end(), is_<int> ( 1 )));
+
+ std::list<int>::iterator l_iter = li.begin ();
+ l_iter++; l_iter++; l_iter++;
+ BOOST_CHECK ( ba::any_of_equal ( li.begin(), l_iter, 5 ));
+ BOOST_CHECK ( ba::any_of ( li.begin(), l_iter, is_<int> ( 5 )));
+ BOOST_CHECK (!ba::any_of_equal ( li.begin(), l_iter, 18 ));
+ BOOST_CHECK (!ba::any_of ( li.begin(), l_iter, is_<int> ( 18 )));
+}
+
+
+int test_main( int , char* [] )
+{
+ test_any ();
+ return 0;
+}
Added: trunk/libs/algorithm/test/copy_n_test1.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/algorithm/test/copy_n_test1.cpp 2012-02-18 02:17:39 EST (Sat, 18 Feb 2012)
@@ -0,0 +1,85 @@
+/*
+ Copyright (c) Marshall Clow 2011-2012.
+
+ 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)
+
+ For more information, see http://www.boost.org
+*/
+
+#include <boost/config.hpp>
+#include <boost/algorithm/cxx11/copy_n.hpp>
+#include <boost/test/included/test_exec_monitor.hpp>
+
+#include <string>
+#include <iostream>
+#include <vector>
+#include <list>
+
+namespace ba = boost::algorithm;
+// namespace ba = boost;
+
+template <typename Container>
+void test_sequence ( Container const &c ) {
+
+ typedef typename Container::value_type value_type;
+ std::vector<value_type> v;
+
+// Copy zero elements
+ v.clear ();
+ ba::copy_n ( c.begin (), 0, back_inserter ( v ));
+ BOOST_CHECK ( v.size () == 0 );
+ ba::copy_n ( c.begin (), 0U, back_inserter ( v ));
+ BOOST_CHECK ( v.size () == 0 );
+
+ if ( c.size () > 0 ) {
+ // Just one element
+ v.clear ();
+ ba::copy_n ( c.begin (), 1, back_inserter ( v ));
+ BOOST_CHECK ( v.size () == 1 );
+ BOOST_CHECK ( v[0] == *c.begin ());
+
+ v.clear ();
+ ba::copy_n ( c.begin (), 1U, back_inserter ( v ));
+ BOOST_CHECK ( v.size () == 1 );
+ BOOST_CHECK ( v[0] == *c.begin ());
+
+ // Half the elements
+ v.clear ();
+ ba::copy_n ( c.begin (), c.size () / 2, back_inserter ( v ));
+ BOOST_CHECK ( v.size () == c.size () / 2);
+ BOOST_CHECK ( std::equal ( v.begin (), v.end (), c.begin ()));
+
+ // Half the elements + 1
+ v.clear ();
+ ba::copy_n ( c.begin (), c.size () / 2 + 1, back_inserter ( v ));
+ BOOST_CHECK ( v.size () == c.size () / 2 + 1 );
+ BOOST_CHECK ( std::equal ( v.begin (), v.end (), c.begin ()));
+
+ // All the elements
+ v.clear ();
+ ba::copy_n ( c.begin (), c.size (), back_inserter ( v ));
+ BOOST_CHECK ( v.size () == c.size ());
+ BOOST_CHECK ( std::equal ( v.begin (), v.end (), c.begin ()));
+ }
+ }
+
+
+void test_sequence1 () {
+ std::vector<int> v;
+ for ( int i = 5; i < 15; ++i )
+ v.push_back ( i );
+ test_sequence ( v );
+
+ std::list<int> l;
+ for ( int i = 25; i > 15; --i )
+ l.push_back ( i );
+ test_sequence ( l );
+ }
+
+
+int test_main( int , char* [] )
+{
+ test_sequence1 ();
+ return 0;
+}
Added: trunk/libs/algorithm/test/find_if_not_test1.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/algorithm/test/find_if_not_test1.cpp 2012-02-18 02:17:39 EST (Sat, 18 Feb 2012)
@@ -0,0 +1,90 @@
+/*
+ Copyright (c) Marshall Clow 2011-2012.
+
+ 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)
+
+ For more information, see http://www.boost.org
+*/
+
+#include <iostream>
+
+#include <boost/config.hpp>
+#include <boost/algorithm/cxx11/find_if_not.hpp>
+#include <boost/test/included/test_exec_monitor.hpp>
+
+#include <string>
+#include <vector>
+#include <list>
+
+namespace ba = boost::algorithm;
+// namespace ba = boost;
+
+template <typename Container>
+typename Container::iterator offset_to_iter ( Container &v, int offset ) {
+ typename Container::iterator retval;
+
+ if ( offset >= 0 ) {
+ retval = v.begin ();
+ std::advance ( retval, offset );
+ }
+ else {
+ retval = v.end ();
+ std::advance ( retval, offset + 1 );
+ }
+ return retval;
+ }
+
+template <typename Container, typename Predicate>
+void test_sequence ( Container &v, Predicate comp, int expected ) {
+ typename Container::iterator res, exp;
+
+ res = ba::find_if_not ( v.begin (), v.end (), comp );
+ exp = offset_to_iter ( v, expected );
+ std::cout << "Expected(1): " << std::distance ( v.begin (), exp )
+ << ", got: " << std::distance ( v.begin (), res ) << std::endl;
+ BOOST_CHECK ( exp == res );
+ }
+
+template <typename T>
+struct less_than {
+public:
+ less_than ( T foo ) : val ( foo ) {}
+ less_than ( const less_than &rhs ) : val ( rhs.val ) {}
+
+ bool operator () ( const T &v ) const { return v < val; }
+private:
+ less_than ();
+ less_than operator = ( const less_than &rhs );
+ T val;
+ };
+
+
+void test_sequence1 () {
+ std::vector<int> v;
+
+ v.clear ();
+ for ( int i = 5; i < 15; ++i )
+ v.push_back ( i );
+ test_sequence ( v, less_than<int>(3), 0 ); // no elements
+ test_sequence ( v, less_than<int>(6), 1 ); // only the first element
+ test_sequence ( v, less_than<int>(10), 5 );
+ test_sequence ( v, less_than<int>(99), -1 ); // all elements satisfy
+
+// With bidirectional iterators.
+ std::list<int> l;
+ for ( int i = 5; i < 15; ++i )
+ l.push_back ( i );
+ test_sequence ( l, less_than<int>(3), 0 ); // no elements
+ test_sequence ( l, less_than<int>(6), 1 ); // only the first element
+ test_sequence ( l, less_than<int>(10), 5 );
+ test_sequence ( l, less_than<int>(99), -1 ); // all elements satisfy
+
+ }
+
+
+int test_main( int , char* [] )
+{
+ test_sequence1 ();
+ return 0;
+}
Added: trunk/libs/algorithm/test/iota_test1.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/algorithm/test/iota_test1.cpp 2012-02-18 02:17:39 EST (Sat, 18 Feb 2012)
@@ -0,0 +1,79 @@
+/*
+ Copyright (c) Marshall Clow 2011-2012.
+
+ 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)
+
+ For more information, see http://www.boost.org
+*/
+
+#include <boost/config.hpp>
+#include <boost/algorithm/cxx11/iota.hpp>
+#include <boost/test/included/test_exec_monitor.hpp>
+
+#include <iostream>
+#include <string>
+#include <vector>
+#include <list>
+
+// Test to make sure a sequence is "correctly formed"; i.e, ascending by one
+template <typename Iterator, typename T>
+bool test_iota_results ( Iterator first, Iterator last, T initial_value ) {
+ if ( first == last ) return true;
+ if ( initial_value != *first ) return false;
+ Iterator prev = first;
+ while ( ++first != last ) {
+ if (( *first - *prev ) != 1 )
+ return false;
+ prev = first;
+ }
+ return true;
+ }
+
+template <typename Range, typename T>
+bool test_iota_results ( const Range &r, T initial_value ) {
+ return test_iota_results (boost::begin (r), boost::end (r), initial_value );
+}
+
+
+void test_ints () {
+ std::vector<int> v;
+ std::list<int> l;
+
+ v.clear (); v.reserve ( 10 );
+ boost::algorithm::iota ( v.begin (), v.end (), 23 );
+ BOOST_CHECK ( test_iota_results ( v.begin (), v.end (), 23 ));
+
+ v.clear (); v.reserve ( 19 );
+ boost::algorithm::iota ( v, 18 );
+ BOOST_CHECK ( test_iota_results ( v, 18 ));
+
+ v.clear ();
+ boost::algorithm::iota_n ( std::back_inserter(v), 99, 20 );
+ BOOST_CHECK ( test_iota_results ( v, 99 ));
+
+/*
+ l.clear (); l.reserve ( 5 );
+ boost::algorithm::iota ( l.begin (), l.end (), 123 );
+ BOOST_CHECK ( test_iota_results ( l.begin (), l.end (), 123 ));
+
+ l.clear (); l.reserve ( 9 );
+ boost::algorithm::iota ( l.begin (), l.end (), 87 );
+ BOOST_CHECK ( test_iota_results ( l.begin (), l.end (), 87 ));
+*/
+
+ l.clear ();
+ boost::algorithm::iota_n ( std::back_inserter(l), 99, 20 );
+ BOOST_CHECK ( test_iota_results ( l, 99 ));
+
+ l.clear ();
+ boost::algorithm::iota_n ( std::front_inserter(l), 123, 20 );
+ BOOST_CHECK ( test_iota_results ( l.rbegin (), l.rend (), 123 ));
+ }
+
+
+int test_main( int , char* [] )
+{
+ test_ints ();
+ return 0;
+}
Added: trunk/libs/algorithm/test/is_partitioned_test1.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/algorithm/test/is_partitioned_test1.cpp 2012-02-18 02:17:39 EST (Sat, 18 Feb 2012)
@@ -0,0 +1,63 @@
+/*
+ Copyright (c) Marshall Clow 2011-2012.
+
+ 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)
+
+ For more information, see http://www.boost.org
+*/
+
+#include <iostream>
+
+#include <boost/config.hpp>
+#include <boost/algorithm/cxx11/is_partitioned.hpp>
+#include <boost/test/included/test_exec_monitor.hpp>
+
+#include <string>
+#include <vector>
+#include <list>
+
+namespace ba = boost::algorithm;
+// namespace ba = boost;
+
+template <typename T>
+struct less_than {
+public:
+ less_than ( T foo ) : val ( foo ) {}
+ less_than ( const less_than &rhs ) : val ( rhs.val ) {}
+
+ bool operator () ( const T &v ) const { return v < val; }
+private:
+ less_than ();
+ less_than operator = ( const less_than &rhs );
+ T val;
+ };
+
+
+void test_sequence1 () {
+ std::vector<int> v;
+
+ v.clear ();
+ for ( int i = 5; i < 15; ++i )
+ v.push_back ( i );
+ BOOST_CHECK ( ba::is_partitioned ( v, less_than<int>(3))); // no elements
+ BOOST_CHECK ( ba::is_partitioned ( v, less_than<int>(6))); // only the first element
+ BOOST_CHECK ( ba::is_partitioned ( v, less_than<int>(10))); // in the middle somewhere
+ BOOST_CHECK ( ba::is_partitioned ( v, less_than<int>(99))); // all elements satisfy
+
+// With bidirectional iterators.
+ std::list<int> l;
+ for ( int i = 5; i < 15; ++i )
+ l.push_back ( i );
+ BOOST_CHECK ( ba::is_partitioned ( l.begin (), l.end (), less_than<int>(3))); // no elements
+ BOOST_CHECK ( ba::is_partitioned ( l.begin (), l.end (), less_than<int>(6))); // only the first element
+ BOOST_CHECK ( ba::is_partitioned ( l.begin (), l.end (), less_than<int>(10))); // in the middle somewhere
+ BOOST_CHECK ( ba::is_partitioned ( l.begin (), l.end (), less_than<int>(99))); // all elements satisfy
+ }
+
+
+int test_main( int , char* [] )
+{
+ test_sequence1 ();
+ return 0;
+}
Added: trunk/libs/algorithm/test/is_permutation_test1.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/algorithm/test/is_permutation_test1.cpp 2012-02-18 02:17:39 EST (Sat, 18 Feb 2012)
@@ -0,0 +1,49 @@
+/*
+ Copyright (c) Marshall Clow 2011-2012.
+
+ 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)
+
+ For more information, see http://www.boost.org
+*/
+
+#include <iostream>
+
+#include <boost/config.hpp>
+#include <boost/algorithm/cxx11/is_permutation.hpp>
+#include <boost/test/included/test_exec_monitor.hpp>
+
+#include <string>
+#include <vector>
+#include <list>
+
+namespace ba = boost::algorithm;
+// namespace ba = boost;
+
+void test_sequence1 () {
+ std::vector<int> v, v1;
+
+ v.clear ();
+ for ( std::size_t i = 5; i < 15; ++i )
+ v.push_back ( i );
+ v1 = v;
+ BOOST_CHECK ( ba::is_permutation ( v.begin (), v.end (), v.begin ())); // better be a permutation of itself!
+ BOOST_CHECK ( ba::is_permutation ( v.begin (), v.end (), v1.begin ()));
+
+// With bidirectional iterators.
+ std::list<int> l;
+ std::copy ( v.begin (), v.end (), std::back_inserter ( l ));
+ BOOST_CHECK ( ba::is_permutation ( l.begin (), l.end (), l.begin ())); // better be a permutation of itself!
+ BOOST_CHECK ( ba::is_permutation ( l.begin (), l.end (), v1.begin ()));
+ for ( std::size_t i = 0; i < l.size (); ++i ) {
+ l.push_back ( *l.begin ()); l.pop_front (); // rotation
+ BOOST_CHECK ( ba::is_permutation ( l.begin (), l.end (), v1.begin ()));
+ }
+ }
+
+
+int test_main( int , char* [] )
+{
+ test_sequence1 ();
+ return 0;
+}
Added: trunk/libs/algorithm/test/none_of_test.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/algorithm/test/none_of_test.cpp 2012-02-18 02:17:39 EST (Sat, 18 Feb 2012)
@@ -0,0 +1,96 @@
+/*
+ Copyright (c) Marshall Clow 2010-2012.
+
+ 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)
+
+ For more information, see http://www.boost.org
+*/
+
+#include <boost/config.hpp>
+#include <boost/algorithm/cxx11/none_of.hpp>
+#include <boost/test/included/test_exec_monitor.hpp>
+
+#include <functional>
+#include <vector>
+#include <list>
+
+template<typename T>
+struct is_ : public std::unary_function<T, bool> {
+ is_ ( T v ) : val_ ( v ) {}
+ ~is_ () {}
+ bool operator () ( T comp ) const { return val_ == comp; }
+private:
+ is_ (); // need a value
+
+ T val_;
+ };
+
+namespace ba = boost::algorithm;
+
+void test_none()
+{
+// Note: The literal values here are tested against directly, careful if you change them:
+ int some_numbers[] = { 1, 5, 0, 18, 1 };
+ std::vector<int> vi(some_numbers, some_numbers + 5);
+ std::list<int> li(vi.begin(), vi.end ());
+
+ int some_letters[] = { 'a', 'q', 'n', 'y', 'n' };
+ std::vector<char> vc(some_letters, some_letters + 5);
+
+ BOOST_CHECK ( ba::none_of_equal ( vi, 100 ));
+ BOOST_CHECK ( ba::none_of ( vi, is_<int> ( 100 )));
+ BOOST_CHECK ( ba::none_of_equal ( vi.begin(), vi.end(), 100 ));
+ BOOST_CHECK ( ba::none_of ( vi.begin(), vi.end(), is_<int> ( 100 )));
+
+ BOOST_CHECK (!ba::none_of_equal ( vi, 1 ));
+ BOOST_CHECK (!ba::none_of ( vi, is_<int> ( 1 )));
+ BOOST_CHECK (!ba::none_of_equal ( vi.begin(), vi.end(), 1 ));
+ BOOST_CHECK (!ba::none_of ( vi.begin(), vi.end(), is_<int> ( 1 )));
+
+ BOOST_CHECK ( ba::none_of_equal ( vi.end(), vi.end(), 0 ));
+ BOOST_CHECK ( ba::none_of ( vi.end(), vi.end(), is_<int> ( 0 )));
+
+// 5 is not in { 0, 18, 1 }, but 1 is
+ BOOST_CHECK ( ba::none_of_equal ( vi.begin() + 2, vi.end(), 5 ));
+ BOOST_CHECK ( ba::none_of ( vi.begin() + 2, vi.end(), is_<int> ( 5 )));
+ BOOST_CHECK (!ba::none_of_equal ( vi.begin() + 2, vi.end(), 1 ));
+ BOOST_CHECK (!ba::none_of ( vi.begin() + 2, vi.end(), is_<int> ( 1 )));
+
+// 18 is not in { 1, 5, 0 }, but 5 is
+ BOOST_CHECK ( ba::none_of_equal ( vi.begin(), vi.begin() + 3, 18 ));
+ BOOST_CHECK ( ba::none_of ( vi.begin(), vi.begin() + 3, is_<int> ( 18 )));
+ BOOST_CHECK (!ba::none_of_equal ( vi.begin(), vi.begin() + 3, 5 ));
+ BOOST_CHECK (!ba::none_of ( vi.begin(), vi.begin() + 3, is_<int> ( 5 )));
+
+ BOOST_CHECK ( ba::none_of_equal ( vc, 'z' ));
+ BOOST_CHECK ( ba::none_of ( vc, is_<char> ( 'z' )));
+
+ BOOST_CHECK (!ba::none_of_equal ( vc, 'a' ));
+ BOOST_CHECK (!ba::none_of ( vc, is_<char> ( 'a' )));
+
+ BOOST_CHECK (!ba::none_of_equal ( vc, 'n' ));
+ BOOST_CHECK (!ba::none_of ( vc, is_<char> ( 'n' )));
+
+ BOOST_CHECK ( ba::none_of_equal ( vi.begin(), vi.begin(), 1 ));
+ BOOST_CHECK ( ba::none_of_equal ( vc.begin(), vc.begin(), 'a' ));
+ BOOST_CHECK ( ba::none_of ( vi.begin(), vi.begin(), is_<int> ( 1 )));
+ BOOST_CHECK ( ba::none_of ( vc.begin(), vc.begin(), is_<char> ( 'a' )));
+
+ BOOST_CHECK ( ba::none_of_equal ( li, 100 ));
+ BOOST_CHECK ( ba::none_of ( li, is_<int> ( 100 )));
+ BOOST_CHECK ( ba::none_of_equal ( li.begin(), li.end(), 100 ));
+ BOOST_CHECK ( ba::none_of ( li.begin(), li.end(), is_<int> ( 100 )));
+
+ std::list<int>::iterator l_iter = li.begin ();
+ l_iter++; l_iter++; l_iter++;
+ BOOST_CHECK ( ba::none_of_equal ( li.begin(), l_iter, 18 ));
+ BOOST_CHECK ( ba::none_of ( li.begin(), l_iter, is_<int> ( 18 )));
+ BOOST_CHECK (!ba::none_of ( li.begin(), l_iter, is_<int> ( 5 )));
+}
+
+int test_main( int , char* [] )
+{
+ test_none();
+ return 0;
+}
Added: trunk/libs/algorithm/test/one_of_test.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/algorithm/test/one_of_test.cpp 2012-02-18 02:17:39 EST (Sat, 18 Feb 2012)
@@ -0,0 +1,101 @@
+/*
+ Copyright (c) Marshall Clow 2008-2012.
+
+ 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)
+
+ For more information, see http://www.boost.org
+*/
+
+#include <boost/config.hpp>
+#include <boost/algorithm/cxx11/one_of.hpp>
+#include <boost/test/included/test_exec_monitor.hpp>
+
+#include <functional>
+#include <vector>
+#include <list>
+
+template<typename T>
+struct is_ : public std::unary_function<T, bool> {
+ is_ ( T v ) : val_ ( v ) {}
+ ~is_ () {}
+ bool operator () ( T comp ) const { return val_ == comp; }
+private:
+ is_ (); // need a value
+
+ T val_;
+ };
+
+namespace ba = boost::algorithm;
+
+void test_one ()
+{
+// Note: The literal values here are tested against directly, careful if you change them:
+ int some_numbers[] = { 1, 1, 2, 3, 5 };
+ std::vector<int> vi(some_numbers, some_numbers + 5);
+ std::list<int> li(vi.begin(), vi.end ());
+
+ int some_letters[] = { 'a', 'q', 'n', 'y', 'n' };
+ std::vector<char> vc(some_letters, some_letters + 5);
+
+ BOOST_CHECK (!ba::one_of_equal ( vi, 1 ));
+ BOOST_CHECK (!ba::one_of ( vi, is_<int> ( 1 )));
+ BOOST_CHECK (!ba::one_of_equal ( vi.begin(), vi.end(), 1 ));
+ BOOST_CHECK (!ba::one_of ( vi.begin(), vi.end(), is_<int> ( 1 )));
+
+ BOOST_CHECK (!ba::one_of_equal ( vi, 0 ));
+ BOOST_CHECK (!ba::one_of ( vi, is_<int> ( 0 )));
+ BOOST_CHECK (!ba::one_of_equal ( vi.begin(), vi.end(), 0 ));
+ BOOST_CHECK (!ba::one_of ( vi.begin(), vi.end(), is_<int> ( 0 )));
+
+ BOOST_CHECK ( ba::one_of_equal ( vi, 2 ));
+ BOOST_CHECK ( ba::one_of ( vi, is_<int> ( 2 )));
+ BOOST_CHECK ( ba::one_of_equal ( vi.begin(), vi.end(), 2 ));
+ BOOST_CHECK ( ba::one_of ( vi.begin(), vi.end(), is_<int> ( 2 )));
+
+// Check for a match at the end
+ BOOST_CHECK ( ba::one_of_equal ( vi, 5 ));
+ BOOST_CHECK ( ba::one_of ( vi, is_<int> ( 5 )));
+ BOOST_CHECK ( ba::one_of_equal ( vi.begin(), vi.end(), 5 ));
+ BOOST_CHECK ( ba::one_of ( vi.begin(), vi.end(), is_<int> ( 5 )));
+
+ BOOST_CHECK ( ba::one_of_equal ( vi.begin() + 1, vi.end(), 1 ));
+ BOOST_CHECK ( ba::one_of ( vi.begin() + 1, vi.end(), is_<int> ( 1 )));
+
+ BOOST_CHECK ( ba::one_of_equal ( vc.begin() + 1, vc.begin() + 2, 'q' ));
+ BOOST_CHECK ( ba::one_of ( vc.begin() + 1, vc.begin() + 2, is_<char> ( 'q' )));
+
+ BOOST_CHECK (!ba::one_of_equal ( vc, '!' ));
+ BOOST_CHECK (!ba::one_of ( vc, is_<char> ( '!' )));
+
+ BOOST_CHECK (!ba::one_of_equal ( vc, 'n' ));
+ BOOST_CHECK (!ba::one_of ( vc, is_<char> ( 'n' )));
+
+// Empty range check
+ BOOST_CHECK (!ba::one_of_equal ( vi.begin(), vi.begin(), 1 ));
+ BOOST_CHECK (!ba::one_of_equal ( vc.begin(), vc.begin(), 'a' ));
+ BOOST_CHECK (!ba::one_of ( vi.begin(), vi.begin(), is_<int> ( 1 )));
+ BOOST_CHECK (!ba::one_of ( vc.begin(), vc.begin(), is_<char> ( 'a' )));
+
+ BOOST_CHECK (!ba::one_of_equal ( li, 1 ));
+ BOOST_CHECK (!ba::one_of ( li, is_<int> ( 1 )));
+ BOOST_CHECK (!ba::one_of_equal ( li.begin(), li.end(), 1 ));
+ BOOST_CHECK (!ba::one_of ( li.begin(), li.end(), is_<int> ( 1 )));
+
+ std::list<int>::iterator l_iter = li.begin ();
+ l_iter++; l_iter++; l_iter++;
+ BOOST_CHECK (!ba::one_of_equal ( li.begin(), l_iter, 1 ));
+ BOOST_CHECK (!ba::one_of ( li.begin(), l_iter, is_<int> ( 1 )));
+ BOOST_CHECK ( ba::one_of_equal ( li.begin(), l_iter, 2 ));
+ BOOST_CHECK ( ba::one_of ( li.begin(), l_iter, is_<int> ( 2 )));
+ BOOST_CHECK (!ba::one_of_equal ( li.begin(), l_iter, 3 ));
+ BOOST_CHECK (!ba::one_of ( li.begin(), l_iter, is_<int> ( 3 )));
+
+}
+
+
+int test_main( int , char* [] )
+{
+ test_one ();
+ return 0;
+}
Added: trunk/libs/algorithm/test/ordered_test.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/algorithm/test/ordered_test.cpp 2012-02-18 02:17:39 EST (Sat, 18 Feb 2012)
@@ -0,0 +1,127 @@
+// Copyright (c) 2010 Nuovation System Designs, LLC
+// Grant Erickson <gerickson_at_[hidden]>
+//
+// Reworked by Marshall Clow; August 2010
+//
+// 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)
+//
+// See http://www.boost.org/ for latest version.
+
+#include <algorithm>
+#include <iostream>
+
+#include <boost/algorithm/cxx11/ordered.hpp>
+#include <boost/test/included/test_exec_monitor.hpp>
+
+using namespace boost;
+
+/* Preprocessor Defines */
+
+#define elementsof(v) (sizeof (v) / sizeof (v[0]))
+#define a_begin(v) (&v[0])
+#define a_end(v) (v + elementsof (v))
+#define a_range(v) v
+#define b_e(v) a_begin(v),a_end(v)
+
+namespace ba = boost::algorithm;
+
+static void
+test_ordered(void)
+{
+ const int strictlyIncreasingValues[] = { 1, 2, 3, 4, 5 };
+ const int strictlyDecreasingValues[] = { 9, 8, 7, 6, 5 };
+ const int increasingValues[] = { 1, 2, 2, 2, 5 };
+ const int decreasingValues[] = { 9, 7, 7, 7, 5 };
+ const int randomValues[] = { 3, 6, 1, 2, 7 };
+ const int constantValues[] = { 7, 7, 7, 7, 7 };
+ int nonConstantArray[] = { 7, 7, 7, 7, 7 };
+ const int inOrderUntilTheEnd [] = { 0, 1, 2, 3, 4, 5, 6, 7, 6 };
+
+ // Test a strictly increasing sequence
+ BOOST_CHECK ( ba::is_strictly_increasing (b_e(strictlyIncreasingValues)));
+ BOOST_CHECK ( ba::is_increasing (b_e(strictlyIncreasingValues)));
+ BOOST_CHECK ( !ba::is_strictly_decreasing (b_e(strictlyIncreasingValues)));
+ BOOST_CHECK ( !ba::is_decreasing (b_e(strictlyIncreasingValues)));
+
+ BOOST_CHECK ( ba::is_strictly_increasing (a_range(strictlyIncreasingValues)));
+ BOOST_CHECK ( ba::is_increasing (a_range(strictlyIncreasingValues)));
+ BOOST_CHECK ( !ba::is_strictly_decreasing (a_range(strictlyIncreasingValues)));
+ BOOST_CHECK ( !ba::is_decreasing (a_range(strictlyIncreasingValues)));
+
+ // Test a strictly decreasing sequence
+ BOOST_CHECK ( !ba::is_strictly_increasing (b_e(strictlyDecreasingValues)));
+ BOOST_CHECK ( !ba::is_increasing (b_e(strictlyDecreasingValues)));
+ BOOST_CHECK ( ba::is_strictly_decreasing (b_e(strictlyDecreasingValues)));
+ BOOST_CHECK ( ba::is_decreasing (b_e(strictlyDecreasingValues)));
+
+ // Test an increasing sequence
+ BOOST_CHECK ( !ba::is_strictly_increasing (b_e(increasingValues)));
+ BOOST_CHECK ( ba::is_increasing (b_e(increasingValues)));
+ BOOST_CHECK ( !ba::is_strictly_decreasing (b_e(increasingValues)));
+ BOOST_CHECK ( !ba::is_decreasing (b_e(increasingValues)));
+
+ // Test a decreasing sequence
+ BOOST_CHECK ( !ba::is_strictly_increasing (b_e(decreasingValues)));
+ BOOST_CHECK ( !ba::is_increasing (b_e(decreasingValues)));
+ BOOST_CHECK ( !ba::is_strictly_decreasing (b_e(decreasingValues)));
+ BOOST_CHECK ( ba::is_decreasing (b_e(decreasingValues)));
+
+ // Test a random sequence
+ BOOST_CHECK ( !ba::is_strictly_increasing (b_e(randomValues)));
+ BOOST_CHECK ( !ba::is_increasing (b_e(randomValues)));
+ BOOST_CHECK ( !ba::is_strictly_decreasing (b_e(randomValues)));
+ BOOST_CHECK ( !ba::is_decreasing (b_e(randomValues)));
+
+ // Test a constant sequence
+ BOOST_CHECK ( !ba::is_strictly_increasing (b_e(constantValues)));
+ BOOST_CHECK ( ba::is_increasing (b_e(constantValues)));
+ BOOST_CHECK ( !ba::is_strictly_decreasing (b_e(constantValues)));
+ BOOST_CHECK ( ba::is_decreasing (b_e(constantValues)));
+
+ // Test an empty sequence
+ BOOST_CHECK ( ba::is_strictly_increasing (strictlyIncreasingValues, strictlyIncreasingValues));
+ BOOST_CHECK ( ba::is_increasing (strictlyIncreasingValues, strictlyIncreasingValues));
+ BOOST_CHECK ( ba::is_strictly_decreasing (strictlyIncreasingValues, strictlyIncreasingValues));
+ BOOST_CHECK ( ba::is_decreasing (strictlyIncreasingValues, strictlyIncreasingValues));
+
+ // Test a one-element sequence
+ BOOST_CHECK ( ba::is_strictly_increasing (strictlyIncreasingValues, strictlyIncreasingValues+1));
+ BOOST_CHECK ( ba::is_increasing (strictlyIncreasingValues, strictlyIncreasingValues+1));
+ BOOST_CHECK ( ba::is_strictly_decreasing (strictlyIncreasingValues, strictlyIncreasingValues+1));
+ BOOST_CHECK ( ba::is_decreasing (strictlyIncreasingValues, strictlyIncreasingValues+1));
+
+ // Test a two-element sequence
+ BOOST_CHECK ( ba::is_strictly_increasing (strictlyIncreasingValues, strictlyIncreasingValues+2));
+ BOOST_CHECK ( ba::is_increasing (strictlyIncreasingValues, strictlyIncreasingValues+2));
+ BOOST_CHECK ( !ba::is_strictly_decreasing (strictlyIncreasingValues, strictlyIncreasingValues+2));
+ BOOST_CHECK ( !ba::is_decreasing (strictlyIncreasingValues, strictlyIncreasingValues+2));
+
+ // Test underlying routines
+ BOOST_CHECK ( ba::is_sorted_until ( b_e(strictlyIncreasingValues), std::less<int>()) == a_end(strictlyIncreasingValues));
+ BOOST_CHECK ( ba::is_sorted_until ( a_range(strictlyIncreasingValues), std::less<int>()) == boost::end(strictlyIncreasingValues));
+
+ BOOST_CHECK ( ba::is_sorted_until ( b_e(nonConstantArray), std::less<int>()) != a_end(nonConstantArray));
+ BOOST_CHECK ( ba::is_sorted_until ( a_range(nonConstantArray), std::less<int>()) != boost::end(nonConstantArray));
+
+ BOOST_CHECK ( ba::is_sorted_until ( b_e(randomValues), std::less<int>()) == &randomValues[2] );
+ BOOST_CHECK ( ba::is_sorted_until ( a_range(randomValues), std::less<int>()) == &randomValues[2] );
+
+ BOOST_CHECK ( ba::is_sorted_until ( b_e(randomValues), std::less<int>()) == &randomValues[2] );
+ BOOST_CHECK ( ba::is_sorted_until ( a_range(randomValues), std::less<int>()) == &randomValues[2] );
+
+ BOOST_CHECK ( ba::is_sorted_until ( a_range(inOrderUntilTheEnd), std::less<int>()) == &inOrderUntilTheEnd[8] );
+
+// For zero and one element collections, the comparison predicate should never be called
+ BOOST_CHECK ( ba::is_sorted_until ( a_begin(randomValues), a_begin(randomValues), std::equal_to<int>()) == a_begin(randomValues));
+ BOOST_CHECK ( ba::is_sorted_until ( a_begin(randomValues), a_begin(randomValues) + 1, std::equal_to<int>()) == a_begin(randomValues) + 1);
+
+}
+
+int test_main( int, char * [] )
+{
+ test_ordered ();
+
+ return 0;
+}
Added: trunk/libs/algorithm/test/partition_copy_test1.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/algorithm/test/partition_copy_test1.cpp 2012-02-18 02:17:39 EST (Sat, 18 Feb 2012)
@@ -0,0 +1,87 @@
+/*
+ Copyright (c) Marshall Clow 2011-2012.
+
+ 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)
+
+ For more information, see http://www.boost.org
+*/
+
+#include <iostream>
+
+#include <boost/config.hpp>
+#include <boost/algorithm/cxx11/partition_copy.hpp>
+#include <boost/test/included/test_exec_monitor.hpp>
+
+#include <boost/algorithm/cxx11/all_of.hpp>
+#include <boost/algorithm/cxx11/none_of.hpp>
+#include <string>
+#include <vector>
+#include <list>
+
+namespace ba = boost::algorithm;
+// namespace ba = boost;
+
+template <typename Container, typename Predicate>
+void test_sequence ( const Container &c, Predicate comp ) {
+ std::vector<typename Container::value_type> v1, v2;
+
+ v1.clear (); v2.clear ();
+ ba::partition_copy ( c.begin (), c.end (),
+ std::back_inserter (v1), std::back_inserter (v2), comp );
+// std::cout << "Sizes(1): " << c.size () << " -> { " << v1.size () << ", " << v2.size () << " }" << std::endl;
+ BOOST_CHECK ( v1.size () + v2.size () == c.size ());
+ BOOST_CHECK ( ba::all_of ( v1.begin (), v1.end (), comp ));
+ BOOST_CHECK ( ba::none_of ( v2.begin (), v2.end (), comp ));
+
+ v1.clear (); v2.clear ();
+ ba::partition_copy ( c, std::back_inserter (v1), std::back_inserter ( v2 ), comp );
+// std::cout << "Sizes(2): " << c.size () << " -> { " << v1.size () << ", " << v2.size () << " }" << std::endl;
+ BOOST_CHECK ( v1.size () + v2.size () == c.size ());
+ BOOST_CHECK ( ba::all_of ( v1, comp ));
+ BOOST_CHECK ( ba::none_of ( v2, comp ));
+ }
+
+template <typename T>
+struct less_than {
+public:
+ less_than ( T foo ) : val ( foo ) {}
+ less_than ( const less_than &rhs ) : val ( rhs.val ) {}
+
+ bool operator () ( const T &v ) const { return v < val; }
+private:
+ less_than ();
+ less_than operator = ( const less_than &rhs );
+ T val;
+ };
+
+bool is_even ( int v ) { return v % 2 == 0; }
+
+void test_sequence1 () {
+ std::vector<int> v;
+
+ v.clear ();
+ for ( int i = 5; i < 15; ++i )
+ v.push_back ( i );
+ test_sequence ( v, less_than<int>(3)); // no elements
+ test_sequence ( v, less_than<int>(6)); // only the first element
+ test_sequence ( v, less_than<int>(10));
+ test_sequence ( v, less_than<int>(99)); // all elements satisfy
+
+// With bidirectional iterators.
+ std::list<int> l;
+ for ( int i = 5; i < 16; ++i )
+ l.push_back ( i );
+ test_sequence ( l, less_than<int>(3)); // no elements
+ test_sequence ( l, less_than<int>(6)); // only the first element
+ test_sequence ( l, less_than<int>(10));
+ test_sequence ( l, less_than<int>(99)); // all elements satisfy
+
+ }
+
+
+int test_main( int , char* [] )
+{
+ test_sequence1 ();
+ return 0;
+}
Added: trunk/libs/algorithm/test/partition_point_test1.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/algorithm/test/partition_point_test1.cpp 2012-02-18 02:17:39 EST (Sat, 18 Feb 2012)
@@ -0,0 +1,98 @@
+/*
+ Copyright (c) Marshall Clow 2011-2012.
+
+ 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)
+
+ For more information, see http://www.boost.org
+*/
+
+#include <iostream>
+
+#include <boost/config.hpp>
+#include <boost/algorithm/cxx11/partition_point.hpp>
+#include <boost/test/included/test_exec_monitor.hpp>
+
+#include <string>
+#include <vector>
+#include <list>
+
+namespace ba = boost::algorithm;
+// namespace ba = boost;
+
+template <typename Container>
+typename Container::iterator offset_to_iter ( Container &v, int offset ) {
+ typename Container::iterator retval;
+
+ if ( offset >= 0 ) {
+ retval = v.begin ();
+ std::advance ( retval, offset );
+ }
+ else {
+ retval = v.end ();
+ std::advance ( retval, offset + 1 );
+ }
+ return retval;
+ }
+
+template <typename Container, typename Predicate>
+void test_sequence ( Container &v, Predicate comp, int expected ) {
+ typename Container::iterator res, exp;
+
+ res = ba::partition_point ( v.begin (), v.end (), comp );
+ exp = offset_to_iter ( v, expected );
+ std::cout << "Expected(1): " << std::distance ( v.begin (), exp )
+ << ", got: " << std::distance ( v.begin (), res ) << std::endl;
+ BOOST_CHECK ( exp == res );
+
+// Duplicate the last element; this checks for any even/odd problems
+ v.push_back ( * v.rbegin ());
+ res = ba::partition_point ( v.begin (), v.end (), comp );
+ exp = offset_to_iter ( v, expected );
+ std::cout << "Expected(2): " << std::distance ( v.begin (), exp )
+ << ", got: " << std::distance ( v.begin (), res ) << std::endl;
+ BOOST_CHECK ( exp == res );
+ }
+
+template <typename T>
+struct less_than {
+public:
+ less_than ( T foo ) : val ( foo ) {}
+ less_than ( const less_than &rhs ) : val ( rhs.val ) {}
+
+ bool operator () ( const T &v ) const { return v < val; }
+private:
+ less_than ();
+ less_than operator = ( const less_than &rhs );
+ T val;
+ };
+
+
+void test_sequence1 () {
+ std::vector<int> v;
+
+ v.clear ();
+ for ( int i = 5; i < 15; ++i )
+ v.push_back ( i );
+ test_sequence ( v, less_than<int>(3), 0 ); // no elements
+ test_sequence ( v, less_than<int>(6), 1 ); // only the first element
+ test_sequence ( v, less_than<int>(10), 5 );
+ test_sequence ( v, less_than<int>(99), -1 ); // all elements satisfy
+
+// With bidirectional iterators.
+ std::list<int> l;
+ for ( int i = 5; i < 15; ++i )
+ l.push_back ( i );
+ test_sequence ( l, less_than<int>(3), 0 ); // no elements
+ test_sequence ( l, less_than<int>(6), 1 ); // only the first element
+ test_sequence ( l, less_than<int>(10), 5 );
+ test_sequence ( l, less_than<int>(99), -1 ); // all elements satisfy
+
+ }
+
+
+int test_main( int , char* [] )
+{
+ test_sequence1 ();
+ return 0;
+}