1 /* Copyright (c) Marshall Clow 2014. Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) */ /// \file is_permutation.hpp /// \brief Is a sequence a permutation of another sequence (four iterator versions) /// \author Marshall Clow #ifndef BOOST_ALGORITHM_IS_PERMUTATION14_HPP #define BOOST_ALGORITHM_IS_PERMUTATION14_HPP #include // for std::less, tie, mismatch and is_permutation (if available) #include // for std::make_pair #include // for std::equal_to #include #include #include namespace boost { namespace algorithm { /// \fn is_permutation ( ForwardIterator1 first, ForwardIterator1 last, /// ForwardIterator2 first2, ForwardIterator2 last2 ) /// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2 /// /// \param first1 The start of the input sequence /// \param last2 One past the end of the input sequence /// \param first2 The start of the second sequence /// \param last1 One past the end of the second sequence /// \note This function is part of the C++2014 standard library. /// We will use the standard one if it is available, /// otherwise we have our own implementation. template< class ForwardIterator1, class ForwardIterator2 > bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2 ) { // How should I deal with the idea that ForwardIterator1::value_type // and ForwardIterator2::value_type could be different? Define my own comparison predicate? std::pair eq = boost::algorithm::mismatch ( first1, last1, first2, last2 ); if ( eq.first == last1 && eq.second == last2) return true; return boost::algorithm::detail::is_permutation_tag ( eq.first, last1, eq.second, last2, std::equal_to::value_type> (), typename std::iterator_traits::iterator_category (), typename std::iterator_traits::iterator_category ()); } /// \fn is_permutation ( ForwardIterator1 first, ForwardIterator1 last, /// ForwardIterator2 first2, ForwardIterator2 last2, /// BinaryPredicate p ) /// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2 /// /// \param first1 The start of the input sequence /// \param last1 One past the end of the input sequence /// \param first2 The start of the second sequence /// \param last2 One past the end of the second sequence /// \param pred The predicate to compare elements with /// /// \note This function is part of the C++2014 standard library. /// We will use the standard one if it is available, /// otherwise we have our own implementation. template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate > bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate pred ) { std::pair eq = boost::algorithm::mismatch ( first1, last1, first2, last2, pred ); if ( eq.first == last1 && eq.second == last2) return true; return boost::algorithm::detail::is_permutation_tag ( first1, last1, first2, last2, pred, typename std::iterator_traits::iterator_category (), typename std::iterator_traits::iterator_category ()); } }} #endif // BOOST_ALGORITHM_IS_PERMUTATION14_HPP