1 /* Copyright (c) Marshall Clow 2011-2012. Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) */ /// \file is_permutation.hpp /// \brief Is a sequence a permutation of another sequence /// \author Marshall Clow #ifndef BOOST_ALGORITHM_IS_PERMUTATION11_HPP #define BOOST_ALGORITHM_IS_PERMUTATION11_HPP #include // for std::less, tie, mismatch and is_permutation (if available) #include // for std::make_pair #include // for std::equal_to #include #include #include #include #include namespace boost { namespace algorithm { /// \cond DOXYGEN_HIDE namespace detail { template struct value_predicate { value_predicate ( Predicate p, Iterator it ) : p_ ( p ), it_ ( it ) {} template bool operator () ( const T1 &t1 ) const { return p_ ( *it_, t1 ); } private: 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 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::value_type> ()); return first1 == last1 && first2 == last2; } template 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 /// \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 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 /// /// \note This function is part of the C++2011 standard library. /// We will use the standard one if it is available, /// otherwise we have our own implementation. template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate > bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, BinaryPredicate p ) { // Skip the common prefix (if any) std::pair eq = std::mismatch (first1, last1, first2, p); first1 = eq.first; first2 = eq.second; if ( first1 != last1 ) { // Create last2 ForwardIterator2 last2 = first2; std::advance ( last2, std::distance (first1, last1)); 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 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 /// \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 ) { // How should I deal with the idea that ForwardIterator1::value_type // and ForwardIterator2::value_type could be different? Define my own comparison predicate? // Skip the common prefix (if any) std::pair 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::value_type> ()); } return true; } /// \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 /// /// \param r The input range /// \param first2 The start of the second sequence template bool is_permutation ( const Range &r, ForwardIterator first2 ) { return boost::algorithm::is_permutation (boost::begin (r), boost::end (r), first2 ); } /// \fn is_permutation ( const Range &r, ForwardIterator first2, BinaryPredicate pred ) /// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2 /// /// \param r The input range /// \param first2 The start of the second sequence /// \param pred The predicate to compare elements with /// // Disable this template when the first two parameters are the same type // That way the non-range version will be chosen. template typename boost::disable_if_c::value, bool>::type is_permutation ( const Range &r, ForwardIterator first2, BinaryPredicate pred ) { return boost::algorithm::is_permutation (boost::begin (r), boost::end (r), first2, pred ); } }} #endif // BOOST_ALGORITHM_IS_PERMUTATION11_HPP