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 <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/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 | /// We will use the standard one if it is available, |
35 | /// otherwise we have our own implementation. |
36 | template< class ForwardIterator1, class ForwardIterator2 > |
37 | bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1, |
38 | ForwardIterator2 first2, ForwardIterator2 last2 ) |
39 | { |
40 | // How should I deal with the idea that ForwardIterator1::value_type |
41 | // and ForwardIterator2::value_type could be different? Define my own comparison predicate? |
42 | std::pair<ForwardIterator1, ForwardIterator2> eq = boost::algorithm::mismatch |
43 | ( first1, last1, first2, last2 ); |
44 | if ( eq.first == last1 && eq.second == last2) |
45 | return true; |
46 | return boost::algorithm::detail::is_permutation_tag ( |
47 | eq.first, last1, eq.second, last2, |
48 | std::equal_to<typename std::iterator_traits<ForwardIterator1>::value_type> (), |
49 | typename std::iterator_traits<ForwardIterator1>::iterator_category (), |
50 | typename std::iterator_traits<ForwardIterator2>::iterator_category ()); |
51 | } |
52 | |
53 | /// \fn is_permutation ( ForwardIterator1 first, ForwardIterator1 last, |
54 | /// ForwardIterator2 first2, ForwardIterator2 last2, |
55 | /// BinaryPredicate p ) |
56 | /// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2 |
57 | /// |
58 | /// \param first1 The start of the input sequence |
59 | /// \param last1 One past the end of the input sequence |
60 | /// \param first2 The start of the second sequence |
61 | /// \param last2 One past the end of the second sequence |
62 | /// \param pred The predicate to compare elements with |
63 | /// |
64 | /// \note This function is part of the C++2014 standard library. |
65 | /// We will use the standard one if it is available, |
66 | /// otherwise we have our own implementation. |
67 | template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate > |
68 | bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1, |
69 | ForwardIterator2 first2, ForwardIterator2 last2, |
70 | BinaryPredicate pred ) |
71 | { |
72 | std::pair<ForwardIterator1, ForwardIterator2> eq = boost::algorithm::mismatch |
73 | ( first1, last1, first2, last2, pred ); |
74 | if ( eq.first == last1 && eq.second == last2) |
75 | return true; |
76 | return boost::algorithm::detail::is_permutation_tag ( |
77 | first1, last1, first2, last2, pred, |
78 | typename std::iterator_traits<ForwardIterator1>::iterator_category (), |
79 | typename std::iterator_traits<ForwardIterator2>::iterator_category ()); |
80 | } |
81 | |
82 | }} |
83 | |
84 | #endif // BOOST_ALGORITHM_IS_PERMUTATION14_HPP |
85 | |