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
23namespace 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.
36template< class ForwardIterator1, class ForwardIterator2 >
37bool 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.
67template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate >
68bool 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