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::less, tie, mismatch and is_permutation (if available)
16#include <utility> // for std::make_pair
17#include <functional> // for std::equal_to
18#include <iterator>
19
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>
24
25namespace boost { namespace algorithm {
26
27/// \cond DOXYGEN_HIDE
28namespace detail {
29 template <typename Predicate, typename Iterator>
30 struct value_predicate {
31 value_predicate ( Predicate p, Iterator it ) : p_ ( p ), it_ ( it ) {}
32
33 template <typename T1>
34 bool operator () ( const T1 &t1 ) const { return p_ ( *it_, t1 ); }
35 private:
36 Predicate p_;
37 Iterator it_;
38 };
39
40// Preconditions:
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,
46 BinaryPredicate p ) {
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 );
51
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 ))
56 return false;
57 }
58 }
59
60 return true;
61 }
62
63 template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
64 bool is_permutation_tag ( ForwardIterator1 first1, ForwardIterator1 last1,
65 ForwardIterator2 first2, ForwardIterator2 last2,
66 BinaryPredicate p,
67 std::forward_iterator_tag, std::forward_iterator_tag ) {
68
69 // Skip the common prefix (if any)
70 while ( first1 != last1 && first2 != last2 && p ( *first1, *first2 )) {
71 ++first1;
72 ++first2;
73 }
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;
78 }
79
80 template <class RandomAccessIterator1, class RandomAccessIterator2, class BinaryPredicate>
81 bool is_permutation_tag ( RandomAccessIterator1 first1, RandomAccessIterator1 last1,
82 RandomAccessIterator2 first2, RandomAccessIterator2 last2,
83 BinaryPredicate p,
84 std::random_access_iterator_tag, std::random_access_iterator_tag ) {
85 // Cheap check
86 if ( std::distance ( first1, last1 ) != std::distance ( first2, last2 ))
87 return false;
88 // Skip the common prefix (if any)
89 while ( first1 != last1 && first2 != last2 && p ( *first1, *first2 )) {
90 ++first1;
91 ++first2;
92 }
93
94 if ( first1 != last1 && first2 != last2 )
95 return is_permutation_inner (first1, last1, first2, last2, p);
96 return first1 == last1 && first2 == last2;
97 }
98
99}
100/// \endcond
101
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
104///
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
109///
110/// \note This function is part of the C++2011 standard library.
111/// We will use the standard one if it is available,
112/// otherwise we have our own implementation.
113template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate >
114bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1,
115 ForwardIterator2 first2, BinaryPredicate p )
116{
117// Skip the common prefix (if any)
118 std::pair<ForwardIterator1, ForwardIterator2> eq = std::mismatch (first1, last1, first2, p);
119 first1 = eq.first;
120 first2 = eq.second;
121 if ( first1 != last1 ) {
122 // Create last2
123 ForwardIterator2 last2 = first2;
124 std::advance ( last2, std::distance (first1, last1));
125 return boost::algorithm::detail::is_permutation_inner ( first1, last1, first2, last2, p );
126 }
127
128 return true;
129}
130
131/// \fn is_permutation ( ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 first2 )
132/// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2
133///
134/// \param first1 The start of the input sequence
135/// \param last2 One past the end of the input sequence
136/// \param first2 The start of the second sequence
137/// \note This function is part of the C++2011 standard library.
138/// We will use the standard one if it is available,
139/// otherwise we have our own implementation.
140template< class ForwardIterator1, class ForwardIterator2 >
141bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2 )
142{
143// How should I deal with the idea that ForwardIterator1::value_type
144// and ForwardIterator2::value_type could be different? Define my own comparison predicate?
145// Skip the common prefix (if any)
146 std::pair<ForwardIterator1, ForwardIterator2> eq = std::mismatch (first1, last1, first2 );
147 first1 = eq.first;
148 first2 = eq.second;
149 if ( first1 != last1 ) {
150 // Create last2
151 ForwardIterator2 last2 = first2;
152 std::advance ( last2, std::distance (first1, last1));
153 return boost::algorithm::detail::is_permutation_inner ( first1, last1, first2, last2,
154 std::equal_to<typename std::iterator_traits<ForwardIterator1>::value_type> ());
155 }
156 return true;
157}
158
159
160/// \fn is_permutation ( const Range &r, ForwardIterator first2 )
161/// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2
162///
163/// \param r The input range
164/// \param first2 The start of the second sequence
165template <typename Range, typename ForwardIterator>
166bool is_permutation ( const Range &r, ForwardIterator first2 )
167{
168 return boost::algorithm::is_permutation (boost::begin (r), boost::end (r), first2 );
169}
170
171/// \fn is_permutation ( const Range &r, ForwardIterator first2, BinaryPredicate pred )
172/// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2
173///
174/// \param r The input range
175/// \param first2 The start of the second sequence
176/// \param pred The predicate to compare elements with
177///
178// Disable this template when the first two parameters are the same type
179// That way the non-range version will be chosen.
180template <typename Range, typename ForwardIterator, typename BinaryPredicate>
181typename boost::disable_if_c<boost::is_same<Range, ForwardIterator>::value, bool>::type
182is_permutation ( const Range &r, ForwardIterator first2, BinaryPredicate pred )
183{
184 return boost::algorithm::is_permutation (boost::begin (r), boost::end (r), first2, pred );
185}
186
187}}
188
189#endif // BOOST_ALGORITHM_IS_PERMUTATION11_HPP
190