Release 1.55.0

[SVN r86621]

doc/equal.qbk

@@ -22,7 +22,7 @@ Consider the two sequences:
 	
 	std::equal ( seq1.begin (), seq1.end (), seq2.begin ()); // true
 	std::equal ( seq2.begin (), seq2.end (), seq1.begin ()); // Undefined behavior
-	std::equal ( seq1.begin (), seq1.end (), seq1.begin (), seq2.end ()); // false
+	std::equal ( seq1.begin (), seq1.end (), seq2.begin (), seq2.end ()); // false
 ```
 
 You can argue that `true` is the correct answer in the first case, even though the sequences are not the same. The first N entries in `seq2` are the same as the entries in `seq1` - but that's not all that's in `seq2`. But in the second case, the algorithm will read past the end of `seq1`, resulting in undefined behavior (large earthquake, incorrect results, pregnant cat, etc).

doc/mismatch.qbk

@@ -22,7 +22,7 @@ Consider the two sequences:
 	
 	std::mismatch ( seq1.begin (), seq1.end (), seq2.begin ()); // <3, 3>
 	std::mismatch ( seq2.begin (), seq2.end (), seq1.begin ()); // Undefined behavior
-	std::mismatch ( seq1.begin (), seq1.end (), seq1.begin (), seq2.end ()); // <3, 3>
+	std::mismatch ( seq1.begin (), seq1.end (), seq2.begin (), seq2.end ()); // <3, 3>
 ```
 
 The first N entries in `seq2` are the same as the entries in `seq1` - but that's not all that's in `seq2`. In the second case, the algorithm will read past the end of `seq1`, resulting in undefined behavior (large earthquake, incorrect results, pregnant cat, etc).

include/boost/algorithm/cxx11/iota.hpp

@@ -63,8 +63,8 @@ void iota ( Range &r, T value )
 template <typename OutputIterator, typename T>
 OutputIterator iota_n ( OutputIterator out, T value, std::size_t n )
 {
-    for ( ; n > 0; --n, ++value )
+    while ( n-- > 0 )
-        *out++ = value;
+        *out++ = value++;
 
     return out;
 }

include/boost/algorithm/cxx11/is_permutation.hpp

@@ -21,6 +21,7 @@
 #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 {
 
@@ -120,6 +121,7 @@ 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;

include/boost/algorithm/cxx14/is_permutation.hpp

@@ -0,0 +1,130 @@
+/* 
+   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

include/boost/algorithm/searching/detail/bm_traits.hpp

@@ -20,11 +20,7 @@
 #include <boost/type_traits/remove_const.hpp>
 
 #include <boost/array.hpp>
-#ifdef BOOST_NO_CXX11_HDR_UNORDERED_MAP
 #include <boost/tr1/tr1/unordered_map>
-#else
-#include <unordered_map>
-#endif
 
 #include <boost/algorithm/searching/detail/debugging.hpp>
 
@@ -39,11 +35,7 @@ namespace boost { namespace algorithm { namespace detail {
     template<typename key_type, typename value_type>
     class skip_table<key_type, value_type, false> {
     private:
-#ifdef BOOST_NO_CXX11_HDR_UNORDERED_MAP
         typedef std::tr1::unordered_map<key_type, value_type> skip_map;
-#else
-        typedef std::unordered_map<key_type, value_type> skip_map;
-#endif
         const value_type k_default_value;
         skip_map skip_;
         

include/boost/algorithm/string/find_iterator.hpp

@@ -132,12 +132,7 @@ namespace boost {
             // increment
             void increment()
             {
-                if(m_Match.begin() == m_Match.end())
                 m_Match=this->do_find(m_Match.end(),m_End);
-                else {
-                    input_iterator_type last = m_Match.begin();
-                    m_Match=this->do_find(++last,m_End);
-                    }
             }
 
             // comparison

include/boost/algorithm/wrappers.hpp

@@ -1,52 +0,0 @@
-/* 
-   Copyright (c) Marshall Clow 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)
-   
-   Alternate interfaces (aka "wrappers") for algorithms.
-*/
-
-#ifndef BOOST_ALGORITHM_WRAPPERS_HPP
-#define BOOST_ALGORITHM_WRAPPERS_HPP
-
-namespace boost { namespace algorithm {
-
-/// \fn find_ptr ( Container &c, Key k )
-/// \return a pointer to the value matching the key in the container, 
-/// or NULL if the key does not exist in the container.
-///
-/// \note: This is a wrapper around Container::find, with a useful interface.
-/// Suggested by Olaf van der Spek 
-/// 
-/// \param c    The container to be searched
-/// \param k    The key value to search with
-template <class Container, class Key>
-typename Container::value_type::second_type* 
-find_ptr ( Container &c, Key k )
-{
-    typename Container::iterator iter = c.find ( k );
-    return iter == c.end() ? NULL : &iter->second;
-}
-
-/// \fn find_ptr ( const Container &c, Key k )
-/// \return a pointer to the value matching the key in the container, 
-/// or NULL if the key does not exist in the container.
-///
-/// \note: This is a wrapper around Container::find, with a useful interface.
-/// Suggested by Olaf van der Spek 
-/// 
-/// \param c    The container to be searched
-/// \param k    The key value to search with
-template <class Container, class Key>
-const typename Container::value_type::second_type* 
-find_ptr ( const Container &c, Key k )
-{
-    typename Container::const_iterator iter = c.find ( k );
-    return iter == c.end() ? NULL : &iter->second;
-}
-
-
-}}
-
-#endif

string/test/find_test.cpp

@@ -181,6 +181,21 @@ void find_test()
         ( (cv_result.begin()-str1.begin()) == 3) &&
         ( (cv_result.end()-str1.begin()) == 6) );
 
+    string s1("abc def ghi jkl");
+    find_iterator<string::iterator> fEnd;
+
+    find_iterator<string::iterator> fxIt = make_find_iterator(s1,
+            token_finder(is_alnum(), token_compress_on));
+    BOOST_CHECK((fxIt != fEnd) && (*fxIt == string("abc")));
+    ++fxIt;
+    BOOST_CHECK((fxIt != fEnd) && (*fxIt == string("def")));
+    ++fxIt;
+    BOOST_CHECK((fxIt != fEnd) && (*fxIt == string("ghi")));
+    ++fxIt;
+    BOOST_CHECK((fxIt != fEnd) && (*fxIt == string("jkl")));
+    ++fxIt;
+    BOOST_CHECK(fxIt == fEnd);
+
     nc_result=find_token( str1, is_any_of("abc"), token_compress_off );
     BOOST_CHECK( 
         ( (nc_result.begin()-str1.begin()) == 3) &&
@@ -251,19 +266,6 @@ void find_test()
     osstr << find_first( str1, "abc" );
     BOOST_CHECK( osstr.str()=="abc" );
 
-    // Empty string test
-    BOOST_TEST_CHECKPOINT( "overlapping" );
-    
-    std::string overlap_target("aaaa");
-    std::vector<boost::iterator_range<std::string::iterator> > overlap_results;
-    boost::algorithm::find_all(overlap_results, overlap_target, string("aaa"));
-    BOOST_CHECK( overlap_results.size() == 2 );
-
-    std::string overlap_target2("aaaabbbbaaaa");
-    boost::algorithm::find_all(overlap_results, overlap_target2, string("bb"));
-    BOOST_CHECK( overlap_results.size() == 3 );
-    boost::algorithm::find_all(overlap_results, overlap_target2, string("aa"));
-    BOOST_CHECK( overlap_results.size() == 6 );
 }
 
 // test main 

test/Jamfile.v2

@@ -58,9 +58,6 @@ alias unit_test_framework
      [ run hex_test4.cpp unit_test_framework         : : : : hex_test4 ]
      [ compile-fail hex_fail1.cpp ]
 
-# Wrapper tests
-     [ run wrapper_test1.cpp unit_test_framework         : : : : wrapper_test1 ]
-
 # Gather tests
      [ run gather_test1.cpp unit_test_framework        : : : : gather_test1 ]
      [ compile-fail gather_fail1.cpp ]

test/iota_test1.cpp

@@ -42,11 +42,11 @@ void test_ints () {
     std::vector<int> v;
     std::list<int> l;
 
-    v.clear (); v.resize ( 10 );
+    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.resize ( 19 );
+    v.clear (); v.reserve ( 19 );
     boost::algorithm::iota ( v, 18 );
     BOOST_CHECK ( test_iota_results ( v, 18 ));
     
@@ -54,10 +54,6 @@ void test_ints () {
     boost::algorithm::iota_n ( std::back_inserter(v), 99, 20 );
     BOOST_CHECK ( test_iota_results ( v, 99 ));
     
-    v.clear ();
-    boost::algorithm::iota_n ( std::back_inserter(v), 99, 0 );
-    BOOST_CHECK ( v.size() == 0 );
-
 /*
     l.clear (); l.reserve ( 5 );
     boost::algorithm::iota ( l.begin (), l.end (), 123 );

test/iterator_test.hpp

@@ -1,3 +1,12 @@
+/* 
+   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)
+
+    For more information, see http://www.boost.org
+*/
+
 #ifndef ITERATOR_TEST_H
 #define ITERATOR_TEST_H
 

test/wrapper_test1.cpp

@@ -1,76 +0,0 @@
-/* 
-   Copyright (c) Marshall Clow 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/wrappers.hpp>
-
-#define BOOST_TEST_MAIN
-#include <boost/test/unit_test.hpp>
-
-#include <functional>
-#include <string>
-#include <map>
-
-namespace ba = boost::algorithm;
-
-void test_int ()
-{
-    std::map<int, int> m;
-    std::multimap<int, int> mm;
-    
-    int *ptr;
-    
-//  try with an empty map
-    BOOST_CHECK ( ba::find_ptr ( m , 3 ) == NULL );
-    BOOST_CHECK ( ba::find_ptr ( mm, 3 ) == NULL );
-    
-    m.insert  ( std::make_pair <int, int> ( 5, 5 ));
-    mm.insert ( std::make_pair <int, int> ( 9, 9 ));
-    BOOST_CHECK ( ba::find_ptr ( m , 3 ) == NULL );
-    BOOST_CHECK ( ba::find_ptr ( mm, 3 ) == NULL );
-
-    ptr = ba::find_ptr ( m, 5 );
-    BOOST_CHECK ( ptr != NULL && *ptr == 5 );
-    BOOST_CHECK ( ba::find_ptr ( m , 9 ) == NULL );
-
-    ptr = ba::find_ptr ( mm, 9 );
-    BOOST_CHECK ( ptr != NULL && *ptr == 9 );
-    BOOST_CHECK ( ba::find_ptr ( mm, 5 ) == NULL );
-    
-}
-
-void test_str ()
-{
-    std::map<int, std::string> m;
-    std::multimap<int, std::string> mm;
-    std::string *ptr;
-
-//  try with an empty map
-    BOOST_CHECK ( ba::find_ptr ( m , 31 ) == NULL );
-    BOOST_CHECK ( ba::find_ptr ( mm, 31 ) == NULL );
-    
-    m.insert  ( std::make_pair <int, std::string> ( 55, "fifty-five" ));
-    mm.insert ( std::make_pair <int, std::string> ( 66, "sixty-six" ));
-    BOOST_CHECK ( ba::find_ptr ( m , 3 ) == NULL );
-    BOOST_CHECK ( ba::find_ptr ( mm, 3 ) == NULL );
-
-    ptr = ba::find_ptr ( m, 55 );
-    BOOST_CHECK ( ptr != NULL && *ptr == "fifty-five" );
-    BOOST_CHECK ( ba::find_ptr ( m , 66 ) == NULL );
-
-    ptr = ba::find_ptr ( mm, 66 );
-    BOOST_CHECK ( ptr != NULL && *ptr == "sixty-six" );
-    BOOST_CHECK ( ba::find_ptr ( mm, 55 ) == NULL );
-}
-
-BOOST_AUTO_TEST_CASE( test_main )
-{
-  test_int ();
-  test_str ();
-}