Subject: [Boost-commit] svn:boost r84415 - in branches/release: boost/algorithm boost/algorithm/cxx11 boost/algorithm/cxx14 boost/algorithm/searching boost/algorithm/searching/detail boost/algorithm/string boost/algorithm/string/detail libs/algorithm libs/algorithm/doc libs/algorithm/example libs/algorithm/minmax libs/algorithm/string libs/algorithm/string/doc libs/algorithm/string/test libs/algorithm/test libs/algorithm/test/search_test_data
From: marshall_at_[hidden]
Date: 2013-05-22 11:10:51
Author: marshall
Date: 2013-05-22 11:10:49 EDT (Wed, 22 May 2013)
New Revision: 84415
URL: http://svn.boost.org/trac/boost/changeset/84415
Log:
Merge c++14 changes to release
Added:
branches/release/boost/algorithm/cxx14/
- copied from r84206, /trunk/boost/algorithm/cxx14/
branches/release/boost/algorithm/cxx14/equal.hpp
- copied unchanged from r84206, /trunk/boost/algorithm/cxx14/equal.hpp
branches/release/boost/algorithm/cxx14/mismatch.hpp
- copied unchanged from r84206, /trunk/boost/algorithm/cxx14/mismatch.hpp
branches/release/libs/algorithm/test/equal_test.cpp
- copied, changed from r84206, /trunk/libs/algorithm/test/equal_test.cpp
branches/release/libs/algorithm/test/mismatch_test.cpp
- copied, changed from r84206, /trunk/libs/algorithm/test/mismatch_test.cpp
Properties modified:
branches/release/boost/algorithm/ (props changed)
branches/release/boost/algorithm/clamp.hpp (props changed)
branches/release/boost/algorithm/cxx11/all_of.hpp (props changed)
branches/release/boost/algorithm/cxx11/any_of.hpp (props changed)
branches/release/boost/algorithm/cxx11/copy_if.hpp (props changed)
branches/release/boost/algorithm/cxx11/copy_n.hpp (props changed)
branches/release/boost/algorithm/cxx11/find_if_not.hpp (props changed)
branches/release/boost/algorithm/cxx11/iota.hpp (props changed)
branches/release/boost/algorithm/cxx11/is_partitioned.hpp (props changed)
branches/release/boost/algorithm/cxx11/is_permutation.hpp (contents, props changed)
branches/release/boost/algorithm/cxx11/is_sorted.hpp (props changed)
branches/release/boost/algorithm/cxx11/none_of.hpp (props changed)
branches/release/boost/algorithm/cxx11/one_of.hpp (props changed)
branches/release/boost/algorithm/cxx11/partition_copy.hpp (props changed)
branches/release/boost/algorithm/cxx11/partition_point.hpp (props changed)
branches/release/boost/algorithm/hex.hpp (props changed)
branches/release/boost/algorithm/minmax_element.hpp (props changed)
branches/release/boost/algorithm/searching/ (props changed)
branches/release/boost/algorithm/searching/boyer_moore.hpp (props changed)
branches/release/boost/algorithm/searching/boyer_moore_horspool.hpp (props changed)
branches/release/boost/algorithm/searching/detail/bm_traits.hpp (props changed)
branches/release/boost/algorithm/searching/detail/debugging.hpp (props changed)
branches/release/boost/algorithm/searching/knuth_morris_pratt.hpp (props changed)
branches/release/boost/algorithm/string/ (props changed)
branches/release/boost/algorithm/string/detail/case_conv.hpp (props changed)
branches/release/boost/algorithm/string/detail/classification.hpp (props changed)
branches/release/boost/algorithm/string/find.hpp (props changed)
branches/release/boost/algorithm/string/find_iterator.hpp (props changed)
branches/release/libs/algorithm/ (props changed)
branches/release/libs/algorithm/doc/ (props changed)
branches/release/libs/algorithm/doc/Jamfile.v2 (props changed)
branches/release/libs/algorithm/doc/algorithm.qbk (props changed)
branches/release/libs/algorithm/doc/all_of.qbk (props changed)
branches/release/libs/algorithm/doc/any_of.qbk (props changed)
branches/release/libs/algorithm/doc/boyer_moore.qbk (props changed)
branches/release/libs/algorithm/doc/boyer_moore_horspool.qbk (props changed)
branches/release/libs/algorithm/doc/clamp-hpp.qbk (props changed)
branches/release/libs/algorithm/doc/hex.qbk (props changed)
branches/release/libs/algorithm/doc/is_partitioned.qbk (props changed)
branches/release/libs/algorithm/doc/knuth_morris_pratt.qbk (props changed)
branches/release/libs/algorithm/doc/none_of.qbk (props changed)
branches/release/libs/algorithm/doc/one_of.qbk (props changed)
branches/release/libs/algorithm/doc/ordered-hpp.qbk (props changed)
branches/release/libs/algorithm/doc/partition_point.qbk (props changed)
branches/release/libs/algorithm/example/Jamfile.v2 (props changed)
branches/release/libs/algorithm/example/clamp_example.cpp (props changed)
branches/release/libs/algorithm/example/search_example.cpp (props changed)
branches/release/libs/algorithm/minmax/index.html (props changed)
branches/release/libs/algorithm/string/ (props changed)
branches/release/libs/algorithm/string/doc/Jamfile.v2 (props changed)
branches/release/libs/algorithm/string/doc/usage.xml (props changed)
branches/release/libs/algorithm/string/test/find_test.cpp (props changed)
branches/release/libs/algorithm/string/test/split_test.cpp (props changed)
branches/release/libs/algorithm/test/ (props changed)
branches/release/libs/algorithm/test/Jamfile.v2 (contents, props changed)
branches/release/libs/algorithm/test/all_of_test.cpp (props changed)
branches/release/libs/algorithm/test/any_of_test.cpp (props changed)
branches/release/libs/algorithm/test/clamp_test.cpp (props changed)
branches/release/libs/algorithm/test/copy_if_test1.cpp (props changed)
branches/release/libs/algorithm/test/copy_n_test1.cpp (props changed)
branches/release/libs/algorithm/test/empty_search_test.cpp (props changed)
branches/release/libs/algorithm/test/find_if_not_test1.cpp (props changed)
branches/release/libs/algorithm/test/hex_fail1.cpp (props changed)
branches/release/libs/algorithm/test/hex_test1.cpp (props changed)
branches/release/libs/algorithm/test/hex_test2.cpp (props changed)
branches/release/libs/algorithm/test/hex_test3.cpp (props changed)
branches/release/libs/algorithm/test/hex_test4.cpp (props changed)
branches/release/libs/algorithm/test/iota_test1.cpp (props changed)
branches/release/libs/algorithm/test/is_partitioned_test1.cpp (props changed)
branches/release/libs/algorithm/test/is_permutation_test1.cpp (contents, props changed)
branches/release/libs/algorithm/test/none_of_test.cpp (props changed)
branches/release/libs/algorithm/test/one_of_test.cpp (props changed)
branches/release/libs/algorithm/test/ordered_test.cpp (props changed)
branches/release/libs/algorithm/test/partition_copy_test1.cpp (props changed)
branches/release/libs/algorithm/test/partition_point_test1.cpp (props changed)
branches/release/libs/algorithm/test/search_fail1.cpp (props changed)
branches/release/libs/algorithm/test/search_fail2.cpp (props changed)
branches/release/libs/algorithm/test/search_fail3.cpp (props changed)
branches/release/libs/algorithm/test/search_test1.cpp (props changed)
branches/release/libs/algorithm/test/search_test2.cpp (props changed)
branches/release/libs/algorithm/test/search_test3.cpp (props changed)
branches/release/libs/algorithm/test/search_test_data/0001.corpus (props changed)
branches/release/libs/algorithm/test/search_test_data/0001b.pat (props changed)
branches/release/libs/algorithm/test/search_test_data/0001e.pat (props changed)
branches/release/libs/algorithm/test/search_test_data/0001f.pat (props changed)
branches/release/libs/algorithm/test/search_test_data/0001n.pat (props changed)
branches/release/libs/algorithm/test/search_test_data/0002b.pat (props changed)
branches/release/libs/algorithm/test/search_test_data/0002e.pat (props changed)
branches/release/libs/algorithm/test/search_test_data/0002f.pat (props changed)
branches/release/libs/algorithm/test/search_test_data/0002n.pat (props changed)
Text files modified:
branches/release/boost/algorithm/cxx11/is_permutation.hpp | 159 +++++++++++++++++++++----
branches/release/libs/algorithm/test/Jamfile.v2 | 4
branches/release/libs/algorithm/test/equal_test.cpp | 169 ++++++++++++++-------------
branches/release/libs/algorithm/test/is_permutation_test1.cpp | 87 ++++++++++++++
branches/release/libs/algorithm/test/mismatch_test.cpp | 244 ++++++++++++++++++++-------------------
5 files changed, 435 insertions(+), 228 deletions(-)
Modified: branches/release/boost/algorithm/cxx11/is_permutation.hpp
==============================================================================
--- branches/release/boost/algorithm/cxx11/is_permutation.hpp (original)
+++ branches/release/boost/algorithm/cxx11/is_permutation.hpp 2013-05-22 11:10:49 EDT (Wed, 22 May 2013)
@@ -25,10 +25,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>
@@ -38,18 +34,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
///
@@ -69,19 +129,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;
@@ -90,23 +138,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
///
Modified: branches/release/libs/algorithm/test/Jamfile.v2
==============================================================================
--- branches/release/libs/algorithm/test/Jamfile.v2 (original)
+++ branches/release/libs/algorithm/test/Jamfile.v2 2013-05-22 11:10:49 EDT (Wed, 22 May 2013)
@@ -47,6 +47,10 @@
[ run is_partitioned_test1.cpp unit_test_framework : : : : is_partitioned_test1 ]
[ run partition_copy_test1.cpp unit_test_framework : : : : partition_copy_test1 ]
+# Cxx14 tests
+ [ run equal_test.cpp unit_test_framework : : : : equal_test ]
+ [ run mismatch_test.cpp unit_test_framework : : : : mismatch_test ]
+
# Hex tests
[ run hex_test1.cpp unit_test_framework : : : : hex_test1 ]
[ run hex_test2.cpp unit_test_framework : : : : hex_test2 ]
Copied: branches/release/libs/algorithm/test/equal_test.cpp (from r84206, /trunk/libs/algorithm/test/equal_test.cpp)
==============================================================================
--- /trunk/libs/algorithm/test/equal_test.cpp (original)
+++ branches/release/libs/algorithm/test/equal_test.cpp 2013-05-22 11:10:49 EDT (Wed, 22 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: branches/release/libs/algorithm/test/is_permutation_test1.cpp
==============================================================================
--- branches/release/libs/algorithm/test/is_permutation_test1.cpp (original)
+++ branches/release/libs/algorithm/test/is_permutation_test1.cpp 2013-05-22 11:10:49 EDT (Wed, 22 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 ();
Copied: branches/release/libs/algorithm/test/mismatch_test.cpp (from r84206, /trunk/libs/algorithm/test/mismatch_test.cpp)
==============================================================================
--- /trunk/libs/algorithm/test/mismatch_test.cpp (original)
+++ branches/release/libs/algorithm/test/mismatch_test.cpp 2013-05-22 11:10:49 EDT (Wed, 22 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)));
}