ceph/src/boost/libs/algorithm/include/boost/algorithm/cxx11/is_permutation.hpp

   1 /*
   2    Copyright (c) Marshall Clow 2011-2012.
   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
  10 /// \author Marshall Clow
  11
  12 #ifndef BOOST_ALGORITHM_IS_PERMUTATION11_HPP
  13 #define BOOST_ALGORITHM_IS_PERMUTATION11_HPP
  14
  15 #include <algorithm>    // for std::find_if, count_if, mismatch
  16 #include <utility>      // for std::pair
  17 #include <functional>   // for std::equal_to
  18 #include <iterator>
  19
  20 #include <boost/range/begin.hpp>
  21 #include <boost/range/end.hpp>
  22 #include <boost/utility/enable_if.hpp>
  23 #include <boost/type_traits/is_same.hpp>
  24
  25 namespace boost { namespace algorithm {
  26
  27 /// \cond DOXYGEN_HIDE
  28 namespace detail {
  29     template <typename Predicate, typename Iterator>
  30     struct value_predicate {
  31         value_predicate ( Predicate p, Iterator it ) : p_ ( p ), it_ ( it ) {}
  32
  33         template <typename T1>
  34         bool operator () ( const T1 &t1 ) const { return p_ ( *it_, t1 ); }
  35     private:
  36         Predicate p_;
  37         Iterator it_;
  38         };
  39
  40 //  Preconditions:
  41 //  1. The sequences are the same length
  42 //  2. Any common elements on the front have been removed (not necessary for correctness, just for performance)
  43     template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate >
  44     bool is_permutation_inner ( ForwardIterator1 first1, ForwardIterator1 last1,
  45                                 ForwardIterator2 first2, ForwardIterator2 last2,
  46                                 BinaryPredicate p ) {
  47         //  for each unique value in the sequence [first1,last1), count how many times
  48         //  it occurs, and make sure it occurs the same number of times in [first2, last2)
  49             for ( ForwardIterator1 iter = first1; iter != last1; ++iter ) {
  50                 value_predicate<BinaryPredicate, ForwardIterator1> pred ( p, iter );
  51
  52             /*  For each value we haven't seen yet... */
  53                 if ( std::find_if ( first1, iter, pred ) == iter ) {
  54                     std::size_t dest_count = std::count_if ( first2, last2, pred );
  55                     if ( dest_count == 0 || dest_count != (std::size_t) std::count_if ( iter, last1, pred ))
  56                         return false;
  57                     }
  58                 }
  59
  60         return true;
  61         }
  62
  63     template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
  64     bool is_permutation_tag ( ForwardIterator1 first1, ForwardIterator1 last1,
  65                           ForwardIterator2 first2, ForwardIterator2 last2,
  66                           BinaryPredicate p,
  67                           std::forward_iterator_tag, std::forward_iterator_tag ) {
  68
  69     //  Skip the common prefix (if any)
  70         while ( first1 != last1 && first2 != last2 && p ( *first1, *first2 )) {
  71             ++first1;
  72             ++first2;
  73             }
  74         if ( first1 != last1 && first2 != last2 )
  75             return boost::algorithm::detail::is_permutation_inner ( first1, last1, first2, last2,
  76                 std::equal_to<typename std::iterator_traits<ForwardIterator1>::value_type> ());
  77         return first1 == last1 && first2 == last2;
  78         }
  79
  80     template <class RandomAccessIterator1, class RandomAccessIterator2, class BinaryPredicate>
  81     bool is_permutation_tag ( RandomAccessIterator1 first1, RandomAccessIterator1 last1,
  82                           RandomAccessIterator2 first2, RandomAccessIterator2 last2,
  83                           BinaryPredicate p,
  84                           std::random_access_iterator_tag, std::random_access_iterator_tag ) {
  85     //  Cheap check
  86         if ( std::distance ( first1, last1 ) != std::distance ( first2, last2 ))
  87             return false;
  88     //  Skip the common prefix (if any)
  89         while ( first1 != last1 && first2 != last2 && p ( *first1, *first2 )) {
  90             ++first1;
  91             ++first2;
  92             }
  93
  94         if ( first1 != last1 && first2 != last2 )
  95             return is_permutation_inner (first1, last1, first2, last2, p);
  96         return first1 == last1 && first2 == last2;
  97         }
  98
  99 }
 100 /// \endcond
 101
 102 /// \fn is_permutation ( ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 first2, BinaryPredicate p )
 103 /// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2
 104 ///
 105 /// \param first1   The start of the input sequence
 106 /// \param last1    One past the end of the input sequence
 107 /// \param first2   The start of the second sequence
 108 /// \param p        The predicate to compare elements with
 109 ///
 110 /// \note           This function is part of the C++2011 standard library.
 111 template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate >
 112 bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1,
 113                       ForwardIterator2 first2, BinaryPredicate p )
 114 {
 115 //  Skip the common prefix (if any)
 116     std::pair<ForwardIterator1, ForwardIterator2> eq = std::mismatch (first1, last1, first2, p);
 117     first1 = eq.first;
 118     first2 = eq.second;
 119     if ( first1 != last1 ) {
 120     //  Create last2
 121         ForwardIterator2 last2 = first2;
 122         std::advance ( last2, std::distance (first1, last1));
 123         return boost::algorithm::detail::is_permutation_inner ( first1, last1, first2, last2, p );
 124         }
 125
 126     return true;
 127 }
 128
 129 /// \fn is_permutation ( ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 first2 )
 130 /// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2
 131 ///
 132 /// \param first1   The start of the input sequence
 133 /// \param last2    One past the end of the input sequence
 134 /// \param first2   The start of the second sequence
 135 /// \note           This function is part of the C++2011 standard library.
 136 template< class ForwardIterator1, class ForwardIterator2 >
 137 bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2 )
 138 {
 139 //  How should I deal with the idea that ForwardIterator1::value_type
 140 //  and ForwardIterator2::value_type could be different? Define my own comparison predicate?
 141 //  Skip the common prefix (if any)
 142     std::pair<ForwardIterator1, ForwardIterator2> eq = std::mismatch (first1, last1, first2 );
 143     first1 = eq.first;
 144     first2 = eq.second;
 145     if ( first1 != last1 ) {
 146     //  Create last2
 147         ForwardIterator2 last2 = first2;
 148         std::advance ( last2, std::distance (first1, last1));
 149         return boost::algorithm::detail::is_permutation_inner ( first1, last1, first2, last2,
 150             std::equal_to<typename std::iterator_traits<ForwardIterator1>::value_type> ());
 151         }
 152     return true;
 153 }
 154
 155
 156 /// \fn is_permutation ( const Range &r, ForwardIterator first2 )
 157 /// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2
 158 ///
 159 /// \param r        The input range
 160 /// \param first2   The start of the second sequence
 161 template <typename Range, typename ForwardIterator>
 162 bool is_permutation ( const Range &r, ForwardIterator first2 )
 163 {
 164     return boost::algorithm::is_permutation (boost::begin (r), boost::end (r), first2 );
 165 }
 166
 167 /// \fn is_permutation ( const Range &r, ForwardIterator first2, BinaryPredicate pred )
 168 /// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2
 169 ///
 170 /// \param r        The input range
 171 /// \param first2   The start of the second sequence
 172 /// \param pred     The predicate to compare elements with
 173 ///
 174 //  Disable this template when the first two parameters are the same type
 175 //  That way the non-range version will be chosen.
 176 template <typename Range, typename ForwardIterator, typename BinaryPredicate>
 177 typename boost::disable_if_c<boost::is_same<Range, ForwardIterator>::value, bool>::type
 178 is_permutation ( const Range &r, ForwardIterator first2, BinaryPredicate pred )
 179 {
 180     return boost::algorithm::is_permutation (boost::begin (r), boost::end (r), first2, pred );
 181 }
 182
 183 }}
 184
 185 #endif  // BOOST_ALGORITHM_IS_PERMUTATION11_HPP