diff options
| author | bugaevskiy <bugaevskiy@yandex-team.com> | 2022-08-14 11:32:24 +0300 |
|---|---|---|
| committer | bugaevskiy <bugaevskiy@yandex-team.com> | 2022-08-14 11:32:24 +0300 |
| commit | 6e78c26bd08cf9e33f011d1642dee5a4f6709e54 (patch) | |
| tree | a5b7894471c33b19cbd476a4e1713e386aa30cc0 /contrib/restricted/boost | |
| parent | dcd0f59d274b8651b7a32a1ff68bd684aea19feb (diff) | |
| download | ydb-6e78c26bd08cf9e33f011d1642dee5a4f6709e54.tar.gz | |
Reimport boost/algorithm as a separate project
Diffstat (limited to 'contrib/restricted/boost')
85 files changed, 72 insertions, 5554 deletions
diff --git a/contrib/restricted/boost/CMakeLists.txt b/contrib/restricted/boost/CMakeLists.txt index 033c41960e..0715813402 100644 --- a/contrib/restricted/boost/CMakeLists.txt +++ b/contrib/restricted/boost/CMakeLists.txt @@ -13,6 +13,7 @@ target_include_directories(contrib-restricted-boost INTERFACE ) target_link_libraries(contrib-restricted-boost INTERFACE contrib-libs-cxxsupp + restricted-boost-algorithm restricted-boost-align restricted-boost-any restricted-boost-array diff --git a/contrib/restricted/boost/algorithm/CMakeLists.txt b/contrib/restricted/boost/algorithm/CMakeLists.txt new file mode 100644 index 0000000000..cfdc6eaf88 --- /dev/null +++ b/contrib/restricted/boost/algorithm/CMakeLists.txt @@ -0,0 +1,34 @@ + +# This file was gererated by the build system used internally in the Yandex monorepo. +# Only simple modifications are allowed (adding source-files to targets, adding simple properties +# like target_include_directories). These modifications will be ported to original +# ya.make files by maintainers. Any complex modifications which can't be ported back to the +# original buildsystem will not be accepted. + + + +add_library(restricted-boost-algorithm INTERFACE) +target_include_directories(restricted-boost-algorithm INTERFACE + ${CMAKE_SOURCE_DIR}/contrib/restricted/boost/algorithm/include +) +target_link_libraries(restricted-boost-algorithm INTERFACE + contrib-libs-cxxsupp + yutil + restricted-boost-array + restricted-boost-assert + restricted-boost-bind + restricted-boost-concept_check + restricted-boost-config + restricted-boost-core + restricted-boost-exception + restricted-boost-function + restricted-boost-iterator + restricted-boost-mpl + restricted-boost-range + restricted-boost-regex + restricted-boost-static_assert + restricted-boost-throw_exception + restricted-boost-tuple + restricted-boost-type_traits + restricted-boost-unordered +) diff --git a/contrib/restricted/boost/boost/algorithm/cxx11/all_of.hpp b/contrib/restricted/boost/algorithm/include/boost/algorithm/cxx11/all_of.hpp index 8280b18d62..8280b18d62 100644 --- a/contrib/restricted/boost/boost/algorithm/cxx11/all_of.hpp +++ b/contrib/restricted/boost/algorithm/include/boost/algorithm/cxx11/all_of.hpp diff --git a/contrib/restricted/boost/boost/algorithm/string.hpp b/contrib/restricted/boost/algorithm/include/boost/algorithm/string.hpp index 0771517396..0771517396 100644 --- a/contrib/restricted/boost/boost/algorithm/string.hpp +++ b/contrib/restricted/boost/algorithm/include/boost/algorithm/string.hpp diff --git a/contrib/restricted/boost/boost/algorithm/string/case_conv.hpp b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/case_conv.hpp index 683340b8ec..683340b8ec 100644 --- a/contrib/restricted/boost/boost/algorithm/string/case_conv.hpp +++ b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/case_conv.hpp diff --git a/contrib/restricted/boost/boost/algorithm/string/classification.hpp b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/classification.hpp index ca43602d47..ca43602d47 100644 --- a/contrib/restricted/boost/boost/algorithm/string/classification.hpp +++ b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/classification.hpp diff --git a/contrib/restricted/boost/boost/algorithm/string/compare.hpp b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/compare.hpp index 734303a9a9..734303a9a9 100644 --- a/contrib/restricted/boost/boost/algorithm/string/compare.hpp +++ b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/compare.hpp diff --git a/contrib/restricted/boost/boost/algorithm/string/concept.hpp b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/concept.hpp index 17e8349596..17e8349596 100644 --- a/contrib/restricted/boost/boost/algorithm/string/concept.hpp +++ b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/concept.hpp diff --git a/contrib/restricted/boost/boost/algorithm/string/config.hpp b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/config.hpp index 559750ac8a..559750ac8a 100644 --- a/contrib/restricted/boost/boost/algorithm/string/config.hpp +++ b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/config.hpp diff --git a/contrib/restricted/boost/boost/algorithm/string/constants.hpp b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/constants.hpp index 6ed70effca..6ed70effca 100644 --- a/contrib/restricted/boost/boost/algorithm/string/constants.hpp +++ b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/constants.hpp diff --git a/contrib/restricted/boost/boost/algorithm/string/detail/case_conv.hpp b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/detail/case_conv.hpp index 233912ca0f..233912ca0f 100644 --- a/contrib/restricted/boost/boost/algorithm/string/detail/case_conv.hpp +++ b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/detail/case_conv.hpp diff --git a/contrib/restricted/boost/boost/algorithm/string/detail/classification.hpp b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/detail/classification.hpp index 704d9d20ff..704d9d20ff 100644 --- a/contrib/restricted/boost/boost/algorithm/string/detail/classification.hpp +++ b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/detail/classification.hpp diff --git a/contrib/restricted/boost/boost/algorithm/string/detail/find_format.hpp b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/detail/find_format.hpp index b39875024c..b39875024c 100644 --- a/contrib/restricted/boost/boost/algorithm/string/detail/find_format.hpp +++ b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/detail/find_format.hpp diff --git a/contrib/restricted/boost/boost/algorithm/string/detail/find_format_all.hpp b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/detail/find_format_all.hpp index 52930c83ad..52930c83ad 100644 --- a/contrib/restricted/boost/boost/algorithm/string/detail/find_format_all.hpp +++ b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/detail/find_format_all.hpp diff --git a/contrib/restricted/boost/boost/algorithm/string/detail/find_format_store.hpp b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/detail/find_format_store.hpp index b9f4a88d91..b9f4a88d91 100644 --- a/contrib/restricted/boost/boost/algorithm/string/detail/find_format_store.hpp +++ b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/detail/find_format_store.hpp diff --git a/contrib/restricted/boost/boost/algorithm/string/detail/find_iterator.hpp b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/detail/find_iterator.hpp index 4f90a98fc0..c990785256 100644 --- a/contrib/restricted/boost/boost/algorithm/string/detail/find_iterator.hpp +++ b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/detail/find_iterator.hpp @@ -40,10 +40,18 @@ namespace boost { // Protected construction/destruction // Default constructor - find_iterator_base() {} + BOOST_DEFAULTED_FUNCTION(find_iterator_base(), {}) + // Copy construction - find_iterator_base( const find_iterator_base& Other ) : + BOOST_DEFAULTED_FUNCTION(find_iterator_base( const find_iterator_base& Other ), : m_Finder(Other.m_Finder) {} + ) + + // Assignment + BOOST_DEFAULTED_FUNCTION(find_iterator_base& operator=( const find_iterator_base& Other ), { + m_Finder = Other.m_Finder; + return *this; + }) // Constructor template<typename FinderT> @@ -51,7 +59,7 @@ namespace boost { m_Finder(Finder) {} // Destructor - ~find_iterator_base() {} + BOOST_DEFAULTED_FUNCTION(~find_iterator_base(), {}) // Find operation match_type do_find( diff --git a/contrib/restricted/boost/boost/algorithm/string/detail/finder.hpp b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/detail/finder.hpp index a2a958212d..a2a958212d 100644 --- a/contrib/restricted/boost/boost/algorithm/string/detail/finder.hpp +++ b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/detail/finder.hpp diff --git a/contrib/restricted/boost/boost/algorithm/string/detail/formatter.hpp b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/detail/formatter.hpp index c071822f2a..c071822f2a 100644 --- a/contrib/restricted/boost/boost/algorithm/string/detail/formatter.hpp +++ b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/detail/formatter.hpp diff --git a/contrib/restricted/boost/boost/algorithm/string/detail/predicate.hpp b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/detail/predicate.hpp index 5acf3cc663..5acf3cc663 100644 --- a/contrib/restricted/boost/boost/algorithm/string/detail/predicate.hpp +++ b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/detail/predicate.hpp diff --git a/contrib/restricted/boost/boost/algorithm/string/detail/replace_storage.hpp b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/detail/replace_storage.hpp index db35e4c53b..db35e4c53b 100644 --- a/contrib/restricted/boost/boost/algorithm/string/detail/replace_storage.hpp +++ b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/detail/replace_storage.hpp diff --git a/contrib/restricted/boost/boost/algorithm/string/detail/sequence.hpp b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/detail/sequence.hpp index dc47409115..dc47409115 100644 --- a/contrib/restricted/boost/boost/algorithm/string/detail/sequence.hpp +++ b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/detail/sequence.hpp diff --git a/contrib/restricted/boost/boost/algorithm/string/detail/trim.hpp b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/detail/trim.hpp index 1233e49d30..1233e49d30 100644 --- a/contrib/restricted/boost/boost/algorithm/string/detail/trim.hpp +++ b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/detail/trim.hpp diff --git a/contrib/restricted/boost/boost/algorithm/string/detail/util.hpp b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/detail/util.hpp index 7844b6723c..7844b6723c 100644 --- a/contrib/restricted/boost/boost/algorithm/string/detail/util.hpp +++ b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/detail/util.hpp diff --git a/contrib/restricted/boost/boost/algorithm/string/erase.hpp b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/erase.hpp index 6883790978..6883790978 100644 --- a/contrib/restricted/boost/boost/algorithm/string/erase.hpp +++ b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/erase.hpp diff --git a/contrib/restricted/boost/boost/algorithm/string/find.hpp b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/find.hpp index f2c2926b50..f2c2926b50 100644 --- a/contrib/restricted/boost/boost/algorithm/string/find.hpp +++ b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/find.hpp diff --git a/contrib/restricted/boost/boost/algorithm/string/find_format.hpp b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/find_format.hpp index 0e84a4ee68..0e84a4ee68 100644 --- a/contrib/restricted/boost/boost/algorithm/string/find_format.hpp +++ b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/find_format.hpp diff --git a/contrib/restricted/boost/boost/algorithm/string/find_iterator.hpp b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/find_iterator.hpp index 75287d9672..47c20e673c 100644 --- a/contrib/restricted/boost/boost/algorithm/string/find_iterator.hpp +++ b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/find_iterator.hpp @@ -74,7 +74,7 @@ namespace boost { \post eof()==true */ - find_iterator() {} + BOOST_DEFAULTED_FUNCTION(find_iterator(), {}) //! Copy constructor /*! @@ -85,6 +85,18 @@ namespace boost { m_Match(Other.m_Match), m_End(Other.m_End) {} + //! Copy assignment + /*! + Assigns a copy of the find_iterator + */ + BOOST_DEFAULTED_FUNCTION(find_iterator& operator=( const find_iterator& Other ), { + if (this == &Other) return *this; + this->base_type::operator=(Other); + m_Match = Other.m_Match; + m_End = Other.m_End; + return *this; + }) + //! Constructor /*! Construct new find_iterator for a given finder @@ -248,7 +260,19 @@ namespace boost { m_bEof(Other.m_bEof) {} - split_iterator& operator=(const split_iterator& Other) = default; + //! Assignment operator + /*! + Assigns a copy of the split_iterator + */ + BOOST_DEFAULTED_FUNCTION(split_iterator& operator=( const split_iterator& Other ), { + if (this == &Other) return *this; + this->base_type::operator=(Other); + m_Match = Other.m_Match; + m_Next = Other.m_Next; + m_End = Other.m_End; + m_bEof = Other.m_bEof; + return *this; + }) //! Constructor /*! diff --git a/contrib/restricted/boost/boost/algorithm/string/finder.hpp b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/finder.hpp index 93f7ec304a..93f7ec304a 100644 --- a/contrib/restricted/boost/boost/algorithm/string/finder.hpp +++ b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/finder.hpp diff --git a/contrib/restricted/boost/boost/algorithm/string/formatter.hpp b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/formatter.hpp index de8681bc3f..de8681bc3f 100644 --- a/contrib/restricted/boost/boost/algorithm/string/formatter.hpp +++ b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/formatter.hpp diff --git a/contrib/restricted/boost/boost/algorithm/string/iter_find.hpp b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/iter_find.hpp index 10424abc74..10424abc74 100644 --- a/contrib/restricted/boost/boost/algorithm/string/iter_find.hpp +++ b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/iter_find.hpp diff --git a/contrib/restricted/boost/boost/algorithm/string/join.hpp b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/join.hpp index b871eb44f6..b871eb44f6 100644 --- a/contrib/restricted/boost/boost/algorithm/string/join.hpp +++ b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/join.hpp diff --git a/contrib/restricted/boost/boost/algorithm/string/predicate.hpp b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/predicate.hpp index 0879829b5a..0879829b5a 100644 --- a/contrib/restricted/boost/boost/algorithm/string/predicate.hpp +++ b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/predicate.hpp diff --git a/contrib/restricted/boost/boost/algorithm/string/predicate_facade.hpp b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/predicate_facade.hpp index a9753fc2ae..a9753fc2ae 100644 --- a/contrib/restricted/boost/boost/algorithm/string/predicate_facade.hpp +++ b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/predicate_facade.hpp diff --git a/contrib/restricted/boost/boost/algorithm/string/replace.hpp b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/replace.hpp index 2adb031c59..2adb031c59 100644 --- a/contrib/restricted/boost/boost/algorithm/string/replace.hpp +++ b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/replace.hpp diff --git a/contrib/restricted/boost/boost/algorithm/string/sequence_traits.hpp b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/sequence_traits.hpp index be151f8d3d..be151f8d3d 100644 --- a/contrib/restricted/boost/boost/algorithm/string/sequence_traits.hpp +++ b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/sequence_traits.hpp diff --git a/contrib/restricted/boost/boost/algorithm/string/split.hpp b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/split.hpp index cae712c07f..cae712c07f 100644 --- a/contrib/restricted/boost/boost/algorithm/string/split.hpp +++ b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/split.hpp diff --git a/contrib/restricted/boost/boost/algorithm/string/std/list_traits.hpp b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/std/list_traits.hpp index a3cf7bb18c..a3cf7bb18c 100644 --- a/contrib/restricted/boost/boost/algorithm/string/std/list_traits.hpp +++ b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/std/list_traits.hpp diff --git a/contrib/restricted/boost/boost/algorithm/string/std/slist_traits.hpp b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/std/slist_traits.hpp index c30b93c73a..c30b93c73a 100644 --- a/contrib/restricted/boost/boost/algorithm/string/std/slist_traits.hpp +++ b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/std/slist_traits.hpp diff --git a/contrib/restricted/boost/boost/algorithm/string/std/string_traits.hpp b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/std/string_traits.hpp index c9408307d3..c9408307d3 100644 --- a/contrib/restricted/boost/boost/algorithm/string/std/string_traits.hpp +++ b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/std/string_traits.hpp diff --git a/contrib/restricted/boost/boost/algorithm/string/std_containers_traits.hpp b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/std_containers_traits.hpp index 3f02246fda..3f02246fda 100644 --- a/contrib/restricted/boost/boost/algorithm/string/std_containers_traits.hpp +++ b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/std_containers_traits.hpp diff --git a/contrib/restricted/boost/boost/algorithm/string/trim.hpp b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/trim.hpp index e740d57d93..e740d57d93 100644 --- a/contrib/restricted/boost/boost/algorithm/string/trim.hpp +++ b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/trim.hpp diff --git a/contrib/restricted/boost/boost/algorithm/string/yes_no_type.hpp b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/yes_no_type.hpp index b76cc6c155..b76cc6c155 100644 --- a/contrib/restricted/boost/boost/algorithm/string/yes_no_type.hpp +++ b/contrib/restricted/boost/algorithm/include/boost/algorithm/string/yes_no_type.hpp diff --git a/contrib/restricted/boost/boost/algorithm/algorithm.hpp b/contrib/restricted/boost/boost/algorithm/algorithm.hpp deleted file mode 100644 index ab0d4aff58..0000000000 --- a/contrib/restricted/boost/boost/algorithm/algorithm.hpp +++ /dev/null @@ -1,88 +0,0 @@ -/* - 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 <functional> // for plus and multiplies - -#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 operation "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/contrib/restricted/boost/boost/algorithm/clamp.hpp b/contrib/restricted/boost/boost/algorithm/clamp.hpp deleted file mode 100644 index 7bfa47ec9b..0000000000 --- a/contrib/restricted/boost/boost/algorithm/clamp.hpp +++ /dev/null @@ -1,175 +0,0 @@ -/* - Copyright (c) Marshall Clow 2008-2012. - - 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: - 27 June 2009 mtc First version - 23 Oct 2010 mtc Added predicate version - -*/ - -/// \file clamp.hpp -/// \brief Clamp algorithm -/// \author Marshall Clow -/// -/// Suggested by olafvdspek in https://svn.boost.org/trac/boost/ticket/3215 - -#ifndef BOOST_ALGORITHM_CLAMP_HPP -#define BOOST_ALGORITHM_CLAMP_HPP - -#include <functional> // For std::less -#include <iterator> // For std::iterator_traits -#include <cassert> - -#include <boost/range/begin.hpp> -#include <boost/range/end.hpp> -#include <boost/mpl/identity.hpp> // for identity -#include <boost/utility/enable_if.hpp> // for boost::disable_if - -namespace boost { namespace algorithm { - -/// \fn clamp ( T const& val, -/// typename boost::mpl::identity<T>::type const & lo, -/// typename boost::mpl::identity<T>::type const & hi, Pred p ) -/// \return the value "val" brought into the range [ lo, hi ] -/// using the comparison predicate p. -/// If p ( val, lo ) return lo. -/// If p ( hi, val ) return hi. -/// Otherwise, return the original value. -/// -/// \param val The value to be clamped -/// \param lo The lower bound of the range to be clamped to -/// \param hi The upper bound of the range to be clamped to -/// \param p A predicate to use to compare the values. -/// p ( a, b ) returns a boolean. -/// - template<typename T, typename Pred> - T const & clamp ( T const& val, - typename boost::mpl::identity<T>::type const & lo, - typename boost::mpl::identity<T>::type const & hi, Pred p ) - { -// assert ( !p ( hi, lo )); // Can't assert p ( lo, hi ) b/c they might be equal - return p ( val, lo ) ? lo : p ( hi, val ) ? hi : val; - } - - -/// \fn clamp ( T const& val, -/// typename boost::mpl::identity<T>::type const & lo, -/// typename boost::mpl::identity<T>::type const & hi ) -/// \return the value "val" brought into the range [ lo, hi ]. -/// If the value is less than lo, return lo. -/// If the value is greater than "hi", return hi. -/// Otherwise, return the original value. -/// -/// \param val The value to be clamped -/// \param lo The lower bound of the range to be clamped to -/// \param hi The upper bound of the range to be clamped to -/// - template<typename T> - T const& clamp ( const T& val, - typename boost::mpl::identity<T>::type const & lo, - typename boost::mpl::identity<T>::type const & hi ) - { - return (clamp) ( val, lo, hi, std::less<T>()); - } - -/// \fn clamp_range ( InputIterator first, InputIterator last, OutputIterator out, -/// std::iterator_traits<InputIterator>::value_type const & lo, -/// std::iterator_traits<InputIterator>::value_type const & hi ) -/// \return clamp the sequence of values [first, last) into [ lo, hi ] -/// -/// \param first The start of the range of values -/// \param last One past the end of the range of input values -/// \param out An output iterator to write the clamped values into -/// \param lo The lower bound of the range to be clamped to -/// \param hi The upper bound of the range to be clamped to -/// - template<typename InputIterator, typename OutputIterator> - OutputIterator clamp_range ( InputIterator first, InputIterator last, OutputIterator out, - typename std::iterator_traits<InputIterator>::value_type const & lo, - typename std::iterator_traits<InputIterator>::value_type const & hi ) - { - // this could also be written with bind and std::transform - while ( first != last ) - *out++ = clamp ( *first++, lo, hi ); - return out; - } - -/// \fn clamp_range ( const Range &r, OutputIterator out, -/// typename std::iterator_traits<typename boost::range_iterator<const Range>::type>::value_type const & lo, -/// typename std::iterator_traits<typename boost::range_iterator<const Range>::type>::value_type const & hi ) -/// \return clamp the sequence of values [first, last) into [ lo, hi ] -/// -/// \param r The range of values to be clamped -/// \param out An output iterator to write the clamped values into -/// \param lo The lower bound of the range to be clamped to -/// \param hi The upper bound of the range to be clamped to -/// - template<typename Range, typename OutputIterator> - typename boost::disable_if_c<boost::is_same<Range, OutputIterator>::value, OutputIterator>::type - clamp_range ( const Range &r, OutputIterator out, - typename std::iterator_traits<typename boost::range_iterator<const Range>::type>::value_type const & lo, - typename std::iterator_traits<typename boost::range_iterator<const Range>::type>::value_type const & hi ) - { - return clamp_range ( boost::begin ( r ), boost::end ( r ), out, lo, hi ); - } - - -/// \fn clamp_range ( InputIterator first, InputIterator last, OutputIterator out, -/// std::iterator_traits<InputIterator>::value_type const & lo, -/// std::iterator_traits<InputIterator>::value_type const & hi, Pred p ) -/// \return clamp the sequence of values [first, last) into [ lo, hi ] -/// using the comparison predicate p. -/// -/// \param first The start of the range of values -/// \param last One past the end of the range of input values -/// \param out An output iterator to write the clamped values into -/// \param lo The lower bound of the range to be clamped to -/// \param hi The upper bound of the range to be clamped to -/// \param p A predicate to use to compare the values. -/// p ( a, b ) returns a boolean. - -/// - template<typename InputIterator, typename OutputIterator, typename Pred> - OutputIterator clamp_range ( InputIterator first, InputIterator last, OutputIterator out, - typename std::iterator_traits<InputIterator>::value_type const & lo, - typename std::iterator_traits<InputIterator>::value_type const & hi, Pred p ) - { - // this could also be written with bind and std::transform - while ( first != last ) - *out++ = clamp ( *first++, lo, hi, p ); - return out; - } - -/// \fn clamp_range ( const Range &r, OutputIterator out, -/// typename std::iterator_traits<typename boost::range_iterator<const Range>::type>::value_type const & lo, -/// typename std::iterator_traits<typename boost::range_iterator<const Range>::type>::value_type const & hi, -/// Pred p ) -/// \return clamp the sequence of values [first, last) into [ lo, hi ] -/// using the comparison predicate p. -/// -/// \param r The range of values to be clamped -/// \param out An output iterator to write the clamped values into -/// \param lo The lower bound of the range to be clamped to -/// \param hi The upper bound of the range to be clamped to -/// \param p A predicate to use to compare the values. -/// p ( a, b ) returns a boolean. -// -// Disable this template if the first two parameters are the same type; -// In that case, the user will get the two iterator version. - template<typename Range, typename OutputIterator, typename Pred> - typename boost::disable_if_c<boost::is_same<Range, OutputIterator>::value, OutputIterator>::type - clamp_range ( const Range &r, OutputIterator out, - typename std::iterator_traits<typename boost::range_iterator<const Range>::type>::value_type const & lo, - typename std::iterator_traits<typename boost::range_iterator<const Range>::type>::value_type const & hi, - Pred p ) - { - return clamp_range ( boost::begin ( r ), boost::end ( r ), out, lo, hi, p ); - } - - -}} - -#endif // BOOST_ALGORITHM_CLAMP_HPP diff --git a/contrib/restricted/boost/boost/algorithm/cxx11/any_of.hpp b/contrib/restricted/boost/boost/algorithm/cxx11/any_of.hpp deleted file mode 100644 index e68135a2b3..0000000000 --- a/contrib/restricted/boost/boost/algorithm/cxx11/any_of.hpp +++ /dev/null @@ -1,84 +0,0 @@ -/* - Copyright (c) Marshall Clow 2008-2012. - - 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) - - For more information, see http://www.boost.org -*/ - -/// \file -/// \brief Test ranges to see if any elements match a value or predicate. -/// \author Marshall Clow - -#ifndef BOOST_ALGORITHM_ANY_OF_HPP -#define BOOST_ALGORITHM_ANY_OF_HPP - -#include <boost/range/begin.hpp> -#include <boost/range/end.hpp> - -namespace boost { namespace algorithm { - -/// \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 -/// -/// \param first The start of the input sequence -/// \param last One past the end of the input sequence -/// \param p A predicate for testing the elements of the sequence -/// -template<typename InputIterator, typename Predicate> -bool any_of ( InputIterator first, InputIterator last, Predicate p ) -{ - for ( ; first != last; ++first ) - if ( p(*first)) - return true; - return false; -} - -/// \fn any_of ( const Range &r, Predicate p ) -/// \return true if any elements in the range satisfy the predicate 'p' -/// \note returns false on an empty range -/// -/// \param r The input range -/// \param p A predicate for testing the elements of the range -/// -template<typename Range, typename Predicate> -bool any_of ( const Range &r, Predicate p ) -{ - return boost::algorithm::any_of (boost::begin (r), boost::end (r), p); -} - -/// \fn any_of_equal ( InputIterator first, InputIterator last, const V &val ) -/// \return true if any of the elements in [first, last) are equal to 'val' -/// \note returns false on an empty range -/// -/// \param first The start of the input sequence -/// \param last One past the end of the input sequence -/// \param val A value to compare against -/// -template<typename InputIterator, typename V> -bool any_of_equal ( InputIterator first, InputIterator last, const V &val ) -{ - for ( ; first != last; ++first ) - if ( val == *first ) - return true; - return false; -} - -/// \fn any_of_equal ( const Range &r, const V &val ) -/// \return true if any of the elements in the range are equal to 'val' -/// \note returns false on an empty range -/// -/// \param r The input range -/// \param val A value to compare against -/// -template<typename Range, typename V> -bool any_of_equal ( const Range &r, const V &val ) -{ - return boost::algorithm::any_of_equal (boost::begin (r), boost::end (r), val); -} - -}} // namespace boost and algorithm - -#endif // BOOST_ALGORITHM_ANY_OF_HPP diff --git a/contrib/restricted/boost/boost/algorithm/cxx11/copy_if.hpp b/contrib/restricted/boost/boost/algorithm/cxx11/copy_if.hpp deleted file mode 100644 index 73e85d99c6..0000000000 --- a/contrib/restricted/boost/boost/algorithm/cxx11/copy_if.hpp +++ /dev/null @@ -1,129 +0,0 @@ -/* - Copyright (c) Marshall Clow 2008-2012. - - 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) -*/ - -/// \file copy_if.hpp -/// \brief Copy a subset of a sequence to a new sequence -/// \author Marshall Clow - -#ifndef BOOST_ALGORITHM_COPY_IF_HPP -#define BOOST_ALGORITHM_COPY_IF_HPP - -#include <utility> // for std::pair, std::make_pair -#include <boost/range/begin.hpp> -#include <boost/range/end.hpp> - -namespace boost { namespace algorithm { - -/// \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. -/// \return The updated output iterator -/// -/// \param first The start of the input sequence -/// \param last One past the end of the input sequence -/// \param result An output iterator to write the results into -/// \param p A predicate for testing the elements of the range -/// \note This function is part of the C++2011 standard library. -template<typename InputIterator, typename OutputIterator, typename Predicate> -OutputIterator copy_if ( InputIterator first, InputIterator last, OutputIterator result, Predicate p ) -{ - for ( ; first != last; ++first ) - if (p(*first)) - *result++ = *first; - return result; -} - -/// \fn copy_if ( const Range &r, OutputIterator result, Predicate p ) -/// \brief Copies all the elements from the input range that satisfy the -/// predicate to the output range. -/// \return The updated output iterator -/// -/// \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_if ( const Range &r, OutputIterator result, Predicate p ) -{ - return boost::algorithm::copy_if (boost::begin (r), boost::end(r), result, 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 input and output iterators -/// -/// \param first The start of the input sequence -/// \param last One past the end of the input sequence -/// \param result An output iterator to write the results into -/// \param p A predicate for testing the elements of the range -/// -template<typename InputIterator, typename OutputIterator, typename Predicate> -std::pair<InputIterator, OutputIterator> -copy_while ( InputIterator first, InputIterator last, OutputIterator result, Predicate p ) -{ - for ( ; first != last && p(*first); ++first ) - *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 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> -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); -} - - -/// \fn copy_until ( InputIterator first, InputIterator last, OutputIterator result, Predicate p ) -/// \brief Copies all the elements at the start of the input range that do not -/// satisfy the predicate to the output range. -/// \return The updated output iterator -/// -/// \param first The start of the input sequence -/// \param last One past the end of the input sequence -/// \param result An output iterator to write the results into -/// \param p A predicate for testing the elements of the range -/// -template<typename InputIterator, typename OutputIterator, typename Predicate> -std::pair<InputIterator, OutputIterator> -copy_until ( InputIterator first, InputIterator last, OutputIterator result, Predicate p ) -{ - for ( ; first != last && !p(*first); ++first ) - *result++ = *first; - return std::make_pair(first, result); -} - -/// \fn copy_until ( const Range &r, OutputIterator result, Predicate p ) -/// \brief Copies all the elements at the start of the input range that do not -/// satisfy the predicate to the output range. -/// \return The updated output iterator -/// -/// \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> -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); -} - -}} // namespace boost and algorithm - -#endif // BOOST_ALGORITHM_COPY_IF_HPP diff --git a/contrib/restricted/boost/boost/algorithm/cxx11/copy_n.hpp b/contrib/restricted/boost/boost/algorithm/cxx11/copy_n.hpp deleted file mode 100644 index ac880856db..0000000000 --- a/contrib/restricted/boost/boost/algorithm/cxx11/copy_n.hpp +++ /dev/null @@ -1,35 +0,0 @@ -/* - Copyright (c) Marshall Clow 2011-2012. - - 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) -*/ - -/// \file copy_n.hpp -/// \brief Copy n items from one sequence to another -/// \author Marshall Clow - -#ifndef BOOST_ALGORITHM_COPY_N_HPP -#define BOOST_ALGORITHM_COPY_N_HPP - -namespace boost { namespace algorithm { - -/// \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. -/// \return The updated output iterator -/// -/// \param first The start of the input sequence -/// \param n The number of elements to copy -/// \param result An output iterator to write the results into -/// \note This function is part of the C++2011 standard library. -template <typename InputIterator, typename Size, typename OutputIterator> -OutputIterator copy_n ( InputIterator first, Size n, OutputIterator result ) -{ - for ( ; n > 0; --n, ++first, ++result ) - *result = *first; - return result; -} -}} // namespace boost and algorithm - -#endif // BOOST_ALGORITHM_COPY_IF_HPP diff --git a/contrib/restricted/boost/boost/algorithm/cxx11/find_if_not.hpp b/contrib/restricted/boost/boost/algorithm/cxx11/find_if_not.hpp deleted file mode 100644 index 02ff4dce7b..0000000000 --- a/contrib/restricted/boost/boost/algorithm/cxx11/find_if_not.hpp +++ /dev/null @@ -1,51 +0,0 @@ -/* - Copyright (c) Marshall Clow 2011-2012. - - 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) -*/ - -/// \file find_if_not.hpp -/// \brief Find the first element in a sequence that does not satisfy a predicate. -/// \author Marshall Clow - -#ifndef BOOST_ALGORITHM_FIND_IF_NOT_HPP -#define BOOST_ALGORITHM_FIND_IF_NOT_HPP - -#include <boost/range/begin.hpp> -#include <boost/range/end.hpp> - -namespace boost { namespace algorithm { - -/// \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. -/// -/// \param first The start of the input sequence -/// \param last One past the end of the input sequence -/// \param p A predicate for testing the elements of the range -/// \note This function is part of the C++2011 standard library. -template<typename InputIterator, typename Predicate> -InputIterator find_if_not ( InputIterator first, InputIterator last, Predicate p ) -{ - for ( ; first != last; ++first ) - if ( !p(*first)) - break; - return first; -} - -/// \fn find_if_not ( const Range &r, Predicate p ) -/// \brief Finds the first element in the sequence that does not satisfy the predicate. -/// \return The iterator pointing to the desired element. -/// -/// \param r The input range -/// \param p A predicate for testing the elements of the range -/// -template<typename Range, typename Predicate> -typename boost::range_iterator<const Range>::type find_if_not ( const Range &r, Predicate p ) -{ - return boost::algorithm::find_if_not (boost::begin (r), boost::end(r), p); -} - -}} -#endif // BOOST_ALGORITHM_FIND_IF_NOT_HPP diff --git a/contrib/restricted/boost/boost/algorithm/cxx11/iota.hpp b/contrib/restricted/boost/boost/algorithm/cxx11/iota.hpp deleted file mode 100644 index 675093f02d..0000000000 --- a/contrib/restricted/boost/boost/algorithm/cxx11/iota.hpp +++ /dev/null @@ -1,65 +0,0 @@ -/* - Copyright (c) Marshall Clow 2008-2012. - - 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) -*/ - -/// \file iota.hpp -/// \brief Generate an increasing series -/// \author Marshall Clow - -#ifndef BOOST_ALGORITHM_IOTA_HPP -#define BOOST_ALGORITHM_IOTA_HPP - -#include <boost/range/begin.hpp> -#include <boost/range/end.hpp> - -namespace boost { namespace algorithm { - -/// \fn iota ( ForwardIterator first, ForwardIterator last, T value ) -/// \brief Generates an increasing sequence of values, and stores them in [first, last) -/// -/// \param first The start of the input sequence -/// \param last One past the end of the input sequence -/// \param value The initial value of the sequence to be generated -/// \note This function is part of the C++2011 standard library. -template <typename ForwardIterator, typename T> -void iota ( ForwardIterator first, ForwardIterator last, T value ) -{ - for ( ; first != last; ++first, ++value ) - *first = value; -} - -/// \fn iota ( Range &r, T value ) -/// \brief Generates an increasing sequence of values, and stores them in the input Range. -/// -/// \param r The input range -/// \param value The initial value of the sequence to be generated -/// -template <typename Range, typename T> -void iota ( Range &r, T value ) -{ - boost::algorithm::iota (boost::begin(r), boost::end(r), value); -} - - -/// \fn iota_n ( OutputIterator out, T value, std::size_t n ) -/// \brief Generates an increasing sequence of values, and stores them in the input Range. -/// -/// \param out An output iterator to write the results into -/// \param value The initial value of the sequence to be generated -/// \param n The number of items to write -/// -template <typename OutputIterator, typename T> -OutputIterator iota_n ( OutputIterator out, T value, std::size_t n ) -{ - for ( ; n > 0; --n, ++value ) - *out++ = value; - - return out; -} - -}} - -#endif // BOOST_ALGORITHM_IOTA_HPP diff --git a/contrib/restricted/boost/boost/algorithm/cxx11/is_partitioned.hpp b/contrib/restricted/boost/boost/algorithm/cxx11/is_partitioned.hpp deleted file mode 100644 index c0076b932b..0000000000 --- a/contrib/restricted/boost/boost/algorithm/cxx11/is_partitioned.hpp +++ /dev/null @@ -1,58 +0,0 @@ -/* - Copyright (c) Marshall Clow 2011-2012. - - 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) -*/ - -/// \file is_partitioned.hpp -/// \brief Tell if a sequence is partitioned -/// \author Marshall Clow - -#ifndef BOOST_ALGORITHM_IS_PARTITIONED_HPP -#define BOOST_ALGORITHM_IS_PARTITIONED_HPP - -#include <boost/range/begin.hpp> -#include <boost/range/end.hpp> - -namespace boost { namespace algorithm { - -/// \fn is_partitioned ( InputIterator first, InputIterator last, UnaryPredicate p ) -/// \brief Tests to see if a sequence is partitioned according to a predicate. -/// In other words, all the items in the sequence that satisfy the predicate are at the beginning of the sequence. -/// -/// \param first The start of the input sequence -/// \param last One past the end of the input sequence -/// \param p The predicate to test the values with -/// \note This function is part of the C++2011 standard library. -template <typename InputIterator, typename UnaryPredicate> -bool is_partitioned ( InputIterator first, InputIterator last, UnaryPredicate p ) -{ -// Run through the part that satisfy the predicate - for ( ; first != last; ++first ) - if ( !p (*first)) - break; -// Now the part that does not satisfy the predicate - for ( ; first != last; ++first ) - if ( p (*first)) - return false; - return true; -} - -/// \fn is_partitioned ( const Range &r, UnaryPredicate p ) -/// \brief Tests to see if a sequence is partitioned according to a predicate. -/// In other words, all the items in the sequence that satisfy the predicate are at the beginning of the sequence. -/// -/// \param r The input range -/// \param p The predicate to test the values with -/// -template <typename Range, typename UnaryPredicate> -bool is_partitioned ( const Range &r, UnaryPredicate p ) -{ - return boost::algorithm::is_partitioned (boost::begin(r), boost::end(r), p); -} - - -}} - -#endif // BOOST_ALGORITHM_IS_PARTITIONED_HPP diff --git a/contrib/restricted/boost/boost/algorithm/cxx11/is_permutation.hpp b/contrib/restricted/boost/boost/algorithm/cxx11/is_permutation.hpp deleted file mode 100644 index 0098cd53fe..0000000000 --- a/contrib/restricted/boost/boost/algorithm/cxx11/is_permutation.hpp +++ /dev/null @@ -1,185 +0,0 @@ -/* - Copyright (c) Marshall Clow 2011-2012. - - 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) -*/ - -/// \file is_permutation.hpp -/// \brief Is a sequence a permutation of another sequence -/// \author Marshall Clow - -#ifndef BOOST_ALGORITHM_IS_PERMUTATION11_HPP -#define BOOST_ALGORITHM_IS_PERMUTATION11_HPP - -#include <algorithm> // for std::find_if, count_if, mismatch -#include <utility> // for std::pair -#include <functional> // for std::equal_to -#include <iterator> - -#include <boost/range/begin.hpp> -#include <boost/range/end.hpp> -#include <boost/utility/enable_if.hpp> -#include <boost/type_traits/is_same.hpp> - -namespace boost { namespace algorithm { - -/// \cond DOXYGEN_HIDE -namespace detail { - template <typename Predicate, typename Iterator> - struct value_predicate { - value_predicate ( Predicate p, Iterator it ) : p_ ( p ), it_ ( it ) {} - - template <typename T1> - bool operator () ( const T1 &t1 ) const { return p_ ( *it_, t1 ); } - private: - 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 - -/// \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 -/// -/// \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 -/// -/// \note This function is part of the C++2011 standard library. -template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate > -bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1, - ForwardIterator2 first2, BinaryPredicate p ) -{ -// Skip the common prefix (if any) - std::pair<ForwardIterator1, ForwardIterator2> eq = std::mismatch (first1, last1, first2, p); - 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, p ); - } - - return true; -} - -/// \fn is_permutation ( ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 first2 ) -/// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2 -/// -/// \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. -template< class ForwardIterator1, class ForwardIterator2 > -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? -// 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; -} - - -/// \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 -/// -/// \param r The input range -/// \param first2 The start of the second sequence -template <typename Range, typename ForwardIterator> -bool is_permutation ( const Range &r, ForwardIterator first2 ) -{ - return boost::algorithm::is_permutation (boost::begin (r), boost::end (r), first2 ); -} - -/// \fn is_permutation ( const Range &r, ForwardIterator first2, BinaryPredicate pred ) -/// \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 -/// \param pred The predicate to compare elements with -/// -// Disable this template when the first two parameters are the same type -// That way the non-range version will be chosen. -template <typename Range, typename ForwardIterator, typename BinaryPredicate> -typename boost::disable_if_c<boost::is_same<Range, ForwardIterator>::value, bool>::type -is_permutation ( const Range &r, ForwardIterator first2, BinaryPredicate pred ) -{ - return boost::algorithm::is_permutation (boost::begin (r), boost::end (r), first2, pred ); -} - -}} - -#endif // BOOST_ALGORITHM_IS_PERMUTATION11_HPP diff --git a/contrib/restricted/boost/boost/algorithm/cxx11/is_sorted.hpp b/contrib/restricted/boost/boost/algorithm/cxx11/is_sorted.hpp deleted file mode 100644 index f4dbb38c08..0000000000 --- a/contrib/restricted/boost/boost/algorithm/cxx11/is_sorted.hpp +++ /dev/null @@ -1,280 +0,0 @@ -// Copyright (c) 2010 Nuovation System Designs, LLC -// Grant Erickson <gerickson@nuovations.com> -// -// Reworked somewhat by Marshall Clow; August 2010 -// -// 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) -// -// See http://www.boost.org/ for latest version. -// - -#ifndef BOOST_ALGORITHM_ORDERED_HPP -#define BOOST_ALGORITHM_ORDERED_HPP - -#include <functional> -#include <iterator> - -#include <boost/range/begin.hpp> -#include <boost/range/end.hpp> - -#include <boost/utility/enable_if.hpp> -#include <boost/type_traits/is_same.hpp> -#include <boost/mpl/identity.hpp> - -namespace boost { namespace algorithm { - -/// \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'). -/// -/// \param first The start of the sequence to be tested. -/// \param last One past the end of the sequence -/// \param p A binary predicate that returns true if two elements are ordered. -/// - template <typename ForwardIterator, typename Pred> - ForwardIterator is_sorted_until ( ForwardIterator first, ForwardIterator last, Pred p ) - { - if ( first == last ) return last; // the empty sequence is ordered - ForwardIterator next = first; - while ( ++next != last ) - { - if ( p ( *next, *first )) - return next; - first = next; - } - return last; - } - -/// \fn is_sorted_until ( ForwardIterator first, ForwardIterator last ) -/// \return the point in the sequence [first, last) where the elements are unordered -/// -/// \param first The start of the sequence to be tested. -/// \param last One past the end of the sequence -/// - template <typename ForwardIterator> - ForwardIterator is_sorted_until ( ForwardIterator first, ForwardIterator last ) - { - typedef typename std::iterator_traits<ForwardIterator>::value_type value_type; - return boost::algorithm::is_sorted_until ( first, last, std::less<value_type>()); - } - - -/// \fn is_sorted ( ForwardIterator first, ForwardIterator last, Pred p ) -/// \return whether or not the entire sequence is sorted -/// -/// \param first The start of the sequence to be tested. -/// \param last One past the end of the sequence -/// \param p A binary predicate that returns true if two elements are ordered. -/// - template <typename ForwardIterator, typename Pred> - bool is_sorted ( ForwardIterator first, ForwardIterator last, Pred p ) - { - return boost::algorithm::is_sorted_until (first, last, p) == last; - } - -/// \fn is_sorted ( ForwardIterator first, ForwardIterator last ) -/// \return whether or not the entire sequence is sorted -/// -/// \param first The start of the sequence to be tested. -/// \param last One past the end of the sequence -/// - template <typename ForwardIterator> - bool is_sorted ( ForwardIterator first, ForwardIterator last ) - { - return boost::algorithm::is_sorted_until (first, last) == last; - } - -/// -/// -- Range based versions of the C++11 functions -/// - -/// \fn is_sorted_until ( const R &range, Pred p ) -/// \return the point in the range R where the elements are unordered -/// (according to the comparison predicate 'p'). -/// -/// \param range The range to be tested. -/// \param p A binary predicate that returns true if two elements are ordered. -/// - template <typename R, typename Pred> - typename boost::lazy_disable_if_c< - boost::is_same<R, Pred>::value, - typename boost::range_iterator<const R> - >::type is_sorted_until ( const R &range, Pred p ) - { - return boost::algorithm::is_sorted_until ( boost::begin ( range ), boost::end ( range ), p ); - } - - -/// \fn is_sorted_until ( const R &range ) -/// \return the point in the range R where the elements are unordered -/// -/// \param range The range to be tested. -/// - template <typename R> - typename boost::range_iterator<const R>::type is_sorted_until ( const R &range ) - { - return boost::algorithm::is_sorted_until ( boost::begin ( range ), boost::end ( range )); - } - -/// \fn is_sorted ( const R &range, Pred p ) -/// \return whether or not the entire range R is sorted -/// (according to the comparison predicate 'p'). -/// -/// \param range The range to be tested. -/// \param p A binary predicate that returns true if two elements are ordered. -/// - template <typename R, typename Pred> - typename boost::lazy_disable_if_c< boost::is_same<R, Pred>::value, boost::mpl::identity<bool> >::type - is_sorted ( const R &range, Pred p ) - { - return boost::algorithm::is_sorted ( boost::begin ( range ), boost::end ( range ), p ); - } - - -/// \fn is_sorted ( const R &range ) -/// \return whether or not the entire range R is sorted -/// -/// \param range The range to be tested. -/// - template <typename R> - bool is_sorted ( const R &range ) - { - return boost::algorithm::is_sorted ( boost::begin ( range ), boost::end ( range )); - } - - -/// -/// -- Range based versions of the C++11 functions -/// - -/// \fn is_increasing ( ForwardIterator first, ForwardIterator last ) -/// \return true if the entire sequence is increasing; i.e, each item is greater than or -/// equal to the previous one. -/// -/// \param first The start of the sequence to be tested. -/// \param last One past the end of the sequence -/// -/// \note This function will return true for sequences that contain items that compare -/// equal. If that is not what you intended, you should use is_strictly_increasing instead. - template <typename ForwardIterator> - bool is_increasing ( ForwardIterator first, ForwardIterator last ) - { - typedef typename std::iterator_traits<ForwardIterator>::value_type value_type; - return boost::algorithm::is_sorted (first, last, std::less<value_type>()); - } - - -/// \fn is_increasing ( const R &range ) -/// \return true if the entire sequence is increasing; i.e, each item is greater than or -/// equal to the previous one. -/// -/// \param range The range to be tested. -/// -/// \note This function will return true for sequences that contain items that compare -/// equal. If that is not what you intended, you should use is_strictly_increasing instead. - template <typename R> - bool is_increasing ( const R &range ) - { - return is_increasing ( boost::begin ( range ), boost::end ( range )); - } - - - -/// \fn is_decreasing ( ForwardIterator first, ForwardIterator last ) -/// \return true if the entire sequence is decreasing; i.e, each item is less than -/// or equal to the previous one. -/// -/// \param first The start of the sequence to be tested. -/// \param last One past the end of the sequence -/// -/// \note This function will return true for sequences that contain items that compare -/// equal. If that is not what you intended, you should use is_strictly_decreasing instead. - template <typename ForwardIterator> - bool is_decreasing ( ForwardIterator first, ForwardIterator last ) - { - typedef typename std::iterator_traits<ForwardIterator>::value_type value_type; - return boost::algorithm::is_sorted (first, last, std::greater<value_type>()); - } - -/// \fn is_decreasing ( const R &range ) -/// \return true if the entire sequence is decreasing; i.e, each item is less than -/// or equal to the previous one. -/// -/// \param range The range to be tested. -/// -/// \note This function will return true for sequences that contain items that compare -/// equal. If that is not what you intended, you should use is_strictly_decreasing instead. - template <typename R> - bool is_decreasing ( const R &range ) - { - return is_decreasing ( boost::begin ( range ), boost::end ( range )); - } - - - -/// \fn is_strictly_increasing ( ForwardIterator first, ForwardIterator last ) -/// \return true if the entire sequence is strictly increasing; i.e, each item is greater -/// than the previous one -/// -/// \param first The start of the sequence to be tested. -/// \param last One past the end of the sequence -/// -/// \note This function will return false for sequences that contain items that compare -/// equal. If that is not what you intended, you should use is_increasing instead. - template <typename ForwardIterator> - bool is_strictly_increasing ( ForwardIterator first, ForwardIterator last ) - { - typedef typename std::iterator_traits<ForwardIterator>::value_type value_type; - return boost::algorithm::is_sorted (first, last, std::less_equal<value_type>()); - } - -/// \fn is_strictly_increasing ( const R &range ) -/// \return true if the entire sequence is strictly increasing; i.e, each item is greater -/// than the previous one -/// -/// \param range The range to be tested. -/// -/// \note This function will return false for sequences that contain items that compare -/// equal. If that is not what you intended, you should use is_increasing instead. - template <typename R> - bool is_strictly_increasing ( const R &range ) - { - return is_strictly_increasing ( boost::begin ( range ), boost::end ( range )); - } - - -/// \fn is_strictly_decreasing ( ForwardIterator first, ForwardIterator last ) -/// \return true if the entire sequence is strictly decreasing; i.e, each item is less than -/// the previous one -/// -/// \param first The start of the sequence to be tested. -/// \param last One past the end of the sequence -/// -/// \note This function will return false for sequences that contain items that compare -/// equal. If that is not what you intended, you should use is_decreasing instead. - template <typename ForwardIterator> - bool is_strictly_decreasing ( ForwardIterator first, ForwardIterator last ) - { - typedef typename std::iterator_traits<ForwardIterator>::value_type value_type; - return boost::algorithm::is_sorted (first, last, std::greater_equal<value_type>()); - } - -/// \fn is_strictly_decreasing ( const R &range ) -/// \return true if the entire sequence is strictly decreasing; i.e, each item is less than -/// the previous one -/// -/// \param range The range to be tested. -/// -/// \note This function will return false for sequences that contain items that compare -/// equal. If that is not what you intended, you should use is_decreasing instead. - template <typename R> - bool is_strictly_decreasing ( const R &range ) - { - return is_strictly_decreasing ( boost::begin ( range ), boost::end ( range )); - } - -}} // namespace boost - -#endif // BOOST_ALGORITHM_ORDERED_HPP diff --git a/contrib/restricted/boost/boost/algorithm/cxx11/none_of.hpp b/contrib/restricted/boost/boost/algorithm/cxx11/none_of.hpp deleted file mode 100644 index ba13144fb8..0000000000 --- a/contrib/restricted/boost/boost/algorithm/cxx11/none_of.hpp +++ /dev/null @@ -1,82 +0,0 @@ -/* - Copyright (c) Marshall Clow 2008-2012. - - 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) -*/ - -/// \file none_of.hpp -/// \brief Test ranges to see if no elements match a value or predicate. -/// \author Marshall Clow - -#ifndef BOOST_ALGORITHM_NONE_OF_HPP -#define BOOST_ALGORITHM_NONE_OF_HPP - -#include <boost/range/begin.hpp> -#include <boost/range/end.hpp> - -namespace boost { namespace algorithm { - -/// \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 -/// -/// \param first The start of the input sequence -/// \param last One past the end of the input sequence -/// \param p A predicate for testing the elements of the sequence -/// -template<typename InputIterator, typename Predicate> -bool none_of ( InputIterator first, InputIterator last, Predicate p ) -{ - for ( ; first != last; ++first ) - if ( p(*first)) - return false; - return true; -} - -/// \fn none_of ( const Range &r, Predicate p ) -/// \return true if none of the elements in the range satisfy the predicate 'p' -/// \note returns true on an empty range -/// -/// \param r The input range -/// \param p A predicate for testing the elements of the range -/// -template<typename Range, typename Predicate> -bool none_of ( const Range &r, Predicate p ) -{ - return boost::algorithm::none_of (boost::begin (r), boost::end (r), p ); -} - -/// \fn none_of_equal ( InputIterator first, InputIterator last, const V &val ) -/// \return true if none of the elements in [first, last) are equal to 'val' -/// \note returns true on an empty range -/// -/// \param first The start of the input sequence -/// \param last One past the end of the input sequence -/// \param val A value to compare against -/// -template<typename InputIterator, typename V> -bool none_of_equal ( InputIterator first, InputIterator last, const V &val ) -{ - for ( ; first != last; ++first ) - if ( val == *first ) - return false; - return true; -} - -/// \fn none_of_equal ( const Range &r, const V &val ) -/// \return true if none of the elements in the range are equal to 'val' -/// \note returns true on an empty range -/// -/// \param r The input range -/// \param val A value to compare against -/// -template<typename Range, typename V> -bool none_of_equal ( const Range &r, const V & val ) -{ - return boost::algorithm::none_of_equal (boost::begin (r), boost::end (r), val); -} - -}} // namespace boost and algorithm - -#endif // BOOST_ALGORITHM_NONE_OF_HPP diff --git a/contrib/restricted/boost/boost/algorithm/cxx11/one_of.hpp b/contrib/restricted/boost/boost/algorithm/cxx11/one_of.hpp deleted file mode 100644 index b6e8c77194..0000000000 --- a/contrib/restricted/boost/boost/algorithm/cxx11/one_of.hpp +++ /dev/null @@ -1,82 +0,0 @@ -/* - Copyright (c) Marshall Clow 2008-2012. - - 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) -*/ - -/// \file one_of.hpp -/// \brief Test ranges to see if only one element matches a value or predicate. -/// \author Marshall Clow - -#ifndef BOOST_ALGORITHM_ONE_OF_HPP -#define BOOST_ALGORITHM_ONE_OF_HPP - -#include <algorithm> // for std::find and std::find_if -#include <boost/algorithm/cxx11/none_of.hpp> - -#include <boost/range/begin.hpp> -#include <boost/range/end.hpp> - -namespace boost { namespace algorithm { - -/// \fn one_of ( InputIterator first, InputIterator last, Predicate p ) -/// \return true if the predicate 'p' is true for exactly one item in [first, last). -/// -/// \param first The start of the input sequence -/// \param last One past the end of the input sequence -/// \param p A predicate for testing the elements of the sequence -/// -template<typename InputIterator, typename Predicate> -bool one_of ( InputIterator first, InputIterator last, Predicate p ) -{ - InputIterator i = std::find_if (first, last, p); - if (i == last) - return false; // Didn't occur at all - return boost::algorithm::none_of (++i, last, p); -} - -/// \fn one_of ( const Range &r, Predicate p ) -/// \return true if the predicate 'p' is true for exactly one item in the range. -/// -/// \param r The input range -/// \param p A predicate for testing the elements of the range -/// -template<typename Range, typename Predicate> -bool one_of ( const Range &r, Predicate p ) -{ - return boost::algorithm::one_of ( boost::begin (r), boost::end (r), p ); -} - - -/// \fn one_of_equal ( InputIterator first, InputIterator last, const V &val ) -/// \return true if the value 'val' exists only once in [first, last). -/// -/// \param first The start of the input sequence -/// \param last One past the end of the input sequence -/// \param val A value to compare against -/// -template<typename InputIterator, typename V> -bool one_of_equal ( InputIterator first, InputIterator last, const V &val ) -{ - InputIterator i = std::find (first, last, val); // find first occurrence of 'val' - if (i == last) - return false; // Didn't occur at all - return boost::algorithm::none_of_equal (++i, last, val); -} - -/// \fn one_of_equal ( const Range &r, const V &val ) -/// \return true if the value 'val' exists only once in the range. -/// -/// \param r The input range -/// \param val A value to compare against -/// -template<typename Range, typename V> -bool one_of_equal ( const Range &r, const V &val ) -{ - return boost::algorithm::one_of_equal ( boost::begin (r), boost::end (r), val ); -} - -}} // namespace boost and algorithm - -#endif // BOOST_ALGORITHM_ALL_HPP diff --git a/contrib/restricted/boost/boost/algorithm/cxx11/partition_copy.hpp b/contrib/restricted/boost/boost/algorithm/cxx11/partition_copy.hpp deleted file mode 100644 index f347f2128f..0000000000 --- a/contrib/restricted/boost/boost/algorithm/cxx11/partition_copy.hpp +++ /dev/null @@ -1,70 +0,0 @@ -/* - Copyright (c) Marshall Clow 2011-2012. - - 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) -*/ - -/// \file partition_copy.hpp -/// \brief Copy a subset of a sequence to a new sequence -/// \author Marshall Clow - -#ifndef BOOST_ALGORITHM_PARTITION_COPY_HPP -#define BOOST_ALGORITHM_PARTITION_COPY_HPP - -#include <utility> // for std::pair - -#include <boost/range/begin.hpp> -#include <boost/range/end.hpp> - -namespace boost { namespace algorithm { - -/// \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) -/// to the range beginning at d_first_true, and -/// copies the elements that do not satisfy p to the range beginning at d_first_false. -/// -/// -/// \param first The start of the input sequence -/// \param last One past the end of the input sequence -/// \param out_true An output iterator to write the elements that satisfy the predicate into -/// \param out_false An output iterator to write the elements that do not satisfy the predicate into -/// \param p A predicate for dividing the elements of the input sequence. -/// -/// \note This function is part of the C++2011 standard library. -template <typename InputIterator, - typename OutputIterator1, typename OutputIterator2, typename UnaryPredicate> -std::pair<OutputIterator1, OutputIterator2> -partition_copy ( InputIterator first, InputIterator last, - OutputIterator1 out_true, OutputIterator2 out_false, UnaryPredicate p ) -{ - for ( ; first != last; ++first ) - if ( p (*first)) - *out_true++ = *first; - else - *out_false++ = *first; - return std::pair<OutputIterator1, OutputIterator2> ( out_true, out_false ); -} - -/// \fn partition_copy ( const Range &r, -/// OutputIterator1 out_true, OutputIterator2 out_false, UnaryPredicate p ) -/// -/// \param r The input range -/// \param out_true An output iterator to write the elements that satisfy the predicate into -/// \param out_false An output iterator to write the elements that do not satisfy the predicate into -/// \param p A predicate for dividing the elements of the input sequence. -/// -template <typename Range, typename OutputIterator1, typename OutputIterator2, - typename UnaryPredicate> -std::pair<OutputIterator1, OutputIterator2> -partition_copy ( const Range &r, OutputIterator1 out_true, OutputIterator2 out_false, - UnaryPredicate p ) -{ - return boost::algorithm::partition_copy - (boost::begin(r), boost::end(r), out_true, out_false, p ); -} - -}} // namespace boost and algorithm - -#endif // BOOST_ALGORITHM_PARTITION_COPY_HPP diff --git a/contrib/restricted/boost/boost/algorithm/cxx11/partition_point.hpp b/contrib/restricted/boost/boost/algorithm/cxx11/partition_point.hpp deleted file mode 100644 index 2c2767ae5a..0000000000 --- a/contrib/restricted/boost/boost/algorithm/cxx11/partition_point.hpp +++ /dev/null @@ -1,65 +0,0 @@ -/* - Copyright (c) Marshall Clow 2011-2012. - - 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) -*/ - -/// \file partition_point.hpp -/// \brief Find the partition point in a sequence -/// \author Marshall Clow - -#ifndef BOOST_ALGORITHM_PARTITION_POINT_HPP -#define BOOST_ALGORITHM_PARTITION_POINT_HPP - -#include <iterator> // for std::distance, advance - -#include <boost/range/begin.hpp> -#include <boost/range/end.hpp> - -namespace boost { namespace algorithm { - -/// \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 -/// -/// \param first The start of the input sequence -/// \param last One past the end of the input sequence -/// \param p The predicate to test the values with -/// \note This function is part of the C++2011 standard library. -template <typename ForwardIterator, typename Predicate> -ForwardIterator partition_point ( ForwardIterator first, ForwardIterator last, Predicate p ) -{ - std::size_t dist = std::distance ( first, last ); - while ( first != last ) { - std::size_t d2 = dist / 2; - ForwardIterator ret_val = first; - std::advance (ret_val, d2); - if (p (*ret_val)) { - first = ++ret_val; - dist -= d2 + 1; - } - else { - last = ret_val; - dist = d2; - } - } - return first; -} - -/// \fn partition_point ( Range &r, Predicate p ) -/// \brief Given a partitioned range, returns the partition point -/// -/// \param r The input range -/// \param p The predicate to test the values with -/// -template <typename Range, typename Predicate> -typename boost::range_iterator<Range>::type partition_point ( Range &r, Predicate p ) -{ - return boost::algorithm::partition_point (boost::begin(r), boost::end(r), p); -} - - -}} - -#endif // BOOST_ALGORITHM_PARTITION_POINT_HPP diff --git a/contrib/restricted/boost/boost/algorithm/cxx14/equal.hpp b/contrib/restricted/boost/boost/algorithm/cxx14/equal.hpp deleted file mode 100644 index 9f97be1d62..0000000000 --- a/contrib/restricted/boost/boost/algorithm/cxx14/equal.hpp +++ /dev/null @@ -1,97 +0,0 @@ -/* - Copyright (c) Marshall Clow 2008-2012. - - 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) -*/ - -/// \file equal.hpp -/// \brief Test ranges to if they are equal -/// \author Marshall Clow - -#ifndef BOOST_ALGORITHM_EQUAL_HPP -#define BOOST_ALGORITHM_EQUAL_HPP - -#include <algorithm> // for std::equal -#include <iterator> - -namespace boost { namespace algorithm { - -namespace detail { - - template <class T1, class T2> - struct eq { - bool operator () ( const T1& v1, const T2& v2 ) const { return v1 == v2 ;} - }; - - template <class RandomAccessIterator1, class RandomAccessIterator2, class BinaryPredicate> - bool equal ( RandomAccessIterator1 first1, RandomAccessIterator1 last1, - RandomAccessIterator2 first2, RandomAccessIterator2 last2, BinaryPredicate pred, - std::random_access_iterator_tag, std::random_access_iterator_tag ) - { - // Random-access iterators let is check the sizes in constant time - if ( std::distance ( first1, last1 ) != std::distance ( first2, last2 )) - return false; - // If we know that the sequences are the same size, the original version is fine - return std::equal ( first1, last1, first2, pred ); - } - - template <class InputIterator1, class InputIterator2, class BinaryPredicate> - bool equal ( InputIterator1 first1, InputIterator1 last1, - InputIterator2 first2, InputIterator2 last2, BinaryPredicate pred, - std::input_iterator_tag, std::input_iterator_tag ) - { - for (; first1 != last1 && first2 != last2; ++first1, ++first2 ) - if ( !pred(*first1, *first2 )) - return false; - - return first1 == last1 && first2 == last2; - } -} - -/// \fn equal ( InputIterator1 first1, InputIterator1 last1, -/// InputIterator2 first2, InputIterator2 last2, -/// BinaryPredicate pred ) -/// \return true if all elements in the two ranges are equal -/// -/// \param first1 The start of the first range. -/// \param last1 One past the end of the first range. -/// \param first2 The start of the second range. -/// \param last2 One past the end of the second range. -/// \param pred A predicate for comparing the elements of the ranges -template <class InputIterator1, class InputIterator2, class BinaryPredicate> -bool equal ( InputIterator1 first1, InputIterator1 last1, - InputIterator2 first2, InputIterator2 last2, BinaryPredicate pred ) -{ - return boost::algorithm::detail::equal ( - first1, last1, first2, last2, pred, - typename std::iterator_traits<InputIterator1>::iterator_category (), - typename std::iterator_traits<InputIterator2>::iterator_category ()); -} - -/// \fn equal ( InputIterator1 first1, InputIterator1 last1, -/// InputIterator2 first2, InputIterator2 last2 ) -/// \return true if all elements in the two ranges are equal -/// -/// \param first1 The start of the first range. -/// \param last1 One past the end of the first range. -/// \param first2 The start of the second range. -/// \param last2 One past the end of the second range. -template <class InputIterator1, class InputIterator2> -bool equal ( InputIterator1 first1, InputIterator1 last1, - InputIterator2 first2, InputIterator2 last2 ) -{ - return boost::algorithm::detail::equal ( - first1, last1, first2, last2, - boost::algorithm::detail::eq< - typename std::iterator_traits<InputIterator1>::value_type, - typename std::iterator_traits<InputIterator2>::value_type> (), - typename std::iterator_traits<InputIterator1>::iterator_category (), - typename std::iterator_traits<InputIterator2>::iterator_category ()); -} - -// There are already range-based versions of these. - -}} // namespace boost and algorithm - -#endif // BOOST_ALGORITHM_EQUAL_HPP diff --git a/contrib/restricted/boost/boost/algorithm/cxx14/is_permutation.hpp b/contrib/restricted/boost/boost/algorithm/cxx14/is_permutation.hpp deleted file mode 100644 index 639446bf37..0000000000 --- a/contrib/restricted/boost/boost/algorithm/cxx14/is_permutation.hpp +++ /dev/null @@ -1,79 +0,0 @@ -/* - 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) -*/ - -/// \file is_permutation.hpp -/// \brief Is a sequence a permutation of another sequence (four iterator versions) -/// \author Marshall Clow - -#ifndef BOOST_ALGORITHM_IS_PERMUTATION14_HPP -#define BOOST_ALGORITHM_IS_PERMUTATION14_HPP - -#include <utility> // for std::pair -#include <functional> // for std::equal_to -#include <iterator> - -#include <boost/algorithm/cxx11/is_permutation.hpp> -#include <boost/algorithm/cxx14/mismatch.hpp> - -namespace boost { namespace algorithm { - -/// \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 -/// -/// \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 -/// \param last1 One past the end of the second sequence -/// \note This function is part of the C++2014 standard library. -template< class ForwardIterator1, class ForwardIterator2 > -bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1, - ForwardIterator2 first2, ForwardIterator2 last2 ) -{ -// 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; - return boost::algorithm::detail::is_permutation_tag ( - eq.first, last1, eq.second, last2, - std::equal_to<typename std::iterator_traits<ForwardIterator1>::value_type> (), - typename std::iterator_traits<ForwardIterator1>::iterator_category (), - typename std::iterator_traits<ForwardIterator2>::iterator_category ()); -} - -/// \fn is_permutation ( ForwardIterator1 first, ForwardIterator1 last, -/// ForwardIterator2 first2, ForwardIterator2 last2, -/// BinaryPredicate p ) -/// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2 -/// -/// \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 last2 One past the end of the second sequence -/// \param pred The predicate to compare elements with -/// -/// \note This function is part of the C++2014 standard library. -template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate > -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; - 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 // BOOST_ALGORITHM_IS_PERMUTATION14_HPP diff --git a/contrib/restricted/boost/boost/algorithm/cxx14/mismatch.hpp b/contrib/restricted/boost/boost/algorithm/cxx14/mismatch.hpp deleted file mode 100644 index c3de418222..0000000000 --- a/contrib/restricted/boost/boost/algorithm/cxx14/mismatch.hpp +++ /dev/null @@ -1,64 +0,0 @@ -/* - Copyright (c) Marshall Clow 2008-2012. - - Distributed under the Boost Software License, Version 1.0. (See accompanying - file LICENSE10.txt or copy at http://www.boost.org/LICENSE10.txt) -*/ - -/// \file mismatch.hpp -/// \brief Find the first mismatched element in a sequence -/// \author Marshall Clow - -#ifndef BOOST_ALGORITHM_MISMATCH_HPP -#define BOOST_ALGORITHM_MISMATCH_HPP - -#include <utility> // for std::pair - -namespace boost { namespace algorithm { - -/// \fn mismatch ( InputIterator1 first1, InputIterator1 last1, -/// InputIterator2 first2, InputIterator2 last2, -/// BinaryPredicate pred ) -/// \return a pair of iterators pointing to the first elements in the sequence that do not match -/// -/// \param first1 The start of the first range. -/// \param last1 One past the end of the first range. -/// \param first2 The start of the second range. -/// \param last2 One past the end of the second range. -/// \param pred A predicate for comparing the elements of the ranges -template <class InputIterator1, class InputIterator2, class BinaryPredicate> -std::pair<InputIterator1, InputIterator2> mismatch ( - InputIterator1 first1, InputIterator1 last1, - InputIterator2 first2, InputIterator2 last2, - BinaryPredicate pred ) -{ - for (; first1 != last1 && first2 != last2; ++first1, ++first2) - if ( !pred ( *first1, *first2 )) - break; - return std::pair<InputIterator1, InputIterator2>(first1, first2); -} - -/// \fn mismatch ( InputIterator1 first1, InputIterator1 last1, -/// InputIterator2 first2, InputIterator2 last2 ) -/// \return a pair of iterators pointing to the first elements in the sequence that do not match -/// -/// \param first1 The start of the first range. -/// \param last1 One past the end of the first range. -/// \param first2 The start of the second range. -/// \param last2 One past the end of the second range. -template <class InputIterator1, class InputIterator2> -std::pair<InputIterator1, InputIterator2> mismatch ( - InputIterator1 first1, InputIterator1 last1, - InputIterator2 first2, InputIterator2 last2 ) -{ - for (; first1 != last1 && first2 != last2; ++first1, ++first2) - if ( *first1 != *first2 ) - break; - return std::pair<InputIterator1, InputIterator2>(first1, first2); -} - -// There are already range-based versions of these. - -}} // namespace boost and algorithm - -#endif // BOOST_ALGORITHM_MISMATCH_HPP diff --git a/contrib/restricted/boost/boost/algorithm/cxx17/exclusive_scan.hpp b/contrib/restricted/boost/boost/algorithm/cxx17/exclusive_scan.hpp deleted file mode 100644 index 03ecea52ec..0000000000 --- a/contrib/restricted/boost/boost/algorithm/cxx17/exclusive_scan.hpp +++ /dev/null @@ -1,52 +0,0 @@ -/* - Copyright (c) Marshall Clow 2017. - - Distributed under the Boost Software License, Version 1.0. (See accompanying - file LICENSE10.txt or copy at http://www.boost.org/LICENSE10.txt) -*/ - -/// \file exclusive_scan.hpp -/// \brief ??? -/// \author Marshall Clow - -#ifndef BOOST_ALGORITHM_EXCLUSIVE_SCAN_HPP -#define BOOST_ALGORITHM_EXCLUSIVE_SCAN_HPP - -#include <functional> // for std::plus -#include <iterator> // for std::iterator_traits - -#include <boost/range/begin.hpp> -#include <boost/range/end.hpp> -#include <boost/range/value_type.hpp> - -namespace boost { namespace algorithm { - -template<class InputIterator, class OutputIterator, class T, class BinaryOperation> -OutputIterator exclusive_scan(InputIterator first, InputIterator last, - OutputIterator result, T init, BinaryOperation bOp) -{ - if (first != last) - { - T saved = init; - do - { - init = bOp(init, *first); - *result = saved; - saved = init; - ++result; - } while (++first != last); - } - return result; -} - -template<class InputIterator, class OutputIterator, class T> -OutputIterator exclusive_scan(InputIterator first, InputIterator last, - OutputIterator result, T init) -{ - typedef typename std::iterator_traits<InputIterator>::value_type VT; - return exclusive_scan(first, last, result, init, std::plus<VT>()); -} - -}} // namespace boost and algorithm - -#endif // BOOST_ALGORITHM_EXCLUSIVE_SCAN_HPP diff --git a/contrib/restricted/boost/boost/algorithm/cxx17/for_each_n.hpp b/contrib/restricted/boost/boost/algorithm/cxx17/for_each_n.hpp deleted file mode 100644 index b8134cc06a..0000000000 --- a/contrib/restricted/boost/boost/algorithm/cxx17/for_each_n.hpp +++ /dev/null @@ -1,37 +0,0 @@ -/* - Copyright (c) Marshall Clow 2017. - - Distributed under the Boost Software License, Version 1.0. (See accompanying - file LICENSE10.txt or copy at http://www.boost.org/LICENSE10.txt) -*/ - -/// \file for_each_n.hpp -/// \brief Apply a functor to the elements of a sequence -/// \author Marshall Clow - -#ifndef BOOST_ALGORITHM_FOR_EACH_N_HPP -#define BOOST_ALGORITHM_FOR_EACH_N_HPP - -#include <utility> // for std::pair - -namespace boost { namespace algorithm { - -/// \fn for_each_n(InputIterator first, Size n, Function f); -/// \return first + n -/// -/// \param first The start of the first range. -/// \param n One past the end of the first range. -/// \param f A functor to apply to the elements of the sequence -/// \note If f returns a result, the result is ignored. -template<class InputIterator, class Size, class Function> -InputIterator for_each_n(InputIterator first, Size n, Function f) -{ - for ( ; n > 0; --n, ++first ) - f(*first); - - return first; -} - -}} // namespace boost and algorithm - -#endif // BOOST_ALGORITHM_FOR_EACH_N_HPP diff --git a/contrib/restricted/boost/boost/algorithm/cxx17/inclusive_scan.hpp b/contrib/restricted/boost/boost/algorithm/cxx17/inclusive_scan.hpp deleted file mode 100644 index cd015f100f..0000000000 --- a/contrib/restricted/boost/boost/algorithm/cxx17/inclusive_scan.hpp +++ /dev/null @@ -1,60 +0,0 @@ -/* - Copyright (c) Marshall Clow 2017. - - Distributed under the Boost Software License, Version 1.0. (See accompanying - file LICENSE10.txt or copy at http://www.boost.org/LICENSE10.txt) -*/ - -/// \file transform_reduce.hpp -/// \brief Combine the (transformed) elements of a sequence (or two) into a single value. -/// \author Marshall Clow - -#ifndef BOOST_ALGORITHM_TRANSFORM_REDUCE_HPP -#define BOOST_ALGORITHM_TRANSFORM_REDUCE_HPP - -#include <functional> // for std::plus -#include <iterator> // for std::iterator_traits - -#include <boost/range/begin.hpp> -#include <boost/range/end.hpp> -#include <boost/range/value_type.hpp> - -namespace boost { namespace algorithm { - -template<class InputIterator, class OutputIterator, class T, class BinaryOperation> -OutputIterator inclusive_scan(InputIterator first, InputIterator last, - OutputIterator result, BinaryOperation bOp, T init) -{ - for (; first != last; ++first, (void) ++result) { - init = bOp(init, *first); - *result = init; - } - return result; -} - - -template<class InputIterator, class OutputIterator, class BinaryOperation> -OutputIterator inclusive_scan(InputIterator first, InputIterator last, - OutputIterator result, BinaryOperation bOp) -{ - if (first != last) { - typename std::iterator_traits<InputIterator>::value_type init = *first; - *result++ = init; - if (++first != last) - return inclusive_scan(first, last, result, bOp, init); - } - - return result; -} - -template<class InputIterator, class OutputIterator> -OutputIterator inclusive_scan(InputIterator first, InputIterator last, - OutputIterator result) -{ - typedef typename std::iterator_traits<InputIterator>::value_type VT; - return inclusive_scan(first, last, result, std::plus<VT>()); -} - -}} // namespace boost and algorithm - -#endif // BOOST_ALGORITHM_TRANSFORM_REDUCE_HPP diff --git a/contrib/restricted/boost/boost/algorithm/cxx17/reduce.hpp b/contrib/restricted/boost/boost/algorithm/cxx17/reduce.hpp deleted file mode 100644 index f47695b53a..0000000000 --- a/contrib/restricted/boost/boost/algorithm/cxx17/reduce.hpp +++ /dev/null @@ -1,72 +0,0 @@ -/* - Copyright (c) Marshall Clow 2017. - - Distributed under the Boost Software License, Version 1.0. (See accompanying - file LICENSE10.txt or copy at http://www.boost.org/LICENSE10.txt) -*/ - -/// \file reduce.hpp -/// \brief Combine the elements of a sequence into a single value -/// \author Marshall Clow - -#ifndef BOOST_ALGORITHM_REDUCE_HPP -#define BOOST_ALGORITHM_REDUCE_HPP - -#include <functional> // for std::plus -#include <iterator> // for std::iterator_traits - -#include <boost/range/begin.hpp> -#include <boost/range/end.hpp> -#include <boost/range/value_type.hpp> - -namespace boost { namespace algorithm { - -template<class InputIterator, class T, class BinaryOperation> -T reduce(InputIterator first, InputIterator last, T init, BinaryOperation bOp) -{ - ; - for (; first != last; ++first) - init = bOp(init, *first); - return init; -} - -template<class InputIterator, class T> -T reduce(InputIterator first, InputIterator last, T init) -{ - typedef typename std::iterator_traits<InputIterator>::value_type VT; - return reduce(first, last, init, std::plus<VT>()); -} - -template<class InputIterator> -typename std::iterator_traits<InputIterator>::value_type -reduce(InputIterator first, InputIterator last) -{ - return reduce(first, last, - typename std::iterator_traits<InputIterator>::value_type()); -} - -template<class Range> -typename boost::range_value<Range>::type -reduce(const Range &r) -{ - return reduce(boost::begin(r), boost::end(r)); -} - -// Not sure that this won't be ambiguous (1) -template<class Range, class T> -T reduce(const Range &r, T init) -{ - return reduce(boost::begin (r), boost::end (r), init); -} - - -// Not sure that this won't be ambiguous (2) -template<class Range, class T, class BinaryOperation> -T reduce(const Range &r, T init, BinaryOperation bOp) -{ - return reduce(boost::begin(r), boost::end(r), init, bOp); -} - -}} // namespace boost and algorithm - -#endif // BOOST_ALGORITHM_REDUCE_HPP diff --git a/contrib/restricted/boost/boost/algorithm/cxx17/transform_exclusive_scan.hpp b/contrib/restricted/boost/boost/algorithm/cxx17/transform_exclusive_scan.hpp deleted file mode 100644 index d3b4329a0a..0000000000 --- a/contrib/restricted/boost/boost/algorithm/cxx17/transform_exclusive_scan.hpp +++ /dev/null @@ -1,46 +0,0 @@ -/* - Copyright (c) Marshall Clow 2017. - - Distributed under the Boost Software License, Version 1.0. (See accompanying - file LICENSE10.txt or copy at http://www.boost.org/LICENSE10.txt) -*/ - -/// \file transform_exclusive_scan.hpp -/// \brief ???? -/// \author Marshall Clow - -#ifndef BOOST_ALGORITHM_TRANSFORM_EXCLUSIVE_SCAN_HPP -#define BOOST_ALGORITHM_TRANSFORM_EXCLUSIVE_SCAN_HPP - -#include <functional> // for std::plus -#include <iterator> // for std::iterator_traits - -#include <boost/range/begin.hpp> -#include <boost/range/end.hpp> -#include <boost/range/value_type.hpp> - -namespace boost { namespace algorithm { - -template<class InputIterator, class OutputIterator, class T, - class BinaryOperation, class UnaryOperation> -OutputIterator transform_exclusive_scan(InputIterator first, InputIterator last, - OutputIterator result, T init, - BinaryOperation bOp, UnaryOperation uOp) -{ - if (first != last) - { - T saved = init; - do - { - init = bOp(init, uOp(*first)); - *result = saved; - saved = init; - ++result; - } while (++first != last); - } - return result; -} - -}} // namespace boost and algorithm - -#endif // BOOST_ALGORITHM_TRANSFORM_EXCLUSIVE_SCAN_HPP diff --git a/contrib/restricted/boost/boost/algorithm/cxx17/transform_inclusive_scan.hpp b/contrib/restricted/boost/boost/algorithm/cxx17/transform_inclusive_scan.hpp deleted file mode 100644 index 476c117f92..0000000000 --- a/contrib/restricted/boost/boost/algorithm/cxx17/transform_inclusive_scan.hpp +++ /dev/null @@ -1,58 +0,0 @@ -/* - Copyright (c) Marshall Clow 2017. - - Distributed under the Boost Software License, Version 1.0. (See accompanying - file LICENSE10.txt or copy at http://www.boost.org/LICENSE10.txt) -*/ - -/// \file transform_reduce.hpp -/// \brief Combine the (transformed) elements of a sequence (or two) into a single value. -/// \author Marshall Clow - -#ifndef BOOST_ALGORITHM_TRANSFORM_REDUCE_HPP -#define BOOST_ALGORITHM_TRANSFORM_REDUCE_HPP - -#include <functional> // for std::plus -#include <iterator> // for std::iterator_traits - -#include <boost/range/begin.hpp> -#include <boost/range/end.hpp> -#include <boost/range/value_type.hpp> - -namespace boost { namespace algorithm { - -template<class InputIterator, class OutputIterator, - class BinaryOperation, class UnaryOperation, class T> -OutputIterator transform_inclusive_scan(InputIterator first, InputIterator last, - OutputIterator result, - BinaryOperation bOp, UnaryOperation uOp, - T init) -{ - for (; first != last; ++first, (void) ++result) { - init = bOp(init, uOp(*first)); - *result = init; - } - - return result; -} - -template<class InputIterator, class OutputIterator, - class BinaryOperation, class UnaryOperation> -OutputIterator transform_inclusive_scan(InputIterator first, InputIterator last, - OutputIterator result, - BinaryOperation bOp, UnaryOperation uOp) -{ - if (first != last) { - typename std::iterator_traits<InputIterator>::value_type init = uOp(*first); - *result++ = init; - if (++first != last) - return transform_inclusive_scan(first, last, result, bOp, uOp, init); - } - - return result; -} - - -}} // namespace boost and algorithm - -#endif // BOOST_ALGORITHM_TRANSFORM_REDUCE_HPP diff --git a/contrib/restricted/boost/boost/algorithm/cxx17/transform_reduce.hpp b/contrib/restricted/boost/boost/algorithm/cxx17/transform_reduce.hpp deleted file mode 100644 index 7ebde7d325..0000000000 --- a/contrib/restricted/boost/boost/algorithm/cxx17/transform_reduce.hpp +++ /dev/null @@ -1,55 +0,0 @@ -/* - Copyright (c) Marshall Clow 2017. - - Distributed under the Boost Software License, Version 1.0. (See accompanying - file LICENSE10.txt or copy at http://www.boost.org/LICENSE10.txt) -*/ - -/// \file transform_reduce.hpp -/// \brief Combine the (transformed) elements of a sequence (or two) into a single value. -/// \author Marshall Clow - -#ifndef BOOST_ALGORITHM_TRANSFORM_REDUCE_HPP -#define BOOST_ALGORITHM_TRANSFORM_REDUCE_HPP - -#include <functional> // for std::plus -#include <iterator> // for std::iterator_traits - -#include <boost/range/begin.hpp> -#include <boost/range/end.hpp> -#include <boost/range/value_type.hpp> - -namespace boost { namespace algorithm { - -template<class InputIterator1, class InputIterator2, class T, - class BinaryOperation1, class BinaryOperation2> -T transform_reduce(InputIterator1 first1, InputIterator1 last1, - InputIterator2 first2, T init, - BinaryOperation1 bOp1, BinaryOperation2 bOp2) -{ - for (; first1 != last1; ++first1, (void) ++first2) - init = bOp1(init, bOp2(*first1, *first2)); - return init; -} - -template<class InputIterator, class T, - class BinaryOperation, class UnaryOperation> -T transform_reduce(InputIterator first, InputIterator last, - T init, BinaryOperation bOp, UnaryOperation uOp) -{ - for (; first != last; ++first) - init = bOp(init, uOp(*first)); - return init; -} - -template<class InputIterator1, class InputIterator2, class T> -T transform_reduce(InputIterator1 first1, InputIterator1 last1, - InputIterator2 first2, T init) -{ - return transform_reduce(first1, last1, first2, init, - std::plus<T>(), std::multiplies<T>()); -} - -}} // namespace boost and algorithm - -#endif // BOOST_ALGORITHM_TRANSFORM_REDUCE_HPP diff --git a/contrib/restricted/boost/boost/algorithm/gather.hpp b/contrib/restricted/boost/boost/algorithm/gather.hpp deleted file mode 100644 index 944bc94348..0000000000 --- a/contrib/restricted/boost/boost/algorithm/gather.hpp +++ /dev/null @@ -1,123 +0,0 @@ -/* - Copyright 2008 Adobe Systems Incorporated - - 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: - January 2008 mtc Version for Adobe Source Library - January 2013 mtc Version for Boost.Algorithm - -*/ - -/**************************************************************************************************/ - -/*! -\author Marshall Clow -\date January 2008 -*/ - -#ifndef BOOST_ALGORITHM_GATHER_HPP -#define BOOST_ALGORITHM_GATHER_HPP - -#include <algorithm> // for std::stable_partition -#include <functional> - -#include <boost/bind.hpp> // for boost::bind -#include <boost/range/begin.hpp> // for boost::begin(range) -#include <boost/range/end.hpp> // for boost::end(range) - - -/**************************************************************************************************/ -/*! - \defgroup gather gather - \ingroup mutating_algorithm - - \c gather() takes a collection of elements defined by a pair of iterators and moves - the ones satisfying a predicate to them to a position (called the pivot) within - the sequence. The algorithm is stable. The result is a pair of iterators that - contains the items that satisfy the predicate. - - Given an sequence containing: - <pre> - 0 1 2 3 4 5 6 7 8 9 - </pre> - - a call to gather ( arr, arr + 10, arr + 4, IsEven ()) will result in: - - <pre> - 1 3 0 2 4 6 8 5 7 9 - |---|-----| - first | second - pivot - </pre> - - - The problem is broken down into two basic steps, namely, moving the items before the pivot - and then moving the items from the pivot to the end. These "moves" are done with calls to - stable_partition. - - \par Storage Requirements: - - The algorithm uses stable_partition, which will attempt to allocate temporary memory, - but will work in-situ if there is none available. - - \par Time Complexity: - - If there is sufficient memory available, the run time is linear in <code>N</code>. - If there is not any memory available, then the run time is <code>O(N log N)</code>. -*/ - -/**************************************************************************************************/ - -namespace boost { namespace algorithm { - -/**************************************************************************************************/ - -/*! - \ingroup gather - \brief iterator-based gather implementation -*/ - -template < - typename BidirectionalIterator, // Iter models BidirectionalIterator - typename Pred> // Pred models UnaryPredicate -std::pair<BidirectionalIterator, BidirectionalIterator> gather - ( BidirectionalIterator first, BidirectionalIterator last, BidirectionalIterator pivot, Pred pred ) -{ -// The first call partitions everything up to (but not including) the pivot element, -// while the second call partitions the rest of the sequence. - return std::make_pair ( - std::stable_partition ( first, pivot, !boost::bind<bool> ( pred, _1 )), - std::stable_partition ( pivot, last, boost::bind<bool> ( pred, _1 ))); -} - -/**************************************************************************************************/ - -/*! - \ingroup gather - \brief range-based gather implementation -*/ - -template < - typename BidirectionalRange, // - typename Pred> // Pred models UnaryPredicate -std::pair< - typename boost::range_iterator<const BidirectionalRange>::type, - typename boost::range_iterator<const BidirectionalRange>::type> -gather ( - const BidirectionalRange &range, - typename boost::range_iterator<const BidirectionalRange>::type pivot, - Pred pred ) -{ - return boost::algorithm::gather ( boost::begin ( range ), boost::end ( range ), pivot, pred ); -} - -/**************************************************************************************************/ - -}} // namespace - -/**************************************************************************************************/ - -#endif - diff --git a/contrib/restricted/boost/boost/algorithm/hex.hpp b/contrib/restricted/boost/boost/algorithm/hex.hpp deleted file mode 100644 index b8335843a8..0000000000 --- a/contrib/restricted/boost/boost/algorithm/hex.hpp +++ /dev/null @@ -1,325 +0,0 @@ -/* - Copyright (c) Marshall Clow 2011-2012. - - 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) - - Thanks to Nevin for his comments/help. -*/ - -/* - General problem - turn a sequence of integral types into a sequence of hexadecimal characters. - - and back. -*/ - -/// \file hex.hpp -/// \brief Convert sequence of integral types into a sequence of hexadecimal -/// characters and back. Based on the MySQL functions HEX and UNHEX -/// \author Marshall Clow - -#ifndef BOOST_ALGORITHM_HEXHPP -#define BOOST_ALGORITHM_HEXHPP - -#include <iterator> // for std::iterator_traits -#include <stdexcept> - -#include <boost/range/begin.hpp> -#include <boost/range/end.hpp> -#include <boost/exception/exception.hpp> -#include <boost/exception/info.hpp> -#include <boost/throw_exception.hpp> - -#include <boost/utility/enable_if.hpp> -#include <boost/type_traits/is_integral.hpp> - - -namespace boost { namespace algorithm { - -/*! - \struct hex_decode_error - \brief Base exception class for all hex decoding errors -*/ /*! - \struct non_hex_input - \brief Thrown when a non-hex value (0-9, A-F) encountered when decoding. - Contains the offending character -*/ /*! - \struct not_enough_input - \brief Thrown when the input sequence unexpectedly ends - -*/ -struct hex_decode_error : virtual boost::exception, virtual std::exception {}; -struct not_enough_input : virtual hex_decode_error {}; -struct non_hex_input : virtual hex_decode_error {}; -typedef boost::error_info<struct bad_char_,char> bad_char; - -namespace detail { -/// \cond DOXYGEN_HIDE - - template <typename T, typename OutputIterator> - OutputIterator encode_one ( T val, OutputIterator out, const char * hexDigits ) { - const std::size_t num_hex_digits = 2 * sizeof ( T ); - char res [ num_hex_digits ]; - char *p = res + num_hex_digits; - for ( std::size_t i = 0; i < num_hex_digits; ++i, val >>= 4 ) - *--p = hexDigits [ val & 0x0F ]; - return std::copy ( res, res + num_hex_digits, out ); - } - - template <typename T> - unsigned char hex_char_to_int ( T val ) { - char c = static_cast<char> ( val ); - unsigned retval = 0; - if ( c >= '0' && c <= '9' ) retval = c - '0'; - else if ( c >= 'A' && c <= 'F' ) retval = c - 'A' + 10; - else if ( c >= 'a' && c <= 'f' ) retval = c - 'a' + 10; - else BOOST_THROW_EXCEPTION (non_hex_input() << bad_char (c)); - return static_cast<char>(retval); - } - -// My own iterator_traits class. -// It is here so that I can "reach inside" some kinds of output iterators -// and get the type to write. - template <typename Iterator> - struct hex_iterator_traits { - typedef typename std::iterator_traits<Iterator>::value_type value_type; - }; - - template<typename Container> - struct hex_iterator_traits< std::back_insert_iterator<Container> > { - typedef typename Container::value_type value_type; - }; - - template<typename Container> - struct hex_iterator_traits< std::front_insert_iterator<Container> > { - typedef typename Container::value_type value_type; - }; - - template<typename Container> - struct hex_iterator_traits< std::insert_iterator<Container> > { - typedef typename Container::value_type value_type; - }; - -// ostream_iterators have three template parameters. -// The first one is the output type, the second one is the character type of -// the underlying stream, the third is the character traits. -// We only care about the first one. - template<typename T, typename charType, typename traits> - struct hex_iterator_traits< std::ostream_iterator<T, charType, traits> > { - typedef T value_type; - }; - - template <typename Iterator> - bool iter_end ( Iterator current, Iterator last ) { return current == last; } - - template <typename T> - bool ptr_end ( const T* ptr, const T* /*end*/ ) { return *ptr == '\0'; } - -// What can we assume here about the inputs? -// is std::iterator_traits<InputIterator>::value_type always 'char' ? -// Could it be wchar_t, say? Does it matter? -// We are assuming ASCII for the values - but what about the storage? - template <typename InputIterator, typename OutputIterator, typename EndPred> - typename boost::enable_if<boost::is_integral<typename hex_iterator_traits<OutputIterator>::value_type>, OutputIterator>::type - decode_one ( InputIterator &first, InputIterator last, OutputIterator out, EndPred pred ) { - typedef typename hex_iterator_traits<OutputIterator>::value_type T; - T res (0); - - // Need to make sure that we get can read that many chars here. - for ( std::size_t i = 0; i < 2 * sizeof ( T ); ++i, ++first ) { - if ( pred ( first, last )) - BOOST_THROW_EXCEPTION (not_enough_input ()); - res = ( 16 * res ) + hex_char_to_int (*first); - } - - *out = res; - return ++out; - } -/// \endcond - } - - -/// \fn hex ( InputIterator first, InputIterator last, OutputIterator out ) -/// \brief Converts a sequence of integral types into a hexadecimal sequence of characters. -/// -/// \param first The start of the input sequence -/// \param last One past the end of the input sequence -/// \param out An output iterator to the results into -/// \return The updated output iterator -/// \note Based on the MySQL function of the same name -template <typename InputIterator, typename OutputIterator> -typename boost::enable_if<boost::is_integral<typename detail::hex_iterator_traits<InputIterator>::value_type>, OutputIterator>::type -hex ( InputIterator first, InputIterator last, OutputIterator out ) { - for ( ; first != last; ++first ) - out = detail::encode_one ( *first, out, "0123456789ABCDEF" ); - return out; - } - - -/// \fn hex_lower ( InputIterator first, InputIterator last, OutputIterator out ) -/// \brief Converts a sequence of integral types into a lower case hexadecimal sequence of characters. -/// -/// \param first The start of the input sequence -/// \param last One past the end of the input sequence -/// \param out An output iterator to the results into -/// \return The updated output iterator -/// \note Based on the MySQL function of the same name -template <typename InputIterator, typename OutputIterator> -typename boost::enable_if<boost::is_integral<typename detail::hex_iterator_traits<InputIterator>::value_type>, OutputIterator>::type -hex_lower ( InputIterator first, InputIterator last, OutputIterator out ) { - for ( ; first != last; ++first ) - out = detail::encode_one ( *first, out, "0123456789abcdef" ); - return out; - } - - -/// \fn hex ( const T *ptr, OutputIterator out ) -/// \brief Converts a sequence of integral types into a hexadecimal sequence of characters. -/// -/// \param ptr A pointer to a 0-terminated sequence of data. -/// \param out An output iterator to the results into -/// \return The updated output iterator -/// \note Based on the MySQL function of the same name -template <typename T, typename OutputIterator> -typename boost::enable_if<boost::is_integral<T>, OutputIterator>::type -hex ( const T *ptr, OutputIterator out ) { - while ( *ptr ) - out = detail::encode_one ( *ptr++, out, "0123456789ABCDEF" ); - return out; - } - - -/// \fn hex_lower ( const T *ptr, OutputIterator out ) -/// \brief Converts a sequence of integral types into a lower case hexadecimal sequence of characters. -/// -/// \param ptr A pointer to a 0-terminated sequence of data. -/// \param out An output iterator to the results into -/// \return The updated output iterator -/// \note Based on the MySQL function of the same name -template <typename T, typename OutputIterator> -typename boost::enable_if<boost::is_integral<T>, OutputIterator>::type -hex_lower ( const T *ptr, OutputIterator out ) { - while ( *ptr ) - out = detail::encode_one ( *ptr++, out, "0123456789abcdef" ); - return out; - } - - -/// \fn hex ( const Range &r, OutputIterator out ) -/// \brief Converts a sequence of integral types into a hexadecimal sequence of characters. -/// -/// \param r The input range -/// \param out An output iterator to the results into -/// \return The updated output iterator -/// \note Based on the MySQL function of the same name -template <typename Range, typename OutputIterator> -typename boost::enable_if<boost::is_integral<typename detail::hex_iterator_traits<typename Range::iterator>::value_type>, OutputIterator>::type -hex ( const Range &r, OutputIterator out ) { - return hex (boost::begin(r), boost::end(r), out); -} - - -/// \fn hex_lower ( const Range &r, OutputIterator out ) -/// \brief Converts a sequence of integral types into a lower case hexadecimal sequence of characters. -/// -/// \param r The input range -/// \param out An output iterator to the results into -/// \return The updated output iterator -/// \note Based on the MySQL function of the same name -template <typename Range, typename OutputIterator> -typename boost::enable_if<boost::is_integral<typename detail::hex_iterator_traits<typename Range::iterator>::value_type>, OutputIterator>::type -hex_lower ( const Range &r, OutputIterator out ) { - return hex_lower (boost::begin(r), boost::end(r), out); -} - - -/// \fn unhex ( InputIterator first, InputIterator last, OutputIterator out ) -/// \brief Converts a sequence of hexadecimal characters into a sequence of integers. -/// -/// \param first The start of the input sequence -/// \param last One past the end of the input sequence -/// \param out An output iterator to the results into -/// \return The updated output iterator -/// \note Based on the MySQL function of the same name -template <typename InputIterator, typename OutputIterator> -OutputIterator unhex ( InputIterator first, InputIterator last, OutputIterator out ) { - while ( first != last ) - out = detail::decode_one ( first, last, out, detail::iter_end<InputIterator> ); - return out; - } - - -/// \fn unhex ( const T *ptr, OutputIterator out ) -/// \brief Converts a sequence of hexadecimal characters into a sequence of integers. -/// -/// \param ptr A pointer to a null-terminated input sequence. -/// \param out An output iterator to the results into -/// \return The updated output iterator -/// \note Based on the MySQL function of the same name -template <typename T, typename OutputIterator> -OutputIterator unhex ( const T *ptr, OutputIterator out ) { -// 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? - while ( *ptr ) - out = detail::decode_one ( ptr, (const T *) NULL, out, detail::ptr_end<T> ); - return out; - } - - -/// \fn OutputIterator unhex ( const Range &r, OutputIterator out ) -/// \brief Converts a sequence of hexadecimal characters into a sequence of integers. -/// -/// \param r The input range -/// \param out An output iterator to the results into -/// \return The updated output iterator -/// \note Based on the MySQL function of the same name -template <typename Range, typename OutputIterator> -OutputIterator unhex ( const Range &r, OutputIterator out ) { - return unhex (boost::begin(r), boost::end(r), out); - } - - -/// \fn String hex ( const String &input ) -/// \brief Converts a sequence of integral types into a hexadecimal sequence of characters. -/// -/// \param input A container to be converted -/// \return A container with the encoded text -template<typename String> -String hex ( const String &input ) { - String output; - output.reserve (input.size () * (2 * sizeof (typename String::value_type))); - (void) hex (input, std::back_inserter (output)); - return output; - } - - -/// \fn String hex_lower ( const String &input ) -/// \brief Converts a sequence of integral types into a lower case hexadecimal sequence of characters. -/// -/// \param input A container to be converted -/// \return A container with the encoded text -template<typename String> -String hex_lower ( const String &input ) { - String output; - output.reserve (input.size () * (2 * sizeof (typename String::value_type))); - (void) hex_lower (input, std::back_inserter (output)); - return output; - } - - -/// \fn String unhex ( const String &input ) -/// \brief Converts a sequence of hexadecimal characters into a sequence of characters. -/// -/// \param input A container to be converted -/// \return A container with the decoded text -template<typename String> -String unhex ( const String &input ) { - String output; - output.reserve (input.size () / (2 * sizeof (typename String::value_type))); - (void) unhex (input, std::back_inserter (output)); - return output; - } - -}} - -#endif // BOOST_ALGORITHM_HEXHPP diff --git a/contrib/restricted/boost/boost/algorithm/is_palindrome.hpp b/contrib/restricted/boost/boost/algorithm/is_palindrome.hpp deleted file mode 100644 index 09881109a3..0000000000 --- a/contrib/restricted/boost/boost/algorithm/is_palindrome.hpp +++ /dev/null @@ -1,140 +0,0 @@ -/* - Copyright (c) Alexander Zaitsev <zamazan4ik@gmail.com>, 2016 - - 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) - - See http://www.boost.org/ for latest version. -*/ - -/// \file is_palindrome.hpp -/// \brief Checks the input sequence on palindrome. -/// \author Alexander Zaitsev - -#ifndef BOOST_ALGORITHM_IS_PALINDROME_HPP -#define BOOST_ALGORITHM_IS_PALINDROME_HPP - -#include <iterator> -#include <functional> -#include <cstring> - -#include <boost/range/begin.hpp> -#include <boost/range/end.hpp> - -namespace boost { namespace algorithm { - -/// \fn is_palindrome ( BidirectionalIterator begin, BidirectionalIterator end, Predicate p ) -/// \return true if the entire sequence is palindrome -/// -/// \param begin The start of the input sequence -/// \param end One past the end of the input sequence -/// \param p A predicate used to compare the values. -/// -/// \note This function will return true for empty sequences and for palindromes. -/// For other sequences function will return false. -/// Complexity: O(N). -template <typename BidirectionalIterator, typename Predicate> -bool is_palindrome(BidirectionalIterator begin, BidirectionalIterator end, Predicate p) -{ - if(begin == end) - { - return true; - } - - --end; - while(begin != end) - { - if(!p(*begin, *end)) - { - return false; - } - ++begin; - if(begin == end) - { - break; - } - --end; - } - return true; -} - -/// \fn is_palindrome ( BidirectionalIterator begin, BidirectionalIterator end ) -/// \return true if the entire sequence is palindrome -/// -/// \param begin The start of the input sequence -/// \param end One past the end of the input sequence -/// -/// \note This function will return true for empty sequences and for palindromes. -/// For other sequences function will return false. -/// Complexity: O(N). -template <typename BidirectionalIterator> -bool is_palindrome(BidirectionalIterator begin, BidirectionalIterator end) -{ - return is_palindrome(begin, end, - std::equal_to<typename std::iterator_traits<BidirectionalIterator>::value_type> ()); -} - -/// \fn is_palindrome ( const R& range ) -/// \return true if the entire sequence is palindrome -/// -/// \param range The range to be tested. -/// -/// \note This function will return true for empty sequences and for palindromes. -/// For other sequences function will return false. -/// Complexity: O(N). -template <typename R> -bool is_palindrome(const R& range) -{ - return is_palindrome(boost::begin(range), boost::end(range)); -} - -/// \fn is_palindrome ( const R& range, Predicate p ) -/// \return true if the entire sequence is palindrome -/// -/// \param range The range to be tested. -/// \param p A predicate used to compare the values. -/// -/// \note This function will return true for empty sequences and for palindromes. -/// For other sequences function will return false. -/// Complexity: O(N). -template <typename R, typename Predicate> -bool is_palindrome(const R& range, Predicate p) -{ - return is_palindrome(boost::begin(range), boost::end(range), p); -} - -/// \fn is_palindrome ( const char* str ) -/// \return true if the entire sequence is palindrome -/// -/// \param str C-string to be tested. -/// -/// \note This function will return true for empty sequences and for palindromes. -/// For other sequences function will return false. -/// Complexity: O(N). -bool is_palindrome(const char* str) -{ - if(!str) - return true; - return is_palindrome(str, str + strlen(str)); -} - -/// \fn is_palindrome ( const char* str, Predicate p ) -/// \return true if the entire sequence is palindrome -/// -/// \param str C-string to be tested. -/// \param p A predicate used to compare the values. -/// -/// \note This function will return true for empty sequences and for palindromes. -/// For other sequences function will return false. -/// Complexity: O(N). -template<typename Predicate> -bool is_palindrome(const char* str, Predicate p) -{ - if(!str) - return true; - return is_palindrome(str, str + strlen(str), p); -} -}} - -#endif // BOOST_ALGORITHM_IS_PALINDROME_HPP diff --git a/contrib/restricted/boost/boost/algorithm/is_partitioned_until.hpp b/contrib/restricted/boost/boost/algorithm/is_partitioned_until.hpp deleted file mode 100644 index 42683e1d8e..0000000000 --- a/contrib/restricted/boost/boost/algorithm/is_partitioned_until.hpp +++ /dev/null @@ -1,63 +0,0 @@ -/* - Copyright (c) Alexander Zaitsev <zamazan4ik@gmail.by>, 2017. - - 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) -*/ - -/// \file is_partitioned_until.hpp -/// \brief Tell if a sequence is partitioned -/// \author Alexander Zaitsev - -#ifndef BOOST_ALGORITHM_IS_PARTITIONED_UNTIL_HPP -#define BOOST_ALGORITHM_IS_PARTITIONED_UNTIL_HPP - -#include <boost/range/begin.hpp> -#include <boost/range/end.hpp> - -namespace boost { namespace algorithm { - -/// \fn is_partitioned_until ( InputIterator first, InputIterator last, UnaryPredicate p ) -/// \brief Tests to see if a sequence is partitioned according to a predicate. -/// In other words, all the items in the sequence that satisfy the predicate are at the beginning of the sequence. -/// -/// \param first The start of the input sequence -/// \param last One past the end of the input sequence -/// \param p The predicate to test the values with -/// -/// \note Returns the first iterator 'it' in the sequence [first, last) for which is_partitioned(first, it, p) is false. -/// Returns last if the entire sequence is partitioned. -/// Complexity: O(N). -template <typename InputIterator, typename UnaryPredicate> -InputIterator is_partitioned_until ( InputIterator first, InputIterator last, UnaryPredicate p ) -{ -// Run through the part that satisfy the predicate - for ( ; first != last; ++first ) - if ( !p (*first)) - break; -// Now the part that does not satisfy the predicate - for ( ; first != last; ++first ) - if ( p (*first)) - return first; - return last; -} - -/// \fn is_partitioned_until ( const Range &r, UnaryPredicate p ) -/// \brief Tests to see if a sequence is partitioned according to a predicate. -/// In other words, all the items in the sequence that satisfy the predicate are at the beginning of the sequence. -/// -/// \param r The input range -/// \param p The predicate to test the values with -/// -/// \note Returns the first iterator 'it' in the sequence [first, last) for which is_partitioned(first, it, p) is false. -/// Returns last if the entire sequence is partitioned. -/// Complexity: O(N). -template <typename Range, typename UnaryPredicate> -typename boost::range_iterator<const Range>::type is_partitioned_until ( const Range &r, UnaryPredicate p ) -{ - return boost::algorithm::is_partitioned_until (boost::begin(r), boost::end(r), p); -} - -}} - -#endif // BOOST_ALGORITHM_IS_PARTITIONED_UNTIL_HPP diff --git a/contrib/restricted/boost/boost/algorithm/minmax.hpp b/contrib/restricted/boost/boost/algorithm/minmax.hpp deleted file mode 100644 index 053a7d60ae..0000000000 --- a/contrib/restricted/boost/boost/algorithm/minmax.hpp +++ /dev/null @@ -1,47 +0,0 @@ -// (C) Copyright Herve Bronnimann 2004. -// -// 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: - 1 July 2004 - Split the code into two headers to lessen dependence on - Boost.tuple. (Herve) - 26 June 2004 - Added the code for the boost minmax library. (Herve) -*/ - -#ifndef BOOST_ALGORITHM_MINMAX_HPP -#define BOOST_ALGORITHM_MINMAX_HPP - -/* PROPOSED STANDARD EXTENSIONS: - * - * minmax(a, b) - * Effect: (b<a) ? std::make_pair(b,a) : std::make_pair(a,b); - * - * minmax(a, b, comp) - * Effect: comp(b,a) ? std::make_pair(b,a) : std::make_pair(a,b); - * - */ - -#include <boost/tuple/tuple.hpp> // for using pairs with boost::cref -#include <boost/ref.hpp> - -namespace boost { - - template <typename T> - tuple< T const&, T const& > - minmax(T const& a, T const& b) { - return (b<a) ? make_tuple(cref(b),cref(a)) : make_tuple(cref(a),cref(b)); - } - - template <typename T, class BinaryPredicate> - tuple< T const&, T const& > - minmax(T const& a, T const& b, BinaryPredicate comp) { - return comp(b,a) ? make_tuple(cref(b),cref(a)) : make_tuple(cref(a),cref(b)); - } - -} // namespace boost - -#endif // BOOST_ALGORITHM_MINMAX_HPP diff --git a/contrib/restricted/boost/boost/algorithm/minmax_element.hpp b/contrib/restricted/boost/boost/algorithm/minmax_element.hpp deleted file mode 100644 index 752f6cbdb1..0000000000 --- a/contrib/restricted/boost/boost/algorithm/minmax_element.hpp +++ /dev/null @@ -1,553 +0,0 @@ -// (C) Copyright Herve Bronnimann 2004. -// -// 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: - 1 July 2004 - Split the code into two headers to lessen dependence on - Boost.tuple. (Herve) - 26 June 2004 - Added the code for the boost minmax library. (Herve) -*/ - -#ifndef BOOST_ALGORITHM_MINMAX_ELEMENT_HPP -#define BOOST_ALGORITHM_MINMAX_ELEMENT_HPP - -/* PROPOSED STANDARD EXTENSIONS: - * - * minmax_element(first, last) - * Effect: std::make_pair( std::min_element(first, last), - * std::max_element(first, last) ); - * - * minmax_element(first, last, comp) - * Effect: std::make_pair( std::min_element(first, last, comp), - * std::max_element(first, last, comp) ); - */ - -#include <utility> // for std::pair and std::make_pair - -namespace boost { - - namespace detail { // for obtaining a uniform version of minmax_element - // that compiles with VC++ 6.0 -- avoid the iterator_traits by - // having comparison object over iterator, not over dereferenced value - - template <typename Iterator> - struct less_over_iter { - bool operator()(Iterator const& it1, - Iterator const& it2) const { return *it1 < *it2; } - }; - - template <typename Iterator, class BinaryPredicate> - struct binary_pred_over_iter { - explicit binary_pred_over_iter(BinaryPredicate const& p ) : m_p( p ) {} - bool operator()(Iterator const& it1, - Iterator const& it2) const { return m_p(*it1, *it2); } - private: - BinaryPredicate m_p; - }; - - // common base for the two minmax_element overloads - - template <typename ForwardIter, class Compare > - std::pair<ForwardIter,ForwardIter> - basic_minmax_element(ForwardIter first, ForwardIter last, Compare comp) - { - if (first == last) - return std::make_pair(last,last); - - ForwardIter min_result = first; - ForwardIter max_result = first; - - // if only one element - ForwardIter second = first; ++second; - if (second == last) - return std::make_pair(min_result, max_result); - - // treat first pair separately (only one comparison for first two elements) - ForwardIter potential_min_result = last; - if (comp(first, second)) - max_result = second; - else { - min_result = second; - potential_min_result = first; - } - - // then each element by pairs, with at most 3 comparisons per pair - first = ++second; if (first != last) ++second; - while (second != last) { - if (comp(first, second)) { - if (comp(first, min_result)) { - min_result = first; - potential_min_result = last; - } - if (comp(max_result, second)) - max_result = second; - } else { - if (comp(second, min_result)) { - min_result = second; - potential_min_result = first; - } - if (comp(max_result, first)) - max_result = first; - } - first = ++second; - if (first != last) ++second; - } - - // if odd number of elements, treat last element - if (first != last) { // odd number of elements - if (comp(first, min_result)) { - min_result = first; - potential_min_result = last; - } - else if (comp(max_result, first)) - max_result = first; - } - - // resolve min_result being incorrect with one extra comparison - // (in which case potential_min_result is necessarily the correct result) - if (potential_min_result != last - && !comp(min_result, potential_min_result)) - min_result = potential_min_result; - - return std::make_pair(min_result,max_result); - } - - } // namespace detail - - template <typename ForwardIter> - std::pair<ForwardIter,ForwardIter> - minmax_element(ForwardIter first, ForwardIter last) - { - return detail::basic_minmax_element(first, last, - detail::less_over_iter<ForwardIter>() ); - } - - template <typename ForwardIter, class BinaryPredicate> - std::pair<ForwardIter,ForwardIter> - minmax_element(ForwardIter first, ForwardIter last, BinaryPredicate comp) - { - return detail::basic_minmax_element(first, last, - detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) ); - } - -} - -/* PROPOSED BOOST EXTENSIONS - * In the description below, [rfirst,rlast) denotes the reversed range - * of [first,last). Even though the iterator type of first and last may - * be only a Forward Iterator, it is possible to explain the semantics - * by assuming that it is a Bidirectional Iterator. In the sequel, - * reverse(ForwardIterator&) returns the reverse_iterator adaptor. - * This is not how the functions would be implemented! - * - * first_min_element(first, last) - * Effect: std::min_element(first, last); - * - * first_min_element(first, last, comp) - * Effect: std::min_element(first, last, comp); - * - * last_min_element(first, last) - * Effect: reverse( std::min_element(reverse(last), reverse(first)) ); - * - * last_min_element(first, last, comp) - * Effect: reverse( std::min_element(reverse(last), reverse(first), comp) ); - * - * first_max_element(first, last) - * Effect: std::max_element(first, last); - * - * first_max_element(first, last, comp) - * Effect: max_element(first, last); - * - * last_max_element(first, last) - * Effect: reverse( std::max_element(reverse(last), reverse(first)) ); - * - * last_max_element(first, last, comp) - * Effect: reverse( std::max_element(reverse(last), reverse(first), comp) ); - * - * first_min_first_max_element(first, last) - * Effect: std::make_pair( first_min_element(first, last), - * first_max_element(first, last) ); - * - * first_min_first_max_element(first, last, comp) - * Effect: std::make_pair( first_min_element(first, last, comp), - * first_max_element(first, last, comp) ); - * - * first_min_last_max_element(first, last) - * Effect: std::make_pair( first_min_element(first, last), - * last_max_element(first, last) ); - * - * first_min_last_max_element(first, last, comp) - * Effect: std::make_pair( first_min_element(first, last, comp), - * last_max_element(first, last, comp) ); - * - * last_min_first_max_element(first, last) - * Effect: std::make_pair( last_min_element(first, last), - * first_max_element(first, last) ); - * - * last_min_first_max_element(first, last, comp) - * Effect: std::make_pair( last_min_element(first, last, comp), - * first_max_element(first, last, comp) ); - * - * last_min_last_max_element(first, last) - * Effect: std::make_pair( last_min_element(first, last), - * last_max_element(first, last) ); - * - * last_min_last_max_element(first, last, comp) - * Effect: std::make_pair( last_min_element(first, last, comp), - * last_max_element(first, last, comp) ); - */ - -namespace boost { - - // Min_element and max_element variants - - namespace detail { // common base for the overloads - - template <typename ForwardIter, class BinaryPredicate> - ForwardIter - basic_first_min_element(ForwardIter first, ForwardIter last, - BinaryPredicate comp) - { - if (first == last) return last; - ForwardIter min_result = first; - while (++first != last) - if (comp(first, min_result)) - min_result = first; - return min_result; - } - - template <typename ForwardIter, class BinaryPredicate> - ForwardIter - basic_last_min_element(ForwardIter first, ForwardIter last, - BinaryPredicate comp) - { - if (first == last) return last; - ForwardIter min_result = first; - while (++first != last) - if (!comp(min_result, first)) - min_result = first; - return min_result; - } - - template <typename ForwardIter, class BinaryPredicate> - ForwardIter - basic_first_max_element(ForwardIter first, ForwardIter last, - BinaryPredicate comp) - { - if (first == last) return last; - ForwardIter max_result = first; - while (++first != last) - if (comp(max_result, first)) - max_result = first; - return max_result; - } - - template <typename ForwardIter, class BinaryPredicate> - ForwardIter - basic_last_max_element(ForwardIter first, ForwardIter last, - BinaryPredicate comp) - { - if (first == last) return last; - ForwardIter max_result = first; - while (++first != last) - if (!comp(first, max_result)) - max_result = first; - return max_result; - } - - } // namespace detail - - template <typename ForwardIter> - ForwardIter - first_min_element(ForwardIter first, ForwardIter last) - { - return detail::basic_first_min_element(first, last, - detail::less_over_iter<ForwardIter>() ); - } - - template <typename ForwardIter, class BinaryPredicate> - ForwardIter - first_min_element(ForwardIter first, ForwardIter last, BinaryPredicate comp) - { - return detail::basic_first_min_element(first, last, - detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) ); - } - - template <typename ForwardIter> - ForwardIter - last_min_element(ForwardIter first, ForwardIter last) - { - return detail::basic_last_min_element(first, last, - detail::less_over_iter<ForwardIter>() ); - } - - template <typename ForwardIter, class BinaryPredicate> - ForwardIter - last_min_element(ForwardIter first, ForwardIter last, BinaryPredicate comp) - { - return detail::basic_last_min_element(first, last, - detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) ); - } - - template <typename ForwardIter> - ForwardIter - first_max_element(ForwardIter first, ForwardIter last) - { - return detail::basic_first_max_element(first, last, - detail::less_over_iter<ForwardIter>() ); - } - - template <typename ForwardIter, class BinaryPredicate> - ForwardIter - first_max_element(ForwardIter first, ForwardIter last, BinaryPredicate comp) - { - return detail::basic_first_max_element(first, last, - detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) ); - } - - template <typename ForwardIter> - ForwardIter - last_max_element(ForwardIter first, ForwardIter last) - { - return detail::basic_last_max_element(first, last, - detail::less_over_iter<ForwardIter>() ); - } - - template <typename ForwardIter, class BinaryPredicate> - ForwardIter - last_max_element(ForwardIter first, ForwardIter last, BinaryPredicate comp) - { - return detail::basic_last_max_element(first, last, - detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) ); - } - - - // Minmax_element variants -- comments removed - - namespace detail { - - template <typename ForwardIter, class BinaryPredicate> - std::pair<ForwardIter,ForwardIter> - basic_first_min_last_max_element(ForwardIter first, ForwardIter last, - BinaryPredicate comp) - { - if (first == last) - return std::make_pair(last,last); - - ForwardIter min_result = first; - ForwardIter max_result = first; - - ForwardIter second = ++first; - if (second == last) - return std::make_pair(min_result, max_result); - - if (comp(second, min_result)) - min_result = second; - else - max_result = second; - - first = ++second; if (first != last) ++second; - while (second != last) { - if (!comp(second, first)) { - if (comp(first, min_result)) - min_result = first; - if (!comp(second, max_result)) - max_result = second; - } else { - if (comp(second, min_result)) - min_result = second; - if (!comp(first, max_result)) - max_result = first; - } - first = ++second; if (first != last) ++second; - } - - if (first != last) { - if (comp(first, min_result)) - min_result = first; - else if (!comp(first, max_result)) - max_result = first; - } - - return std::make_pair(min_result, max_result); - } - - template <typename ForwardIter, class BinaryPredicate> - std::pair<ForwardIter,ForwardIter> - basic_last_min_first_max_element(ForwardIter first, ForwardIter last, - BinaryPredicate comp) - { - if (first == last) return std::make_pair(last,last); - - ForwardIter min_result = first; - ForwardIter max_result = first; - - ForwardIter second = ++first; - if (second == last) - return std::make_pair(min_result, max_result); - - if (comp(max_result, second)) - max_result = second; - else - min_result = second; - - first = ++second; if (first != last) ++second; - while (second != last) { - if (comp(first, second)) { - if (!comp(min_result, first)) - min_result = first; - if (comp(max_result, second)) - max_result = second; - } else { - if (!comp(min_result, second)) - min_result = second; - if (comp(max_result, first)) - max_result = first; - } - first = ++second; if (first != last) ++second; - } - - if (first != last) { - if (!comp(min_result, first)) - min_result = first; - else if (comp(max_result, first)) - max_result = first; - } - - return std::make_pair(min_result, max_result); - } - - template <typename ForwardIter, class BinaryPredicate> - std::pair<ForwardIter,ForwardIter> - basic_last_min_last_max_element(ForwardIter first, ForwardIter last, - BinaryPredicate comp) - { - if (first == last) return std::make_pair(last,last); - - ForwardIter min_result = first; - ForwardIter max_result = first; - - ForwardIter second = first; ++second; - if (second == last) - return std::make_pair(min_result,max_result); - - ForwardIter potential_max_result = last; - if (comp(first, second)) - max_result = second; - else { - min_result = second; - potential_max_result = second; - } - - first = ++second; if (first != last) ++second; - while (second != last) { - if (comp(first, second)) { - if (!comp(min_result, first)) - min_result = first; - if (!comp(second, max_result)) { - max_result = second; - potential_max_result = last; - } - } else { - if (!comp(min_result, second)) - min_result = second; - if (!comp(first, max_result)) { - max_result = first; - potential_max_result = second; - } - } - first = ++second; - if (first != last) ++second; - } - - if (first != last) { - if (!comp(min_result, first)) - min_result = first; - if (!comp(first, max_result)) { - max_result = first; - potential_max_result = last; - } - } - - if (potential_max_result != last - && !comp(potential_max_result, max_result)) - max_result = potential_max_result; - - return std::make_pair(min_result,max_result); - } - - } // namespace detail - - template <typename ForwardIter> - inline std::pair<ForwardIter,ForwardIter> - first_min_first_max_element(ForwardIter first, ForwardIter last) - { - return minmax_element(first, last); - } - - template <typename ForwardIter, class BinaryPredicate> - inline std::pair<ForwardIter,ForwardIter> - first_min_first_max_element(ForwardIter first, ForwardIter last, - BinaryPredicate comp) - { - return minmax_element(first, last, comp); - } - - template <typename ForwardIter> - std::pair<ForwardIter,ForwardIter> - first_min_last_max_element(ForwardIter first, ForwardIter last) - { - return detail::basic_first_min_last_max_element(first, last, - detail::less_over_iter<ForwardIter>() ); - } - - template <typename ForwardIter, class BinaryPredicate> - inline std::pair<ForwardIter,ForwardIter> - first_min_last_max_element(ForwardIter first, ForwardIter last, - BinaryPredicate comp) - { - return detail::basic_first_min_last_max_element(first, last, - detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) ); - } - - template <typename ForwardIter> - std::pair<ForwardIter,ForwardIter> - last_min_first_max_element(ForwardIter first, ForwardIter last) - { - return detail::basic_last_min_first_max_element(first, last, - detail::less_over_iter<ForwardIter>() ); - } - - template <typename ForwardIter, class BinaryPredicate> - inline std::pair<ForwardIter,ForwardIter> - last_min_first_max_element(ForwardIter first, ForwardIter last, - BinaryPredicate comp) - { - return detail::basic_last_min_first_max_element(first, last, - detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) ); - } - - template <typename ForwardIter> - std::pair<ForwardIter,ForwardIter> - last_min_last_max_element(ForwardIter first, ForwardIter last) - { - return detail::basic_last_min_last_max_element(first, last, - detail::less_over_iter<ForwardIter>() ); - } - - template <typename ForwardIter, class BinaryPredicate> - inline std::pair<ForwardIter,ForwardIter> - last_min_last_max_element(ForwardIter first, ForwardIter last, - BinaryPredicate comp) - { - return detail::basic_last_min_last_max_element(first, last, - detail::binary_pred_over_iter<ForwardIter,BinaryPredicate>(comp) ); - } - -} // namespace boost - -#endif // BOOST_ALGORITHM_MINMAX_ELEMENT_HPP diff --git a/contrib/restricted/boost/boost/algorithm/searching/boyer_moore.hpp b/contrib/restricted/boost/boost/algorithm/searching/boyer_moore.hpp deleted file mode 100644 index 192d4dec25..0000000000 --- a/contrib/restricted/boost/boost/algorithm/searching/boyer_moore.hpp +++ /dev/null @@ -1,272 +0,0 @@ -/* - Copyright (c) Marshall Clow 2010-2012. - - 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) - - For more information, see http://www.boost.org -*/ - -#ifndef BOOST_ALGORITHM_BOYER_MOORE_SEARCH_HPP -#define BOOST_ALGORITHM_BOYER_MOORE_SEARCH_HPP - -#include <iterator> // for std::iterator_traits - -#include <boost/assert.hpp> -#include <boost/static_assert.hpp> - -#include <boost/range/begin.hpp> -#include <boost/range/end.hpp> - -#include <boost/utility/enable_if.hpp> -#include <boost/type_traits/is_same.hpp> - -#include <boost/algorithm/searching/detail/bm_traits.hpp> -#include <boost/algorithm/searching/detail/debugging.hpp> - -namespace boost { namespace algorithm { - -/* - A templated version of the boyer-moore searching algorithm. - -References: - http://www.cs.utexas.edu/users/moore/best-ideas/string-searching/ - http://www.cs.utexas.edu/~moore/publications/fstrpos.pdf - -Explanations: - http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm - http://www.movsd.com/bm.htm - http://www.cs.ucdavis.edu/~gusfield/cs224f09/bnotes.pdf - -The Boyer-Moore search algorithm uses two tables, a "bad character" table -to tell how far to skip ahead when it hits a character that is not in the pattern, -and a "good character" table to tell how far to skip ahead when it hits a -mismatch on a character that _is_ in the pattern. - -Requirements: - * Random access iterators - * The two iterator types (patIter and corpusIter) must - "point to" the same underlying type and be comparable. - * Additional requirements may be imposed but the skip table, such as: - ** Numeric type (array-based skip table) - ** Hashable type (map-based skip table) -*/ - - template <typename patIter, typename traits = detail::BM_traits<patIter> > - class boyer_moore { - typedef typename std::iterator_traits<patIter>::difference_type difference_type; - public: - boyer_moore ( patIter first, patIter last ) - : pat_first ( first ), pat_last ( last ), - k_pattern_length ( std::distance ( pat_first, pat_last )), - skip_ ( k_pattern_length, -1 ), - suffix_ ( k_pattern_length + 1 ) - { - this->build_skip_table ( first, last ); - this->build_suffix_table ( first, last ); - } - - ~boyer_moore () {} - - /// \fn operator ( corpusIter corpus_first, corpusIter corpus_last ) - /// \brief Searches the corpus for the pattern that was passed into the constructor - /// - /// \param corpus_first The start of the data to search (Random Access Iterator) - /// \param corpus_last One past the end of the data to search - /// - template <typename corpusIter> - std::pair<corpusIter, corpusIter> - operator () ( corpusIter corpus_first, corpusIter corpus_last ) const { - BOOST_STATIC_ASSERT (( boost::is_same< - typename std::iterator_traits<patIter>::value_type, - typename std::iterator_traits<corpusIter>::value_type>::value )); - - if ( corpus_first == corpus_last ) return std::make_pair(corpus_last, corpus_last); // if nothing to search, we didn't find it! - if ( pat_first == pat_last ) return std::make_pair(corpus_first, corpus_first); // empty pattern matches at start - - const difference_type k_corpus_length = std::distance ( corpus_first, corpus_last ); - // If the pattern is larger than the corpus, we can't find it! - if ( k_corpus_length < k_pattern_length ) - return std::make_pair(corpus_last, corpus_last); - - // Do the search - return this->do_search ( corpus_first, corpus_last ); - } - - template <typename Range> - std::pair<typename boost::range_iterator<Range>::type, typename boost::range_iterator<Range>::type> - operator () ( Range &r ) const { - return (*this) (boost::begin(r), boost::end(r)); - } - - private: -/// \cond DOXYGEN_HIDE - patIter pat_first, pat_last; - const difference_type k_pattern_length; - typename traits::skip_table_t skip_; - std::vector <difference_type> suffix_; - - /// \fn operator ( corpusIter corpus_first, corpusIter corpus_last, Pred p ) - /// \brief Searches the corpus for the pattern that was passed into the constructor - /// - /// \param corpus_first The start of the data to search (Random Access Iterator) - /// \param corpus_last One past the end of the data to search - /// \param p A predicate used for the search comparisons. - /// - template <typename corpusIter> - std::pair<corpusIter, corpusIter> - do_search ( corpusIter corpus_first, corpusIter corpus_last ) const { - /* ---- Do the matching ---- */ - corpusIter curPos = corpus_first; - const corpusIter lastPos = corpus_last - k_pattern_length; - difference_type j, k, m; - - while ( curPos <= lastPos ) { - /* while ( std::distance ( curPos, corpus_last ) >= k_pattern_length ) { */ - // Do we match right where we are? - j = k_pattern_length; - while ( pat_first [j-1] == curPos [j-1] ) { - j--; - // We matched - we're done! - if ( j == 0 ) - return std::make_pair(curPos, curPos + k_pattern_length); - } - - // Since we didn't match, figure out how far to skip forward - k = skip_ [ curPos [ j - 1 ]]; - m = j - k - 1; - if ( k < j && m > suffix_ [ j ] ) - curPos += m; - else - curPos += suffix_ [ j ]; - } - - return std::make_pair(corpus_last, corpus_last); // We didn't find anything - } - - - void build_skip_table ( patIter first, patIter last ) { - for ( std::size_t i = 0; first != last; ++first, ++i ) - skip_.insert ( *first, i ); - } - - - template<typename Iter, typename Container> - void compute_bm_prefix ( Iter first, Iter last, Container &prefix ) { - const std::size_t count = std::distance ( first, last ); - BOOST_ASSERT ( count > 0 ); - BOOST_ASSERT ( prefix.size () == count ); - - prefix[0] = 0; - std::size_t k = 0; - for ( std::size_t i = 1; i < count; ++i ) { - BOOST_ASSERT ( k < count ); - while ( k > 0 && ( first[k] != first[i] )) { - BOOST_ASSERT ( k < count ); - k = prefix [ k - 1 ]; - } - - if ( first[k] == first[i] ) - k++; - prefix [ i ] = k; - } - } - - void build_suffix_table ( patIter first, patIter last ) { - const std::size_t count = (std::size_t) std::distance ( first, last ); - - if ( count > 0 ) { // empty pattern - std::vector<typename std::iterator_traits<patIter>::value_type> reversed(count); - (void) std::reverse_copy ( first, last, reversed.begin ()); - - std::vector<difference_type> prefix (count); - compute_bm_prefix ( first, last, prefix ); - - std::vector<difference_type> prefix_reversed (count); - compute_bm_prefix ( reversed.begin (), reversed.end (), prefix_reversed ); - - for ( std::size_t i = 0; i <= count; i++ ) - suffix_[i] = count - prefix [count-1]; - - for ( std::size_t i = 0; i < count; i++ ) { - const std::size_t j = count - prefix_reversed[i]; - const difference_type k = i - prefix_reversed[i] + 1; - - if (suffix_[j] > k) - suffix_[j] = k; - } - } - } -/// \endcond - }; - - -/* Two ranges as inputs gives us four possibilities; with 2,3,3,4 parameters - Use a bit of TMP to disambiguate the 3-argument templates */ - -/// \fn boyer_moore_search ( corpusIter corpus_first, corpusIter corpus_last, -/// patIter pat_first, patIter pat_last ) -/// \brief Searches the corpus for the pattern. -/// -/// \param corpus_first The start of the data to search (Random Access Iterator) -/// \param corpus_last One past the end of the data to search -/// \param pat_first The start of the pattern to search for (Random Access Iterator) -/// \param pat_last One past the end of the data to search for -/// - template <typename patIter, typename corpusIter> - std::pair<corpusIter, corpusIter> boyer_moore_search ( - corpusIter corpus_first, corpusIter corpus_last, - patIter pat_first, patIter pat_last ) - { - boyer_moore<patIter> bm ( pat_first, pat_last ); - return bm ( corpus_first, corpus_last ); - } - - template <typename PatternRange, typename corpusIter> - std::pair<corpusIter, corpusIter> boyer_moore_search ( - corpusIter corpus_first, corpusIter corpus_last, const PatternRange &pattern ) - { - typedef typename boost::range_iterator<const PatternRange>::type pattern_iterator; - boyer_moore<pattern_iterator> bm ( boost::begin(pattern), boost::end (pattern)); - return bm ( corpus_first, corpus_last ); - } - - template <typename patIter, typename CorpusRange> - typename boost::disable_if_c< - boost::is_same<CorpusRange, patIter>::value, - std::pair<typename boost::range_iterator<CorpusRange>::type, typename boost::range_iterator<CorpusRange>::type> > - ::type - boyer_moore_search ( CorpusRange &corpus, patIter pat_first, patIter pat_last ) - { - boyer_moore<patIter> bm ( pat_first, pat_last ); - return bm (boost::begin (corpus), boost::end (corpus)); - } - - template <typename PatternRange, typename CorpusRange> - std::pair<typename boost::range_iterator<CorpusRange>::type, typename boost::range_iterator<CorpusRange>::type> - boyer_moore_search ( CorpusRange &corpus, const PatternRange &pattern ) - { - typedef typename boost::range_iterator<const PatternRange>::type pattern_iterator; - boyer_moore<pattern_iterator> bm ( boost::begin(pattern), boost::end (pattern)); - return bm (boost::begin (corpus), boost::end (corpus)); - } - - - // Creator functions -- take a pattern range, return an object - template <typename Range> - boost::algorithm::boyer_moore<typename boost::range_iterator<const Range>::type> - make_boyer_moore ( const Range &r ) { - return boost::algorithm::boyer_moore - <typename boost::range_iterator<const Range>::type> (boost::begin(r), boost::end(r)); - } - - template <typename Range> - boost::algorithm::boyer_moore<typename boost::range_iterator<Range>::type> - make_boyer_moore ( Range &r ) { - return boost::algorithm::boyer_moore - <typename boost::range_iterator<Range>::type> (boost::begin(r), boost::end(r)); - } - -}} - -#endif // BOOST_ALGORITHM_BOYER_MOORE_SEARCH_HPP diff --git a/contrib/restricted/boost/boost/algorithm/searching/boyer_moore_horspool.hpp b/contrib/restricted/boost/boost/algorithm/searching/boyer_moore_horspool.hpp deleted file mode 100644 index aacb5cb833..0000000000 --- a/contrib/restricted/boost/boost/algorithm/searching/boyer_moore_horspool.hpp +++ /dev/null @@ -1,202 +0,0 @@ -/* - Copyright (c) Marshall Clow 2010-2012. - - 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) - - For more information, see http://www.boost.org -*/ - -#ifndef BOOST_ALGORITHM_BOYER_MOORE_HORSPOOOL_SEARCH_HPP -#define BOOST_ALGORITHM_BOYER_MOORE_HORSPOOOL_SEARCH_HPP - -#include <iterator> // for std::iterator_traits - -#include <boost/assert.hpp> -#include <boost/static_assert.hpp> - -#include <boost/range/begin.hpp> -#include <boost/range/end.hpp> - -#include <boost/utility/enable_if.hpp> -#include <boost/type_traits/is_same.hpp> - -#include <boost/algorithm/searching/detail/bm_traits.hpp> -#include <boost/algorithm/searching/detail/debugging.hpp> - -// #define BOOST_ALGORITHM_BOYER_MOORE_HORSPOOL_DEBUG_HPP - -namespace boost { namespace algorithm { - -/* - A templated version of the boyer-moore-horspool searching algorithm. - - Requirements: - * Random access iterators - * The two iterator types (patIter and corpusIter) must - "point to" the same underlying type. - * Additional requirements may be imposed buy the skip table, such as: - ** Numeric type (array-based skip table) - ** Hashable type (map-based skip table) - -http://www-igm.univ-mlv.fr/%7Elecroq/string/node18.html - -*/ - - template <typename patIter, typename traits = detail::BM_traits<patIter> > - class boyer_moore_horspool { - typedef typename std::iterator_traits<patIter>::difference_type difference_type; - public: - boyer_moore_horspool ( patIter first, patIter last ) - : pat_first ( first ), pat_last ( last ), - k_pattern_length ( std::distance ( pat_first, pat_last )), - skip_ ( k_pattern_length, k_pattern_length ) { - - // Build the skip table - std::size_t i = 0; - if ( first != last ) // empty pattern? - for ( patIter iter = first; iter != last-1; ++iter, ++i ) - skip_.insert ( *iter, k_pattern_length - 1 - i ); -#ifdef BOOST_ALGORITHM_BOYER_MOORE_HORSPOOL_DEBUG_HPP - skip_.PrintSkipTable (); -#endif - } - - ~boyer_moore_horspool () {} - - /// \fn operator ( corpusIter corpus_first, corpusIter corpus_last) - /// \brief Searches the corpus for the pattern that was passed into the constructor - /// - /// \param corpus_first The start of the data to search (Random Access Iterator) - /// \param corpus_last One past the end of the data to search - /// - template <typename corpusIter> - std::pair<corpusIter, corpusIter> - operator () ( corpusIter corpus_first, corpusIter corpus_last ) const { - BOOST_STATIC_ASSERT (( boost::is_same< - typename std::iterator_traits<patIter>::value_type, - typename std::iterator_traits<corpusIter>::value_type>::value )); - - if ( corpus_first == corpus_last ) return std::make_pair(corpus_last, corpus_last); // if nothing to search, we didn't find it! - if ( pat_first == pat_last ) return std::make_pair(corpus_first, corpus_first); // empty pattern matches at start - - const difference_type k_corpus_length = std::distance ( corpus_first, corpus_last ); - // If the pattern is larger than the corpus, we can't find it! - if ( k_corpus_length < k_pattern_length ) - return std::make_pair(corpus_last, corpus_last); - - // Do the search - return this->do_search ( corpus_first, corpus_last ); - } - - template <typename Range> - std::pair<typename boost::range_iterator<Range>::type, typename boost::range_iterator<Range>::type> - operator () ( Range &r ) const { - return (*this) (boost::begin(r), boost::end(r)); - } - - private: -/// \cond DOXYGEN_HIDE - patIter pat_first, pat_last; - const difference_type k_pattern_length; - typename traits::skip_table_t skip_; - - /// \fn do_search ( corpusIter corpus_first, corpusIter corpus_last ) - /// \brief Searches the corpus for the pattern that was passed into the constructor - /// - /// \param corpus_first The start of the data to search (Random Access Iterator) - /// \param corpus_last One past the end of the data to search - /// \param k_corpus_length The length of the corpus to search - /// - template <typename corpusIter> - std::pair<corpusIter, corpusIter> - do_search ( corpusIter corpus_first, corpusIter corpus_last ) const { - corpusIter curPos = corpus_first; - const corpusIter lastPos = corpus_last - k_pattern_length; - while ( curPos <= lastPos ) { - // Do we match right where we are? - std::size_t j = k_pattern_length - 1; - while ( pat_first [j] == curPos [j] ) { - // We matched - we're done! - if ( j == 0 ) - return std::make_pair(curPos, curPos + k_pattern_length); - j--; - } - - curPos += skip_ [ curPos [ k_pattern_length - 1 ]]; - } - - return std::make_pair(corpus_last, corpus_last); - } -// \endcond - }; - -/* Two ranges as inputs gives us four possibilities; with 2,3,3,4 parameters - Use a bit of TMP to disambiguate the 3-argument templates */ - -/// \fn boyer_moore_horspool_search ( corpusIter corpus_first, corpusIter corpus_last, -/// patIter pat_first, patIter pat_last ) -/// \brief Searches the corpus for the pattern. -/// -/// \param corpus_first The start of the data to search (Random Access Iterator) -/// \param corpus_last One past the end of the data to search -/// \param pat_first The start of the pattern to search for (Random Access Iterator) -/// \param pat_last One past the end of the data to search for -/// - template <typename patIter, typename corpusIter> - std::pair<corpusIter, corpusIter> boyer_moore_horspool_search ( - corpusIter corpus_first, corpusIter corpus_last, - patIter pat_first, patIter pat_last ) - { - boyer_moore_horspool<patIter> bmh ( pat_first, pat_last ); - return bmh ( corpus_first, corpus_last ); - } - - template <typename PatternRange, typename corpusIter> - std::pair<corpusIter, corpusIter> boyer_moore_horspool_search ( - corpusIter corpus_first, corpusIter corpus_last, const PatternRange &pattern ) - { - typedef typename boost::range_iterator<const PatternRange>::type pattern_iterator; - boyer_moore_horspool<pattern_iterator> bmh ( boost::begin(pattern), boost::end (pattern)); - return bmh ( corpus_first, corpus_last ); - } - - template <typename patIter, typename CorpusRange> - typename boost::disable_if_c< - boost::is_same<CorpusRange, patIter>::value, - std::pair<typename boost::range_iterator<CorpusRange>::type, typename boost::range_iterator<CorpusRange>::type> > - ::type - boyer_moore_horspool_search ( CorpusRange &corpus, patIter pat_first, patIter pat_last ) - { - boyer_moore_horspool<patIter> bmh ( pat_first, pat_last ); - return bm (boost::begin (corpus), boost::end (corpus)); - } - - template <typename PatternRange, typename CorpusRange> - std::pair<typename boost::range_iterator<CorpusRange>::type, typename boost::range_iterator<CorpusRange>::type> - boyer_moore_horspool_search ( CorpusRange &corpus, const PatternRange &pattern ) - { - typedef typename boost::range_iterator<const PatternRange>::type pattern_iterator; - boyer_moore_horspool<pattern_iterator> bmh ( boost::begin(pattern), boost::end (pattern)); - return bmh (boost::begin (corpus), boost::end (corpus)); - } - - - // Creator functions -- take a pattern range, return an object - template <typename Range> - boost::algorithm::boyer_moore_horspool<typename boost::range_iterator<const Range>::type> - make_boyer_moore_horspool ( const Range &r ) { - return boost::algorithm::boyer_moore_horspool - <typename boost::range_iterator<const Range>::type> (boost::begin(r), boost::end(r)); - } - - template <typename Range> - boost::algorithm::boyer_moore_horspool<typename boost::range_iterator<Range>::type> - make_boyer_moore_horspool ( Range &r ) { - return boost::algorithm::boyer_moore_horspool - <typename boost::range_iterator<Range>::type> (boost::begin(r), boost::end(r)); - } - -}} - -#endif // BOOST_ALGORITHM_BOYER_MOORE_HORSPOOOL_SEARCH_HPP diff --git a/contrib/restricted/boost/boost/algorithm/searching/detail/bm_traits.hpp b/contrib/restricted/boost/boost/algorithm/searching/detail/bm_traits.hpp deleted file mode 100644 index 12143636be..0000000000 --- a/contrib/restricted/boost/boost/algorithm/searching/detail/bm_traits.hpp +++ /dev/null @@ -1,113 +0,0 @@ -/* - Copyright (c) Marshall Clow 2010-2012. - - 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) - - For more information, see http://www.boost.org -*/ - -#ifndef BOOST_ALGORITHM_SEARCH_DETAIL_BM_TRAITS_HPP -#define BOOST_ALGORITHM_SEARCH_DETAIL_BM_TRAITS_HPP - -#include <climits> // for CHAR_BIT -#include <vector> -#include <iterator> // for std::iterator_traits - -#include <boost/type_traits/make_unsigned.hpp> -#include <boost/type_traits/is_integral.hpp> -#include <boost/type_traits/remove_pointer.hpp> -#include <boost/type_traits/remove_const.hpp> - -#include <boost/array.hpp> -#ifdef BOOST_NO_CXX11_HDR_UNORDERED_MAP -#include <boost/unordered_map.hpp> -#else -#include <unordered_map> -#endif - -#include <boost/algorithm/searching/detail/debugging.hpp> - -namespace boost { namespace algorithm { namespace detail { - -// -// Default implementations of the skip tables for B-M and B-M-H -// - template<typename key_type, typename value_type, bool /*useArray*/> class skip_table; - -// General case for data searching other than bytes; use a map - template<typename key_type, typename value_type> - class skip_table<key_type, value_type, false> { - private: -#ifdef BOOST_NO_CXX11_HDR_UNORDERED_MAP - typedef boost::unordered_map<key_type, value_type> skip_map; -#else - typedef std::unordered_map<key_type, value_type> skip_map; -#endif - const value_type k_default_value; - skip_map skip_; - - public: - skip_table ( std::size_t patSize, value_type default_value ) - : k_default_value ( default_value ), skip_ ( patSize ) {} - - void insert ( key_type key, value_type val ) { - skip_ [ key ] = val; // Would skip_.insert (val) be better here? - } - - value_type operator [] ( key_type key ) const { - typename skip_map::const_iterator it = skip_.find ( key ); - return it == skip_.end () ? k_default_value : it->second; - } - - void PrintSkipTable () const { - std::cout << "BM(H) Skip Table <unordered_map>:" << std::endl; - for ( typename skip_map::const_iterator it = skip_.begin (); it != skip_.end (); ++it ) - if ( it->second != k_default_value ) - std::cout << " " << it->first << ": " << it->second << std::endl; - std::cout << std::endl; - } - }; - - -// Special case small numeric values; use an array - template<typename key_type, typename value_type> - class skip_table<key_type, value_type, true> { - private: - typedef typename boost::make_unsigned<key_type>::type unsigned_key_type; - typedef boost::array<value_type, 1U << (CHAR_BIT * sizeof(key_type))> skip_map; - skip_map skip_; - const value_type k_default_value; - public: - skip_table ( std::size_t /*patSize*/, value_type default_value ) : k_default_value ( default_value ) { - std::fill_n ( skip_.begin(), skip_.size(), default_value ); - } - - void insert ( key_type key, value_type val ) { - skip_ [ static_cast<unsigned_key_type> ( key ) ] = val; - } - - value_type operator [] ( key_type key ) const { - return skip_ [ static_cast<unsigned_key_type> ( key ) ]; - } - - void PrintSkipTable () const { - std::cout << "BM(H) Skip Table <boost:array>:" << std::endl; - for ( typename skip_map::const_iterator it = skip_.begin (); it != skip_.end (); ++it ) - if ( *it != k_default_value ) - std::cout << " " << std::distance (skip_.begin (), it) << ": " << *it << std::endl; - std::cout << std::endl; - } - }; - - template<typename Iterator> - struct BM_traits { - typedef typename std::iterator_traits<Iterator>::difference_type value_type; - typedef typename std::iterator_traits<Iterator>::value_type key_type; - typedef boost::algorithm::detail::skip_table<key_type, value_type, - boost::is_integral<key_type>::value && (sizeof(key_type)==1)> skip_table_t; - }; - -}}} // namespaces - -#endif // BOOST_ALGORITHM_SEARCH_DETAIL_BM_TRAITS_HPP diff --git a/contrib/restricted/boost/boost/algorithm/searching/detail/debugging.hpp b/contrib/restricted/boost/boost/algorithm/searching/detail/debugging.hpp deleted file mode 100644 index 3996e0f503..0000000000 --- a/contrib/restricted/boost/boost/algorithm/searching/detail/debugging.hpp +++ /dev/null @@ -1,30 +0,0 @@ -/* - Copyright (c) Marshall Clow 2010-2012. - - 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) - - For more information, see http://www.boost.org -*/ - -#ifndef BOOST_ALGORITHM_SEARCH_DETAIL_DEBUG_HPP -#define BOOST_ALGORITHM_SEARCH_DETAIL_DEBUG_HPP - -#include <iostream> -/// \cond DOXYGEN_HIDE - -namespace boost { namespace algorithm { namespace detail { - -// Debugging support - template <typename Iter> - void PrintTable ( Iter first, Iter last ) { - std::cout << std::distance ( first, last ) << ": { "; - for ( Iter iter = first; iter != last; ++iter ) - std::cout << *iter << " "; - std::cout << "}" << std::endl; - } - -}}} -/// \endcond - -#endif // BOOST_ALGORITHM_SEARCH_DETAIL_DEBUG_HPP diff --git a/contrib/restricted/boost/boost/algorithm/searching/knuth_morris_pratt.hpp b/contrib/restricted/boost/boost/algorithm/searching/knuth_morris_pratt.hpp deleted file mode 100644 index 5b5b64a729..0000000000 --- a/contrib/restricted/boost/boost/algorithm/searching/knuth_morris_pratt.hpp +++ /dev/null @@ -1,263 +0,0 @@ -/* - Copyright (c) Marshall Clow 2010-2012. - - 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) - - For more information, see http://www.boost.org -*/ - -#ifndef BOOST_ALGORITHM_KNUTH_MORRIS_PRATT_SEARCH_HPP -#define BOOST_ALGORITHM_KNUTH_MORRIS_PRATT_SEARCH_HPP - -#include <vector> -#include <iterator> // for std::iterator_traits - -#include <boost/assert.hpp> -#include <boost/static_assert.hpp> - -#include <boost/range/begin.hpp> -#include <boost/range/end.hpp> - -#include <boost/utility/enable_if.hpp> -#include <boost/type_traits/is_same.hpp> - -#include <boost/algorithm/searching/detail/debugging.hpp> - -// #define BOOST_ALGORITHM_KNUTH_MORRIS_PRATT_DEBUG - -namespace boost { namespace algorithm { - -// #define NEW_KMP - -/* - A templated version of the Knuth-Morris-Pratt searching algorithm. - - Requirements: - * Random-access iterators - * The two iterator types (I1 and I2) must "point to" the same underlying type. - - http://en.wikipedia.org/wiki/Knuth-Morris-Pratt_algorithm - http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm -*/ - - template <typename patIter> - class knuth_morris_pratt { - typedef typename std::iterator_traits<patIter>::difference_type difference_type; - public: - knuth_morris_pratt ( patIter first, patIter last ) - : pat_first ( first ), pat_last ( last ), - k_pattern_length ( std::distance ( pat_first, pat_last )), - skip_ ( k_pattern_length + 1 ) { -#ifdef NEW_KMP - preKmp ( pat_first, pat_last ); -#else - init_skip_table ( pat_first, pat_last ); -#endif -#ifdef BOOST_ALGORITHM_KNUTH_MORRIS_PRATT_DEBUG - detail::PrintTable ( skip_.begin (), skip_.end ()); -#endif - } - - ~knuth_morris_pratt () {} - - /// \fn operator ( corpusIter corpus_first, corpusIter corpus_last, Pred p ) - /// \brief Searches the corpus for the pattern that was passed into the constructor - /// - /// \param corpus_first The start of the data to search (Random Access Iterator) - /// \param corpus_last One past the end of the data to search - /// \param p A predicate used for the search comparisons. - /// - template <typename corpusIter> - std::pair<corpusIter, corpusIter> - operator () ( corpusIter corpus_first, corpusIter corpus_last ) const { - BOOST_STATIC_ASSERT (( boost::is_same< - typename std::iterator_traits<patIter>::value_type, - typename std::iterator_traits<corpusIter>::value_type>::value )); - - if ( corpus_first == corpus_last ) return std::make_pair(corpus_last, corpus_last); // if nothing to search, we didn't find it! - if ( pat_first == pat_last ) return std::make_pair(corpus_first, corpus_first); // empty pattern matches at start - - const difference_type k_corpus_length = std::distance ( corpus_first, corpus_last ); - // If the pattern is larger than the corpus, we can't find it! - if ( k_corpus_length < k_pattern_length ) - return std::make_pair(corpus_last, corpus_last); - - return do_search ( corpus_first, corpus_last, k_corpus_length ); - } - - template <typename Range> - std::pair<typename boost::range_iterator<Range>::type, typename boost::range_iterator<Range>::type> - operator () ( Range &r ) const { - return (*this) (boost::begin(r), boost::end(r)); - } - - private: -/// \cond DOXYGEN_HIDE - patIter pat_first, pat_last; - const difference_type k_pattern_length; - std::vector <difference_type> skip_; - - /// \fn operator ( corpusIter corpus_first, corpusIter corpus_last, Pred p ) - /// \brief Searches the corpus for the pattern that was passed into the constructor - /// - /// \param corpus_first The start of the data to search (Random Access Iterator) - /// \param corpus_last One past the end of the data to search - /// \param p A predicate used for the search comparisons. - /// - template <typename corpusIter> - std::pair<corpusIter, corpusIter> - do_search ( corpusIter corpus_first, corpusIter corpus_last, - difference_type k_corpus_length ) const { - difference_type match_start = 0; // position in the corpus that we're matching - -#ifdef NEW_KMP - int patternIdx = 0; - while ( match_start < k_corpus_length ) { - while ( patternIdx > -1 && pat_first[patternIdx] != corpus_first [match_start] ) - patternIdx = skip_ [patternIdx]; //<--- Shifting the pattern on mismatch - - patternIdx++; - match_start++; //<--- corpus is always increased by 1 - - if ( patternIdx >= (int) k_pattern_length ) - return corpus_first + match_start - patternIdx; - } - -#else -// At this point, we know: -// k_pattern_length <= k_corpus_length -// for all elements of skip, it holds -1 .. k_pattern_length -// -// In the loop, we have the following invariants -// idx is in the range 0 .. k_pattern_length -// match_start is in the range 0 .. k_corpus_length - k_pattern_length + 1 - - const difference_type last_match = k_corpus_length - k_pattern_length; - difference_type idx = 0; // position in the pattern we're comparing - - while ( match_start <= last_match ) { - while ( pat_first [ idx ] == corpus_first [ match_start + idx ] ) { - if ( ++idx == k_pattern_length ) - return std::make_pair(corpus_first + match_start, corpus_first + match_start + k_pattern_length); - } - // Figure out where to start searching again - // assert ( idx - skip_ [ idx ] > 0 ); // we're always moving forward - match_start += idx - skip_ [ idx ]; - idx = skip_ [ idx ] >= 0 ? skip_ [ idx ] : 0; - // assert ( idx >= 0 && idx < k_pattern_length ); - } -#endif - - // We didn't find anything - return std::make_pair(corpus_last, corpus_last); - } - - - void preKmp ( patIter first, patIter last ) { - const difference_type count = std::distance ( first, last ); - - difference_type i, j; - - i = 0; - j = skip_[0] = -1; - while (i < count) { - while (j > -1 && first[i] != first[j]) - j = skip_[j]; - i++; - j++; - if (first[i] == first[j]) - skip_[i] = skip_[j]; - else - skip_[i] = j; - } - } - - - void init_skip_table ( patIter first, patIter last ) { - const difference_type count = std::distance ( first, last ); - - difference_type j; - skip_ [ 0 ] = -1; - for ( int i = 1; i <= count; ++i ) { - j = skip_ [ i - 1 ]; - while ( j >= 0 ) { - if ( first [ j ] == first [ i - 1 ] ) - break; - j = skip_ [ j ]; - } - skip_ [ i ] = j + 1; - } - } -// \endcond - }; - - -/* Two ranges as inputs gives us four possibilities; with 2,3,3,4 parameters - Use a bit of TMP to disambiguate the 3-argument templates */ - -/// \fn knuth_morris_pratt_search ( corpusIter corpus_first, corpusIter corpus_last, -/// patIter pat_first, patIter pat_last ) -/// \brief Searches the corpus for the pattern. -/// -/// \param corpus_first The start of the data to search (Random Access Iterator) -/// \param corpus_last One past the end of the data to search -/// \param pat_first The start of the pattern to search for (Random Access Iterator) -/// \param pat_last One past the end of the data to search for -/// - template <typename patIter, typename corpusIter> - std::pair<corpusIter, corpusIter> knuth_morris_pratt_search ( - corpusIter corpus_first, corpusIter corpus_last, - patIter pat_first, patIter pat_last ) - { - knuth_morris_pratt<patIter> kmp ( pat_first, pat_last ); - return kmp ( corpus_first, corpus_last ); - } - - template <typename PatternRange, typename corpusIter> - std::pair<corpusIter, corpusIter> knuth_morris_pratt_search ( - corpusIter corpus_first, corpusIter corpus_last, const PatternRange &pattern ) - { - typedef typename boost::range_iterator<const PatternRange>::type pattern_iterator; - knuth_morris_pratt<pattern_iterator> kmp ( boost::begin(pattern), boost::end (pattern)); - return kmp ( corpus_first, corpus_last ); - } - - template <typename patIter, typename CorpusRange> - typename boost::disable_if_c< - boost::is_same<CorpusRange, patIter>::value, - std::pair<typename boost::range_iterator<CorpusRange>::type, typename boost::range_iterator<CorpusRange>::type> > - ::type - knuth_morris_pratt_search ( CorpusRange &corpus, patIter pat_first, patIter pat_last ) - { - knuth_morris_pratt<patIter> kmp ( pat_first, pat_last ); - return kmp (boost::begin (corpus), boost::end (corpus)); - } - - template <typename PatternRange, typename CorpusRange> - std::pair<typename boost::range_iterator<CorpusRange>::type, typename boost::range_iterator<CorpusRange>::type> - knuth_morris_pratt_search ( CorpusRange &corpus, const PatternRange &pattern ) - { - typedef typename boost::range_iterator<const PatternRange>::type pattern_iterator; - knuth_morris_pratt<pattern_iterator> kmp ( boost::begin(pattern), boost::end (pattern)); - return kmp (boost::begin (corpus), boost::end (corpus)); - } - - - // Creator functions -- take a pattern range, return an object - template <typename Range> - boost::algorithm::knuth_morris_pratt<typename boost::range_iterator<const Range>::type> - make_knuth_morris_pratt ( const Range &r ) { - return boost::algorithm::knuth_morris_pratt - <typename boost::range_iterator<const Range>::type> (boost::begin(r), boost::end(r)); - } - - template <typename Range> - boost::algorithm::knuth_morris_pratt<typename boost::range_iterator<Range>::type> - make_knuth_morris_pratt ( Range &r ) { - return boost::algorithm::knuth_morris_pratt - <typename boost::range_iterator<Range>::type> (boost::begin(r), boost::end(r)); - } -}} - -#endif // BOOST_ALGORITHM_KNUTH_MORRIS_PRATT_SEARCH_HPP diff --git a/contrib/restricted/boost/boost/algorithm/sort_subrange.hpp b/contrib/restricted/boost/boost/algorithm/sort_subrange.hpp deleted file mode 100644 index 7fb2cb55d0..0000000000 --- a/contrib/restricted/boost/boost/algorithm/sort_subrange.hpp +++ /dev/null @@ -1,109 +0,0 @@ -/* - Copyright (c) Marshall Clow 2008-2012. - - 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: - 28 Sep 2015 mtc First version - -*/ - -/// \file sort_subrange.hpp -/// \brief Sort a subrange -/// \author Marshall Clow -/// -/// Suggested by Sean Parent in his CppCon 2015 keynote - -#ifndef BOOST_ALGORITHM_SORT_SUBRANGE_HPP -#define BOOST_ALGORITHM_SORT_SUBRANGE_HPP - -#include <functional> // For std::less -#include <iterator> // For std::iterator_traits -#include <algorithm> // For nth_element and partial_sort - -#include <boost/range/begin.hpp> -#include <boost/range/end.hpp> - -namespace boost { namespace algorithm { - -/// \fn sort_subrange ( T const& val, -/// Iterator first, Iterator last, -/// Iterator sub_first, Iterator sub_last, -/// Pred p ) -/// \brief Sort the subrange [sub_first, sub_last) that is inside -/// the range [first, last) as if you had sorted the entire range. -/// -/// \param first The start of the larger range -/// \param last The end of the larger range -/// \param sub_first The start of the sub range -/// \param sub_last The end of the sub range -/// \param p A predicate to use to compare the values. -/// p ( a, b ) returns a boolean. -/// - template<typename Iterator, typename Pred> - void sort_subrange ( - Iterator first, Iterator last, - Iterator sub_first, Iterator sub_last, - Pred p) - { - if (sub_first == sub_last) return; // the empty sub-range is already sorted. - - if (sub_first != first) { // sub-range is at the start, don't need to partition - (void) std::nth_element(first, sub_first, last, p); - ++sub_first; - } - std::partial_sort(sub_first, sub_last, last, p); - } - - - - template<typename Iterator> - void sort_subrange (Iterator first, Iterator last, Iterator sub_first, Iterator sub_last) - { - typedef typename std::iterator_traits<Iterator>::value_type value_type; - return sort_subrange(first, last, sub_first, sub_last, std::less<value_type>()); - } - -/// range versions? - - -/// \fn partition_subrange ( T const& val, -/// Iterator first, Iterator last, -/// Iterator sub_first, Iterator sub_last, -/// Pred p ) -/// \brief Gather the elements of the subrange [sub_first, sub_last) that is -/// inside the range [first, last) as if you had sorted the entire range. -/// -/// \param first The start of the larger range -/// \param last The end of the larger range -/// \param sub_first The start of the sub range -/// \param sub_last The end of the sub range -/// \param p A predicate to use to compare the values. -/// p ( a, b ) returns a boolean. -/// - template<typename Iterator, typename Pred> - void partition_subrange ( - Iterator first, Iterator last, - Iterator sub_first, Iterator sub_last, - Pred p) - { - if (sub_first != first) { - (void) std::nth_element(first, sub_first, last, p); - ++sub_first; - } - - if (sub_last != last) - (void) std::nth_element(sub_first, sub_last, last, p); - } - - template<typename Iterator> - void partition_subrange (Iterator first, Iterator last, Iterator sub_first, Iterator sub_last) - { - typedef typename std::iterator_traits<Iterator>::value_type value_type; - return partition_subrange(first, last, sub_first, sub_last, std::less<value_type>()); - } - -}} - -#endif // BOOST_ALGORITHM_SORT_SUBRANGE_HPP diff --git a/contrib/restricted/boost/boost/algorithm/string/detail/finder_regex.hpp b/contrib/restricted/boost/boost/algorithm/string/detail/finder_regex.hpp deleted file mode 100644 index 9cb01cfaf1..0000000000 --- a/contrib/restricted/boost/boost/algorithm/string/detail/finder_regex.hpp +++ /dev/null @@ -1,122 +0,0 @@ -// Boost string_algo library find_regex.hpp header file ---------------------------// - -// Copyright Pavol Droba 2002-2003. -// -// 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) - -// See http://www.boost.org/ for updates, documentation, and revision history. - -#ifndef BOOST_STRING_FINDER_REGEX_DETAIL_HPP -#define BOOST_STRING_FINDER_REGEX_DETAIL_HPP - -#include <boost/algorithm/string/config.hpp> -#include <boost/regex.hpp> - -#include <boost/range/iterator_range_core.hpp> -#include <boost/range/begin.hpp> -#include <boost/range/end.hpp> - -namespace boost { - namespace algorithm { - namespace detail { - -// regex find functor -----------------------------------------------// - - // regex search result - template<typename IteratorT> - struct regex_search_result : - public iterator_range<IteratorT> - { - typedef regex_search_result<IteratorT> type; - typedef iterator_range<IteratorT> base_type; - typedef BOOST_STRING_TYPENAME base_type::value_type value_type; - typedef BOOST_STRING_TYPENAME base_type::difference_type difference_type; - typedef BOOST_STRING_TYPENAME base_type::const_iterator const_iterator; - typedef BOOST_STRING_TYPENAME base_type::iterator iterator; - typedef boost::match_results<iterator> match_results_type; - - // Construction - - // Construction from the match result - regex_search_result( const match_results_type& MatchResults ) : - base_type( MatchResults[0].first, MatchResults[0].second ), - m_MatchResults( MatchResults ) {} - - // Construction of empty match. End iterator has to be specified - regex_search_result( IteratorT End ) : - base_type( End, End ) {} - - regex_search_result( const regex_search_result& Other ) : - base_type( Other.begin(), Other.end() ), - m_MatchResults( Other.m_MatchResults ) {} - - // Assignment - regex_search_result& operator=( const regex_search_result& Other ) - { - base_type::operator=( Other ); - m_MatchResults=Other.m_MatchResults; - return *this; - } - - // Match result retrieval - const match_results_type& match_results() const - { - return m_MatchResults; - } - - private: - // Saved match result - match_results_type m_MatchResults; - }; - - // find_regex - /* - Regex based search functor - */ - template<typename RegExT> - struct find_regexF - { - typedef RegExT regex_type; - typedef const RegExT& regex_reference_type; - - // Construction - find_regexF( regex_reference_type Rx, match_flag_type MatchFlags = match_default ) : - m_Rx(Rx), m_MatchFlags(MatchFlags) {} - - // Operation - template< typename ForwardIteratorT > - regex_search_result<ForwardIteratorT> - operator()( - ForwardIteratorT Begin, - ForwardIteratorT End ) const - { - typedef ForwardIteratorT input_iterator_type; - typedef regex_search_result<ForwardIteratorT> result_type; - - // instantiate match result - match_results<input_iterator_type> result; - // search for a match - if ( ::boost::regex_search( Begin, End, result, m_Rx, m_MatchFlags ) ) - { - // construct a result - return result_type( result ); - } - else - { - // empty result - return result_type( End ); - } - } - - private: - regex_reference_type m_Rx; // Regexp - match_flag_type m_MatchFlags; // match flags - }; - - } // namespace detail - } // namespace algorithm -} // namespace boost - -#endif // BOOST_STRING_FIND_DETAIL_HPP diff --git a/contrib/restricted/boost/boost/algorithm/string/detail/formatter_regex.hpp b/contrib/restricted/boost/boost/algorithm/string/detail/formatter_regex.hpp deleted file mode 100644 index 5f26407bed..0000000000 --- a/contrib/restricted/boost/boost/algorithm/string/detail/formatter_regex.hpp +++ /dev/null @@ -1,61 +0,0 @@ -// Boost string_algo library formatter_regex.hpp header file ---------------------------// - -// Copyright Pavol Droba 2002-2003. -// -// 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) - -// See http://www.boost.org/ for updates, documentation, and revision history. - -#ifndef BOOST_STRING_FORMATTER_REGEX_DETAIL_HPP -#define BOOST_STRING_FORMATTER_REGEX_DETAIL_HPP - -#include <boost/algorithm/string/config.hpp> -#include <string> -#include <boost/regex.hpp> -#include <boost/algorithm/string/detail/finder_regex.hpp> - -namespace boost { - namespace algorithm { - namespace detail { - -// regex format functor -----------------------------------------// - - // regex format functor - template<typename StringT> - struct regex_formatF - { - private: - typedef StringT result_type; - typedef BOOST_STRING_TYPENAME StringT::value_type char_type; - - public: - // Construction - regex_formatF( const StringT& Fmt, match_flag_type Flags=format_default ) : - m_Fmt(Fmt), m_Flags( Flags ) {} - - template<typename InputIteratorT> - result_type operator()( - const regex_search_result<InputIteratorT>& Replace ) const - { - if ( Replace.empty() ) - { - return result_type(); - } - else - { - return Replace.match_results().format( m_Fmt, m_Flags ); - } - } - private: - const StringT& m_Fmt; - match_flag_type m_Flags; - }; - - - } // namespace detail - } // namespace algorithm -} // namespace boost - -#endif // BOOST_STRING_FORMATTER_DETAIL_HPP diff --git a/contrib/restricted/boost/boost/algorithm/string/regex.hpp b/contrib/restricted/boost/boost/algorithm/string/regex.hpp deleted file mode 100644 index a6c7c60ae8..0000000000 --- a/contrib/restricted/boost/boost/algorithm/string/regex.hpp +++ /dev/null @@ -1,646 +0,0 @@ -// Boost string_algo library regex.hpp header file ---------------------------// - -// Copyright Pavol Droba 2002-2003. -// -// 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) - -// See http://www.boost.org/ for updates, documentation, and revision history. - -#ifndef BOOST_STRING_REGEX_HPP -#define BOOST_STRING_REGEX_HPP - -#include <boost/algorithm/string/config.hpp> -#include <boost/regex.hpp> - -#include <boost/range/iterator_range_core.hpp> -#include <boost/range/begin.hpp> -#include <boost/range/end.hpp> -#include <boost/range/iterator.hpp> -#include <boost/range/as_literal.hpp> - -#include <boost/algorithm/string/find_format.hpp> -#include <boost/algorithm/string/regex_find_format.hpp> -#include <boost/algorithm/string/formatter.hpp> -#include <boost/algorithm/string/iter_find.hpp> - -/*! \file - Defines regex variants of the algorithms. -*/ - -namespace boost { - namespace algorithm { - -// find_regex -----------------------------------------------// - - //! Find regex algorithm - /*! - Search for a substring matching the given regex in the input. - - \param Input A container which will be searched. - \param Rx A regular expression - \param Flags Regex options - \return - An \c iterator_range delimiting the match. - Returned iterator is either \c RangeT::iterator or - \c RangeT::const_iterator, depending on the constness of - the input parameter. - - \note This function provides the strong exception-safety guarantee - */ - template< - typename RangeT, - typename CharT, - typename RegexTraitsT> - inline iterator_range< - BOOST_STRING_TYPENAME range_iterator<RangeT>::type > - find_regex( - RangeT& Input, - const basic_regex<CharT, RegexTraitsT>& Rx, - match_flag_type Flags=match_default ) - { - iterator_range<BOOST_STRING_TYPENAME range_iterator<RangeT>::type> lit_input(::boost::as_literal(Input)); - - return ::boost::algorithm::regex_finder(Rx,Flags)( - ::boost::begin(lit_input), ::boost::end(lit_input) ); - } - -// replace_regex --------------------------------------------------------------------// - - //! Replace regex algorithm - /*! - Search for a substring matching given regex and format it with - the specified format. - The result is a modified copy of the input. It is returned as a sequence - or copied to the output iterator. - - \param Output An output iterator to which the result will be copied - \param Input An input string - \param Rx A regular expression - \param Format Regex format definition - \param Flags Regex options - \return An output iterator pointing just after the last inserted character or - a modified copy of the input - - \note The second variant of this function provides the strong exception-safety guarantee - */ - template< - typename OutputIteratorT, - typename RangeT, - typename CharT, - typename RegexTraitsT, - typename FormatStringTraitsT, typename FormatStringAllocatorT > - inline OutputIteratorT replace_regex_copy( - OutputIteratorT Output, - const RangeT& Input, - const basic_regex<CharT, RegexTraitsT>& Rx, - const std::basic_string<CharT, FormatStringTraitsT, FormatStringAllocatorT>& Format, - match_flag_type Flags=match_default | format_default ) - { - return ::boost::algorithm::find_format_copy( - Output, - Input, - ::boost::algorithm::regex_finder( Rx, Flags ), - ::boost::algorithm::regex_formatter( Format, Flags ) ); - } - - //! Replace regex algorithm - /*! - \overload - */ - template< - typename SequenceT, - typename CharT, - typename RegexTraitsT, - typename FormatStringTraitsT, typename FormatStringAllocatorT > - inline SequenceT replace_regex_copy( - const SequenceT& Input, - const basic_regex<CharT, RegexTraitsT>& Rx, - const std::basic_string<CharT, FormatStringTraitsT, FormatStringAllocatorT>& Format, - match_flag_type Flags=match_default | format_default ) - { - return ::boost::algorithm::find_format_copy( - Input, - ::boost::algorithm::regex_finder( Rx, Flags ), - ::boost::algorithm::regex_formatter( Format, Flags ) ); - } - - //! Replace regex algorithm - /*! - Search for a substring matching given regex and format it with - the specified format. The input string is modified in-place. - - \param Input An input string - \param Rx A regular expression - \param Format Regex format definition - \param Flags Regex options - */ - template< - typename SequenceT, - typename CharT, - typename RegexTraitsT, - typename FormatStringTraitsT, typename FormatStringAllocatorT > - inline void replace_regex( - SequenceT& Input, - const basic_regex<CharT, RegexTraitsT>& Rx, - const std::basic_string<CharT, FormatStringTraitsT, FormatStringAllocatorT>& Format, - match_flag_type Flags=match_default | format_default ) - { - ::boost::algorithm::find_format( - Input, - ::boost::algorithm::regex_finder( Rx, Flags ), - ::boost::algorithm::regex_formatter( Format, Flags ) ); - } - -// replace_all_regex --------------------------------------------------------------------// - - //! Replace all regex algorithm - /*! - Format all substrings, matching given regex, with the specified format. - The result is a modified copy of the input. It is returned as a sequence - or copied to the output iterator. - - \param Output An output iterator to which the result will be copied - \param Input An input string - \param Rx A regular expression - \param Format Regex format definition - \param Flags Regex options - \return An output iterator pointing just after the last inserted character or - a modified copy of the input - - \note The second variant of this function provides the strong exception-safety guarantee - */ - template< - typename OutputIteratorT, - typename RangeT, - typename CharT, - typename RegexTraitsT, - typename FormatStringTraitsT, typename FormatStringAllocatorT > - inline OutputIteratorT replace_all_regex_copy( - OutputIteratorT Output, - const RangeT& Input, - const basic_regex<CharT, RegexTraitsT>& Rx, - const std::basic_string<CharT, FormatStringTraitsT, FormatStringAllocatorT>& Format, - match_flag_type Flags=match_default | format_default ) - { - return ::boost::algorithm::find_format_all_copy( - Output, - Input, - ::boost::algorithm::regex_finder( Rx, Flags ), - ::boost::algorithm::regex_formatter( Format, Flags ) ); - } - - //! Replace all regex algorithm - /*! - \overload - */ - template< - typename SequenceT, - typename CharT, - typename RegexTraitsT, - typename FormatStringTraitsT, typename FormatStringAllocatorT > - inline SequenceT replace_all_regex_copy( - const SequenceT& Input, - const basic_regex<CharT, RegexTraitsT>& Rx, - const std::basic_string<CharT, FormatStringTraitsT, FormatStringAllocatorT>& Format, - match_flag_type Flags=match_default | format_default ) - { - return ::boost::algorithm::find_format_all_copy( - Input, - ::boost::algorithm::regex_finder( Rx, Flags ), - ::boost::algorithm::regex_formatter( Format, Flags ) ); - } - - //! Replace all regex algorithm - /*! - Format all substrings, matching given regex, with the specified format. - The input string is modified in-place. - - \param Input An input string - \param Rx A regular expression - \param Format Regex format definition - \param Flags Regex options - */ - template< - typename SequenceT, - typename CharT, - typename RegexTraitsT, - typename FormatStringTraitsT, typename FormatStringAllocatorT > - inline void replace_all_regex( - SequenceT& Input, - const basic_regex<CharT, RegexTraitsT>& Rx, - const std::basic_string<CharT, FormatStringTraitsT, FormatStringAllocatorT>& Format, - match_flag_type Flags=match_default | format_default ) - { - ::boost::algorithm::find_format_all( - Input, - ::boost::algorithm::regex_finder( Rx, Flags ), - ::boost::algorithm::regex_formatter( Format, Flags ) ); - } - -// erase_regex --------------------------------------------------------------------// - - //! Erase regex algorithm - /*! - Remove a substring matching given regex from the input. - The result is a modified copy of the input. It is returned as a sequence - or copied to the output iterator. - - \param Output An output iterator to which the result will be copied - \param Input An input string - \param Rx A regular expression - \param Flags Regex options - \return An output iterator pointing just after the last inserted character or - a modified copy of the input - - \note The second variant of this function provides the strong exception-safety guarantee - */ - template< - typename OutputIteratorT, - typename RangeT, - typename CharT, - typename RegexTraitsT > - inline OutputIteratorT erase_regex_copy( - OutputIteratorT Output, - const RangeT& Input, - const basic_regex<CharT, RegexTraitsT>& Rx, - match_flag_type Flags=match_default ) - { - return ::boost::algorithm::find_format_copy( - Output, - Input, - ::boost::algorithm::regex_finder( Rx, Flags ), - ::boost::algorithm::empty_formatter( Input ) ); - } - - //! Erase regex algorithm - /*! - \overload - */ - template< - typename SequenceT, - typename CharT, - typename RegexTraitsT > - inline SequenceT erase_regex_copy( - const SequenceT& Input, - const basic_regex<CharT, RegexTraitsT>& Rx, - match_flag_type Flags=match_default ) - { - return ::boost::algorithm::find_format_copy( - Input, - ::boost::algorithm::regex_finder( Rx, Flags ), - ::boost::algorithm::empty_formatter( Input ) ); - } - - //! Erase regex algorithm - /*! - Remove a substring matching given regex from the input. - The input string is modified in-place. - - \param Input An input string - \param Rx A regular expression - \param Flags Regex options - */ - template< - typename SequenceT, - typename CharT, - typename RegexTraitsT > - inline void erase_regex( - SequenceT& Input, - const basic_regex<CharT, RegexTraitsT>& Rx, - match_flag_type Flags=match_default ) - { - ::boost::algorithm::find_format( - Input, - ::boost::algorithm::regex_finder( Rx, Flags ), - ::boost::algorithm::empty_formatter( Input ) ); - } - -// erase_all_regex --------------------------------------------------------------------// - - //! Erase all regex algorithm - /*! - Erase all substrings, matching given regex, from the input. - The result is a modified copy of the input. It is returned as a sequence - or copied to the output iterator. - - - \param Output An output iterator to which the result will be copied - \param Input An input string - \param Rx A regular expression - \param Flags Regex options - \return An output iterator pointing just after the last inserted character or - a modified copy of the input - - \note The second variant of this function provides the strong exception-safety guarantee - */ - template< - typename OutputIteratorT, - typename RangeT, - typename CharT, - typename RegexTraitsT > - inline OutputIteratorT erase_all_regex_copy( - OutputIteratorT Output, - const RangeT& Input, - const basic_regex<CharT, RegexTraitsT>& Rx, - match_flag_type Flags=match_default ) - { - return ::boost::algorithm::find_format_all_copy( - Output, - Input, - ::boost::algorithm::regex_finder( Rx, Flags ), - ::boost::algorithm::empty_formatter( Input ) ); - } - - //! Erase all regex algorithm - /*! - \overload - */ - template< - typename SequenceT, - typename CharT, - typename RegexTraitsT > - inline SequenceT erase_all_regex_copy( - const SequenceT& Input, - const basic_regex<CharT, RegexTraitsT>& Rx, - match_flag_type Flags=match_default ) - { - return ::boost::algorithm::find_format_all_copy( - Input, - ::boost::algorithm::regex_finder( Rx, Flags ), - ::boost::algorithm::empty_formatter( Input ) ); - } - - //! Erase all regex algorithm - /*! - Erase all substrings, matching given regex, from the input. - The input string is modified in-place. - - \param Input An input string - \param Rx A regular expression - \param Flags Regex options - */ - template< - typename SequenceT, - typename CharT, - typename RegexTraitsT> - inline void erase_all_regex( - SequenceT& Input, - const basic_regex<CharT, RegexTraitsT>& Rx, - match_flag_type Flags=match_default ) - { - ::boost::algorithm::find_format_all( - Input, - ::boost::algorithm::regex_finder( Rx, Flags ), - ::boost::algorithm::empty_formatter( Input ) ); - } - -// find_all_regex ------------------------------------------------------------------// - - //! Find all regex algorithm - /*! - This algorithm finds all substrings matching the give regex - in the input. - - Each part is copied and added as a new element to the output container. - Thus the result container must be able to hold copies - of the matches (in a compatible structure like std::string) or - a reference to it (e.g. using the iterator range class). - Examples of such a container are \c std::vector<std::string> - or \c std::list<boost::iterator_range<std::string::iterator>> - - \param Result A container that can hold copies of references to the substrings. - \param Input A container which will be searched. - \param Rx A regular expression - \param Flags Regex options - \return A reference to the result - - \note Prior content of the result will be overwritten. - - \note This function provides the strong exception-safety guarantee - */ - template< - typename SequenceSequenceT, - typename RangeT, - typename CharT, - typename RegexTraitsT > - inline SequenceSequenceT& find_all_regex( - SequenceSequenceT& Result, - const RangeT& Input, - const basic_regex<CharT, RegexTraitsT>& Rx, - match_flag_type Flags=match_default ) - { - return ::boost::algorithm::iter_find( - Result, - Input, - ::boost::algorithm::regex_finder(Rx,Flags) ); - } - -// split_regex ------------------------------------------------------------------// - - //! Split regex algorithm - /*! - Tokenize expression. This function is equivalent to C strtok. Input - sequence is split into tokens, separated by separators. Separator - is an every match of the given regex. - Each part is copied and added as a new element to the output container. - Thus the result container must be able to hold copies - of the matches (in a compatible structure like std::string) or - a reference to it (e.g. using the iterator range class). - Examples of such a container are \c std::vector<std::string> - or \c std::list<boost::iterator_range<std::string::iterator>> - - \param Result A container that can hold copies of references to the substrings. - \param Input A container which will be searched. - \param Rx A regular expression - \param Flags Regex options - \return A reference to the result - - \note Prior content of the result will be overwritten. - - \note This function provides the strong exception-safety guarantee - */ - template< - typename SequenceSequenceT, - typename RangeT, - typename CharT, - typename RegexTraitsT > - inline SequenceSequenceT& split_regex( - SequenceSequenceT& Result, - const RangeT& Input, - const basic_regex<CharT, RegexTraitsT>& Rx, - match_flag_type Flags=match_default ) - { - return ::boost::algorithm::iter_split( - Result, - Input, - ::boost::algorithm::regex_finder(Rx,Flags) ); - } - -// join_if ------------------------------------------------------------------// - -#ifndef BOOST_NO_FUNCTION_TEMPLATE_ORDERING - - //! Conditional join algorithm - /*! - This algorithm joins all strings in a 'list' into one long string. - Segments are concatenated by given separator. Only segments that - match the given regular expression will be added to the result - - This is a specialization of join_if algorithm. - - \param Input A container that holds the input strings. It must be a container-of-containers. - \param Separator A string that will separate the joined segments. - \param Rx A regular expression - \param Flags Regex options - \return Concatenated string. - - \note This function provides the strong exception-safety guarantee - */ - template< - typename SequenceSequenceT, - typename Range1T, - typename CharT, - typename RegexTraitsT > - inline typename range_value<SequenceSequenceT>::type - join_if( - const SequenceSequenceT& Input, - const Range1T& Separator, - const basic_regex<CharT, RegexTraitsT>& Rx, - match_flag_type Flags=match_default ) - { - // Define working types - typedef typename range_value<SequenceSequenceT>::type ResultT; - typedef typename range_const_iterator<SequenceSequenceT>::type InputIteratorT; - - // Parse input - InputIteratorT itBegin=::boost::begin(Input); - InputIteratorT itEnd=::boost::end(Input); - - // Construct container to hold the result - ResultT Result; - - - // Roll to the first element that will be added - while( - itBegin!=itEnd && - !::boost::regex_match(::boost::begin(*itBegin), ::boost::end(*itBegin), Rx, Flags)) ++itBegin; - - // Add this element - if(itBegin!=itEnd) - { - detail::insert(Result, ::boost::end(Result), *itBegin); - ++itBegin; - } - - for(;itBegin!=itEnd; ++itBegin) - { - if(::boost::regex_match(::boost::begin(*itBegin), ::boost::end(*itBegin), Rx, Flags)) - { - // Add separator - detail::insert(Result, ::boost::end(Result), ::boost::as_literal(Separator)); - // Add element - detail::insert(Result, ::boost::end(Result), *itBegin); - } - } - - return Result; - } - -#else // BOOST_NO_FUNCTION_TEMPLATE_ORDERING - - //! Conditional join algorithm - /*! - This algorithm joins all strings in a 'list' into one long string. - Segments are concatenated by given separator. Only segments that - match the given regular expression will be added to the result - - This is a specialization of join_if algorithm. - - \param Input A container that holds the input strings. It must be a container-of-containers. - \param Separator A string that will separate the joined segments. - \param Rx A regular expression - \param Flags Regex options - \return Concatenated string. - - \note This function provides the strong exception-safety guarantee - */ - template< - typename SequenceSequenceT, - typename Range1T, - typename CharT, - typename RegexTraitsT > - inline typename range_value<SequenceSequenceT>::type - join_if_regex( - const SequenceSequenceT& Input, - const Range1T& Separator, - const basic_regex<CharT, RegexTraitsT>& Rx, - match_flag_type Flags=match_default ) - { - // Define working types - typedef typename range_value<SequenceSequenceT>::type ResultT; - typedef typename range_const_iterator<SequenceSequenceT>::type InputIteratorT; - - // Parse input - InputIteratorT itBegin=::boost::begin(Input); - InputIteratorT itEnd=::boost::end(Input); - - // Construct container to hold the result - ResultT Result; - - - // Roll to the first element that will be added - while( - itBegin!=itEnd && - !::boost::regex_match(::boost::begin(*itBegin), ::boost::end(*itBegin), Rx, Flags)) ++itBegin; - - // Add this element - if(itBegin!=itEnd) - { - detail::insert(Result, ::boost::end(Result), *itBegin); - ++itBegin; - } - - for(;itBegin!=itEnd; ++itBegin) - { - if(::boost::regex_match(::boost::begin(*itBegin), ::boost::end(*itBegin), Rx, Flags)) - { - // Add separator - detail::insert(Result, ::boost::end(Result), ::boost::as_literal(Separator)); - // Add element - detail::insert(Result, ::boost::end(Result), *itBegin); - } - } - - return Result; - } - - -#endif // BOOST_NO_FUNCTION_TEMPLATE_ORDERING - - } // namespace algorithm - - // pull names into the boost namespace - using algorithm::find_regex; - using algorithm::replace_regex; - using algorithm::replace_regex_copy; - using algorithm::replace_all_regex; - using algorithm::replace_all_regex_copy; - using algorithm::erase_regex; - using algorithm::erase_regex_copy; - using algorithm::erase_all_regex; - using algorithm::erase_all_regex_copy; - using algorithm::find_all_regex; - using algorithm::split_regex; - -#ifndef BOOST_NO_FUNCTION_TEMPLATE_ORDERING - using algorithm::join_if; -#else // BOOST_NO_FUNCTION_TEMPLATE_ORDERING - using algorithm::join_if_regex; -#endif // BOOST_NO_FUNCTION_TEMPLATE_ORDERING - -} // namespace boost - - -#endif // BOOST_STRING_REGEX_HPP diff --git a/contrib/restricted/boost/boost/algorithm/string/regex_find_format.hpp b/contrib/restricted/boost/boost/algorithm/string/regex_find_format.hpp deleted file mode 100644 index 409afc2ba0..0000000000 --- a/contrib/restricted/boost/boost/algorithm/string/regex_find_format.hpp +++ /dev/null @@ -1,90 +0,0 @@ -// Boost string_algo library regex_find_format.hpp header file ---------------------------// - -// Copyright Pavol Droba 2002-2003. -// -// 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) - -// See http://www.boost.org/ for updates, documentation, and revision history. - -#ifndef BOOST_STRING_REGEX_FIND_FORMAT_HPP -#define BOOST_STRING_REGEX_FIND_FORMAT_HPP - -#include <boost/algorithm/string/config.hpp> -#include <boost/regex.hpp> -#include <boost/algorithm/string/detail/finder_regex.hpp> -#include <boost/algorithm/string/detail/formatter_regex.hpp> - -/*! \file - Defines the \c regex_finder and \c regex_formatter generators. These two functors - are designed to work together. \c regex_formatter uses additional information - about a match contained in the regex_finder search result. -*/ - -namespace boost { - namespace algorithm { - -// regex_finder -----------------------------------------------// - - //! "Regex" finder - /*! - Construct the \c regex_finder. Finder uses the regex engine to search - for a match. - Result is given in \c regex_search_result. This is an extension - of the iterator_range. In addition it contains match results - from the \c regex_search algorithm. - - \param Rx A regular expression - \param MatchFlags Regex search options - \return An instance of the \c regex_finder object - */ - template< - typename CharT, - typename RegexTraitsT> - inline detail::find_regexF< basic_regex<CharT, RegexTraitsT> > - regex_finder( - const basic_regex<CharT, RegexTraitsT>& Rx, - match_flag_type MatchFlags=match_default ) - { - return detail:: - find_regexF< - basic_regex<CharT, RegexTraitsT> >( Rx, MatchFlags ); - } - -// regex_formater ---------------------------------------------// - - //! Regex formatter - /*! - Construct the \c regex_formatter. Regex formatter uses the regex engine to - format a match found by the \c regex_finder. - This formatted it designed to closely cooperate with \c regex_finder. - - \param Format Regex format definition - \param Flags Format flags - \return An instance of the \c regex_formatter functor - */ - template< - typename CharT, - typename TraitsT, typename AllocT > - inline detail::regex_formatF< std::basic_string< CharT, TraitsT, AllocT > > - regex_formatter( - const std::basic_string<CharT, TraitsT, AllocT>& Format, - match_flag_type Flags=format_default ) - { - return - detail::regex_formatF< std::basic_string<CharT, TraitsT, AllocT> >( - Format, - Flags ); - } - - } // namespace algorithm - - // pull the names to the boost namespace - using algorithm::regex_finder; - using algorithm::regex_formatter; - -} // namespace boost - - -#endif // BOOST_STRING_REGEX_FIND_FORMAT_HPP diff --git a/contrib/restricted/boost/boost/algorithm/string/std/rope_traits.hpp b/contrib/restricted/boost/boost/algorithm/string/std/rope_traits.hpp deleted file mode 100644 index 637059a550..0000000000 --- a/contrib/restricted/boost/boost/algorithm/string/std/rope_traits.hpp +++ /dev/null @@ -1,81 +0,0 @@ -// Boost string_algo library string_traits.hpp header file ---------------------------// - -// Copyright Pavol Droba 2002-2003. -// -// 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) - -// See http://www.boost.org/ for updates, documentation, and revision history. - -#ifndef BOOST_STRING_STD_ROPE_TRAITS_HPP -#define BOOST_STRING_STD_ROPE_TRAITS_HPP - -#include <boost/algorithm/string/yes_no_type.hpp> -#include <rope> -#include <boost/algorithm/string/sequence_traits.hpp> - -namespace boost { - namespace algorithm { - -// SGI's std::rope<> traits -----------------------------------------------// - - - // native replace trait - template<typename T, typename TraitsT, typename AllocT> - class has_native_replace< std::rope<T,TraitsT,AllocT> > - { - public: -#if BOOST_WORKAROUND( __IBMCPP__, <= 600 ) - enum { value = true }; -#else - BOOST_STATIC_CONSTANT(bool, value=true); -#endif // BOOST_WORKAROUND( __IBMCPP__, <= 600 ) - typedef mpl::bool_<value> type; - }; - - // stable iterators trait - template<typename T, typename TraitsT, typename AllocT> - class has_stable_iterators< std::rope<T,TraitsT,AllocT> > - { - public: -#if BOOST_WORKAROUND( __IBMCPP__, <= 600 ) - enum { value = true }; -#else - BOOST_STATIC_CONSTANT(bool, value=true); -#endif // BOOST_WORKAROUND( __IBMCPP__, <= 600 ) - typedef mpl::bool_<value> type; - }; - - // const time insert trait - template<typename T, typename TraitsT, typename AllocT> - class has_const_time_insert< std::rope<T,TraitsT,AllocT> > - { - public: -#if BOOST_WORKAROUND( __IBMCPP__, <= 600 ) - enum { value = true }; -#else - BOOST_STATIC_CONSTANT(bool, value=true); -#endif // BOOST_WORKAROUND( __IBMCPP__, <= 600 ) - typedef mpl::bool_<value> type; - }; - - // const time erase trait - template<typename T, typename TraitsT, typename AllocT> - class has_const_time_erase< std::rope<T,TraitsT,AllocT> > - { - public: -#if BOOST_WORKAROUND( __IBMCPP__, <= 600 ) - enum { value = true }; -#else - BOOST_STATIC_CONSTANT(bool, value=true); -#endif // BOOST_WORKAROUND( __IBMCPP__, <= 600 ) - typedef mpl::bool_<value> type; - }; - - - } // namespace algorithm -} // namespace boost - - -#endif // BOOST_STRING_ROPE_TRAITS_HPP diff --git a/contrib/restricted/boost/boost/algorithm/string/trim_all.hpp b/contrib/restricted/boost/boost/algorithm/string/trim_all.hpp deleted file mode 100644 index a616f7f33e..0000000000 --- a/contrib/restricted/boost/boost/algorithm/string/trim_all.hpp +++ /dev/null @@ -1,217 +0,0 @@ -// Boost string_algo library trim.hpp header file ---------------------------// - -// Copyright Pavol Droba 2002-2003. -// -// 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) - -// See http://www.boost.org/ for updates, documentation, and revision history. - -#ifndef BOOST_STRING_TRIM_ALL_HPP -#define BOOST_STRING_TRIM_ALL_HPP - -#include <boost/algorithm/string/config.hpp> - -#include <boost/algorithm/string/trim.hpp> -#include <boost/algorithm/string/classification.hpp> -#include <boost/algorithm/string/find_format.hpp> -#include <boost/algorithm/string/formatter.hpp> -#include <boost/algorithm/string/finder.hpp> -#include <locale> - -/*! \file - Defines trim_all algorithms. - - Just like \c trim, \c trim_all removes all trailing and leading spaces from a - sequence (string). In addition, spaces in the middle of the sequence are truncated - to just one character. Space is recognized using given locales. - - \c trim_fill acts as trim_all, but the spaces in the middle are replaces with - a user-define sequence of character. - - Parametric (\c _if) variants use a predicate (functor) to select which characters - are to be trimmed.. - Functions take a selection predicate as a parameter, which is used to determine - whether a character is a space. Common predicates are provided in classification.hpp header. - -*/ - -namespace boost { - namespace algorithm { - - // multi line trim ----------------------------------------------- // - - //! Trim All - parametric - /*! - Remove all leading and trailing spaces from the input and - compress all other spaces to a single character. - The result is a trimmed copy of the input - - \param Input An input sequence - \param IsSpace A unary predicate identifying spaces - \return A trimmed copy of the input - */ - template<typename SequenceT, typename PredicateT> - inline SequenceT trim_all_copy_if(const SequenceT& Input, PredicateT IsSpace) - { - return - ::boost::find_format_all_copy( - ::boost::trim_copy_if(Input, IsSpace), - ::boost::token_finder(IsSpace, ::boost::token_compress_on), - ::boost::dissect_formatter(::boost::head_finder(1))); - } - - - //! Trim All - /*! - Remove all leading and trailing spaces from the input and - compress all other spaces to a single character. - The input sequence is modified in-place. - - \param Input An input sequence - \param IsSpace A unary predicate identifying spaces - */ - template<typename SequenceT, typename PredicateT> - inline void trim_all_if(SequenceT& Input, PredicateT IsSpace) - { - ::boost::trim_if(Input, IsSpace); - ::boost::find_format_all( - Input, - ::boost::token_finder(IsSpace, ::boost::token_compress_on), - ::boost::dissect_formatter(::boost::head_finder(1))); - } - - - //! Trim All - /*! - Remove all leading and trailing spaces from the input and - compress all other spaces to a single character. - The result is a trimmed copy of the input - - \param Input An input sequence - \param Loc A locale used for 'space' classification - \return A trimmed copy of the input - */ - template<typename SequenceT> - inline SequenceT trim_all_copy(const SequenceT& Input, const std::locale& Loc =std::locale()) - { - return trim_all_copy_if(Input, ::boost::is_space(Loc)); - } - - - //! Trim All - /*! - Remove all leading and trailing spaces from the input and - compress all other spaces to a single character. - The input sequence is modified in-place. - - \param Input An input sequence - \param Loc A locale used for 'space' classification - \return A trimmed copy of the input - */ - template<typename SequenceT> - inline void trim_all(SequenceT& Input, const std::locale& Loc =std::locale()) - { - trim_all_if(Input, ::boost::is_space(Loc)); - } - - - //! Trim Fill - parametric - /*! - Remove all leading and trailing spaces from the input and - replace all every block of consecutive spaces with a fill string - defined by user. - The result is a trimmed copy of the input - - \param Input An input sequence - \param Fill A string used to fill the inner spaces - \param IsSpace A unary predicate identifying spaces - \return A trimmed copy of the input - */ - template<typename SequenceT, typename RangeT, typename PredicateT> - inline SequenceT trim_fill_copy_if(const SequenceT& Input, const RangeT& Fill, PredicateT IsSpace) - { - return - ::boost::find_format_all_copy( - ::boost::trim_copy_if(Input, IsSpace), - ::boost::token_finder(IsSpace, ::boost::token_compress_on), - ::boost::const_formatter(::boost::as_literal(Fill))); - } - - - //! Trim Fill - /*! - Remove all leading and trailing spaces from the input and - replace all every block of consecutive spaces with a fill string - defined by user. - The input sequence is modified in-place. - - \param Input An input sequence - \param Fill A string used to fill the inner spaces - \param IsSpace A unary predicate identifying spaces - */ - template<typename SequenceT, typename RangeT, typename PredicateT> - inline void trim_fill_if(SequenceT& Input, const RangeT& Fill, PredicateT IsSpace) - { - ::boost::trim_if(Input, IsSpace); - ::boost::find_format_all( - Input, - ::boost::token_finder(IsSpace, ::boost::token_compress_on), - ::boost::const_formatter(::boost::as_literal(Fill))); - } - - - //! Trim Fill - /*! - Remove all leading and trailing spaces from the input and - replace all every block of consecutive spaces with a fill string - defined by user. - The result is a trimmed copy of the input - - \param Input An input sequence - \param Fill A string used to fill the inner spaces - \param Loc A locale used for 'space' classification - \return A trimmed copy of the input - */ - template<typename SequenceT, typename RangeT> - inline SequenceT trim_fill_copy(const SequenceT& Input, const RangeT& Fill, const std::locale& Loc =std::locale()) - { - return trim_fill_copy_if(Input, Fill, ::boost::is_space(Loc)); - } - - - //! Trim Fill - /*! - Remove all leading and trailing spaces from the input and - replace all every block of consecutive spaces with a fill string - defined by user. - The input sequence is modified in-place. - - \param Input An input sequence - \param Fill A string used to fill the inner spaces - \param Loc A locale used for 'space' classification - \return A trimmed copy of the input - */ - template<typename SequenceT, typename RangeT> - inline void trim_fill(SequenceT& Input, const RangeT& Fill, const std::locale& Loc =std::locale()) - { - trim_fill_if(Input, Fill, ::boost::is_space(Loc)); - } - - - } // namespace algorithm - - // pull names to the boost namespace - using algorithm::trim_all; - using algorithm::trim_all_if; - using algorithm::trim_all_copy; - using algorithm::trim_all_copy_if; - using algorithm::trim_fill; - using algorithm::trim_fill_if; - using algorithm::trim_fill_copy; - using algorithm::trim_fill_copy_if; - -} // namespace boost - -#endif // BOOST_STRING_TRIM_ALL_HPP diff --git a/contrib/restricted/boost/boost/algorithm/string_regex.hpp b/contrib/restricted/boost/boost/algorithm/string_regex.hpp deleted file mode 100644 index 791aa18481..0000000000 --- a/contrib/restricted/boost/boost/algorithm/string_regex.hpp +++ /dev/null @@ -1,23 +0,0 @@ -// Boost string_algo library string_regex.hpp header file ---------------------------// - -// Copyright Pavol Droba 2002-2004. -// -// 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) - -// See http://www.boost.org/ for updates, documentation, and revision history. - -#ifndef BOOST_STRING_ALGO_REGEX_HPP -#define BOOST_STRING_ALGO_REGEX_HPP - -/*! \file - Cumulative include for string_algo library. - In addition to string.hpp contains also regex-related stuff. -*/ - -#include <boost/regex.hpp> -#include <boost/algorithm/string.hpp> -#include <boost/algorithm/string/regex.hpp> - -#endif // BOOST_STRING_ALGO_REGEX_HPP |