diff options
Diffstat (limited to 'boost/algorithm')
22 files changed, 2600 insertions, 7 deletions
diff --git a/boost/algorithm/clamp.hpp b/boost/algorithm/clamp.hpp new file mode 100644 index 0000000000..ae98d15d2f --- /dev/null +++ b/boost/algorithm/clamp.hpp @@ -0,0 +1,175 @@ +/* + 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 lo, +/// std::iterator_traits<InputIterator>::value_type 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 lo, + typename std::iterator_traits<InputIterator>::value_type 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 lo, +/// typename std::iterator_traits<typename boost::range_iterator<const Range>::type>::value_type 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 lo, + typename std::iterator_traits<typename boost::range_iterator<const Range>::type>::value_type 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 lo, +/// std::iterator_traits<InputIterator>::value_type 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 lo, + typename std::iterator_traits<InputIterator>::value_type 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 lo, +/// typename std::iterator_traits<typename boost::range_iterator<const Range>::type>::value_type 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 lo, + typename std::iterator_traits<typename boost::range_iterator<const Range>::type>::value_type hi, + Pred p ) + { + return clamp_range ( boost::begin ( r ), boost::end ( r ), out, lo, hi, p ); + } + + +}} + +#endif // BOOST_ALGORITHM_CLAMP_HPP diff --git a/boost/algorithm/cxx11/all_of.hpp b/boost/algorithm/cxx11/all_of.hpp new file mode 100644 index 0000000000..b76cb3f010 --- /dev/null +++ b/boost/algorithm/cxx11/all_of.hpp @@ -0,0 +1,91 @@ +/* + 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 all_of.hpp +/// \brief Test ranges to see if all elements match a value or predicate. +/// \author Marshall Clow + +#ifndef BOOST_ALGORITHM_ALL_OF_HPP +#define BOOST_ALGORITHM_ALL_OF_HPP + +#include <algorithm> // for std::all_of, if available +#include <boost/range/begin.hpp> +#include <boost/range/end.hpp> + +namespace boost { namespace algorithm { + +#if __cplusplus >= 201103L +// Use the C++11 versions of all_of if it is available +using std::all_of; // Section 25.2.1 +#else +/// \fn all_of ( InputIterator first, InputIterator last, Predicate p ) +/// \return true if all elements in [first, last) satisfy the predicate 'p' +/// \note returns true on an empty range +/// +/// \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 +/// +/// \note This function is part of the C++2011 standard library. +/// We will use the standard one if it is available, +/// otherwise we have our own implementation. +template<typename InputIterator, typename Predicate> +bool all_of ( InputIterator first, InputIterator last, Predicate p ) +{ + for ( ; first != last; ++first ) + if ( !p(*first)) + return false; + return true; +} +#endif + +/// \fn all_of ( const Range &r, Predicate p ) +/// \return true if all elements in the range satisfy the predicate 'p' +/// \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 all_of ( const Range &r, Predicate p ) +{ + return boost::algorithm::all_of ( boost::begin (r), boost::end (r), p ); +} + +/// \fn all_of_equal ( InputIterator first, InputIterator last, const T &val ) +/// \return true if all 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 T> +bool all_of_equal ( InputIterator first, InputIterator last, const T &val ) +{ + for ( ; first != last; ++first ) + if ( val != *first ) + return false; + return true; +} + +/// \fn all_of_equal ( const Range &r, const T &val ) +/// \return true if all 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 T> +bool all_of_equal ( const Range &r, const T &val ) +{ + return boost::algorithm::all_of_equal ( boost::begin (r), boost::end (r), val ); +} + +}} // namespace boost and algorithm + +#endif // BOOST_ALGORITHM_ALL_OF_HPP diff --git a/boost/algorithm/cxx11/any_of.hpp b/boost/algorithm/cxx11/any_of.hpp new file mode 100644 index 0000000000..c3ab3ce59f --- /dev/null +++ b/boost/algorithm/cxx11/any_of.hpp @@ -0,0 +1,90 @@ +/* + 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 <algorithm> // for std::any_of, if available +#include <boost/range/begin.hpp> +#include <boost/range/end.hpp> + +namespace boost { namespace algorithm { + +// Use the C++11 versions of any_of if it is available +#if __cplusplus >= 201103L +using std::any_of; // Section 25.2.2 +#else +/// \fn any_of ( InputIterator first, InputIterator last, Predicate p ) +/// \return true if any of the elements in [first, last) satisfy the predicate +/// \note returns false on an empty range +/// +/// \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; +} +#endif + +/// \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/boost/algorithm/cxx11/copy_if.hpp b/boost/algorithm/cxx11/copy_if.hpp new file mode 100644 index 0000000000..6d0ba00bae --- /dev/null +++ b/boost/algorithm/cxx11/copy_if.hpp @@ -0,0 +1,133 @@ +/* + 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 <algorithm> // for std::copy_if, if available +#include <boost/range/begin.hpp> +#include <boost/range/end.hpp> + +namespace boost { namespace algorithm { + +#if __cplusplus >= 201103L +// Use the C++11 versions of copy_if if it is available +using std::copy_if; // Section 25.3.1 +#else +/// \fn copy_if ( InputIterator first, InputIterator last, OutputIterator result, Predicate p ) +/// \brief Copies all the elements from the input range that satisfy the +/// predicate to the output range. +/// \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. +/// We will use the standard one if it is available, +/// otherwise we have our own implementation. +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; +} +#endif + +/// \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 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> +OutputIterator copy_while ( InputIterator first, InputIterator last, + OutputIterator result, Predicate p ) +{ + for ( ; first != last && p(*first); ++first ) + *result++ = first; + return result; +} + +/// \fn copy_while ( const Range &r, OutputIterator result, Predicate p ) +/// \brief Copies all the elements at the start of the input range that +/// satisfy the predicate to the output range. +/// \return The updated output iterator +/// +/// \param r The input range +/// \param result An output iterator to write the results into +/// \param p A predicate for testing the elements of the range +/// +template<typename Range, typename OutputIterator, typename Predicate> +OutputIterator copy_while ( const Range &r, OutputIterator result, Predicate p ) +{ + 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> +OutputIterator copy_until ( InputIterator first, InputIterator last, OutputIterator result, Predicate p ) +{ + for ( ; first != last && !p(*first); ++first ) + *result++ = first; + return 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> +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/boost/algorithm/cxx11/copy_n.hpp b/boost/algorithm/cxx11/copy_n.hpp new file mode 100644 index 0000000000..0ea53bd23f --- /dev/null +++ b/boost/algorithm/cxx11/copy_n.hpp @@ -0,0 +1,44 @@ +/* + 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 + +#include <algorithm> // for std::copy_n, if available + +namespace boost { namespace algorithm { + +#if __cplusplus >= 201103L +// Use the C++11 versions of copy_n if it is available +using std::copy_n; // Section 25.3.1 +#else +/// \fn copy_n ( InputIterator first, Size n, OutputIterator result ) +/// \brief Copies exactly n (n > 0) elements from the range starting at first to +/// the range starting at result. +/// \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. +/// We will use the standard one if it is available, +/// otherwise we have our own implementation. +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; +} +#endif +}} // namespace boost and algorithm + +#endif // BOOST_ALGORITHM_COPY_IF_HPP diff --git a/boost/algorithm/cxx11/find_if_not.hpp b/boost/algorithm/cxx11/find_if_not.hpp new file mode 100644 index 0000000000..4beed00083 --- /dev/null +++ b/boost/algorithm/cxx11/find_if_not.hpp @@ -0,0 +1,60 @@ +/* + 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 <algorithm> // for std::find_if_not, if it exists + +#include <boost/range/begin.hpp> +#include <boost/range/end.hpp> + +namespace boost { namespace algorithm { + +#if __cplusplus >= 201103L +// Use the C++11 versions of find_if_not if it is available +using std::find_if_not; // Section 25.2.5 +#else +/// \fn find_if_not(InputIterator first, InputIterator last, Predicate p) +/// \brief Finds the first element in the sequence that does not satisfy the predicate. +/// \return The iterator pointing to the desired element. +/// +/// \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. +/// We will use the standard one if it is available, +/// otherwise we have our own implementation. +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; +} +#endif + +/// \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/boost/algorithm/cxx11/iota.hpp b/boost/algorithm/cxx11/iota.hpp new file mode 100644 index 0000000000..b4f0dafa6d --- /dev/null +++ b/boost/algorithm/cxx11/iota.hpp @@ -0,0 +1,74 @@ +/* + 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 <numeric> + +#include <boost/range/begin.hpp> +#include <boost/range/end.hpp> + +namespace boost { namespace algorithm { + +#if __cplusplus >= 201103L +// Use the C++11 versions of iota if it is available +using std::iota; // Section 26.7.6 +#else +/// \fn iota ( ForwardIterator first, ForwardIterator last, T value ) +/// \brief Generates an increasing sequence of values, and stores them in [first, last) +/// +/// \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. +/// We will use the standard one if it is available, +/// otherwise we have our own implementation. +template <typename ForwardIterator, typename T> +void iota ( ForwardIterator first, ForwardIterator last, T value ) +{ + for ( ; first != last; ++first, ++value ) + *first = value; +} +#endif + +/// \fn iota ( Range &r, T value ) +/// \brief Generates an increasing sequence of values, and stores them in the input Range. +/// +/// \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 ) +{ + while ( n-- > 0 ) + *out++ = value++; + + return out; +} + +}} + +#endif // BOOST_ALGORITHM_IOTA_HPP diff --git a/boost/algorithm/cxx11/is_partitioned.hpp b/boost/algorithm/cxx11/is_partitioned.hpp new file mode 100644 index 0000000000..d647183a8a --- /dev/null +++ b/boost/algorithm/cxx11/is_partitioned.hpp @@ -0,0 +1,65 @@ +/* + 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 <algorithm> // for std::is_partitioned, if available + +#include <boost/range/begin.hpp> +#include <boost/range/end.hpp> + +namespace boost { namespace algorithm { + +#if __cplusplus >= 201103L +// Use the C++11 versions of is_partitioned if it is available +using std::is_partitioned; // Section 25.3.13 +#else +/// \fn is_partitioned ( InputIterator first, InputIterator last, UnaryPredicate p ) +/// \brief Tests to see if a sequence is partititioned according to a predicate +/// +/// \param first The start of the input sequence +/// \param last One past the end of the input sequence +/// \param p The predicicate to test the values with +/// \note This function is part of the C++2011 standard library. +/// We will use the standard one if it is available, +/// otherwise we have our own implementation. +template <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; +} +#endif + +/// \fn is_partitioned ( const Range &r, UnaryPredicate p ) +/// \brief Generates an increasing sequence of values, and stores them in the input Range. +/// +/// \param r The input range +/// \param p The predicicate to test the values with +/// +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/boost/algorithm/cxx11/is_permutation.hpp b/boost/algorithm/cxx11/is_permutation.hpp new file mode 100644 index 0000000000..33cb712378 --- /dev/null +++ b/boost/algorithm/cxx11/is_permutation.hpp @@ -0,0 +1,139 @@ +/* + 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_PERMUTATION_HPP +#define BOOST_ALGORITHM_IS_PERMUTATION_HPP + +#include <algorithm> // for std::less, tie, mismatch and is_permutation (if available) +#include <utility> // for std::make_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> +#include <boost/tr1/tr1/tuple> // for tie + +namespace boost { namespace algorithm { + +#if __cplusplus >= 201103L +// Use the C++11 versions of is_permutation if it is available +using std::is_permutation; // Section 25.2.12 +#else +/// \cond DOXYGEN_HIDE +namespace detail { + template <typename Predicate, typename Iterator> + 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_; + }; +} +/// \endcond + + +/// \fn is_permutation ( ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 first2, BinaryPredicate p ) +/// \brief Tests to see if a the sequence [first,last) is a permutation of the sequence starting at first2 +/// +/// \param first The start of the input sequence +/// \param last 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. +/// We will use the standard one if it is available, +/// otherwise we have our own implementation. +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::tie (first1, first2) = std::mismatch (first1, last1, first2, p); + std::pair<ForwardIterator1, ForwardIterator2> eq = std::mismatch (first1, last1, first2, p); + first1 = eq.first; + first2 = eq.second; + if ( first1 != last1 ) { + // Create last2 + ForwardIterator2 last2 = first2; + std::advance ( last2, std::distance (first1, last1)); + + // for each unique value in the sequence [first1,last1), count how many times + // it occurs, and make sure it occurs the same number of times in [first2, last2) + for ( ForwardIterator1 iter = first1; iter != last1; ++iter ) { + detail::value_predicate<BinaryPredicate, ForwardIterator1> pred ( p, iter ); + + /* For each value we haven't seen yet... */ + if ( std::find_if ( first1, iter, pred ) == iter ) { + std::size_t dest_count = std::count_if ( first2, last2, pred ); + if ( dest_count == 0 || dest_count != (std::size_t) std::count_if ( iter, last1, pred )) + return false; + } + } + } + + return true; +} + +/// \fn is_permutation ( ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 first2 ) +/// \brief Tests to see if a the sequence [first,last) is a permutation of the sequence starting at first2 +/// +/// \param first The start of the input sequence +/// \param last One past the end of the input sequence +/// \param first2 The start of the second sequence +/// \note This function is part of the C++2011 standard library. +/// We will use the standard one if it is available, +/// otherwise we have our own implementation. +template< class ForwardIterator1, class ForwardIterator2 > +bool is_permutation ( ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 first2 ) +{ +// How should I deal with the idea that ForwardIterator1::value_type +// and ForwardIterator2::value_type could be different? Define my own comparison predicate? + return boost::algorithm::is_permutation ( first, last, first2, + std::equal_to<typename std::iterator_traits<ForwardIterator1>::value_type> ()); +} + +#endif + +/// \fn is_permutation ( const Range &r, ForwardIterator first2 ) +/// \brief Tests to see if a the sequence [first,last) is a permutation of the sequence starting at first2 +/// +/// \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 a 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_PERMUTATION_HPP diff --git a/boost/algorithm/cxx11/is_sorted.hpp b/boost/algorithm/cxx11/is_sorted.hpp new file mode 100644 index 0000000000..c9bc65fbe9 --- /dev/null +++ b/boost/algorithm/cxx11/is_sorted.hpp @@ -0,0 +1,287 @@ +// 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 <algorithm> +#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 { + +#if __cplusplus >= 201103L +// Use the C++11 versions of is_sorted/is_sorted_until if they are available +using std::is_sorted_until; // Section 25.4.1.5 +using std::is_sorted; // Section 25.4.1.5 +#else +/// \fn is_sorted_until ( ForwardIterator first, ForwardIterator last, Pred p ) +/// \return the point in the sequence [first, last) where the elements are unordered +/// (according to the comparison predicate 'p'). +/// +/// \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; + } +#endif + +/// +/// -- 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/boost/algorithm/cxx11/none_of.hpp b/boost/algorithm/cxx11/none_of.hpp new file mode 100644 index 0000000000..feae9919fc --- /dev/null +++ b/boost/algorithm/cxx11/none_of.hpp @@ -0,0 +1,88 @@ +/* + 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 <algorithm> // for std::none_of, if available +#include <boost/range/begin.hpp> +#include <boost/range/end.hpp> + +namespace boost { namespace algorithm { + +// Use the C++11 versions of the none_of if it is available +#if __cplusplus >= 201103L +using std::none_of; // Section 25.2.3 +#else +/// \fn none_of ( InputIterator first, InputIterator last, Predicate p ) +/// \return true if none of the elements in [first, last) satisfy the predicate 'p' +/// \note returns true on an empty range +/// +/// \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; +} +#endif + +/// \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/boost/algorithm/cxx11/one_of.hpp b/boost/algorithm/cxx11/one_of.hpp new file mode 100644 index 0000000000..b6e8c77194 --- /dev/null +++ b/boost/algorithm/cxx11/one_of.hpp @@ -0,0 +1,82 @@ +/* + 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/boost/algorithm/cxx11/partition_copy.hpp b/boost/algorithm/cxx11/partition_copy.hpp new file mode 100644 index 0000000000..15c4dd68ab --- /dev/null +++ b/boost/algorithm/cxx11/partition_copy.hpp @@ -0,0 +1,78 @@ +/* + 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 <algorithm> // for std::partition_copy, if available +#include <utility> // for make_pair + +#include <boost/range/begin.hpp> +#include <boost/range/end.hpp> + +namespace boost { namespace algorithm { + +#if __cplusplus >= 201103L +// Use the C++11 versions of partition_copy if it is available +using std::partition_copy; // Section 25.3.13 +#else +/// \fn partition_copy ( InputIterator first, InputIterator last, +/// OutputIterator1 out_true, OutputIterator2 out_false, UnaryPredicate p ) +/// \brief Copies the elements that satisfy the predicate p from the range [first, last) +/// 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. +/// We will use the standard one if it is available, +/// otherwise we have our own implementation. +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 ); +} +#endif + +/// \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/boost/algorithm/cxx11/partition_point.hpp b/boost/algorithm/cxx11/partition_point.hpp new file mode 100644 index 0000000000..36d8384b57 --- /dev/null +++ b/boost/algorithm/cxx11/partition_point.hpp @@ -0,0 +1,72 @@ +/* + 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 <algorithm> // for std::partition_point, if available + +#include <boost/range/begin.hpp> +#include <boost/range/end.hpp> + +namespace boost { namespace algorithm { + +#if __cplusplus >= 201103L +// Use the C++11 versions of partition_point if it is available +using std::partition_point; // Section 25.3.13 +#else +/// \fn partition_point ( ForwardIterator first, ForwardIterator last, Predicate p ) +/// \brief Given a partitioned range, returns the partition point, i.e, the first element +/// that does not satisfy p +/// +/// \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. +/// We will use the standard one if it is available, +/// otherwise we have our own implementation. +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; +} +#endif + +/// \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> 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/boost/algorithm/hex.hpp b/boost/algorithm/hex.hpp new file mode 100644 index 0000000000..3f3c0c694b --- /dev/null +++ b/boost/algorithm/hex.hpp @@ -0,0 +1,265 @@ +/* + 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. + +TO DO: + 1. these should really only work on integral types. (see the >> and << operations) + -- this is done, I think. + 2. The 'value_type_or_char' struct is really a hack. + -- but it's a better hack now that it works with back_insert_iterators +*/ + +/// \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/all.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 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 = "0123456789ABCDEF" [ val & 0x0F ]; + return std::copy ( res, res + num_hex_digits, out ); + } + + unsigned hex_char_to_int ( char c ) { + if ( c >= '0' && c <= '9' ) return c - '0'; + if ( c >= 'A' && c <= 'F' ) return c - 'A' + 10; + if ( c >= 'a' && c <= 'f' ) return c - 'a' + 10; + BOOST_THROW_EXCEPTION (non_hex_input() << bad_char (c)); + return 0; // keep dumb compilers happy + } + + +// 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 (static_cast<char> (*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 ); + 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 ); + 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 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 ) { + typedef typename detail::hex_iterator_traits<OutputIterator>::value_type OutputType; +// If we run into the terminator while decoding, we will throw a +// malformed input exception. It would be nicer to throw a 'Not enough input' +// exception - but how much extra work would that require? + 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 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/boost/algorithm/searching/boyer_moore.hpp b/boost/algorithm/searching/boyer_moore.hpp new file mode 100644 index 0000000000..958f0b8d0c --- /dev/null +++ b/boost/algorithm/searching/boyer_moore.hpp @@ -0,0 +1,268 @@ +/* + 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: boostinspect:noascii (test tool complains) + http://en.wikipedia.org/wiki/Boyer–Moore_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> + 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 corpus_last; // if nothing to search, we didn't find it! + if ( pat_first == pat_last ) return 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 corpus_last; + + // Do the search + return this->do_search ( corpus_first, corpus_last ); + } + + template <typename Range> + 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> + 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 curPos; + } + + // 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 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 pat_first, Iter pat_last, Container &prefix ) { + const std::size_t count = std::distance ( pat_first, pat_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 && ( pat_first[k] != pat_first[i] )) { + BOOST_ASSERT ( k < count ); + k = prefix [ k - 1 ]; + } + + if ( pat_first[k] == pat_first[i] ) + k++; + prefix [ i ] = k; + } + } + + void build_suffix_table ( patIter pat_first, patIter pat_last ) { + const std::size_t count = (std::size_t) std::distance ( pat_first, pat_last ); + + if ( count > 0 ) { // empty pattern + std::vector<typename std::iterator_traits<patIter>::value_type> reversed(count); + (void) std::reverse_copy ( pat_first, pat_last, reversed.begin ()); + + std::vector<difference_type> prefix (count); + compute_bm_prefix ( pat_first, pat_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> + 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> + 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::lazy_disable_if_c< + boost::is_same<CorpusRange, patIter>::value, typename boost::range_iterator<CorpusRange> > + ::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> + 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/boost/algorithm/searching/boyer_moore_horspool.hpp b/boost/algorithm/searching/boyer_moore_horspool.hpp new file mode 100644 index 0000000000..5e59cf3220 --- /dev/null +++ b/boost/algorithm/searching/boyer_moore_horspool.hpp @@ -0,0 +1,194 @@ +/* + 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/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, 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> + 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 corpus_last; // if nothing to search, we didn't find it! + if ( pat_first == pat_last ) return 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 corpus_last; + + // Do the search + return this->do_search ( corpus_first, corpus_last ); + } + + template <typename Range> + 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> + 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 curPos; + j--; + } + + curPos += skip_ [ curPos [ k_pattern_length - 1 ]]; + } + + return 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> + 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> + 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::lazy_disable_if_c< + boost::is_same<CorpusRange, patIter>::value, typename boost::range_iterator<CorpusRange> > + ::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> + 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/boost/algorithm/searching/detail/bm_traits.hpp b/boost/algorithm/searching/detail/bm_traits.hpp new file mode 100644 index 0000000000..ea150c3021 --- /dev/null +++ b/boost/algorithm/searching/detail/bm_traits.hpp @@ -0,0 +1,105 @@ +/* + 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> +#include <boost/tr1/tr1/unordered_map> + +#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: + typedef std::tr1::unordered_map<key_type, value_type> skip_map; + 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/boost/algorithm/searching/detail/debugging.hpp b/boost/algorithm/searching/detail/debugging.hpp new file mode 100644 index 0000000000..3996e0f503 --- /dev/null +++ b/boost/algorithm/searching/detail/debugging.hpp @@ -0,0 +1,30 @@ +/* + 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/boost/algorithm/searching/knuth_morris_pratt.hpp b/boost/algorithm/searching/knuth_morris_pratt.hpp new file mode 100644 index 0000000000..cc83185c51 --- /dev/null +++ b/boost/algorithm/searching/knuth_morris_pratt.hpp @@ -0,0 +1,253 @@ +/* + 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/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> + 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 corpus_last; // if nothing to search, we didn't find it! + if ( pat_first == pat_last ) return 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 corpus_last; + + return do_search ( corpus_first, corpus_last, k_corpus_length ); + } + + template <typename Range> + 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> + 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 corpus_first + match_start; + } + // 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 corpus_last; + } + + + void preKmp ( patIter first, patIter last ) { + const /*std::size_t*/ int count = std::distance ( first, last ); + + int 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 ); + + int 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> + 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> + 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::lazy_disable_if_c< + boost::is_same<CorpusRange, patIter>::value, typename boost::range_iterator<CorpusRange> > + ::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> + 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/boost/algorithm/string/find.hpp b/boost/algorithm/string/find.hpp index 304646d090..cc99ca1c93 100644 --- a/boost/algorithm/string/find.hpp +++ b/boost/algorithm/string/find.hpp @@ -228,13 +228,13 @@ namespace boost { //! Find head algorithm /*! Get the head of the input. Head is a prefix of the string of the - given size. If the input is shorter then required, whole input if considered + given size. If the input is shorter then required, whole input is considered to be the head. \param Input An input string \param N Length of the head For N>=0, at most N characters are extracted. - For N<0, size(Input)-|N| characters are extracted. + For N<0, at most size(Input)-|N| characters are extracted. \return An \c iterator_range delimiting the match. Returned iterator is either \c Range1T::iterator or @@ -258,13 +258,13 @@ namespace boost { //! Find tail algorithm /*! Get the tail of the input. Tail is a suffix of the string of the - given size. If the input is shorter then required, whole input if considered + given size. If the input is shorter then required, whole input is considered to be the tail. \param Input An input string \param N Length of the tail. For N>=0, at most N characters are extracted. - For N<0, size(Input)-|N| characters are extracted. + For N<0, at most size(Input)-|N| characters are extracted. \return An \c iterator_range delimiting the match. Returned iterator is either \c RangeT::iterator or diff --git a/boost/algorithm/string/iter_find.hpp b/boost/algorithm/string/iter_find.hpp index 9e0245f1a7..e10652834b 100644 --- a/boost/algorithm/string/iter_find.hpp +++ b/boost/algorithm/string/iter_find.hpp @@ -60,7 +60,7 @@ namespace boost { a match). \param Input A container which will be searched. \param Finder A Finder object used for searching - \return A reference the result + \return A reference to the result \note Prior content of the result will be overwritten. */ @@ -122,7 +122,7 @@ namespace boost { Each match is used as a separator of segments. These segments are then returned in the result. - \param Result A 'container container' to container the result of search. + \param Result A 'container container' to contain the result of search. Both outer and inner container must have constructor taking a pair of iterators as an argument. Typical type of the result is @@ -131,7 +131,7 @@ namespace boost { a match). \param Input A container which will be searched. \param Finder A finder object used for searching - \return A reference the result + \return A reference to the result \note Prior content of the result will be overwritten. */ |