2 Copyright (c) Marshall Clow 2011-2012.
4 Distributed under the Boost Software License, Version 1.0. (See accompanying
5 file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
8 /// \file is_permutation.hpp
9 /// \brief Is a sequence a permutation of another sequence
10 /// \author Marshall Clow
12 #ifndef BOOST_ALGORITHM_IS_PERMUTATION11_HPP
13 #define BOOST_ALGORITHM_IS_PERMUTATION11_HPP
15 #include <algorithm> // for std::find_if, count_if, mismatch
16 #include <utility> // for std::pair
17 #include <functional> // for std::equal_to
20 #include <boost/range/begin.hpp>
21 #include <boost/range/end.hpp>
22 #include <boost/utility/enable_if.hpp>
23 #include <boost/type_traits/is_same.hpp>
25 namespace boost { namespace algorithm {
27 /// \cond DOXYGEN_HIDE
29 template <typename Predicate, typename Iterator>
30 struct value_predicate {
31 value_predicate ( Predicate p, Iterator it ) : p_ ( p ), it_ ( it ) {}
33 template <typename T1>
34 bool operator () ( const T1 &t1 ) const { return p_ ( *it_, t1 ); }
41 // 1. The sequences are the same length
42 // 2. Any common elements on the front have been removed (not necessary for correctness, just for performance)
43 template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate >
44 bool is_permutation_inner ( ForwardIterator1 first1, ForwardIterator1 last1,
45 ForwardIterator2 first2, ForwardIterator2 last2,
47 // for each unique value in the sequence [first1,last1), count how many times
48 // it occurs, and make sure it occurs the same number of times in [first2, last2)
49 for ( ForwardIterator1 iter = first1; iter != last1; ++iter ) {
50 value_predicate<BinaryPredicate, ForwardIterator1> pred ( p, iter );
52 /* For each value we haven't seen yet... */
53 if ( std::find_if ( first1, iter, pred ) == iter ) {
54 std::size_t dest_count = std::count_if ( first2, last2, pred );
55 if ( dest_count == 0 || dest_count != (std::size_t) std::count_if ( iter, last1, pred ))
63 template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
64 bool is_permutation_tag ( ForwardIterator1 first1, ForwardIterator1 last1,
65 ForwardIterator2 first2, ForwardIterator2 last2,
67 std::forward_iterator_tag, std::forward_iterator_tag ) {
69 // Skip the common prefix (if any)
70 while ( first1 != last1 && first2 != last2 && p ( *first1, *first2 )) {
74 if ( first1 != last1 && first2 != last2 )
75 return boost::algorithm::detail::is_permutation_inner ( first1, last1, first2, last2,
76 std::equal_to<typename std::iterator_traits<ForwardIterator1>::value_type> ());
77 return first1 == last1 && first2 == last2;
80 template <class RandomAccessIterator1, class RandomAccessIterator2, class BinaryPredicate>
81 bool is_permutation_tag ( RandomAccessIterator1 first1, RandomAccessIterator1 last1,
82 RandomAccessIterator2 first2, RandomAccessIterator2 last2,
84 std::random_access_iterator_tag, std::random_access_iterator_tag ) {
86 if ( std::distance ( first1, last1 ) != std::distance ( first2, last2 ))
88 // Skip the common prefix (if any)
89 while ( first1 != last1 && first2 != last2 && p ( *first1, *first2 )) {
94 if ( first1 != last1 && first2 != last2 )
95 return is_permutation_inner (first1, last1, first2, last2, p);
96 return first1 == last1 && first2 == last2;
102 /// \fn is_permutation ( ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 first2, BinaryPredicate p )
103 /// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2
105 /// \param first1 The start of the input sequence
106 /// \param last1 One past the end of the input sequence
107 /// \param first2 The start of the second sequence
108 /// \param p The predicate to compare elements with
110 /// \note This function is part of the C++2011 standard library.
111 template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate >
112 bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1,
113 ForwardIterator2 first2, BinaryPredicate p )
115 // Skip the common prefix (if any)
116 std::pair<ForwardIterator1, ForwardIterator2> eq = std::mismatch (first1, last1, first2, p);
119 if ( first1 != last1 ) {
121 ForwardIterator2 last2 = first2;
122 std::advance ( last2, std::distance (first1, last1));
123 return boost::algorithm::detail::is_permutation_inner ( first1, last1, first2, last2, p );
129 /// \fn is_permutation ( ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 first2 )
130 /// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2
132 /// \param first1 The start of the input sequence
133 /// \param last2 One past the end of the input sequence
134 /// \param first2 The start of the second sequence
135 /// \note This function is part of the C++2011 standard library.
136 template< class ForwardIterator1, class ForwardIterator2 >
137 bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2 )
139 // How should I deal with the idea that ForwardIterator1::value_type
140 // and ForwardIterator2::value_type could be different? Define my own comparison predicate?
141 // Skip the common prefix (if any)
142 std::pair<ForwardIterator1, ForwardIterator2> eq = std::mismatch (first1, last1, first2 );
145 if ( first1 != last1 ) {
147 ForwardIterator2 last2 = first2;
148 std::advance ( last2, std::distance (first1, last1));
149 return boost::algorithm::detail::is_permutation_inner ( first1, last1, first2, last2,
150 std::equal_to<typename std::iterator_traits<ForwardIterator1>::value_type> ());
156 /// \fn is_permutation ( const Range &r, ForwardIterator first2 )
157 /// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2
159 /// \param r The input range
160 /// \param first2 The start of the second sequence
161 template <typename Range, typename ForwardIterator>
162 bool is_permutation ( const Range &r, ForwardIterator first2 )
164 return boost::algorithm::is_permutation (boost::begin (r), boost::end (r), first2 );
167 /// \fn is_permutation ( const Range &r, ForwardIterator first2, BinaryPredicate pred )
168 /// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2
170 /// \param r The input range
171 /// \param first2 The start of the second sequence
172 /// \param pred The predicate to compare elements with
174 // Disable this template when the first two parameters are the same type
175 // That way the non-range version will be chosen.
176 template <typename Range, typename ForwardIterator, typename BinaryPredicate>
177 typename boost::disable_if_c<boost::is_same<Range, ForwardIterator>::value, bool>::type
178 is_permutation ( const Range &r, ForwardIterator first2, BinaryPredicate pred )
180 return boost::algorithm::is_permutation (boost::begin (r), boost::end (r), first2, pred );
185 #endif // BOOST_ALGORITHM_IS_PERMUTATION11_HPP