diff options
Diffstat (limited to 'boost/algorithm/cxx11/is_permutation.hpp')
| -rw-r--r-- | boost/algorithm/cxx11/is_permutation.hpp | 125 |
1 files changed, 91 insertions, 34 deletions
diff --git a/boost/algorithm/cxx11/is_permutation.hpp b/boost/algorithm/cxx11/is_permutation.hpp index 33cb712378..9b3bc220fa 100644 --- a/boost/algorithm/cxx11/is_permutation.hpp +++ b/boost/algorithm/cxx11/is_permutation.hpp @@ -9,8 +9,8 @@ /// \brief Is a sequence a permutation of another sequence /// \author Marshall Clow -#ifndef BOOST_ALGORITHM_IS_PERMUTATION_HPP -#define BOOST_ALGORITHM_IS_PERMUTATION_HPP +#ifndef BOOST_ALGORITHM_IS_PERMUTATION11_HPP +#define BOOST_ALGORITHM_IS_PERMUTATION11_HPP #include <algorithm> // for std::less, tie, mismatch and is_permutation (if available) #include <utility> // for std::make_pair @@ -21,14 +21,9 @@ #include <boost/range/end.hpp> #include <boost/utility/enable_if.hpp> #include <boost/type_traits/is_same.hpp> -#include <boost/tr1/tr1/tuple> // for tie namespace boost { namespace algorithm { -#if __cplusplus >= 201103L -// Use the C++11 versions of is_permutation if it is available -using std::is_permutation; // Section 25.2.12 -#else /// \cond DOXYGEN_HIDE namespace detail { template <typename Predicate, typename Iterator> @@ -38,18 +33,82 @@ namespace detail { 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 a the sequence [first,last) is a permutation of the sequence starting at 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 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 /// @@ -61,7 +120,6 @@ 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; @@ -69,46 +127,45 @@ bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1, // Create last2 ForwardIterator2 last2 = first2; std::advance ( last2, std::distance (first1, last1)); - - // for each unique value in the sequence [first1,last1), count how many times - // it occurs, and make sure it occurs the same number of times in [first2, last2) - for ( ForwardIterator1 iter = first1; iter != last1; ++iter ) { - detail::value_predicate<BinaryPredicate, ForwardIterator1> pred ( p, iter ); - - /* For each value we haven't seen yet... */ - if ( std::find_if ( first1, iter, pred ) == iter ) { - std::size_t dest_count = std::count_if ( first2, last2, pred ); - if ( dest_count == 0 || dest_count != (std::size_t) std::count_if ( iter, last1, pred )) - return false; - } - } + return boost::algorithm::detail::is_permutation_inner ( first1, last1, first2, last2, p ); } return true; } /// \fn is_permutation ( ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 first2 ) -/// \brief Tests to see if a the sequence [first,last) is a permutation of the sequence starting at first2 +/// \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 ( const Range &r, ForwardIterator first2 ) -/// \brief Tests to see if a the sequence [first,last) is a permutation of the sequence starting at first2 +/// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2 /// /// \param r The input range /// \param first2 The start of the second sequence @@ -119,7 +176,7 @@ bool is_permutation ( const Range &r, ForwardIterator first2 ) } /// \fn is_permutation ( const Range &r, ForwardIterator first2, BinaryPredicate pred ) -/// \brief Tests to see if a the sequence [first,last) is a permutation of the sequence starting at first2 +/// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2 /// /// \param r The input range /// \param first2 The start of the second sequence @@ -136,4 +193,4 @@ is_permutation ( const Range &r, ForwardIterator first2, BinaryPredicate pred ) }} -#endif // BOOST_ALGORITHM_IS_PERMUTATION_HPP +#endif // BOOST_ALGORITHM_IS_PERMUTATION11_HPP |