1/*
2 Copyright (c) Marshall Clow 2011-2012.
3
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)
6*/
7
8/// \file is_permutation.hpp
9/// \brief Is a sequence a permutation of another sequence
10/// \author Marshall Clow
11
12#ifndef BOOST_ALGORITHM_IS_PERMUTATION11_HPP
13#define BOOST_ALGORITHM_IS_PERMUTATION11_HPP
14
15#include <algorithm> // for std::find_if, count_if, mismatch
16#include <utility> // for std::pair
17#include <functional> // for std::equal_to
18#include <iterator>
19
20#include <boost/config.hpp>
21#include <boost/range/begin.hpp>
22#include <boost/range/end.hpp>
23#include <boost/core/enable_if.hpp>
24#include <boost/type_traits/is_same.hpp>
25
26namespace boost { namespace algorithm {
27
28/// \cond DOXYGEN_HIDE
29namespace detail {
30 template <typename Predicate, typename Iterator>
31 struct value_predicate {
32 value_predicate ( Predicate p, Iterator it ) : p_ ( p ), it_ ( it ) {}
33
34 template <typename T1>
35 bool operator () ( const T1 &t1 ) const { return p_ ( *it_, t1 ); }
36 private:
37 Predicate p_;
38 Iterator it_;
39 };
40
41// Preconditions:
42// 1. The sequences are the same length
43// 2. Any common elements on the front have been removed (not necessary for correctness, just for performance)
44 template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate >
45 bool is_permutation_inner ( ForwardIterator1 first1, ForwardIterator1 last1,
46 ForwardIterator2 first2, ForwardIterator2 last2,
47 BinaryPredicate p ) {
48 // for each unique value in the sequence [first1,last1), count how many times
49 // it occurs, and make sure it occurs the same number of times in [first2, last2)
50 for ( ForwardIterator1 iter = first1; iter != last1; ++iter ) {
51 value_predicate<BinaryPredicate, ForwardIterator1> pred ( p, iter );
52
53 /* For each value we haven't seen yet... */
54 if ( std::find_if ( first1, iter, pred ) == iter ) {
55 std::size_t dest_count = std::count_if ( first2, last2, pred );
56 if ( dest_count == 0 || dest_count != (std::size_t) std::count_if ( iter, last1, pred ))
57 return false;
58 }
59 }
60
61 return true;
62 }
63
64 template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
65 bool is_permutation_tag ( ForwardIterator1 first1, ForwardIterator1 last1,
66 ForwardIterator2 first2, ForwardIterator2 last2,
67 BinaryPredicate p,
68 std::forward_iterator_tag, std::forward_iterator_tag ) {
69
70 // Skip the common prefix (if any)
71 while ( first1 != last1 && first2 != last2 && p ( *first1, *first2 )) {
72 ++first1;
73 ++first2;
74 }
75 if ( first1 != last1 && first2 != last2 )
76 return boost::algorithm::detail::is_permutation_inner ( first1, last1, first2, last2,
77 std::equal_to<typename std::iterator_traits<ForwardIterator1>::value_type> ());
78 return first1 == last1 && first2 == last2;
79 }
80
81 template <class RandomAccessIterator1, class RandomAccessIterator2, class BinaryPredicate>
82 bool is_permutation_tag ( RandomAccessIterator1 first1, RandomAccessIterator1 last1,
83 RandomAccessIterator2 first2, RandomAccessIterator2 last2,
84 BinaryPredicate p,
85 std::random_access_iterator_tag, std::random_access_iterator_tag ) {
86 // Cheap check
87 if ( std::distance ( first1, last1 ) != std::distance ( first2, last2 ))
88 return false;
89 // Skip the common prefix (if any)
90 while ( first1 != last1 && first2 != last2 && p ( *first1, *first2 )) {
91 ++first1;
92 ++first2;
93 }
94
95 if ( first1 != last1 && first2 != last2 )
96 return is_permutation_inner (first1, last1, first2, last2, p);
97 return first1 == last1 && first2 == last2;
98 }
99
100}
101/// \endcond
102
103/// \fn is_permutation ( ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 first2, BinaryPredicate p )
104/// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2
105///
106/// \param first1 The start of the input sequence
107/// \param last1 One past the end of the input sequence
108/// \param first2 The start of the second sequence
109/// \param p The predicate to compare elements with
110///
111/// \note This function is part of the C++2011 standard library.
112template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate >
113bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1,
114 ForwardIterator2 first2, BinaryPredicate p )
115{
116// Skip the common prefix (if any)
117 std::pair<ForwardIterator1, ForwardIterator2> eq = std::mismatch (first1, last1, first2, p);
118 first1 = eq.first;
119 first2 = eq.second;
120 if ( first1 != last1 ) {
121 // Create last2
122 ForwardIterator2 last2 = first2;
123 std::advance ( last2, std::distance (first1, last1));
124 return boost::algorithm::detail::is_permutation_inner ( first1, last1, first2, last2, p );
125 }
126
127 return true;
128}
129
130/// \fn is_permutation ( ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 first2 )
131/// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2
132///
133/// \param first1 The start of the input sequence
134/// \param last2 One past the end of the input sequence
135/// \param first2 The start of the second sequence
136/// \note This function is part of the C++2011 standard library.
137template< class ForwardIterator1, class ForwardIterator2 >
138bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2 )
139{
140// How should I deal with the idea that ForwardIterator1::value_type
141// and ForwardIterator2::value_type could be different? Define my own comparison predicate?
142// Skip the common prefix (if any)
143 std::pair<ForwardIterator1, ForwardIterator2> eq = std::mismatch (first1, last1, first2 );
144 first1 = eq.first;
145 first2 = eq.second;
146 if ( first1 != last1 ) {
147 // Create last2
148 ForwardIterator2 last2 = first2;
149 std::advance ( last2, std::distance (first1, last1));
150 return boost::algorithm::detail::is_permutation_inner ( first1, last1, first2, last2,
151 std::equal_to<typename std::iterator_traits<ForwardIterator1>::value_type> ());
152 }
153 return true;
154}
155
156
157/// \fn is_permutation ( const Range &r, ForwardIterator first2 )
158/// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2
159///
160/// \param r The input range
161/// \param first2 The start of the second sequence
162template <typename Range, typename ForwardIterator>
163bool is_permutation ( const Range &r, ForwardIterator first2 )
164{
165 return boost::algorithm::is_permutation (boost::begin (r), boost::end (r), first2 );
166}
167
168/// \fn is_permutation ( const Range &r, ForwardIterator first2, BinaryPredicate pred )
169/// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2
170///
171/// \param r The input range
172/// \param first2 The start of the second sequence
173/// \param pred The predicate to compare elements with
174///
175// Disable this template when the first two parameters are the same type
176// That way the non-range version will be chosen.
177template <typename Range, typename ForwardIterator, typename BinaryPredicate>
178typename boost::disable_if_c<boost::is_same<Range, ForwardIterator>::value, bool>::type
179is_permutation ( const Range &r, ForwardIterator first2, BinaryPredicate pred )
180{
181 return boost::algorithm::is_permutation (boost::begin (r), boost::end (r), first2, pred );
182}
183
184}}
185
186#endif // BOOST_ALGORITHM_IS_PERMUTATION11_HPP
187

source code of boost/libs/algorithm/include/boost/algorithm/cxx11/is_permutation.hpp