algorithm/cxx11/is_permutation.hpp

0001 /*
0002    Copyright (c) Marshall Clow 2011-2012.
0003
0004    Distributed under the Boost Software License, Version 1.0. (See accompanying
0005    file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0006 */
0007
0008 /// \file  is_permutation.hpp
0009 /// \brief Is a sequence a permutation of another sequence
0010 /// \author Marshall Clow
0011
0012 #ifndef BOOST_ALGORITHM_IS_PERMUTATION11_HPP
0013 #define BOOST_ALGORITHM_IS_PERMUTATION11_HPP
0014
0015 #include <algorithm>    // for std::find_if, count_if, mismatch
0016 #include <utility>      // for std::pair
0017 #include <functional>   // for std::equal_to
0018 #include <iterator>
0019
0020 #include <boost/config.hpp>
0021 #include <boost/range/begin.hpp>
0022 #include <boost/range/end.hpp>
0023 #include <boost/core/enable_if.hpp>
0024 #include <boost/type_traits/is_same.hpp>
0025
0026 namespace boost { namespace algorithm {
0027
0028 /// \cond DOXYGEN_HIDE
0029 namespace detail {
0030     template <typename Predicate, typename Iterator>
0031     struct value_predicate {
0032         value_predicate ( Predicate p, Iterator it ) : p_ ( p ), it_ ( it ) {}
0033
0034         template <typename T1>
0035         bool operator () ( const T1 &t1 ) const { return p_ ( *it_, t1 ); }
0036     private:
0037         Predicate p_;
0038         Iterator it_;
0039         };
0040
0041 //  Preconditions:
0042 //  1. The sequences are the same length
0043 //  2. Any common elements on the front have been removed (not necessary for correctness, just for performance)
0044     template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate >
0045     bool is_permutation_inner ( ForwardIterator1 first1, ForwardIterator1 last1,
0046                                 ForwardIterator2 first2, ForwardIterator2 last2,
0047                                 BinaryPredicate p ) {
0048         //  for each unique value in the sequence [first1,last1), count how many times
0049         //  it occurs, and make sure it occurs the same number of times in [first2, last2)
0050             for ( ForwardIterator1 iter = first1; iter != last1; ++iter ) {
0051                 value_predicate<BinaryPredicate, ForwardIterator1> pred ( p, iter );
0052
0053             /*  For each value we haven't seen yet... */
0054                 if ( std::find_if ( first1, iter, pred ) == iter ) {
0055                     std::size_t dest_count = std::count_if ( first2, last2, pred );
0056                     if ( dest_count == 0 || dest_count != (std::size_t) std::count_if ( iter, last1, pred ))
0057                         return false;
0058                     }
0059                 }
0060
0061         return true;
0062         }
0063
0064     template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
0065     bool is_permutation_tag ( ForwardIterator1 first1, ForwardIterator1 last1,
0066                           ForwardIterator2 first2, ForwardIterator2 last2,
0067                           BinaryPredicate p,
0068                           std::forward_iterator_tag, std::forward_iterator_tag ) {
0069
0070     //  Skip the common prefix (if any)
0071         while ( first1 != last1 && first2 != last2 && p ( *first1, *first2 )) {
0072             ++first1;
0073             ++first2;
0074             }
0075         if ( first1 != last1 && first2 != last2 )
0076             return boost::algorithm::detail::is_permutation_inner ( first1, last1, first2, last2,
0077                 std::equal_to<typename std::iterator_traits<ForwardIterator1>::value_type> ());
0078         return first1 == last1 && first2 == last2;
0079         }
0080
0081     template <class RandomAccessIterator1, class RandomAccessIterator2, class BinaryPredicate>
0082     bool is_permutation_tag ( RandomAccessIterator1 first1, RandomAccessIterator1 last1,
0083                           RandomAccessIterator2 first2, RandomAccessIterator2 last2,
0084                           BinaryPredicate p,
0085                           std::random_access_iterator_tag, std::random_access_iterator_tag ) {
0086     //  Cheap check
0087         if ( std::distance ( first1, last1 ) != std::distance ( first2, last2 ))
0088             return false;
0089     //  Skip the common prefix (if any)
0090         while ( first1 != last1 && first2 != last2 && p ( *first1, *first2 )) {
0091             ++first1;
0092             ++first2;
0093             }
0094
0095         if ( first1 != last1 && first2 != last2 )
0096             return is_permutation_inner (first1, last1, first2, last2, p);
0097         return first1 == last1 && first2 == last2;
0098         }
0099
0100 }
0101 /// \endcond
0102
0103 /// \fn is_permutation ( ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 first2, BinaryPredicate p )
0104 /// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2
0105 ///
0106 /// \param first1   The start of the input sequence
0107 /// \param last1    One past the end of the input sequence
0108 /// \param first2   The start of the second sequence
0109 /// \param p        The predicate to compare elements with
0110 ///
0111 /// \note           This function is part of the C++2011 standard library.
0112 template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate >
0113 bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1,
0114                       ForwardIterator2 first2, BinaryPredicate p )
0115 {
0116 //  Skip the common prefix (if any)
0117     std::pair<ForwardIterator1, ForwardIterator2> eq = std::mismatch (first1, last1, first2, p);
0118     first1 = eq.first;
0119     first2 = eq.second;
0120     if ( first1 != last1 ) {
0121     //  Create last2
0122         ForwardIterator2 last2 = first2;
0123         std::advance ( last2, std::distance (first1, last1));
0124         return boost::algorithm::detail::is_permutation_inner ( first1, last1, first2, last2, p );
0125         }
0126
0127     return true;
0128 }
0129
0130 /// \fn is_permutation ( ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 first2 )
0131 /// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2
0132 ///
0133 /// \param first1   The start of the input sequence
0134 /// \param last2    One past the end of the input sequence
0135 /// \param first2   The start of the second sequence
0136 /// \note           This function is part of the C++2011 standard library.
0137 template< class ForwardIterator1, class ForwardIterator2 >
0138 bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2 )
0139 {
0140 //  How should I deal with the idea that ForwardIterator1::value_type
0141 //  and ForwardIterator2::value_type could be different? Define my own comparison predicate?
0142 //  Skip the common prefix (if any)
0143     std::pair<ForwardIterator1, ForwardIterator2> eq = std::mismatch (first1, last1, first2 );
0144     first1 = eq.first;
0145     first2 = eq.second;
0146     if ( first1 != last1 ) {
0147     //  Create last2
0148         ForwardIterator2 last2 = first2;
0149         std::advance ( last2, std::distance (first1, last1));
0150         return boost::algorithm::detail::is_permutation_inner ( first1, last1, first2, last2,
0151             std::equal_to<typename std::iterator_traits<ForwardIterator1>::value_type> ());
0152         }
0153     return true;
0154 }
0155
0156
0157 /// \fn is_permutation ( const Range &r, ForwardIterator first2 )
0158 /// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2
0159 ///
0160 /// \param r        The input range
0161 /// \param first2   The start of the second sequence
0162 template <typename Range, typename ForwardIterator>
0163 bool is_permutation ( const Range &r, ForwardIterator first2 )
0164 {
0165     return boost::algorithm::is_permutation (boost::begin (r), boost::end (r), first2 );
0166 }
0167
0168 /// \fn is_permutation ( const Range &r, ForwardIterator first2, BinaryPredicate pred )
0169 /// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2
0170 ///
0171 /// \param r        The input range
0172 /// \param first2   The start of the second sequence
0173 /// \param pred     The predicate to compare elements with
0174 ///
0175 //  Disable this template when the first two parameters are the same type
0176 //  That way the non-range version will be chosen.
0177 template <typename Range, typename ForwardIterator, typename BinaryPredicate>
0178 typename boost::disable_if_c<boost::is_same<Range, ForwardIterator>::value, bool>::type
0179 is_permutation ( const Range &r, ForwardIterator first2, BinaryPredicate pred )
0180 {
0181     return boost::algorithm::is_permutation (boost::begin (r), boost::end (r), first2, pred );
0182 }
0183
0184 }}
0185
0186 #endif  // BOOST_ALGORITHM_IS_PERMUTATION11_HPP