Subject: [Boost-commit] svn:boost r84389 - in trunk: boost/algorithm/cxx11 boost/algorithm/cxx14 libs/algorithm/test
From: marshall_at_[hidden]
Date: 2013-05-20 11:37:51
Author: marshall
Date: 2013-05-20 11:37:50 EDT (Mon, 20 May 2013)
New Revision: 84389
URL: http://svn.boost.org/trac/boost/changeset/84389
Log:
Better 'is_permutation' implementation, tests
Removed:
trunk/boost/algorithm/cxx14/is_permutation.hpp
Text files modified:
trunk/boost/algorithm/cxx11/is_permutation.hpp | 159 +++++++++++++++++++++----
trunk/libs/algorithm/test/equal_test.cpp | 169 ++++++++++++++-------------
trunk/libs/algorithm/test/is_permutation_test1.cpp | 87 ++++++++++++++
trunk/libs/algorithm/test/mismatch_test.cpp | 244 ++++++++++++++++++++-------------------
4 files changed, 431 insertions(+), 228 deletions(-)
Modified: trunk/boost/algorithm/cxx11/is_permutation.hpp
==============================================================================
--- trunk/boost/algorithm/cxx11/is_permutation.hpp (original)
+++ trunk/boost/algorithm/cxx11/is_permutation.hpp 2013-05-20 11:37:50 EDT (Mon, 20 May 2013)
@@ -24,10 +24,6 @@
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>
@@ -37,18 +33,82 @@
template <typename T1>
bool operator () ( const T1 &t1 ) const { return p_ ( *it_, t1 ); }
private:
- Predicate &p_;
+ Predicate p_;
Iterator it_;
};
+
+// Preconditions:
+// 1. The sequences are the same length
+// 2. Any common elements on the front have been removed (not necessary for correctness, just for performance)
+ template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate >
+ bool is_permutation_inner ( ForwardIterator1 first1, ForwardIterator1 last1,
+ ForwardIterator2 first2, ForwardIterator2 last2,
+ BinaryPredicate p ) {
+ // 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 ) {
+ 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;
+ }
+
+ template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
+ bool is_permutation_tag ( ForwardIterator1 first1, ForwardIterator1 last1,
+ ForwardIterator2 first2, ForwardIterator2 last2,
+ BinaryPredicate p,
+ std::forward_iterator_tag, std::forward_iterator_tag ) {
+
+ // Skip the common prefix (if any)
+ while ( first1 != last1 && first2 != last2 && p ( *first1, *first2 )) {
+ ++first1;
+ ++first2;
+ }
+ if ( first1 != last1 && first2 != last2 )
+ return boost::algorithm::detail::is_permutation_inner ( first1, last1, first2, last2,
+ std::equal_to<typename std::iterator_traits<ForwardIterator1>::value_type> ());
+ return first1 == last1 && first2 == last2;
+ }
+
+ template <class RandomAccessIterator1, class RandomAccessIterator2, class BinaryPredicate>
+ bool is_permutation_tag ( RandomAccessIterator1 first1, RandomAccessIterator1 last1,
+ RandomAccessIterator2 first2, RandomAccessIterator2 last2,
+ BinaryPredicate p,
+ std::random_access_iterator_tag, std::random_access_iterator_tag ) {
+ // Cheap check
+ if ( std::distance ( first1, last1 ) != std::distance ( first2, last2 ))
+ return false;
+ // Skip the common prefix (if any)
+ while ( first1 != last1 && first2 != last2 && p ( *first1, *first2 )) {
+ ++first1;
+ ++first2;
+ }
+
+ if ( first1 != last1 && first2 != last2 )
+ return is_permutation_inner (first1, last1, first2, last2, p);
+ return first1 == last1 && first2 == last2;
+ }
+
}
/// \endcond
+#if __cplusplus >= 201103L
+// Use the C++11 versions of is_permutation if it is available
+using std::is_permutation; // Section 25.2.12
+#else
/// \fn is_permutation ( ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 first2, BinaryPredicate p )
/// \brief Tests to see if 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 first1 The start of the input sequence
+/// \param last1 One past the end of the input sequence
/// \param first2 The start of the second sequence
/// \param p The predicate to compare elements with
///
@@ -67,19 +127,7 @@
// 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 boost::algorithm::detail::is_permutation_inner ( first1, last1, first2, last2, p );
}
return true;
@@ -88,23 +136,84 @@
/// \fn is_permutation ( ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 first2 )
/// \brief Tests to see if 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 first1 The start of the input sequence
+/// \param last2 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 )
+bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1, 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 std::iterator_traits<ForwardIterator1>::value_type> ());
+// Skip the common prefix (if any)
+ std::pair<ForwardIterator1, ForwardIterator2> eq = std::mismatch (first1, last1, first2 );
+ first1 = eq.first;
+ first2 = eq.second;
+ if ( first1 != last1 ) {
+ // Create last2
+ ForwardIterator2 last2 = first2;
+ std::advance ( last2, std::distance (first1, last1));
+ return boost::algorithm::detail::is_permutation_inner ( first1, last1, first2, last2,
+ std::equal_to<typename std::iterator_traits<ForwardIterator1>::value_type> ());
+ }
+ return true;
}
#endif
+/// \fn is_permutation ( ForwardIterator1 first, ForwardIterator1 last,
+/// ForwardIterator2 first2, ForwardIterator2 last2 )
+/// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2
+///
+/// \param first1 The start of the input sequence
+/// \param last2 One past the end of the input sequence
+/// \param first2 The start of the second sequence
+/// \param last1 One past the end 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 first1, ForwardIterator1 last1,
+ ForwardIterator2 first2, ForwardIterator2 last2 )
+{
+// 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::detail::is_permutation_tag (
+ first1, last1, first2, last2,
+ std::equal_to<typename std::iterator_traits<ForwardIterator1>::value_type> (),
+ typename std::iterator_traits<ForwardIterator1>::iterator_category (),
+ typename std::iterator_traits<ForwardIterator2>::iterator_category ());
+}
+
+/// \fn is_permutation ( ForwardIterator1 first, ForwardIterator1 last,
+/// ForwardIterator2 first2, ForwardIterator2 last2,
+/// BinaryPredicate p )
+/// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2
+///
+/// \param first1 The start of the input sequence
+/// \param last1 One past the end of the input sequence
+/// \param first2 The start of the second sequence
+/// \param last2 One past the end of the second sequence
+/// \param pred 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, ForwardIterator2 last2,
+ BinaryPredicate pred )
+{
+ return boost::algorithm::detail::is_permutation_tag (
+ first1, last1, first2, last2, pred,
+ typename std::iterator_traits<ForwardIterator1>::iterator_category (),
+ typename std::iterator_traits<ForwardIterator2>::iterator_category ());
+}
+
+
+
/// \fn is_permutation ( const Range &r, ForwardIterator first2 )
/// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2
///
Deleted: trunk/boost/algorithm/cxx14/is_permutation.hpp
==============================================================================
--- trunk/boost/algorithm/cxx14/is_permutation.hpp 2013-05-20 11:37:50 EDT (Mon, 20 May 2013)
+++ (empty file)
@@ -1,130 +0,0 @@
-/*
- Copyright (c) Marshall Clow 2013
-
- 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 equal.hpp
-/// \brief Determines if one
-/// \author Marshall Clow
-
-#ifndef BOOST_ALGORITHM_IS_PERMUTATION_HPP
-#define BOOST_ALGORITHM_IS_PERMUTATION_HPP
-
-#include <algorithm>
-#include <functional> // for std::equal_to
-
-namespace boost { namespace algorithm {
-
-namespace detail {
-
- template <class T1, class T2>
- struct is_perm_eq : public std::binary_function<T1, T2, bool> {
- bool operator () ( const T1& v1, const T2& v2 ) const { return v1 == v2 ;}
- };
-
-
- template <class RandomAccessIterator1, class RandomAccessIterator2, class BinaryPredicate>
- bool is_permutation ( RandomAccessIterator1 first1, RandomAccessIterator1 last1,
- RandomAccessIterator2 first2, RandomAccessIterator2 last2, BinaryPredicate pred,
- std::random_access_iterator_tag, std::random_access_iterator_tag )
- {
- // Random-access iterators let is check the sizes in constant time
- if ( std::distance ( first1, last1 ) != std::distance ( first2, last2 ))
- return false;
- // If we know that the sequences are the same size, the original version is fine
- return std::is_permutation ( first1, last1, first2, pred );
- }
-
-
- template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
- bool is_permutation (
- ForwardIterator1 first1, ForwardIterator1 last1,
- ForwardIterator2 first2, ForwardIterator2 last2,
- BinaryPredicate pred,
- std::forward_iterator_tag, std::forward_iterator_tag )
- {
-
- // Look for common prefix
- for (; first1 != last1 && first2 != last2; ++first1, ++first2)
- if (!pred(*first1, *first2))
- goto not_done;
- // We've reached the end of one of the sequences without a mismatch.
- return first1 == last1 && first2 == last2;
- not_done:
-
- // Check and make sure that we have the same # of elements left
- typedef typename std::iterator_traits<ForwardIterator1>::difference_type diff1_t;
- diff1_t len1 = _VSTD::distance(first1, last1);
- typedef typename std::iterator_traits<ForwardIterator2>::difference_type diff2_t;
- diff2_t len2 = _VSTD::distance(first2, last2);
- if (len1 != len2)
- return false;
-
- // For each element in [f1, l1) see if there are the
- // same number of equal elements in [f2, l2)
- for ( ForwardIterator1 i = first1; i != last1; ++i )
- {
- // Have we already counted this value?
- ForwardIterator1 j;
- for ( j = first1; j != i; ++j )
- if (pred(*j, *i))
- break;
- if ( j == i ) // didn't find it...
- {
- // Count number of *i in [f2, l2)
- diff1_t c2 = 0;
- for ( ForwardIterator2 iter2 = first2; iter2 != last2; ++iter2 )
- if (pred(*i, *iter2))
- ++c2;
- if (c2 == 0)
- return false;
-
- // Count number of *i in [i, l1)
- diff1_t c1 = 0;
- for (_ForwardIterator1 iter1 = i; iter1 != last1; ++iter1 )
- if (pred(*i, *iter1))
- ++c1;
- if (c1 != c2)
- return false;
- }
- }
- return true;
- }
-
-}
-
-
-template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
-bool is_permutation (
- ForwardIterator1 first1, ForwardIterator1 last1,
- ForwardIterator2 first2, ForwardIterator2 last2,
- BinaryPredicate pred )
-{
- return boost::algorithm::detail::is_permutation (
- first1, last1, first2, last2, pred,
- typename std::iterator_traits<ForwardIterator1>::iterator_category (),
- typename std::iterator_traits<ForwardIterator2>::iterator_category ());
-}
-
-template<class ForwardIterator1, class ForwardIterator2>
-bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1,
- ForwardIterator2 first2, ForwardIterator2 last2 )
-{
- typedef typename iterator_traits<_ForwardIterator1>::value_type value1_t;
- typedef typename iterator_traits<_ForwardIterator2>::value_type value2_t;
- return boost::algorithm::detail::is_permutation (
- first1, last1, first2, last2,
- boost::algorithm::detail::is_perm_eq<
- typename std::iterator_traits<InputIterator1>::value_type,
- typename std::iterator_traits<InputIterator2>::value_type> (),
- typename std::iterator_traits<ForwardIterator1>::iterator_category (),
- typename std::iterator_traits<ForwardIterator2>::iterator_category ());
-}
-
-// There are already range-based versions of these.
-
-}} // namespace boost and algorithm
-
-#endif // BOOST_ALGORITHM_IS_PERMUTATION_HPP
Modified: trunk/libs/algorithm/test/equal_test.cpp
==============================================================================
--- trunk/libs/algorithm/test/equal_test.cpp (original)
+++ trunk/libs/algorithm/test/equal_test.cpp 2013-05-20 11:37:50 EDT (Mon, 20 May 2013)
@@ -24,9 +24,9 @@
int comparison_count = 0;
template <typename T>
bool counting_equals ( const T &a, const T &b ) {
- ++comparison_count;
- return a == b;
- }
+ ++comparison_count;
+ return a == b;
+ }
namespace ba = boost::algorithm;
@@ -37,86 +37,89 @@
const int sz = sizeof (num)/sizeof(num[0]);
-// Empty sequences are equal to each other, but not to non-empty sequences
- BOOST_CHECK ( ba::equal ( input_iterator<int *>(num), input_iterator<int *>(num),
- input_iterator<int *>(num), input_iterator<int *>(num)));
- BOOST_CHECK ( ba::equal ( input_iterator<int *>(num), input_iterator<int *>(num),
- input_iterator<int *>(num), input_iterator<int *>(num),
- never_eq<int> ));
- BOOST_CHECK ( ba::equal ( random_access_iterator<int *>(num), random_access_iterator<int *>(num),
- random_access_iterator<int *>(num), random_access_iterator<int *>(num),
- never_eq<int> ));
-
- BOOST_CHECK (!ba::equal ( input_iterator<int *>(num), input_iterator<int *>(num),
- input_iterator<int *>(num), input_iterator<int *>(num + 1)));
- BOOST_CHECK (!ba::equal ( input_iterator<int *>(num + 1), input_iterator<int *>(num + 2),
- input_iterator<int *>(num), input_iterator<int *>(num)));
- BOOST_CHECK (!ba::equal ( random_access_iterator<int *>(num + 1), random_access_iterator<int *>(num + 2),
- random_access_iterator<int *>(num), random_access_iterator<int *>(num)));
-
-// Single element sequences are equal if they contain the same value
- BOOST_CHECK ( ba::equal ( input_iterator<int *>(num), input_iterator<int *>(num + 1),
- input_iterator<int *>(num), input_iterator<int *>(num + 1)));
- BOOST_CHECK ( ba::equal ( input_iterator<int *>(num), input_iterator<int *>(num + 1),
- input_iterator<int *>(num), input_iterator<int *>(num + 1),
- eq<int> ));
- BOOST_CHECK ( ba::equal ( random_access_iterator<int *>(num), random_access_iterator<int *>(num + 1),
- random_access_iterator<int *>(num), random_access_iterator<int *>(num + 1),
- eq<int> ));
- BOOST_CHECK (!ba::equal ( input_iterator<int *>(num), input_iterator<int *>(num + 1),
- input_iterator<int *>(num), input_iterator<int *>(num + 1),
- never_eq<int> ));
- BOOST_CHECK (!ba::equal ( random_access_iterator<int *>(num), random_access_iterator<int *>(num + 1),
- random_access_iterator<int *>(num), random_access_iterator<int *>(num + 1),
- never_eq<int> ));
-
- BOOST_CHECK ( ba::equal ( input_iterator<int *>(num), input_iterator<int *>(num + 1),
- input_iterator<int *>(num + 1), input_iterator<int *>(num + 2)));
- BOOST_CHECK ( ba::equal ( input_iterator<int *>(num), input_iterator<int *>(num + 1),
- input_iterator<int *>(num + 1), input_iterator<int *>(num + 2),
- eq<int> ));
-
- BOOST_CHECK (!ba::equal ( input_iterator<int *>(num + 2), input_iterator<int *>(num + 3),
- input_iterator<int *>(num), input_iterator<int *>(num + 1)));
- BOOST_CHECK (!ba::equal ( input_iterator<int *>(num + 2), input_iterator<int *>(num + 3),
- input_iterator<int *>(num), input_iterator<int *>(num + 1),
- eq<int> ));
-
-// Identical long sequences are equal.
- BOOST_CHECK ( ba::equal ( input_iterator<int *>(num), input_iterator<int *>(num + sz),
- input_iterator<int *>(num), input_iterator<int *>(num + sz)));
- BOOST_CHECK ( ba::equal ( input_iterator<int *>(num), input_iterator<int *>(num + sz),
- input_iterator<int *>(num), input_iterator<int *>(num + sz),
- eq<int> ));
- BOOST_CHECK (!ba::equal ( input_iterator<int *>(num), input_iterator<int *>(num + sz),
- input_iterator<int *>(num), input_iterator<int *>(num + sz),
- never_eq<int> ));
-
-// different sequences are different
- BOOST_CHECK (!ba::equal ( input_iterator<int *>(num + 1), input_iterator<int *>(num + sz),
- input_iterator<int *>(num), input_iterator<int *>(num + sz)));
- BOOST_CHECK (!ba::equal ( input_iterator<int *>(num + 1), input_iterator<int *>(num + sz),
- input_iterator<int *>(num), input_iterator<int *>(num + sz),
- eq<int> ));
- BOOST_CHECK (!ba::equal ( input_iterator<int *>(num), input_iterator<int *>(num + sz),
- input_iterator<int *>(num), input_iterator<int *>(num + sz - 1)));
- BOOST_CHECK (!ba::equal ( input_iterator<int *>(num), input_iterator<int *>(num + sz),
- input_iterator<int *>(num), input_iterator<int *>(num + sz - 1),
- eq<int> ));
-
-// When there's a cheap check, bail early
- comparison_count = 0;
- BOOST_CHECK (!ba::equal ( random_access_iterator<int *>(num), random_access_iterator<int *>(num + sz),
- random_access_iterator<int *>(num), random_access_iterator<int *>(num + sz - 1),
- counting_equals<int> ));
- BOOST_CHECK ( comparison_count == 0 );
-// And when there's not, we can't
- comparison_count = 0;
- BOOST_CHECK (!ba::equal ( input_iterator<int *>(num), input_iterator<int *>(num + sz),
- input_iterator<int *>(num), input_iterator<int *>(num + sz - 1),
- counting_equals<int> ));
- BOOST_CHECK ( comparison_count > 0 );
-
+// Empty sequences are equal to each other, but not to non-empty sequences
+ BOOST_CHECK ( ba::equal ( input_iterator<int *>(num), input_iterator<int *>(num),
+ input_iterator<int *>(num), input_iterator<int *>(num)));
+ BOOST_CHECK ( ba::equal ( input_iterator<int *>(num), input_iterator<int *>(num),
+ input_iterator<int *>(num), input_iterator<int *>(num),
+ never_eq<int> ));
+ BOOST_CHECK ( ba::equal ( random_access_iterator<int *>(num), random_access_iterator<int *>(num),
+ random_access_iterator<int *>(num), random_access_iterator<int *>(num),
+ never_eq<int> ));
+
+ BOOST_CHECK (!ba::equal ( input_iterator<int *>(num), input_iterator<int *>(num),
+ input_iterator<int *>(num), input_iterator<int *>(num + 1)));
+ BOOST_CHECK (!ba::equal ( input_iterator<int *>(num + 1), input_iterator<int *>(num + 2),
+ input_iterator<int *>(num), input_iterator<int *>(num)));
+ BOOST_CHECK (!ba::equal ( random_access_iterator<int *>(num + 1), random_access_iterator<int *>(num + 2),
+ random_access_iterator<int *>(num), random_access_iterator<int *>(num)));
+
+// Single element sequences are equal if they contain the same value
+ BOOST_CHECK ( ba::equal ( input_iterator<int *>(num), input_iterator<int *>(num + 1),
+ input_iterator<int *>(num), input_iterator<int *>(num + 1)));
+ BOOST_CHECK ( ba::equal ( input_iterator<int *>(num), input_iterator<int *>(num + 1),
+ input_iterator<int *>(num), input_iterator<int *>(num + 1),
+ eq<int> ));
+ BOOST_CHECK ( ba::equal ( random_access_iterator<int *>(num), random_access_iterator<int *>(num + 1),
+ random_access_iterator<int *>(num), random_access_iterator<int *>(num + 1),
+ eq<int> ));
+ BOOST_CHECK (!ba::equal ( input_iterator<int *>(num), input_iterator<int *>(num + 1),
+ input_iterator<int *>(num), input_iterator<int *>(num + 1),
+ never_eq<int> ));
+ BOOST_CHECK (!ba::equal ( random_access_iterator<int *>(num), random_access_iterator<int *>(num + 1),
+ random_access_iterator<int *>(num), random_access_iterator<int *>(num + 1),
+ never_eq<int> ));
+
+ BOOST_CHECK ( ba::equal ( input_iterator<int *>(num), input_iterator<int *>(num + 1),
+ input_iterator<int *>(num + 1), input_iterator<int *>(num + 2)));
+ BOOST_CHECK ( ba::equal ( input_iterator<int *>(num), input_iterator<int *>(num + 1),
+ input_iterator<int *>(num + 1), input_iterator<int *>(num + 2),
+ eq<int> ));
+
+ BOOST_CHECK (!ba::equal ( input_iterator<int *>(num + 2), input_iterator<int *>(num + 3),
+ input_iterator<int *>(num), input_iterator<int *>(num + 1)));
+ BOOST_CHECK (!ba::equal ( input_iterator<int *>(num + 2), input_iterator<int *>(num + 3),
+ input_iterator<int *>(num), input_iterator<int *>(num + 1),
+ eq<int> ));
+
+// Identical long sequences are equal.
+ BOOST_CHECK ( ba::equal ( input_iterator<int *>(num), input_iterator<int *>(num + sz),
+ input_iterator<int *>(num), input_iterator<int *>(num + sz)));
+ BOOST_CHECK ( ba::equal ( input_iterator<int *>(num), input_iterator<int *>(num + sz),
+ input_iterator<int *>(num), input_iterator<int *>(num + sz),
+ eq<int> ));
+ BOOST_CHECK (!ba::equal ( input_iterator<int *>(num), input_iterator<int *>(num + sz),
+ input_iterator<int *>(num), input_iterator<int *>(num + sz),
+ never_eq<int> ));
+ BOOST_CHECK ( ba::equal ( input_iterator<int *>(num), input_iterator<int *>(num + sz),
+ random_access_iterator<int *>(num), random_access_iterator<int *>(num + sz),
+ eq<int> ));
+
+// different sequences are different
+ BOOST_CHECK (!ba::equal ( input_iterator<int *>(num + 1), input_iterator<int *>(num + sz),
+ input_iterator<int *>(num), input_iterator<int *>(num + sz)));
+ BOOST_CHECK (!ba::equal ( input_iterator<int *>(num + 1), input_iterator<int *>(num + sz),
+ input_iterator<int *>(num), input_iterator<int *>(num + sz),
+ eq<int> ));
+ BOOST_CHECK (!ba::equal ( input_iterator<int *>(num), input_iterator<int *>(num + sz),
+ input_iterator<int *>(num), input_iterator<int *>(num + sz - 1)));
+ BOOST_CHECK (!ba::equal ( input_iterator<int *>(num), input_iterator<int *>(num + sz),
+ input_iterator<int *>(num), input_iterator<int *>(num + sz - 1),
+ eq<int> ));
+
+// When there's a cheap check, bail early
+ comparison_count = 0;
+ BOOST_CHECK (!ba::equal ( random_access_iterator<int *>(num), random_access_iterator<int *>(num + sz),
+ random_access_iterator<int *>(num), random_access_iterator<int *>(num + sz - 1),
+ counting_equals<int> ));
+ BOOST_CHECK ( comparison_count == 0 );
+// And when there's not, we can't
+ comparison_count = 0;
+ BOOST_CHECK (!ba::equal ( input_iterator<int *>(num), input_iterator<int *>(num + sz),
+ input_iterator<int *>(num), input_iterator<int *>(num + sz - 1),
+ counting_equals<int> ));
+ BOOST_CHECK ( comparison_count > 0 );
+
}
Modified: trunk/libs/algorithm/test/is_permutation_test1.cpp
==============================================================================
--- trunk/libs/algorithm/test/is_permutation_test1.cpp (original)
+++ trunk/libs/algorithm/test/is_permutation_test1.cpp 2013-05-20 11:37:50 EDT (Mon, 20 May 2013)
@@ -19,10 +19,95 @@
#include <vector>
#include <list>
+#include "iterator_test.hpp"
+
+template <typename T>
+bool eq ( const T& a, const T& b ) { return a == b; }
+
+template <typename T>
+bool never_eq ( const T&, const T& ) { return false; }
+
namespace ba = boost::algorithm;
-// namespace ba = boost;
void test_sequence1 () {
+ int num[] = { 1, 1, 2, 3, 5 };
+ const int sz = sizeof (num)/sizeof(num[0]);
+
+// Empty sequences
+ BOOST_CHECK (
+ ba::is_permutation (
+ forward_iterator<int *>(num), forward_iterator<int *>(num),
+ forward_iterator<int *>(num)));
+ BOOST_CHECK (
+ ba::is_permutation (
+ forward_iterator<int *>(num), forward_iterator<int *>(num),
+ forward_iterator<int *>(num), forward_iterator<int *>(num)));
+ BOOST_CHECK (
+ ba::is_permutation (
+ random_access_iterator<int *>(num), random_access_iterator<int *>(num),
+ random_access_iterator<int *>(num), random_access_iterator<int *>(num)));
+ BOOST_CHECK (
+ ba::is_permutation (
+ forward_iterator<int *>(num), forward_iterator<int *>(num),
+ forward_iterator<int *>(num),
+ never_eq<int> )); // Since the sequences are empty, the pred is never called
+
+// Empty vs. non-empty
+ BOOST_CHECK ( !
+ ba::is_permutation (
+ forward_iterator<int *>(num), forward_iterator<int *>(num),
+ forward_iterator<int *>(num), forward_iterator<int *>(num + 1)));
+
+ BOOST_CHECK ( !
+ ba::is_permutation (
+ forward_iterator<int *>(num + 1), forward_iterator<int *>(num + 2),
+ forward_iterator<int *>(num), forward_iterator<int *>(num)));
+
+ BOOST_CHECK ( !
+ ba::is_permutation (
+ random_access_iterator<int *>(num + 1), random_access_iterator<int *>(num + 2),
+ random_access_iterator<int *>(num), random_access_iterator<int *>(num)));
+
+ BOOST_CHECK ( !
+ ba::is_permutation (
+ random_access_iterator<int *>(num), random_access_iterator<int *>(num),
+ random_access_iterator<int *>(num + 1), random_access_iterator<int *>(num + 2)));
+
+// Something should be a permutation of itself
+ BOOST_CHECK (
+ ba::is_permutation (
+ forward_iterator<int *>(num), forward_iterator<int *>(num + sz),
+ forward_iterator<int *>(num)));
+ BOOST_CHECK (
+ ba::is_permutation (
+ forward_iterator<int *>(num), forward_iterator<int *>(num + sz),
+ forward_iterator<int *>(num), eq<int> ));
+ BOOST_CHECK (
+ ba::is_permutation (
+ forward_iterator<int *>(num), forward_iterator<int *>(num + sz),
+ forward_iterator<int *>(num), forward_iterator<int *>(num + sz )));
+ BOOST_CHECK (
+ ba::is_permutation (
+ forward_iterator<int *>(num), forward_iterator<int *>(num + sz),
+ forward_iterator<int *>(num), forward_iterator<int *>(num + sz ),
+ eq<int> ));
+
+ BOOST_CHECK (
+ ba::is_permutation (
+ random_access_iterator<int *>(num), random_access_iterator<int *>(num + sz),
+ random_access_iterator<int *>(num), random_access_iterator<int *>(num + sz)));
+ BOOST_CHECK (
+ ba::is_permutation (
+ random_access_iterator<int *>(num), random_access_iterator<int *>(num + sz),
+ random_access_iterator<int *>(num), random_access_iterator<int *>(num + sz),
+ eq<int> ));
+ BOOST_CHECK (
+ ba::is_permutation (
+ random_access_iterator<int *>(num), random_access_iterator<int *>(num + sz),
+ forward_iterator<int *>(num), forward_iterator<int *>(num + sz),
+ eq<int> ));
+
+
std::vector<int> v, v1;
v.clear ();
Modified: trunk/libs/algorithm/test/mismatch_test.cpp
==============================================================================
--- trunk/libs/algorithm/test/mismatch_test.cpp (original)
+++ trunk/libs/algorithm/test/mismatch_test.cpp 2013-05-20 11:37:50 EDT (Mon, 20 May 2013)
@@ -24,9 +24,9 @@
namespace ba = boost::algorithm;
template <typename Iter1, typename Iter2>
-bool iter_eq ( std::pair<Iter1, Iter1> pr, Iter1 first, Iter2 second ) {
- return pr.first == first && pr.second == second;
- }
+bool iter_eq ( std::pair<Iter1, Iter2> pr, Iter1 first, Iter2 second ) {
+ return pr.first == first && pr.second == second;
+ }
void test_mismatch ()
{
@@ -35,123 +35,129 @@
const int sz = sizeof (num)/sizeof(num[0]);
-// No mismatch for empty sequences
- BOOST_CHECK ( iter_eq (
- ba::mismatch ( input_iterator<int *>(num), input_iterator<int *>(num),
- input_iterator<int *>(num), input_iterator<int *>(num)),
- input_iterator<int *>(num), input_iterator<int *>(num)));
- BOOST_CHECK ( iter_eq (
- ba::mismatch ( input_iterator<int *>(num), input_iterator<int *>(num),
- input_iterator<int *>(num), input_iterator<int *>(num),
- never_eq<int> ),
- input_iterator<int *>(num), input_iterator<int *>(num)));
-
- BOOST_CHECK ( iter_eq (
- ba::mismatch ( random_access_iterator<int *>(num), random_access_iterator<int *>(num),
- random_access_iterator<int *>(num), random_access_iterator<int *>(num),
- never_eq<int> ),
- random_access_iterator<int *>(num), random_access_iterator<int *>(num)));
-
-// Empty vs. non-empty mismatch immediately
- BOOST_CHECK ( iter_eq (
- ba::mismatch ( input_iterator<int *>(num), input_iterator<int *>(num),
- input_iterator<int *>(num), input_iterator<int *>(num + 1)),
- input_iterator<int *>(num), input_iterator<int *>(num)));
-
- BOOST_CHECK ( iter_eq (
- ba::mismatch ( input_iterator<int *>(num + 1), input_iterator<int *>(num + 2),
- input_iterator<int *>(num), input_iterator<int *>(num)),
- input_iterator<int *>(num + 1), input_iterator<int *>(num)));
-
- BOOST_CHECK ( iter_eq (
- ba::mismatch ( random_access_iterator<int *>(num + 1), random_access_iterator<int *>(num + 2),
- random_access_iterator<int *>(num), random_access_iterator<int *>(num)),
- random_access_iterator<int *>(num + 1), random_access_iterator<int *>(num)));
-
-// Single element sequences are equal if they contain the same value
- BOOST_CHECK ( iter_eq (
- ba::mismatch ( input_iterator<int *>(num), input_iterator<int *>(num + 1),
- input_iterator<int *>(num), input_iterator<int *>(num + 1)),
- input_iterator<int *>(num + 1), input_iterator<int *>(num + 1)));
-
- BOOST_CHECK ( iter_eq (
- ba::mismatch ( input_iterator<int *>(num), input_iterator<int *>(num + 1),
+// No mismatch for empty sequences
+ BOOST_CHECK ( iter_eq (
+ ba::mismatch ( input_iterator<int *>(num), input_iterator<int *>(num),
+ input_iterator<int *>(num), input_iterator<int *>(num)),
+ input_iterator<int *>(num), input_iterator<int *>(num)));
+ BOOST_CHECK ( iter_eq (
+ ba::mismatch ( input_iterator<int *>(num), input_iterator<int *>(num),
+ input_iterator<int *>(num), input_iterator<int *>(num),
+ never_eq<int> ),
+ input_iterator<int *>(num), input_iterator<int *>(num)));
+
+ BOOST_CHECK ( iter_eq (
+ ba::mismatch ( random_access_iterator<int *>(num), random_access_iterator<int *>(num),
+ random_access_iterator<int *>(num), random_access_iterator<int *>(num),
+ never_eq<int> ),
+ random_access_iterator<int *>(num), random_access_iterator<int *>(num)));
+
+// Empty vs. non-empty mismatch immediately
+ BOOST_CHECK ( iter_eq (
+ ba::mismatch ( input_iterator<int *>(num), input_iterator<int *>(num),
+ input_iterator<int *>(num), input_iterator<int *>(num + 1)),
+ input_iterator<int *>(num), input_iterator<int *>(num)));
+
+ BOOST_CHECK ( iter_eq (
+ ba::mismatch ( input_iterator<int *>(num + 1), input_iterator<int *>(num + 2),
+ input_iterator<int *>(num), input_iterator<int *>(num)),
+ input_iterator<int *>(num + 1), input_iterator<int *>(num)));
+
+ BOOST_CHECK ( iter_eq (
+ ba::mismatch ( random_access_iterator<int *>(num + 1), random_access_iterator<int *>(num + 2),
+ random_access_iterator<int *>(num), random_access_iterator<int *>(num)),
+ random_access_iterator<int *>(num + 1), random_access_iterator<int *>(num)));
+
+// Single element sequences are equal if they contain the same value
+ BOOST_CHECK ( iter_eq (
+ ba::mismatch ( input_iterator<int *>(num), input_iterator<int *>(num + 1),
+ input_iterator<int *>(num), input_iterator<int *>(num + 1)),
+ input_iterator<int *>(num + 1), input_iterator<int *>(num + 1)));
+
+ BOOST_CHECK ( iter_eq (
+ ba::mismatch ( input_iterator<int *>(num), input_iterator<int *>(num + 1),
input_iterator<int *>(num), input_iterator<int *>(num + 1),
- eq<int> ),
- input_iterator<int *>(num + 1), input_iterator<int *>(num + 1)));
-
- BOOST_CHECK ( iter_eq (
- ba::mismatch ( random_access_iterator<int *>(num), random_access_iterator<int *>(num + 1),
- random_access_iterator<int *>(num), random_access_iterator<int *>(num + 1),
- eq<int> ),
- random_access_iterator<int *>(num + 1), random_access_iterator<int *>(num + 1)));
-
-
- BOOST_CHECK ( iter_eq (
- ba::mismatch ( input_iterator<int *>(num), input_iterator<int *>(num + 1),
- input_iterator<int *>(num), input_iterator<int *>(num + 1),
- never_eq<int> ),
- input_iterator<int *>(num), input_iterator<int *>(num)));
-
- BOOST_CHECK ( iter_eq (
- ba::mismatch ( random_access_iterator<int *>(num), random_access_iterator<int *>(num + 1),
- random_access_iterator<int *>(num), random_access_iterator<int *>(num + 1),
- never_eq<int> ),
- random_access_iterator<int *>(num), random_access_iterator<int *>(num)));
-
- BOOST_CHECK ( iter_eq (
- ba::mismatch ( input_iterator<int *>(num), input_iterator<int *>(num + 1),
- input_iterator<int *>(num + 1), input_iterator<int *>(num + 2)),
- input_iterator<int *>(num + 1), input_iterator<int *>(num + 2)));
-
- BOOST_CHECK ( iter_eq (
- ba::mismatch ( input_iterator<int *>(num), input_iterator<int *>(num + 1),
- input_iterator<int *>(num + 1), input_iterator<int *>(num + 2),
- eq<int> ),
- input_iterator<int *>(num + 1), input_iterator<int *>(num + 2)));
-
- BOOST_CHECK ( iter_eq (
- ba::mismatch ( input_iterator<int *>(num + 2), input_iterator<int *>(num + 3),
- input_iterator<int *>(num), input_iterator<int *>(num + 1)),
- input_iterator<int *>(num + 2), input_iterator<int *>(num)));
-
- BOOST_CHECK ( iter_eq (
- ba::mismatch ( input_iterator<int *>(num + 2), input_iterator<int *>(num + 3),
- input_iterator<int *>(num), input_iterator<int *>(num + 1),
- eq<int> ),
- input_iterator<int *>(num + 2), input_iterator<int *>(num)));
-
-
-
-// Identical long sequences are equal.
- BOOST_CHECK ( iter_eq (
- ba::mismatch ( input_iterator<int *>(num), input_iterator<int *>(num + sz),
- input_iterator<int *>(num), input_iterator<int *>(num + sz)),
- input_iterator<int *>(num + sz), input_iterator<int *>(num + sz)));
-
- BOOST_CHECK ( iter_eq (
- ba::mismatch ( input_iterator<int *>(num), input_iterator<int *>(num + sz),
- input_iterator<int *>(num), input_iterator<int *>(num + sz),
- eq<int> ),
- input_iterator<int *>(num + sz), input_iterator<int *>(num + sz)));
-
- BOOST_CHECK ( iter_eq (
- ba::mismatch ( input_iterator<int *>(num), input_iterator<int *>(num + sz),
- input_iterator<int *>(num), input_iterator<int *>(num + sz),
- never_eq<int> ),
- input_iterator<int *>(num), input_iterator<int *>(num)));
-
-// different sequences are different
- BOOST_CHECK ( iter_eq (
- ba::mismatch ( input_iterator<int *>(num + 1), input_iterator<int *>(num + sz),
- input_iterator<int *>(num), input_iterator<int *>(num + sz)),
- input_iterator<int *>(num + 2), input_iterator<int *>(num + 1)));
-
- BOOST_CHECK ( iter_eq (
- ba::mismatch ( input_iterator<int *>(num + 1), input_iterator<int *>(num + sz),
- input_iterator<int *>(num), input_iterator<int *>(num + sz),
- eq<int> ),
- input_iterator<int *>(num + 2), input_iterator<int *>(num + 1)));
+ eq<int> ),
+ input_iterator<int *>(num + 1), input_iterator<int *>(num + 1)));
+
+ BOOST_CHECK ( iter_eq (
+ ba::mismatch ( random_access_iterator<int *>(num), random_access_iterator<int *>(num + 1),
+ random_access_iterator<int *>(num), random_access_iterator<int *>(num + 1),
+ eq<int> ),
+ random_access_iterator<int *>(num + 1), random_access_iterator<int *>(num + 1)));
+
+
+ BOOST_CHECK ( iter_eq (
+ ba::mismatch ( input_iterator<int *>(num), input_iterator<int *>(num + 1),
+ input_iterator<int *>(num), input_iterator<int *>(num + 1),
+ never_eq<int> ),
+ input_iterator<int *>(num), input_iterator<int *>(num)));
+
+ BOOST_CHECK ( iter_eq (
+ ba::mismatch ( random_access_iterator<int *>(num), random_access_iterator<int *>(num + 1),
+ random_access_iterator<int *>(num), random_access_iterator<int *>(num + 1),
+ never_eq<int> ),
+ random_access_iterator<int *>(num), random_access_iterator<int *>(num)));
+
+ BOOST_CHECK ( iter_eq (
+ ba::mismatch ( input_iterator<int *>(num), input_iterator<int *>(num + 1),
+ input_iterator<int *>(num + 1), input_iterator<int *>(num + 2)),
+ input_iterator<int *>(num + 1), input_iterator<int *>(num + 2)));
+
+ BOOST_CHECK ( iter_eq (
+ ba::mismatch ( input_iterator<int *>(num), input_iterator<int *>(num + 1),
+ input_iterator<int *>(num + 1), input_iterator<int *>(num + 2),
+ eq<int> ),
+ input_iterator<int *>(num + 1), input_iterator<int *>(num + 2)));
+
+ BOOST_CHECK ( iter_eq (
+ ba::mismatch ( input_iterator<int *>(num + 2), input_iterator<int *>(num + 3),
+ input_iterator<int *>(num), input_iterator<int *>(num + 1)),
+ input_iterator<int *>(num + 2), input_iterator<int *>(num)));
+
+ BOOST_CHECK ( iter_eq (
+ ba::mismatch ( input_iterator<int *>(num + 2), input_iterator<int *>(num + 3),
+ input_iterator<int *>(num), input_iterator<int *>(num + 1),
+ eq<int> ),
+ input_iterator<int *>(num + 2), input_iterator<int *>(num)));
+
+
+
+// Identical long sequences are equal.
+ BOOST_CHECK ( iter_eq (
+ ba::mismatch ( input_iterator<int *>(num), input_iterator<int *>(num + sz),
+ input_iterator<int *>(num), input_iterator<int *>(num + sz)),
+ input_iterator<int *>(num + sz), input_iterator<int *>(num + sz)));
+
+ BOOST_CHECK ( iter_eq (
+ ba::mismatch ( input_iterator<int *>(num), input_iterator<int *>(num + sz),
+ input_iterator<int *>(num), input_iterator<int *>(num + sz),
+ eq<int> ),
+ input_iterator<int *>(num + sz), input_iterator<int *>(num + sz)));
+
+ BOOST_CHECK ( iter_eq (
+ ba::mismatch ( input_iterator<int *>(num), input_iterator<int *>(num + sz),
+ input_iterator<int *>(num), input_iterator<int *>(num + sz),
+ never_eq<int> ),
+ input_iterator<int *>(num), input_iterator<int *>(num)));
+
+ BOOST_CHECK ( iter_eq (
+ ba::mismatch ( input_iterator<int *>(num), input_iterator<int *>(num + sz),
+ random_access_iterator<int *>(num), random_access_iterator<int *>(num + sz),
+ never_eq<int> ),
+ input_iterator<int *>(num), random_access_iterator<int *>(num)));
+
+// different sequences are different
+ BOOST_CHECK ( iter_eq (
+ ba::mismatch ( input_iterator<int *>(num + 1), input_iterator<int *>(num + sz),
+ input_iterator<int *>(num), input_iterator<int *>(num + sz)),
+ input_iterator<int *>(num + 2), input_iterator<int *>(num + 1)));
+
+ BOOST_CHECK ( iter_eq (
+ ba::mismatch ( input_iterator<int *>(num + 1), input_iterator<int *>(num + sz),
+ input_iterator<int *>(num), input_iterator<int *>(num + sz),
+ eq<int> ),
+ input_iterator<int *>(num + 2), input_iterator<int *>(num + 1)));
}