diff options
author | Chanho Park <chanho61.park@samsung.com> | 2014-12-11 18:55:56 +0900 |
---|---|---|
committer | Chanho Park <chanho61.park@samsung.com> | 2014-12-11 18:55:56 +0900 |
commit | 08c1e93fa36a49f49325a07fe91ff92c964c2b6c (patch) | |
tree | 7a7053ceb8874b28ec4b868d4c49b500008a102e /boost/algorithm/cxx11 | |
parent | bb4dd8289b351fae6b55e303f189127a394a1edd (diff) | |
download | boost-08c1e93fa36a49f49325a07fe91ff92c964c2b6c.tar.gz boost-08c1e93fa36a49f49325a07fe91ff92c964c2b6c.tar.bz2 boost-08c1e93fa36a49f49325a07fe91ff92c964c2b6c.zip |
Imported Upstream version 1.57.0upstream/1.57.0
Diffstat (limited to 'boost/algorithm/cxx11')
-rw-r--r-- | boost/algorithm/cxx11/copy_if.hpp | 27 | ||||
-rw-r--r-- | boost/algorithm/cxx11/iota.hpp | 4 | ||||
-rw-r--r-- | boost/algorithm/cxx11/is_partitioned.hpp | 6 | ||||
-rw-r--r-- | boost/algorithm/cxx11/is_permutation.hpp | 125 |
4 files changed, 111 insertions, 51 deletions
diff --git a/boost/algorithm/cxx11/copy_if.hpp b/boost/algorithm/cxx11/copy_if.hpp index 6d0ba00bae..88b79b500b 100644 --- a/boost/algorithm/cxx11/copy_if.hpp +++ b/boost/algorithm/cxx11/copy_if.hpp @@ -39,7 +39,7 @@ OutputIterator copy_if ( InputIterator first, InputIterator last, OutputIterator { for ( ; first != last; ++first ) if (p(*first)) - *result++ = first; + *result++ = *first; return result; } #endif @@ -63,7 +63,7 @@ OutputIterator copy_if ( const Range &r, OutputIterator result, Predicate p ) /// \fn copy_while ( InputIterator first, InputIterator last, OutputIterator result, Predicate p ) /// \brief Copies all the elements at the start of the input range that /// satisfy the predicate to the output range. -/// \return The updated output iterator +/// \return The updated input and output iterators /// /// \param first The start of the input sequence /// \param last One past the end of the input sequence @@ -71,25 +71,26 @@ OutputIterator copy_if ( const Range &r, OutputIterator result, Predicate p ) /// \param p A predicate for testing the elements of the range /// template<typename InputIterator, typename OutputIterator, typename Predicate> -OutputIterator copy_while ( InputIterator first, InputIterator last, - OutputIterator result, Predicate p ) +std::pair<InputIterator, OutputIterator> +copy_while ( InputIterator first, InputIterator last, OutputIterator result, Predicate p ) { for ( ; first != last && p(*first); ++first ) - *result++ = first; - return result; + *result++ = *first; + return std::make_pair(first, result); } /// \fn copy_while ( const Range &r, OutputIterator result, Predicate p ) /// \brief Copies all the elements at the start of the input range that /// satisfy the predicate to the output range. -/// \return The updated output iterator +/// \return The updated input and output iterators /// /// \param r The input range /// \param result An output iterator to write the results into /// \param p A predicate for testing the elements of the range /// template<typename Range, typename OutputIterator, typename Predicate> -OutputIterator copy_while ( const Range &r, OutputIterator result, Predicate p ) +std::pair<typename boost::range_iterator<const Range>::type, OutputIterator> +copy_while ( const Range &r, OutputIterator result, Predicate p ) { return boost::algorithm::copy_while (boost::begin (r), boost::end(r), result, p); } @@ -106,11 +107,12 @@ OutputIterator copy_while ( const Range &r, OutputIterator result, Predicate p ) /// \param p A predicate for testing the elements of the range /// template<typename InputIterator, typename OutputIterator, typename Predicate> -OutputIterator copy_until ( InputIterator first, InputIterator last, OutputIterator result, Predicate p ) +std::pair<InputIterator, OutputIterator> +copy_until ( InputIterator first, InputIterator last, OutputIterator result, Predicate p ) { for ( ; first != last && !p(*first); ++first ) - *result++ = first; - return result; + *result++ = *first; + return std::make_pair(first, result); } /// \fn copy_until ( const Range &r, OutputIterator result, Predicate p ) @@ -123,7 +125,8 @@ OutputIterator copy_until ( InputIterator first, InputIterator last, OutputItera /// \param p A predicate for testing the elements of the range /// template<typename Range, typename OutputIterator, typename Predicate> -OutputIterator copy_until ( const Range &r, OutputIterator result, Predicate p ) +std::pair<typename boost::range_iterator<const Range>::type, OutputIterator> +copy_until ( const Range &r, OutputIterator result, Predicate p ) { return boost::algorithm::copy_until (boost::begin (r), boost::end(r), result, p); } diff --git a/boost/algorithm/cxx11/iota.hpp b/boost/algorithm/cxx11/iota.hpp index b4f0dafa6d..eb32390b0f 100644 --- a/boost/algorithm/cxx11/iota.hpp +++ b/boost/algorithm/cxx11/iota.hpp @@ -63,8 +63,8 @@ void iota ( Range &r, T value ) template <typename OutputIterator, typename T> OutputIterator iota_n ( OutputIterator out, T value, std::size_t n ) { - while ( n-- > 0 ) - *out++ = value++; + for ( ; n > 0; --n, ++value ) + *out++ = value; return out; } diff --git a/boost/algorithm/cxx11/is_partitioned.hpp b/boost/algorithm/cxx11/is_partitioned.hpp index d647183a8a..e939e05605 100644 --- a/boost/algorithm/cxx11/is_partitioned.hpp +++ b/boost/algorithm/cxx11/is_partitioned.hpp @@ -24,11 +24,11 @@ namespace boost { namespace algorithm { using std::is_partitioned; // Section 25.3.13 #else /// \fn is_partitioned ( InputIterator first, InputIterator last, UnaryPredicate p ) -/// \brief Tests to see if a sequence is partititioned according to a predicate +/// \brief Tests to see if a sequence is partitioned according to a predicate /// /// \param first The start of the input sequence /// \param last One past the end of the input sequence -/// \param p The predicicate to test the values with +/// \param p The predicate to test the values with /// \note This function is part of the C++2011 standard library. /// We will use the standard one if it is available, /// otherwise we have our own implementation. @@ -51,7 +51,7 @@ bool is_partitioned ( InputIterator first, InputIterator last, UnaryPredicate p /// \brief Generates an increasing sequence of values, and stores them in the input Range. /// /// \param r The input range -/// \param p The predicicate to test the values with +/// \param p The predicate to test the values with /// template <typename Range, typename UnaryPredicate> bool is_partitioned ( const Range &r, UnaryPredicate p ) diff --git a/boost/algorithm/cxx11/is_permutation.hpp b/boost/algorithm/cxx11/is_permutation.hpp index 33cb712378..9b3bc220fa 100644 --- a/boost/algorithm/cxx11/is_permutation.hpp +++ b/boost/algorithm/cxx11/is_permutation.hpp @@ -9,8 +9,8 @@ /// \brief Is a sequence a permutation of another sequence /// \author Marshall Clow -#ifndef BOOST_ALGORITHM_IS_PERMUTATION_HPP -#define BOOST_ALGORITHM_IS_PERMUTATION_HPP +#ifndef BOOST_ALGORITHM_IS_PERMUTATION11_HPP +#define BOOST_ALGORITHM_IS_PERMUTATION11_HPP #include <algorithm> // for std::less, tie, mismatch and is_permutation (if available) #include <utility> // for std::make_pair @@ -21,14 +21,9 @@ #include <boost/range/end.hpp> #include <boost/utility/enable_if.hpp> #include <boost/type_traits/is_same.hpp> -#include <boost/tr1/tr1/tuple> // for tie namespace boost { namespace algorithm { -#if __cplusplus >= 201103L -// Use the C++11 versions of is_permutation if it is available -using std::is_permutation; // Section 25.2.12 -#else /// \cond DOXYGEN_HIDE namespace detail { template <typename Predicate, typename Iterator> @@ -38,18 +33,82 @@ namespace detail { template <typename T1> bool operator () ( const T1 &t1 ) const { return p_ ( *it_, t1 ); } private: - Predicate &p_; + Predicate p_; Iterator it_; }; + +// Preconditions: +// 1. The sequences are the same length +// 2. Any common elements on the front have been removed (not necessary for correctness, just for performance) + template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate > + bool is_permutation_inner ( ForwardIterator1 first1, ForwardIterator1 last1, + ForwardIterator2 first2, ForwardIterator2 last2, + BinaryPredicate p ) { + // for each unique value in the sequence [first1,last1), count how many times + // it occurs, and make sure it occurs the same number of times in [first2, last2) + for ( ForwardIterator1 iter = first1; iter != last1; ++iter ) { + value_predicate<BinaryPredicate, ForwardIterator1> pred ( p, iter ); + + /* For each value we haven't seen yet... */ + if ( std::find_if ( first1, iter, pred ) == iter ) { + std::size_t dest_count = std::count_if ( first2, last2, pred ); + if ( dest_count == 0 || dest_count != (std::size_t) std::count_if ( iter, last1, pred )) + return false; + } + } + + return true; + } + + template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate> + bool is_permutation_tag ( ForwardIterator1 first1, ForwardIterator1 last1, + ForwardIterator2 first2, ForwardIterator2 last2, + BinaryPredicate p, + std::forward_iterator_tag, std::forward_iterator_tag ) { + + // Skip the common prefix (if any) + while ( first1 != last1 && first2 != last2 && p ( *first1, *first2 )) { + ++first1; + ++first2; + } + if ( first1 != last1 && first2 != last2 ) + return boost::algorithm::detail::is_permutation_inner ( first1, last1, first2, last2, + std::equal_to<typename std::iterator_traits<ForwardIterator1>::value_type> ()); + return first1 == last1 && first2 == last2; + } + + template <class RandomAccessIterator1, class RandomAccessIterator2, class BinaryPredicate> + bool is_permutation_tag ( RandomAccessIterator1 first1, RandomAccessIterator1 last1, + RandomAccessIterator2 first2, RandomAccessIterator2 last2, + BinaryPredicate p, + std::random_access_iterator_tag, std::random_access_iterator_tag ) { + // Cheap check + if ( std::distance ( first1, last1 ) != std::distance ( first2, last2 )) + return false; + // Skip the common prefix (if any) + while ( first1 != last1 && first2 != last2 && p ( *first1, *first2 )) { + ++first1; + ++first2; + } + + if ( first1 != last1 && first2 != last2 ) + return is_permutation_inner (first1, last1, first2, last2, p); + return first1 == last1 && first2 == last2; + } + } /// \endcond +#if __cplusplus >= 201103L +// Use the C++11 versions of is_permutation if it is available +using std::is_permutation; // Section 25.2.12 +#else /// \fn is_permutation ( ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 first2, BinaryPredicate p ) -/// \brief Tests to see if a the sequence [first,last) is a permutation of the sequence starting at first2 +/// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2 /// -/// \param first The start of the input sequence -/// \param last One past the end of the input sequence +/// \param first1 The start of the input sequence +/// \param last1 One past the end of the input sequence /// \param first2 The start of the second sequence /// \param p The predicate to compare elements with /// @@ -61,7 +120,6 @@ bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, BinaryPredicate p ) { // Skip the common prefix (if any) -// std::tie (first1, first2) = std::mismatch (first1, last1, first2, p); std::pair<ForwardIterator1, ForwardIterator2> eq = std::mismatch (first1, last1, first2, p); first1 = eq.first; first2 = eq.second; @@ -69,46 +127,45 @@ bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1, // Create last2 ForwardIterator2 last2 = first2; std::advance ( last2, std::distance (first1, last1)); - - // for each unique value in the sequence [first1,last1), count how many times - // it occurs, and make sure it occurs the same number of times in [first2, last2) - for ( ForwardIterator1 iter = first1; iter != last1; ++iter ) { - detail::value_predicate<BinaryPredicate, ForwardIterator1> pred ( p, iter ); - - /* For each value we haven't seen yet... */ - if ( std::find_if ( first1, iter, pred ) == iter ) { - std::size_t dest_count = std::count_if ( first2, last2, pred ); - if ( dest_count == 0 || dest_count != (std::size_t) std::count_if ( iter, last1, pred )) - return false; - } - } + return boost::algorithm::detail::is_permutation_inner ( first1, last1, first2, last2, p ); } return true; } /// \fn is_permutation ( ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 first2 ) -/// \brief Tests to see if a the sequence [first,last) is a permutation of the sequence starting at first2 +/// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2 /// -/// \param first The start of the input sequence -/// \param last One past the end of the input sequence +/// \param first1 The start of the input sequence +/// \param last2 One past the end of the input sequence /// \param first2 The start of the second sequence /// \note This function is part of the C++2011 standard library. /// We will use the standard one if it is available, /// otherwise we have our own implementation. template< class ForwardIterator1, class ForwardIterator2 > -bool is_permutation ( ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 first2 ) +bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2 ) { // How should I deal with the idea that ForwardIterator1::value_type // and ForwardIterator2::value_type could be different? Define my own comparison predicate? - return boost::algorithm::is_permutation ( first, last, first2, - std::equal_to<typename std::iterator_traits<ForwardIterator1>::value_type> ()); +// Skip the common prefix (if any) + std::pair<ForwardIterator1, ForwardIterator2> eq = std::mismatch (first1, last1, first2 ); + first1 = eq.first; + first2 = eq.second; + if ( first1 != last1 ) { + // Create last2 + ForwardIterator2 last2 = first2; + std::advance ( last2, std::distance (first1, last1)); + return boost::algorithm::detail::is_permutation_inner ( first1, last1, first2, last2, + std::equal_to<typename std::iterator_traits<ForwardIterator1>::value_type> ()); + } + return true; } #endif + /// \fn is_permutation ( const Range &r, ForwardIterator first2 ) -/// \brief Tests to see if a the sequence [first,last) is a permutation of the sequence starting at first2 +/// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2 /// /// \param r The input range /// \param first2 The start of the second sequence @@ -119,7 +176,7 @@ bool is_permutation ( const Range &r, ForwardIterator first2 ) } /// \fn is_permutation ( const Range &r, ForwardIterator first2, BinaryPredicate pred ) -/// \brief Tests to see if a the sequence [first,last) is a permutation of the sequence starting at first2 +/// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2 /// /// \param r The input range /// \param first2 The start of the second sequence @@ -136,4 +193,4 @@ is_permutation ( const Range &r, ForwardIterator first2, BinaryPredicate pred ) }} -#endif // BOOST_ALGORITHM_IS_PERMUTATION_HPP +#endif // BOOST_ALGORITHM_IS_PERMUTATION11_HPP |