algorithm/cxx14/is_permutation.hpp

0001 /*
0002    Copyright (c) Marshall Clow 2014.
0003
0004    Distributed under the Boost Software License, Version 1.0. (See accompanying
0005    file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0006 */
0007
0008 /// \file  is_permutation.hpp
0009 /// \brief Is a sequence a permutation of another sequence (four iterator versions)
0010 /// \author Marshall Clow
0011
0012 #ifndef BOOST_ALGORITHM_IS_PERMUTATION14_HPP
0013 #define BOOST_ALGORITHM_IS_PERMUTATION14_HPP
0014
0015 #include <utility>      // for std::pair
0016 #include <functional>   // for std::equal_to
0017 #include <iterator>
0018
0019 #include <boost/config.hpp>
0020 #include <boost/algorithm/cxx11/is_permutation.hpp>
0021 #include <boost/algorithm/cxx14/mismatch.hpp>
0022
0023 namespace boost { namespace algorithm {
0024
0025 /// \fn is_permutation ( ForwardIterator1 first, ForwardIterator1 last,
0026 ///                      ForwardIterator2 first2, ForwardIterator2 last2 )
0027 /// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2
0028 ///
0029 /// \param first1   The start of the input sequence
0030 /// \param last2    One past the end of the input sequence
0031 /// \param first2   The start of the second sequence
0032 /// \param last1    One past the end of the second sequence
0033 /// \note           This function is part of the C++2014 standard library.
0034 template< class ForwardIterator1, class ForwardIterator2 >
0035 bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1,
0036                       ForwardIterator2 first2, ForwardIterator2 last2 )
0037 {
0038 //  How should I deal with the idea that ForwardIterator1::value_type
0039 //  and ForwardIterator2::value_type could be different? Define my own comparison predicate?
0040     std::pair<ForwardIterator1, ForwardIterator2> eq = boost::algorithm::mismatch
0041         ( first1, last1, first2, last2 );
0042     if ( eq.first == last1 && eq.second == last2)
0043         return true;
0044     return boost::algorithm::detail::is_permutation_tag (
0045         eq.first, last1, eq.second, last2,
0046         std::equal_to<typename std::iterator_traits<ForwardIterator1>::value_type> (),
0047         typename std::iterator_traits<ForwardIterator1>::iterator_category (),
0048         typename std::iterator_traits<ForwardIterator2>::iterator_category ());
0049 }
0050
0051 /// \fn is_permutation ( ForwardIterator1 first, ForwardIterator1 last,
0052 ///                      ForwardIterator2 first2, ForwardIterator2 last2,
0053 ///                      BinaryPredicate p )
0054 /// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2
0055 ///
0056 /// \param first1   The start of the input sequence
0057 /// \param last1    One past the end of the input sequence
0058 /// \param first2   The start of the second sequence
0059 /// \param last2    One past the end of the second sequence
0060 /// \param pred     The predicate to compare elements with
0061 ///
0062 /// \note           This function is part of the C++2014 standard library.
0063 template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate >
0064 bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1,
0065                       ForwardIterator2 first2, ForwardIterator2 last2,
0066                       BinaryPredicate pred )
0067 {
0068     std::pair<ForwardIterator1, ForwardIterator2> eq = boost::algorithm::mismatch
0069         ( first1, last1, first2, last2, pred );
0070     if ( eq.first == last1 && eq.second == last2)
0071         return true;
0072     return boost::algorithm::detail::is_permutation_tag (
0073         first1, last1, first2, last2, pred,
0074         typename std::iterator_traits<ForwardIterator1>::iterator_category (),
0075         typename std::iterator_traits<ForwardIterator2>::iterator_category ());
0076 }
0077
0078 }}
0079
0080 #endif  // BOOST_ALGORITHM_IS_PERMUTATION14_HPP