BVB Source Codes

mars Show is_permutation.hpp Source code

Return Download mars: download is_permutation.hpp Source code - Download mars Source code - Type:.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::less, tie, mismatch and is_permutation (if available)
  16. #include <utility>      // for std::make_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 mars_boost {} namespace boost = mars_boost; namespace mars_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 mars_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. #if __cplusplus >= 201103L
  103. //  Use the C++11 versions of is_permutation if it is available
  104. using std::is_permutation;              // Section 25.2.12
  105. #else
  106.  
  107. /// \fn is_permutation ( ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 first2, BinaryPredicate p )
  108. /// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2
  109. ///
  110. /// \param first1   The start of the input sequence
  111. /// \param last1    One past the end of the input sequence
  112. /// \param first2   The start of the second sequence
  113. /// \param p        The predicate to compare elements with
  114. ///
  115. /// \note           This function is part of the C++2011 standard library.
  116. ///  We will use the standard one if it is available,
  117. ///     otherwise we have our own implementation.
  118. template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate >
  119. bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1,
  120.                       ForwardIterator2 first2, BinaryPredicate p )
  121. {
  122. //  Skip the common prefix (if any)
  123.     std::pair<ForwardIterator1, ForwardIterator2> eq = std::mismatch (first1, last1, first2, p);
  124.     first1 = eq.first;
  125.     first2 = eq.second;
  126.     if ( first1 != last1 ) {
  127.     //  Create last2
  128.         ForwardIterator2 last2 = first2;
  129.         std::advance ( last2, std::distance (first1, last1));
  130.         return mars_boost::algorithm::detail::is_permutation_inner ( first1, last1, first2, last2, p );
  131.         }
  132.  
  133.     return true;
  134. }
  135.  
  136. /// \fn is_permutation ( ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 first2 )
  137. /// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2
  138. ///
  139. /// \param first1   The start of the input sequence
  140. /// \param last2    One past the end of the input sequence
  141. /// \param first2   The start of the second sequence
  142. /// \note           This function is part of the C++2011 standard library.
  143. ///  We will use the standard one if it is available,
  144. ///     otherwise we have our own implementation.
  145. template< class ForwardIterator1, class ForwardIterator2 >
  146. bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2 )
  147. {
  148. //  How should I deal with the idea that ForwardIterator1::value_type
  149. //  and ForwardIterator2::value_type could be different? Define my own comparison predicate?
  150. //  Skip the common prefix (if any)
  151.     std::pair<ForwardIterator1, ForwardIterator2> eq = std::mismatch (first1, last1, first2 );
  152.     first1 = eq.first;
  153.     first2 = eq.second;
  154.     if ( first1 != last1 ) {
  155.     //  Create last2
  156.         ForwardIterator2 last2 = first2;
  157.         std::advance ( last2, std::distance (first1, last1));
  158.         return mars_boost::algorithm::detail::is_permutation_inner ( first1, last1, first2, last2,
  159.             std::equal_to<typename std::iterator_traits<ForwardIterator1>::value_type> ());
  160.         }
  161.     return true;
  162. }
  163.  
  164. #endif
  165.  
  166.  
  167. /// \fn is_permutation ( const Range &r, ForwardIterator first2 )
  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. template <typename Range, typename ForwardIterator>
  173. bool is_permutation ( const Range &r, ForwardIterator first2 )
  174. {
  175.     return mars_boost::algorithm::is_permutation (mars_boost::begin (r), mars_boost::end (r), first2 );
  176. }
  177.  
  178. /// \fn is_permutation ( const Range &r, ForwardIterator first2, BinaryPredicate pred )
  179. /// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2
  180. ///
  181. /// \param r        The input range
  182. /// \param first2   The start of the second sequence
  183. /// \param pred     The predicate to compare elements with
  184. ///
  185. //  Disable this template when the first two parameters are the same type
  186. //  That way the non-range version will be chosen.
  187. template <typename Range, typename ForwardIterator, typename BinaryPredicate>
  188. typename mars_boost::disable_if_c<boost::is_same<Range, ForwardIterator>::value, bool>::type
  189. is_permutation ( const Range &r, ForwardIterator first2, BinaryPredicate pred )
  190. {
  191.     return mars_boost::algorithm::is_permutation (mars_boost::begin (r), mars_boost::end (r), first2, pred );
  192. }
  193.  
  194. }}
  195.  
  196. #endif  // BOOST_ALGORITHM_IS_PERMUTATION11_HPP
  197.  
downloadis_permutation.hpp Source code - Download mars Source code
Related Source Codes/Software:
Hero - Elegant transition library for iOS & tvOS 2017-06-09
deep-photo-styletransfer - Code and data for paper "Deep Photo Style Transfer... 2017-06-09
mastodon - A GNU Social-compatible microblogging server ... 2017-06-09
plyr - A simple HTML5, YouTube and Vimeo player ... 2017-06-08
prepack - Prepack is a partial evaluator for JavaScript. Pre... 2017-06-08
Public-APIs - 2017-06-09
lottie-ios - An iOS library to natively render After Effects ve... 2017-06-09
Awesome-Hacking - A collection of various awesome lists for hackers,... 2017-06-09
algorithms - Minimal examples of data structures and algorithms... 2017-06-10
lectures - Oxford Deep NLP 2017 course 2017-06-10
CRYENGINE - CRYENGINE is a powerful real-time game development... 2017-06-11
postal - 2017-06-11
reactide - Reactide is the first dedicated IDE for React web ... 2017-06-11
rkt - rkt is a pod-native container engine for Linux. It... 2017-06-11
uWebSockets - Tiny WebSockets https://for... 2017-06-11
realworld - TodoMVC for the RealWorld - Exemplary fullstack Me... 2017-06-11
goreplay - GoReplay is an open-source tool for capturing and ... 2017-06-10
pyenv - Simple Python version management 2017-06-10
redux-saga - An alternative side effect model for Redux apps ... 2017-06-10
angular-starter - 2017-06-10

 Back to top