boost/algorithm/cxx14/is_permutation.hpp

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