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