Chris@16: /*
Chris@16:    Copyright (c) Marshall Clow 2011-2012.
Chris@16: 
Chris@16:    Distributed under the Boost Software License, Version 1.0. (See accompanying
Chris@16:    file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
Chris@16: */
Chris@16: 
Chris@16: /// \file  is_permutation.hpp
Chris@16: /// \brief Is a sequence a permutation of another sequence
Chris@16: /// \author Marshall Clow
Chris@16: 
Chris@101: #ifndef BOOST_ALGORITHM_IS_PERMUTATION11_HPP
Chris@101: #define BOOST_ALGORITHM_IS_PERMUTATION11_HPP
Chris@16: 
Chris@16: #include <algorithm>    // for std::less, tie, mismatch and is_permutation (if available)
Chris@16: #include <utility>      // for std::make_pair
Chris@16: #include <functional>   // for std::equal_to
Chris@16: #include <iterator>
Chris@16: 
Chris@16: #include <boost/range/begin.hpp>
Chris@16: #include <boost/range/end.hpp>
Chris@16: #include <boost/utility/enable_if.hpp>
Chris@16: #include <boost/type_traits/is_same.hpp>
Chris@16: 
Chris@16: namespace boost { namespace algorithm {
Chris@16: 
Chris@16: /// \cond DOXYGEN_HIDE
Chris@16: namespace detail {
Chris@16:     template <typename Predicate, typename Iterator>
Chris@16:     struct value_predicate {
Chris@16:         value_predicate ( Predicate p, Iterator it ) : p_ ( p ), it_ ( it ) {}
Chris@16: 
Chris@16:         template <typename T1>
Chris@16:         bool operator () ( const T1 &t1 ) const { return p_ ( *it_, t1 ); }
Chris@16:     private:
Chris@16:         Predicate p_;
Chris@16:         Iterator it_;
Chris@16:         };
Chris@16:         
Chris@16: //  Preconditions:
Chris@16: //  1. The sequences are the same length
Chris@16: //  2. Any common elements on the front have been removed (not necessary for correctness, just for performance)
Chris@16:     template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate >
Chris@16:     bool is_permutation_inner ( ForwardIterator1 first1, ForwardIterator1 last1,
Chris@16:                                 ForwardIterator2 first2, ForwardIterator2 last2,
Chris@16:                                 BinaryPredicate p ) {
Chris@16:         //  for each unique value in the sequence [first1,last1), count how many times
Chris@16:         //  it occurs, and make sure it occurs the same number of times in [first2, last2)
Chris@16:             for ( ForwardIterator1 iter = first1; iter != last1; ++iter ) {
Chris@16:                 value_predicate<BinaryPredicate, ForwardIterator1> pred ( p, iter );
Chris@16: 
Chris@16:             /*  For each value we haven't seen yet... */
Chris@16:                 if ( std::find_if ( first1, iter, pred ) == iter ) {
Chris@16:                     std::size_t dest_count = std::count_if ( first2, last2, pred );
Chris@16:                     if ( dest_count == 0 || dest_count != (std::size_t) std::count_if ( iter, last1, pred ))
Chris@16:                         return false;
Chris@16:                     }
Chris@16:                 }
Chris@16: 
Chris@16:         return true;
Chris@16:         }                      
Chris@16: 
Chris@16:     template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
Chris@16:     bool is_permutation_tag ( ForwardIterator1 first1, ForwardIterator1 last1, 
Chris@16:                           ForwardIterator2 first2, ForwardIterator2 last2, 
Chris@16:                           BinaryPredicate p,
Chris@16:                           std::forward_iterator_tag, std::forward_iterator_tag ) {
Chris@16: 
Chris@16:     //  Skip the common prefix (if any)
Chris@16:         while ( first1 != last1 && first2 != last2 && p ( *first1, *first2 )) {
Chris@16:             ++first1;
Chris@16:             ++first2;
Chris@16:             }
Chris@16:         if ( first1 != last1 && first2 != last2 )
Chris@16:             return boost::algorithm::detail::is_permutation_inner ( first1, last1, first2, last2,
Chris@16:                 std::equal_to<typename std::iterator_traits<ForwardIterator1>::value_type> ());
Chris@16:         return first1 == last1 && first2 == last2;
Chris@16:         }
Chris@16: 
Chris@16:     template <class RandomAccessIterator1, class RandomAccessIterator2, class BinaryPredicate>
Chris@16:     bool is_permutation_tag ( RandomAccessIterator1 first1, RandomAccessIterator1 last1, 
Chris@16:                           RandomAccessIterator2 first2, RandomAccessIterator2 last2, 
Chris@16:                           BinaryPredicate p,
Chris@16:                           std::random_access_iterator_tag, std::random_access_iterator_tag ) {
Chris@16:     //  Cheap check
Chris@16:         if ( std::distance ( first1, last1 ) != std::distance ( first2, last2 ))
Chris@16:             return false;
Chris@16:     //  Skip the common prefix (if any)
Chris@16:         while ( first1 != last1 && first2 != last2 && p ( *first1, *first2 )) {
Chris@16:             ++first1;
Chris@16:             ++first2;
Chris@16:             }
Chris@16: 
Chris@16:         if ( first1 != last1 && first2 != last2 )
Chris@16:             return is_permutation_inner (first1, last1, first2, last2, p);
Chris@16:         return first1 == last1 && first2 == last2;
Chris@16:         }
Chris@16: 
Chris@16: }
Chris@16: /// \endcond
Chris@16: 
Chris@16: /// \fn is_permutation ( ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 first2, BinaryPredicate p )
Chris@16: /// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2
Chris@16: ///
Chris@16: /// \param first1   The start of the input sequence
Chris@16: /// \param last1    One past the end of the input sequence
Chris@16: /// \param first2   The start of the second sequence
Chris@16: /// \param p        The predicate to compare elements with
Chris@16: ///
Chris@16: /// \note           This function is part of the C++2011 standard library.
Chris@16: ///  We will use the standard one if it is available,
Chris@16: ///     otherwise we have our own implementation.
Chris@16: template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate >
Chris@16: bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1,
Chris@16:                       ForwardIterator2 first2, BinaryPredicate p )
Chris@16: {
Chris@16: //  Skip the common prefix (if any)
Chris@16:     std::pair<ForwardIterator1, ForwardIterator2> eq = std::mismatch (first1, last1, first2, p);
Chris@16:     first1 = eq.first;
Chris@16:     first2 = eq.second;
Chris@16:     if ( first1 != last1 ) {
Chris@16:     //  Create last2
Chris@16:         ForwardIterator2 last2 = first2;
Chris@16:         std::advance ( last2, std::distance (first1, last1));
Chris@16:         return boost::algorithm::detail::is_permutation_inner ( first1, last1, first2, last2, p );
Chris@16:         }
Chris@16: 
Chris@16:     return true;
Chris@16: }
Chris@16: 
Chris@16: /// \fn is_permutation ( ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 first2 )
Chris@16: /// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2
Chris@16: ///
Chris@16: /// \param first1   The start of the input sequence
Chris@16: /// \param last2    One past the end of the input sequence
Chris@16: /// \param first2   The start of the second sequence
Chris@16: /// \note           This function is part of the C++2011 standard library.
Chris@16: ///  We will use the standard one if it is available,
Chris@16: ///     otherwise we have our own implementation.
Chris@16: template< class ForwardIterator1, class ForwardIterator2 >
Chris@16: bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2 )
Chris@16: {
Chris@16: //  How should I deal with the idea that ForwardIterator1::value_type
Chris@16: //  and ForwardIterator2::value_type could be different? Define my own comparison predicate?
Chris@16: //  Skip the common prefix (if any)
Chris@16:     std::pair<ForwardIterator1, ForwardIterator2> eq = std::mismatch (first1, last1, first2 );
Chris@16:     first1 = eq.first;
Chris@16:     first2 = eq.second;
Chris@16:     if ( first1 != last1 ) {
Chris@16:     //  Create last2
Chris@16:         ForwardIterator2 last2 = first2;
Chris@16:         std::advance ( last2, std::distance (first1, last1));
Chris@16:         return boost::algorithm::detail::is_permutation_inner ( first1, last1, first2, last2,
Chris@16:             std::equal_to<typename std::iterator_traits<ForwardIterator1>::value_type> ());
Chris@16:         }
Chris@16:     return true;
Chris@16: }
Chris@16: 
Chris@16: 
Chris@16: /// \fn is_permutation ( const Range &r, ForwardIterator first2 )
Chris@16: /// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2
Chris@16: ///
Chris@16: /// \param r        The input range
Chris@16: /// \param first2   The start of the second sequence
Chris@16: template <typename Range, typename ForwardIterator>
Chris@16: bool is_permutation ( const Range &r, ForwardIterator first2 )
Chris@16: {
Chris@16:     return boost::algorithm::is_permutation (boost::begin (r), boost::end (r), first2 );
Chris@16: }
Chris@16: 
Chris@16: /// \fn is_permutation ( const Range &r, ForwardIterator first2, BinaryPredicate pred )
Chris@16: /// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2
Chris@16: ///
Chris@16: /// \param r        The input range
Chris@16: /// \param first2   The start of the second sequence
Chris@16: /// \param pred     The predicate to compare elements with
Chris@16: ///
Chris@16: //  Disable this template when the first two parameters are the same type
Chris@16: //  That way the non-range version will be chosen.
Chris@16: template <typename Range, typename ForwardIterator, typename BinaryPredicate>
Chris@16: typename boost::disable_if_c<boost::is_same<Range, ForwardIterator>::value, bool>::type
Chris@16: is_permutation ( const Range &r, ForwardIterator first2, BinaryPredicate pred )
Chris@16: {
Chris@16:     return boost::algorithm::is_permutation (boost::begin (r), boost::end (r), first2, pred );
Chris@16: }
Chris@16: 
Chris@16: }}
Chris@16: 
Chris@101: #endif  // BOOST_ALGORITHM_IS_PERMUTATION11_HPP