summaryrefslogtreecommitdiff
path: root/boost/algorithm
diff options
context:
space:
mode:
authorDongHun Kwak <dh0128.kwak@samsung.com>2016-03-21 06:45:20 (GMT)
committerDongHun Kwak <dh0128.kwak@samsung.com>2016-03-21 06:46:37 (GMT)
commit733b5d5ae2c5d625211e2985ac25728ac3f54883 (patch)
treea5b214744b256f07e1dc2bd7273035a7808c659f /boost/algorithm
parent08c1e93fa36a49f49325a07fe91ff92c964c2b6c (diff)
downloadboost-733b5d5ae2c5d625211e2985ac25728ac3f54883.zip
boost-733b5d5ae2c5d625211e2985ac25728ac3f54883.tar.gz
boost-733b5d5ae2c5d625211e2985ac25728ac3f54883.tar.bz2
Imported Upstream version 1.58.0upstream/1.58.0refs/changes/33/62933/1
Change-Id: If0072143aa26874812e0db6872e1efb10a3e5e94 Signed-off-by: DongHun Kwak <dh0128.kwak@samsung.com>
Diffstat (limited to 'boost/algorithm')
-rw-r--r--boost/algorithm/algorithm.hpp86
-rw-r--r--boost/algorithm/cxx11/all_of.hpp5
-rw-r--r--boost/algorithm/cxx11/any_of.hpp5
-rw-r--r--boost/algorithm/cxx11/copy_if.hpp5
-rw-r--r--boost/algorithm/cxx11/copy_n.hpp5
-rw-r--r--boost/algorithm/cxx11/find_if_not.hpp5
-rw-r--r--boost/algorithm/cxx11/iota.hpp5
-rw-r--r--boost/algorithm/cxx11/is_partitioned.hpp5
-rw-r--r--boost/algorithm/cxx11/is_permutation.hpp7
-rw-r--r--boost/algorithm/cxx11/is_sorted.hpp6
-rw-r--r--boost/algorithm/cxx11/none_of.hpp5
-rw-r--r--boost/algorithm/cxx11/partition_copy.hpp5
-rw-r--r--boost/algorithm/cxx11/partition_point.hpp7
-rw-r--r--boost/algorithm/cxx14/is_permutation.hpp18
-rw-r--r--boost/algorithm/hex.hpp1
-rw-r--r--boost/algorithm/searching/detail/bm_traits.hpp4
-rw-r--r--boost/algorithm/string/find_iterator.hpp7
17 files changed, 103 insertions, 78 deletions
diff --git a/boost/algorithm/algorithm.hpp b/boost/algorithm/algorithm.hpp
new file mode 100644
index 0000000..0cf6c45
--- /dev/null
+++ b/boost/algorithm/algorithm.hpp
@@ -0,0 +1,86 @@
+/*
+ Copyright (c) Marshall Clow 2014.
+
+ Distributed under the Boost Software License, Version 1.0. (See accompanying
+ file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+
+ Revision history:
+ 2 Dec 2014 mtc First version; power
+
+*/
+
+/// \file algorithm.hpp
+/// \brief Misc Algorithms
+/// \author Marshall Clow
+///
+
+#ifndef BOOST_ALGORITHM_HPP
+#define BOOST_ALGORITHM_HPP
+
+#include <boost/utility/enable_if.hpp> // for boost::disable_if
+#include <boost/type_traits/is_integral.hpp>
+
+namespace boost { namespace algorithm {
+
+template <typename T>
+T identity_operation ( std::multiplies<T> ) { return T(1); }
+
+template <typename T>
+T identity_operation ( std::plus<T> ) { return T(0); }
+
+
+/// \fn power ( T x, Integer n )
+/// \return the value "x" raised to the power "n"
+///
+/// \param x The value to be exponentiated
+/// \param n The exponent (must be >= 0)
+///
+// \remark Taken from Knuth, The Art of Computer Programming, Volume 2:
+// Seminumerical Algorithms, Section 4.6.3
+template <typename T, typename Integer>
+typename boost::enable_if<boost::is_integral<Integer>, T>::type
+power (T x, Integer n) {
+ T y = 1; // Should be "T y{1};"
+ if (n == 0) return y;
+ while (true) {
+ if (n % 2 == 1) {
+ y = x * y;
+ if (n == 1)
+ return y;
+ }
+ n = n / 2;
+ x = x * x;
+ }
+ return y;
+ }
+
+/// \fn power ( T x, Integer n, Operation op )
+/// \return the value "x" raised to the power "n"
+/// using the operaton "op".
+///
+/// \param x The value to be exponentiated
+/// \param n The exponent (must be >= 0)
+/// \param op The operation used
+///
+// \remark Taken from Knuth, The Art of Computer Programming, Volume 2:
+// Seminumerical Algorithms, Section 4.6.3
+template <typename T, typename Integer, typename Operation>
+typename boost::enable_if<boost::is_integral<Integer>, T>::type
+power (T x, Integer n, Operation op) {
+ T y = identity_operation(op);
+ if (n == 0) return y;
+ while (true) {
+ if (n % 2 == 1) {
+ y = op(x, y);
+ if (n == 1)
+ return y;
+ }
+ n = n / 2;
+ x = op(x, x);
+ }
+ return y;
+ }
+
+}}
+
+#endif // BOOST_ALGORITHM_HPP
diff --git a/boost/algorithm/cxx11/all_of.hpp b/boost/algorithm/cxx11/all_of.hpp
index b76cb3f..39cab39 100644
--- a/boost/algorithm/cxx11/all_of.hpp
+++ b/boost/algorithm/cxx11/all_of.hpp
@@ -18,10 +18,6 @@
namespace boost { namespace algorithm {
-#if __cplusplus >= 201103L
-// Use the C++11 versions of all_of if it is available
-using std::all_of; // Section 25.2.1
-#else
/// \fn all_of ( InputIterator first, InputIterator last, Predicate p )
/// \return true if all elements in [first, last) satisfy the predicate 'p'
/// \note returns true on an empty range
@@ -41,7 +37,6 @@ bool all_of ( InputIterator first, InputIterator last, Predicate p )
return false;
return true;
}
-#endif
/// \fn all_of ( const Range &r, Predicate p )
/// \return true if all elements in the range satisfy the predicate 'p'
diff --git a/boost/algorithm/cxx11/any_of.hpp b/boost/algorithm/cxx11/any_of.hpp
index c3ab3ce..cf69348 100644
--- a/boost/algorithm/cxx11/any_of.hpp
+++ b/boost/algorithm/cxx11/any_of.hpp
@@ -20,10 +20,6 @@
namespace boost { namespace algorithm {
-// Use the C++11 versions of any_of if it is available
-#if __cplusplus >= 201103L
-using std::any_of; // Section 25.2.2
-#else
/// \fn any_of ( InputIterator first, InputIterator last, Predicate p )
/// \return true if any of the elements in [first, last) satisfy the predicate
/// \note returns false on an empty range
@@ -40,7 +36,6 @@ bool any_of ( InputIterator first, InputIterator last, Predicate p )
return true;
return false;
}
-#endif
/// \fn any_of ( const Range &r, Predicate p )
/// \return true if any elements in the range satisfy the predicate 'p'
diff --git a/boost/algorithm/cxx11/copy_if.hpp b/boost/algorithm/cxx11/copy_if.hpp
index 88b79b5..d869caf 100644
--- a/boost/algorithm/cxx11/copy_if.hpp
+++ b/boost/algorithm/cxx11/copy_if.hpp
@@ -18,10 +18,6 @@
namespace boost { namespace algorithm {
-#if __cplusplus >= 201103L
-// Use the C++11 versions of copy_if if it is available
-using std::copy_if; // Section 25.3.1
-#else
/// \fn copy_if ( InputIterator first, InputIterator last, OutputIterator result, Predicate p )
/// \brief Copies all the elements from the input range that satisfy the
/// predicate to the output range.
@@ -42,7 +38,6 @@ OutputIterator copy_if ( InputIterator first, InputIterator last, OutputIterator
*result++ = *first;
return result;
}
-#endif
/// \fn copy_if ( const Range &r, OutputIterator result, Predicate p )
/// \brief Copies all the elements from the input range that satisfy the
diff --git a/boost/algorithm/cxx11/copy_n.hpp b/boost/algorithm/cxx11/copy_n.hpp
index 0ea53bd..ebfe889 100644
--- a/boost/algorithm/cxx11/copy_n.hpp
+++ b/boost/algorithm/cxx11/copy_n.hpp
@@ -16,10 +16,6 @@
namespace boost { namespace algorithm {
-#if __cplusplus >= 201103L
-// Use the C++11 versions of copy_n if it is available
-using std::copy_n; // Section 25.3.1
-#else
/// \fn copy_n ( InputIterator first, Size n, OutputIterator result )
/// \brief Copies exactly n (n > 0) elements from the range starting at first to
/// the range starting at result.
@@ -38,7 +34,6 @@ OutputIterator copy_n ( InputIterator first, Size n, OutputIterator result )
*result = *first;
return result;
}
-#endif
}} // namespace boost and algorithm
#endif // BOOST_ALGORITHM_COPY_IF_HPP
diff --git a/boost/algorithm/cxx11/find_if_not.hpp b/boost/algorithm/cxx11/find_if_not.hpp
index 4beed00..414697c 100644
--- a/boost/algorithm/cxx11/find_if_not.hpp
+++ b/boost/algorithm/cxx11/find_if_not.hpp
@@ -19,10 +19,6 @@
namespace boost { namespace algorithm {
-#if __cplusplus >= 201103L
-// Use the C++11 versions of find_if_not if it is available
-using std::find_if_not; // Section 25.2.5
-#else
/// \fn find_if_not(InputIterator first, InputIterator last, Predicate p)
/// \brief Finds the first element in the sequence that does not satisfy the predicate.
/// \return The iterator pointing to the desired element.
@@ -41,7 +37,6 @@ InputIterator find_if_not ( InputIterator first, InputIterator last, Predicate p
break;
return first;
}
-#endif
/// \fn find_if_not ( const Range &r, Predicate p )
/// \brief Finds the first element in the sequence that does not satisfy the predicate.
diff --git a/boost/algorithm/cxx11/iota.hpp b/boost/algorithm/cxx11/iota.hpp
index eb32390..2e638ec 100644
--- a/boost/algorithm/cxx11/iota.hpp
+++ b/boost/algorithm/cxx11/iota.hpp
@@ -19,10 +19,6 @@
namespace boost { namespace algorithm {
-#if __cplusplus >= 201103L
-// Use the C++11 versions of iota if it is available
-using std::iota; // Section 26.7.6
-#else
/// \fn iota ( ForwardIterator first, ForwardIterator last, T value )
/// \brief Generates an increasing sequence of values, and stores them in [first, last)
///
@@ -38,7 +34,6 @@ void iota ( ForwardIterator first, ForwardIterator last, T value )
for ( ; first != last; ++first, ++value )
*first = value;
}
-#endif
/// \fn iota ( Range &r, T value )
/// \brief Generates an increasing sequence of values, and stores them in the input Range.
diff --git a/boost/algorithm/cxx11/is_partitioned.hpp b/boost/algorithm/cxx11/is_partitioned.hpp
index e939e05..cdabd97 100644
--- a/boost/algorithm/cxx11/is_partitioned.hpp
+++ b/boost/algorithm/cxx11/is_partitioned.hpp
@@ -19,10 +19,6 @@
namespace boost { namespace algorithm {
-#if __cplusplus >= 201103L
-// Use the C++11 versions of is_partitioned if it is available
-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 partitioned according to a predicate
///
@@ -45,7 +41,6 @@ bool is_partitioned ( InputIterator first, InputIterator last, UnaryPredicate p
return false;
return true;
}
-#endif
/// \fn is_partitioned ( const Range &r, UnaryPredicate p )
/// \brief Generates an increasing sequence of values, and stores them in the input Range.
diff --git a/boost/algorithm/cxx11/is_permutation.hpp b/boost/algorithm/cxx11/is_permutation.hpp
index 9b3bc22..ec902dc 100644
--- a/boost/algorithm/cxx11/is_permutation.hpp
+++ b/boost/algorithm/cxx11/is_permutation.hpp
@@ -99,11 +99,6 @@ namespace detail {
}
/// \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 the sequence [first,last) is a permutation of the sequence starting at first2
///
@@ -161,8 +156,6 @@ bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIt
return true;
}
-#endif
-
/// \fn is_permutation ( const Range &r, ForwardIterator first2 )
/// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2
diff --git a/boost/algorithm/cxx11/is_sorted.hpp b/boost/algorithm/cxx11/is_sorted.hpp
index c9bc65f..f6062da 100644
--- a/boost/algorithm/cxx11/is_sorted.hpp
+++ b/boost/algorithm/cxx11/is_sorted.hpp
@@ -26,11 +26,6 @@
namespace boost { namespace algorithm {
-#if __cplusplus >= 201103L
-// Use the C++11 versions of is_sorted/is_sorted_until if they are available
-using std::is_sorted_until; // Section 25.4.1.5
-using std::is_sorted; // Section 25.4.1.5
-#else
/// \fn is_sorted_until ( ForwardIterator first, ForwardIterator last, Pred p )
/// \return the point in the sequence [first, last) where the elements are unordered
/// (according to the comparison predicate 'p').
@@ -91,7 +86,6 @@ using std::is_sorted; // Section 25.4.1.5
{
return boost::algorithm::is_sorted_until (first, last) == last;
}
-#endif
///
/// -- Range based versions of the C++11 functions
diff --git a/boost/algorithm/cxx11/none_of.hpp b/boost/algorithm/cxx11/none_of.hpp
index feae991..67be3d1 100644
--- a/boost/algorithm/cxx11/none_of.hpp
+++ b/boost/algorithm/cxx11/none_of.hpp
@@ -18,10 +18,6 @@
namespace boost { namespace algorithm {
-// Use the C++11 versions of the none_of if it is available
-#if __cplusplus >= 201103L
-using std::none_of; // Section 25.2.3
-#else
/// \fn none_of ( InputIterator first, InputIterator last, Predicate p )
/// \return true if none of the elements in [first, last) satisfy the predicate 'p'
/// \note returns true on an empty range
@@ -38,7 +34,6 @@ for ( ; first != last; ++first )
return false;
return true;
}
-#endif
/// \fn none_of ( const Range &r, Predicate p )
/// \return true if none of the elements in the range satisfy the predicate 'p'
diff --git a/boost/algorithm/cxx11/partition_copy.hpp b/boost/algorithm/cxx11/partition_copy.hpp
index 15c4dd6..2d8c3e9 100644
--- a/boost/algorithm/cxx11/partition_copy.hpp
+++ b/boost/algorithm/cxx11/partition_copy.hpp
@@ -20,10 +20,6 @@
namespace boost { namespace algorithm {
-#if __cplusplus >= 201103L
-// Use the C++11 versions of partition_copy if it is available
-using std::partition_copy; // Section 25.3.13
-#else
/// \fn partition_copy ( InputIterator first, InputIterator last,
/// OutputIterator1 out_true, OutputIterator2 out_false, UnaryPredicate p )
/// \brief Copies the elements that satisfy the predicate p from the range [first, last)
@@ -53,7 +49,6 @@ partition_copy ( InputIterator first, InputIterator last,
*out_false++ = *first;
return std::pair<OutputIterator1, OutputIterator2> ( out_true, out_false );
}
-#endif
/// \fn partition_copy ( const Range &r,
/// OutputIterator1 out_true, OutputIterator2 out_false, UnaryPredicate p )
diff --git a/boost/algorithm/cxx11/partition_point.hpp b/boost/algorithm/cxx11/partition_point.hpp
index 36d8384..f1310c3 100644
--- a/boost/algorithm/cxx11/partition_point.hpp
+++ b/boost/algorithm/cxx11/partition_point.hpp
@@ -19,10 +19,6 @@
namespace boost { namespace algorithm {
-#if __cplusplus >= 201103L
-// Use the C++11 versions of partition_point if it is available
-using std::partition_point; // Section 25.3.13
-#else
/// \fn partition_point ( ForwardIterator first, ForwardIterator last, Predicate p )
/// \brief Given a partitioned range, returns the partition point, i.e, the first element
/// that does not satisfy p
@@ -52,7 +48,6 @@ ForwardIterator partition_point ( ForwardIterator first, ForwardIterator last, P
}
return first;
}
-#endif
/// \fn partition_point ( Range &r, Predicate p )
/// \brief Given a partitioned range, returns the partition point
@@ -61,7 +56,7 @@ ForwardIterator partition_point ( ForwardIterator first, ForwardIterator last, P
/// \param p The predicate to test the values with
///
template <typename Range, typename Predicate>
-typename boost::range_iterator<Range> partition_point ( Range &r, Predicate p )
+typename boost::range_iterator<Range>::type partition_point ( Range &r, Predicate p )
{
return boost::algorithm::partition_point (boost::begin(r), boost::end(r), p);
}
diff --git a/boost/algorithm/cxx14/is_permutation.hpp b/boost/algorithm/cxx14/is_permutation.hpp
index d8002cb..9346881 100644
--- a/boost/algorithm/cxx14/is_permutation.hpp
+++ b/boost/algorithm/cxx14/is_permutation.hpp
@@ -22,7 +22,6 @@
namespace boost { namespace algorithm {
-#if __cplusplus <= 201103L
/// \fn is_permutation ( ForwardIterator1 first, ForwardIterator1 last,
/// ForwardIterator2 first2, ForwardIterator2 last2 )
/// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2
@@ -40,10 +39,10 @@ bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1,
{
// How should I deal with the idea that ForwardIterator1::value_type
// and ForwardIterator2::value_type could be different? Define my own comparison predicate?
- std::pair<ForwardIterator1, ForwardIterator2> eq = boost::algorithm::mismatch
- ( first1, last1, first2, last2 );
- if ( eq.first == last1 && eq.second == last2)
- return true;
+ std::pair<ForwardIterator1, ForwardIterator2> eq = boost::algorithm::mismatch
+ ( first1, last1, first2, last2 );
+ if ( eq.first == last1 && eq.second == last2)
+ return true;
return boost::algorithm::detail::is_permutation_tag (
eq.first, last1, eq.second, last2,
std::equal_to<typename std::iterator_traits<ForwardIterator1>::value_type> (),
@@ -70,16 +69,15 @@ bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
BinaryPredicate pred )
{
- std::pair<ForwardIterator1, ForwardIterator2> eq = boost::algorithm::mismatch
- ( first1, last1, first2, last2, pred );
- if ( eq.first == last1 && eq.second == last2)
- return true;
+ std::pair<ForwardIterator1, ForwardIterator2> eq = boost::algorithm::mismatch
+ ( first1, last1, first2, last2, pred );
+ if ( eq.first == last1 && eq.second == last2)
+ return true;
return boost::algorithm::detail::is_permutation_tag (
first1, last1, first2, last2, pred,
typename std::iterator_traits<ForwardIterator1>::iterator_category (),
typename std::iterator_traits<ForwardIterator2>::iterator_category ());
}
-#endif
}}
diff --git a/boost/algorithm/hex.hpp b/boost/algorithm/hex.hpp
index 2adb0be..145a414 100644
--- a/boost/algorithm/hex.hpp
+++ b/boost/algorithm/hex.hpp
@@ -207,7 +207,6 @@ OutputIterator unhex ( InputIterator first, InputIterator last, OutputIterator o
/// \note Based on the MySQL function of the same name
template <typename T, typename OutputIterator>
OutputIterator unhex ( const T *ptr, OutputIterator out ) {
- typedef typename detail::hex_iterator_traits<OutputIterator>::value_type OutputType;
// If we run into the terminator while decoding, we will throw a
// malformed input exception. It would be nicer to throw a 'Not enough input'
// exception - but how much extra work would that require?
diff --git a/boost/algorithm/searching/detail/bm_traits.hpp b/boost/algorithm/searching/detail/bm_traits.hpp
index 9c25540..b39e539 100644
--- a/boost/algorithm/searching/detail/bm_traits.hpp
+++ b/boost/algorithm/searching/detail/bm_traits.hpp
@@ -21,7 +21,7 @@
#include <boost/array.hpp>
#ifdef BOOST_NO_CXX11_HDR_UNORDERED_MAP
-#include <boost/tr1/tr1/unordered_map>
+#include <boost/unordered_map.hpp>
#else
#include <unordered_map>
#endif
@@ -40,7 +40,7 @@ namespace boost { namespace algorithm { namespace detail {
class skip_table<key_type, value_type, false> {
private:
#ifdef BOOST_NO_CXX11_HDR_UNORDERED_MAP
- typedef std::tr1::unordered_map<key_type, value_type> skip_map;
+ typedef boost::unordered_map<key_type, value_type> skip_map;
#else
typedef std::unordered_map<key_type, value_type> skip_map;
#endif
diff --git a/boost/algorithm/string/find_iterator.hpp b/boost/algorithm/string/find_iterator.hpp
index 5834407..5a52d92 100644
--- a/boost/algorithm/string/find_iterator.hpp
+++ b/boost/algorithm/string/find_iterator.hpp
@@ -230,7 +230,12 @@ namespace boost {
\post eof()==true
*/
- split_iterator() { m_bEof = true; }
+ split_iterator() :
+ m_Next(),
+ m_End(),
+ m_bEof(true)
+ {}
+
//! Copy constructor
/*!
Construct a copy of the split_iterator