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