1 /*
2 Copyright (c) Marshall Clow 2014.
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 (four iterator versions)
10 /// \author Marshall Clow
11
12 #ifndef BOOST_ALGORITHM_IS_PERMUTATION14_HPP
13 #define BOOST_ALGORITHM_IS_PERMUTATION14_HPP
14
15 #include <utility> // for std::pair
16 #include <functional> // for std::equal_to
17 #include <iterator>
18
19 #include <boost/config.hpp>
20 #include <boost/algorithm/cxx11/is_permutation.hpp>
21 #include <boost/algorithm/cxx14/mismatch.hpp>
22
23 namespace boost { namespace algorithm {
24
25 /// \fn is_permutation ( ForwardIterator1 first, ForwardIterator1 last,
26 /// ForwardIterator2 first2, ForwardIterator2 last2 )
27 /// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2
28 ///
29 /// \param first1 The start of the input sequence
30 /// \param last2 One past the end of the input sequence
31 /// \param first2 The start of the second sequence
32 /// \param last1 One past the end of the second sequence
33 /// \note This function is part of the C++2014 standard library.
34 template< class ForwardIterator1, class ForwardIterator2 >
is_permutation(ForwardIterator1 first1,ForwardIterator1 last1,ForwardIterator2 first2,ForwardIterator2 last2)35 bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1,
36 ForwardIterator2 first2, ForwardIterator2 last2 )
37 {
38 // How should I deal with the idea that ForwardIterator1::value_type
39 // and ForwardIterator2::value_type could be different? Define my own comparison predicate?
40 std::pair<ForwardIterator1, ForwardIterator2> eq = boost::algorithm::mismatch
41 ( first1, last1, first2, last2 );
42 if ( eq.first == last1 && eq.second == last2)
43 return true;
44 return boost::algorithm::detail::is_permutation_tag (
45 eq.first, last1, eq.second, last2,
46 std::equal_to<typename std::iterator_traits<ForwardIterator1>::value_type> (),
47 typename std::iterator_traits<ForwardIterator1>::iterator_category (),
48 typename std::iterator_traits<ForwardIterator2>::iterator_category ());
49 }
50
51 /// \fn is_permutation ( ForwardIterator1 first, ForwardIterator1 last,
52 /// ForwardIterator2 first2, ForwardIterator2 last2,
53 /// BinaryPredicate p )
54 /// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2
55 ///
56 /// \param first1 The start of the input sequence
57 /// \param last1 One past the end of the input sequence
58 /// \param first2 The start of the second sequence
59 /// \param last2 One past the end of the second sequence
60 /// \param pred The predicate to compare elements with
61 ///
62 /// \note This function is part of the C++2014 standard library.
63 template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate >
is_permutation(ForwardIterator1 first1,ForwardIterator1 last1,ForwardIterator2 first2,ForwardIterator2 last2,BinaryPredicate pred)64 bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1,
65 ForwardIterator2 first2, ForwardIterator2 last2,
66 BinaryPredicate pred )
67 {
68 std::pair<ForwardIterator1, ForwardIterator2> eq = boost::algorithm::mismatch
69 ( first1, last1, first2, last2, pred );
70 if ( eq.first == last1 && eq.second == last2)
71 return true;
72 return boost::algorithm::detail::is_permutation_tag (
73 first1, last1, first2, last2, pred,
74 typename std::iterator_traits<ForwardIterator1>::iterator_category (),
75 typename std::iterator_traits<ForwardIterator2>::iterator_category ());
76 }
77
78 }}
79
80 #endif // BOOST_ALGORITHM_IS_PERMUTATION14_HPP
81