|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r64746 - in sandbox/SOC/2010/stringalgos: boost/algorithm/string boost/algorithm/string/detail boost/algorithm/string/finder boost/algorithm/string/finder/detail boost/algorithm/string/string_search boost/algorithm/string/string_search/detail libs/algorithm/string/benchmark libs/algorithm/string/doc libs/algorithm/string/test
From: mstefanro_at_[hidden]
Date: 2010-08-11 18:26:50
Author: mstefanro
Date: 2010-08-11 18:26:46 EDT (Wed, 11 Aug 2010)
New Revision: 64746
URL: http://svn.boost.org/trac/boost/changeset/64746
Log:
[GSoC2010][StringAlgo] Refactoring, documenting and adapting the old interface
Added:
sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/
sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/default_search_algorithm.hpp (contents, props changed)
sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/detail/
sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/detail/finder_typedefs.hpp (contents, props changed)
sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/detail/is_pointer_to.hpp (contents, props changed)
sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/detail/last_finder_impl.hpp (contents, props changed)
sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/detail/nth_finder_impl.hpp (contents, props changed)
sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/finder.hpp (contents, props changed)
sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/generated_finders.hpp (contents, props changed)
sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/simplified_finder.hpp (contents, props changed)
Removed:
sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/boyer_moore_horspool.hpp
Text files modified:
sandbox/SOC/2010/stringalgos/boost/algorithm/string/benchmark_finder.hpp | 117 +-
sandbox/SOC/2010/stringalgos/boost/algorithm/string/compare.hpp | 2
sandbox/SOC/2010/stringalgos/boost/algorithm/string/detail/finder.hpp | 47 -
sandbox/SOC/2010/stringalgos/boost/algorithm/string/find.hpp | 98 +
sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder.hpp | 893 +---------------------
sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder_aliases.hpp | 3
sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search.hpp | 2
sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/boyer_moore.hpp | 53
sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/detail/rabin_karp.hpp | 24
sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/knuth_morris_pratt.hpp | 89 -
sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/naive_search.hpp | 18
sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/rabin_karp.hpp | 42
sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/suffix_array.hpp | 17
sandbox/SOC/2010/stringalgos/libs/algorithm/string/benchmark/string_search.cpp | 6
sandbox/SOC/2010/stringalgos/libs/algorithm/string/doc/Jamfile.v2 | 2
sandbox/SOC/2010/stringalgos/libs/algorithm/string/doc/quickref.xml | 1587 +++++++++++++++++++++------------------
sandbox/SOC/2010/stringalgos/libs/algorithm/string/doc/usage.xml | 18
sandbox/SOC/2010/stringalgos/libs/algorithm/string/test/finder_test.cpp | 8
18 files changed, 1188 insertions(+), 1838 deletions(-)
Modified: sandbox/SOC/2010/stringalgos/boost/algorithm/string/benchmark_finder.hpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/boost/algorithm/string/benchmark_finder.hpp (original)
+++ sandbox/SOC/2010/stringalgos/boost/algorithm/string/benchmark_finder.hpp 2010-08-11 18:26:46 EDT (Wed, 11 Aug 2010)
@@ -4,6 +4,8 @@
//Our finder has 6 template params, which means we cannot use it in a placeholder expression
//unless MPL supports metafunctions with arity >= 6
+//\todo remove this, we only have 5 template params now
+/*
#ifdef BOOST_MPL_LIMIT_METAFUNCTION_ARITY
# if BOOST_MPL_LIMIT_METAFUNCTION_ARITY < 6 || !defined BOOST_MPL_CFG_NO_PREPROCESSED_HEADERS
# error "benchmark_finder.hpp requires BOOST_MPL_LIMIT_METAFUNCTION_ARITY to be at least 6. " \
@@ -14,9 +16,10 @@
#define BOOST_MPL_CFG_NO_PREPROCESSED_HEADERS
#define BOOST_MPL_LIMIT_METAFUNCTION_ARITY 6
#endif
+*/
-#include <boost/algorithm/string/finder.hpp>
-#include <boost/algorithm/string/detail/finder.hpp>
+#include <boost/algorithm/string/finder/simplified_finder.hpp>
+#include <boost/algorithm/string/finder/detail/finder_typedefs.hpp>
#include <boost/algorithm/string/string_search/naive_search.hpp>
#include <boost/tuple/tuple.hpp>
@@ -44,7 +47,7 @@
#include <boost/spirit/home/phoenix/core/argument.hpp>
#include <boost/spirit/home/phoenix/core/reference.hpp>
-//!\todo pretty messy, Boost.Chrono?
+//\todo pretty messy, Boost.Chrono?
#ifdef BOOST_WINDOWS
#include <windows.h>
#endif
@@ -59,27 +62,35 @@
#include <boost/throw_exception.hpp>
-//!\todo use something more accurate
+//todo use something more accurate
#include <boost/timer.hpp>
+/*! \file
+ Defines a generic finder type useful for comparing the performance of various string search algorithms.
+*/
+
namespace boost { namespace algorithm {
- //! A generic finder type which benchmarks string search algorithms.
- /** Poseses a similar interface to \ref finder_t and allows to test
+ //! A generic finder type which benchmarks string search algorithms
+ /** Possesses a similar interface to \ref simplified_finder_t and allows to test
the performance of various string search algorithms in order to allow easier
choice of the right algorithm for a certain data set
\tparam Range1T A range representing the type of the substring (the pattern)
\tparam Range2T A range representing the type of the string (the text)
+ \tparam AlgorithmSequenceT A MPL sequence containing algorithm types that are to be benchmarked
+ \tparam ComparatorT The comparator type passed to the algorithms
*/
template <class Range1T, class Range2T, class AlgorithmSequenceT,
- class ComparatorT>
- class benchmark_finder :
- public boost::algorithm::detail::finder_typedefs<Range1T, Range2T,
- ComparatorT, std::allocator<std::size_t> >
- {
- public:
-
- void set_substring (Range1T const *const substring)
+ class ComparatorT = boost::algorithm::is_equal>
+ class benchmark_finder :
+ public boost::algorithm::detail::finder_typedefs<Range1T, Range2T,
+ ComparatorT, std::allocator<std::size_t> >
+ {
+ public:
+
+ //! See \ref simplified_finder_t::set_substring
+ void set_substring (substring_type
+ const *const substring)
{
boost::phoenix::function<finder_set_substring> f;
boost::fusion::for_each(finders,
@@ -88,7 +99,8 @@
trusted_finder.set_substring(substring);
}
- void set_string (Range2T *const string)
+ //! See \ref simplified_finder_t::set_string
+ void set_string (string_type *const string)
{
boost::phoenix::function<finder_set_string> f;
boost::fusion::for_each(
@@ -98,60 +110,50 @@
trusted_finder.set_string(string);
}
+ //! Clears all the benchmark data obtained from searching
void clear ()
{ boost::fusion::for_each(finders, clear_stats()); }
+ //! See \ref simplified_finder_t::find_reset
void find_reset()
{
boost::fusion::for_each(finders, finder_reset());
trusted_finder.find_reset();
}
+ //! See \ref simplified_finder_t::find_next
string_range_type find_next()
{
return boost::fusion::fold(finders, trusted_finder.find_next(),
finder_benchmark_and_test());
}
+ //! See \ref simplified_finder_t::find_first
string_range_type find_first()
{ find_reset(); return find_next(); }
- /*void refresh()
- {
- boost::fusion::for_each(finders, finder_refresh());
- trusted_finder.refresh();
- }
-
- void refresh_string()
- {
- boost::fusion::for_each(finders, finder_refresh_string());
- trusted_finder.refresh_string();
- }
-
- void refresh_substring()
- {
- boost::fusion::for_each(finders, finder_refresh_substring());
- trusted_finder.refresh_substring();
- }*/
-
+ //! Output the benchmark data to a stream
+ /*!
+ \param output The stream to which the benchmark results are to be outputted
+ */
template <class CharT, class TraitsT>
- void output_stats (std::basic_ostream<CharT, TraitsT> &os)
+ void output_stats (std::basic_ostream<CharT, TraitsT> &output)
{
boost::phoenix::function<output_stats_> f;
- boost::fusion::for_each(finders, f(boost::phoenix::ref(os), boost::phoenix::arg_names::arg1) );
+ boost::fusion::for_each(finders, f(boost::phoenix::ref(output), boost::phoenix::arg_names::arg1) );
}
private:
- //! \todo write a proxy type allowing us to have a simplified_finder_t3 taking only the first
- //! 3 template params. use that in boost::mpl::transform for eliminating the metafunction increased
- //! arity requirement
+ // todo write a proxy type allowing us to have a simplified_finder_t3 taking only the first
+ // 3 template params. use that in boost::mpl::transform for eliminating the metafunction increased
+ // arity requirement
typedef typename boost::mpl::transform<AlgorithmSequenceT,
std::pair<
- typename boost::algorithm::simplified_finder_t<Range1T,Range2T,
+ typename boost::algorithm::simplified_finder_t<substring_type,string_type,
boost::mpl::_, ComparatorT>,
std::deque<double>
>
>::type finders_sequence;
- typename boost::simplified_finder_t<Range1T, Range2T, boost::naive_search,
+ typename boost::simplified_finder_t<substring_type, string_type, boost::naive_search,
ComparatorT> trusted_finder;
typename boost::fusion::result_of::as_vector< finders_sequence >::type finders;
@@ -161,7 +163,7 @@
template <class,class> struct result { typedef void type; };
template <class Finder>
- void operator() (Finder &finder, Range1T const *const substring) const
+ void operator() (Finder &finder, substring_type const *const substring) const
{ finder.first.set_substring(substring); }
};
@@ -170,7 +172,7 @@
template <class,class> struct result { typedef void type; };
template <class Finder>
- void operator() (Finder &finder, Range2T *const string) const
+ void operator() (Finder &finder, string_type *const string) const
{ finder.first.set_string(string); }
};
@@ -189,7 +191,7 @@
void operator() (Finder &finder) const { finder.first.find_reset(); }
};
- //!\todo Make sure tests are performed properly (via returning etc.)
+ //todo Make sure tests are performed properly (via returning etc.)
struct finder_benchmark_and_test
{
template <class> struct result { typedef string_range_type type; };
@@ -240,33 +242,6 @@
}
};
- /*struct finder_refresh
- {
- template <class> struct result { typedef void type; };
-
- template <class Finder>
- void operator () (Finder &finder) const
- { finder.first.refresh(); }
- };
-
- struct finder_refresh_string
- {
- template <class> struct result { typedef void type; };
-
- template <class Finder>
- void operator () (Finder &finder) const
- { finder.first.refresh_string(); }
- };
-
- struct finder_refresh_substring
- {
- template <class> struct result { typedef void type; };
-
- template <class Finder>
- void operator () (Finder &finder) const
- { finder.first.refresh_substring(); }
- };*/
-
struct output_stats_
{
template <class,class> struct result { typedef void type; };
@@ -284,7 +259,7 @@
//if (size&1) median = t[size>>1];
//else median = t[size>>1] + t[1 + (size>>1)];
- //!\todo start from t.begin()+1, now we just want to check the values.
+
for (It it = t.begin(); it != t.end(); ++it)
{
if (*it < min) min = *it;
Modified: sandbox/SOC/2010/stringalgos/boost/algorithm/string/compare.hpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/boost/algorithm/string/compare.hpp (original)
+++ sandbox/SOC/2010/stringalgos/boost/algorithm/string/compare.hpp 2010-08-11 18:26:46 EDT (Wed, 11 Aug 2010)
@@ -61,6 +61,8 @@
//! Function operator
/*!
Compare two operands. Case is ignored.
+ TODO: FIX THIS. THE EQUIVALENCE TOUPPER(A)==TOUPPER(B) <=> A IS CASE-INSENSITIVE-EQUAL-TO B
+ DOES NOT ALWAYS HOLD (SEE GREEK!)
*/
template< typename T1, typename T2 >
bool operator()( const T1& Arg1, const T2& Arg2 ) const
Modified: sandbox/SOC/2010/stringalgos/boost/algorithm/string/detail/finder.hpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/boost/algorithm/string/detail/finder.hpp (original)
+++ sandbox/SOC/2010/stringalgos/boost/algorithm/string/detail/finder.hpp 2010-08-11 18:26:46 EDT (Wed, 11 Aug 2010)
@@ -22,52 +22,13 @@
#include <boost/range/as_literal.hpp>
#include <boost/range/category.hpp>
-#include <boost/iterator/iterator_traits.hpp>
-
-#include <boost/mpl/and.hpp>
#include <boost/type_traits/remove_cv.hpp>
+#include <iterator>
+
+
namespace boost { namespace algorithm { namespace detail {
- template <class T, class U> struct is_pointer_to :
- boost::mpl::and_<
- typename boost::is_pointer<T>,
- typename boost::is_same<
- typename boost::remove_cv<typename boost::remove_pointer<T>::type>::type,
- U>
- > {};
- template <class Range1T, class Range2T, class ComparatorT, class AllocatorT>
- struct finder_typedefs
- {
- //! The type of the substring
- typedef Range1T substring_type;
- //! The type of the string
- typedef Range2T string_type;
- //! The type of the comparator
- typedef ComparatorT comparator_type;
- //! The type of the allocator
- typedef AllocatorT allocator_type;
- //! The type of the substring's iterator
- typedef typename boost::range_const_iterator<substring_type>::type
- substring_iterator_type;
- //! The type of the string's iterator
- typedef typename boost::range_iterator<string_type>::type
- string_iterator_type;
- //! The character type of the substring
- typedef typename boost::iterator_value<substring_iterator_type>::type
- substring_char_type;
- //! The character type of the string
- typedef typename boost::iterator_value<string_iterator_type>::type
- string_char_type;
- typedef typename boost::iterator_range<substring_iterator_type>
- substring_range_type;
- typedef typename boost::iterator_range<string_iterator_type>
- string_range_type;
- typedef typename boost::iterator_difference<string_iterator_type>::type
- string_difference_type;
- protected:
- typedef typename boost::range_category<substring_type>::type substring_iterator_category;
- typedef typename boost::range_category<string_type>::type string_iterator_category;
- };
+
// find first functor -----------------------------------------------//
Modified: sandbox/SOC/2010/stringalgos/boost/algorithm/string/find.hpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/boost/algorithm/string/find.hpp (original)
+++ sandbox/SOC/2010/stringalgos/boost/algorithm/string/find.hpp 2010-08-11 18:26:46 EDT (Wed, 11 Aug 2010)
@@ -19,7 +19,8 @@
#include <boost/range/iterator.hpp>
#include <boost/range/as_literal.hpp>
-#include <boost/algorithm/string/finder.hpp>
+#include <boost/algorithm/string/finder/generated_finders.hpp>
+#include <boost/algorithm/string/finder/default_search_algorithm.hpp>
#include <boost/algorithm/string/compare.hpp>
#include <boost/algorithm/string/constants.hpp>
@@ -29,7 +30,7 @@
delimiting the substring.
*/
-//!\todo update doc here
+//todo update doc here
namespace boost {
namespace algorithm {
@@ -54,7 +55,7 @@
BOOST_STRING_TYPENAME range_iterator<RangeT>::type>
find(
RangeT& Input,
- const FinderT& Finder)
+ FinderT& Finder)
{
iterator_range<BOOST_STRING_TYPENAME range_iterator<RangeT>::type> lit_input(::boost::as_literal(Input));
@@ -85,10 +86,10 @@
const Range2T& Search,
AlgorithmTagT const &algorithm)
{
- boost::algorithm::simplified_finder_t<Range2T, Range1T, typename AlgorithmTagT::type>
- finder(&Search, &Input);
- return finder.find_first();
- //return ::boost::algorithm::find(Input, ::boost::algorithm::first_finder(Search));
+ return ::boost::algorithm::find(Input,
+ ::boost::algorithm::first_finder_t<Range2T,Range1T,
+ typename AlgorithmTagT::type,::boost::algorithm::is_equal>(&Search)
+ );
}
template<typename Range1T, typename Range2T>
@@ -127,9 +128,13 @@
AlgorithmTagT const &,
const std::locale& Loc=std::locale())
{
- boost::algorithm::simplified_finder_t<Range2T, Range1T, typename AlgorithmTagT::type,
- ::boost::algorithm::is_iequal> finder(&Search, &Input, ::boost::algorithm::is_iequal(Loc));
- return finder.find_first();
+ //boost::algorithm::simplified_finder_t<Range2T, Range1T, typename AlgorithmTagT::type,
+ // ::boost::algorithm::is_iequal> finder(&Search, &Input, ::boost::algorithm::is_iequal(Loc));
+ //return finder.find_first();
+ return ::boost::algorithm::find(Input,
+ ::boost::algorithm::first_finder_t<Range2T,Range1T,
+ typename AlgorithmTagT::type,::boost::algorithm::is_iequal>(&Search, ::boost::algorithm::is_iequal(Loc))
+ );
}
template<typename Range1T, typename Range2T>
@@ -168,9 +173,7 @@
const Range2T& Search,
AlgorithmTagT const &)
{
- //!\todo find a way to use rbegin and rend here (via boost::adaptors::reversed)
- // if they are available (i.e. if the ranges are bidirectional at least)
- //!\TODO IMPORTANT FIX this so it works (the final if check does not work properly)
+ /*
simplified_finder_t<Range2T, Range1T, typename AlgorithmTagT::type>
finder(&Search, &Input);
boost::iterator_range<typename boost::range_iterator<Range1T>::type>
@@ -180,17 +183,25 @@
{
prev=crt;
crt=finder.find_next();
- if (boost::begin(crt) == boost::end(Input)) break;
+ //note: we don't use boost::end(Input) on the rhs, because Input can be a character
+ //array, which means we would have to apply boost::as_literal to Input first.
+ //however, the finder does that for us before saving the range, so we use the internal
+ //range instead.
+ if (boost::begin(crt) == boost::end(finder.get_string_range())) break;
}
return prev;
-
+ */
+ return ::boost::algorithm::find(Input,
+ ::boost::algorithm::last_finder_t<Range2T,Range1T,
+ typename AlgorithmTagT::type,::boost::algorithm::is_equal>(&Search)
+ );
//return ::boost::algorithm::find(Input, ::boost::algorithm::last_finder(Search));
}
template<typename Range1T, typename Range2T>
inline iterator_range<
BOOST_STRING_TYPENAME range_iterator<Range1T>::type>
- find_last(
+ find_last(
Range1T& Input,
const Range2T& Search)
{
@@ -214,6 +225,20 @@
\note This function provides the strong exception-safety guarantee
*/
+ template<typename Range1T, typename Range2T, typename AlgorithmTagT>
+ inline iterator_range<
+ BOOST_STRING_TYPENAME range_iterator<Range1T>::type>
+ ifind_last(
+ Range1T& Input,
+ const Range2T& Search,
+ AlgorithmTagT const &,
+ const std::locale& Loc=std::locale())
+ {
+ return ::boost::algorithm::find(Input,
+ ::boost::algorithm::last_finder_t<Range2T,Range1T,
+ typename AlgorithmTagT::type,::boost::algorithm::is_iequal>(&Search, ::boost::algorithm::is_iequal(Loc)));
+ }
+
template<typename Range1T, typename Range2T>
inline iterator_range<
BOOST_STRING_TYPENAME range_iterator<Range1T>::type>
@@ -222,7 +247,8 @@
const Range2T& Search,
const std::locale& Loc=std::locale())
{
- return ::boost::algorithm::find(Input, ::boost::algorithm::last_finder(Search, is_iequal(Loc)));
+ return ::boost::algorithm::ifind_last(Input, Search,
+ boost::algorithm::default_finder_algorithm_tag(), Loc);
}
// find_nth ----------------------------------------------------------------------//
@@ -242,6 +268,23 @@
\c Range1T::const_iterator, depending on the constness of
the input parameter.
*/
+
+
+ template<typename Range1T, typename Range2T, typename AlgorithmTagT>
+ inline iterator_range<
+ BOOST_STRING_TYPENAME range_iterator<Range1T>::type>
+ find_nth(
+ Range1T& Input,
+ const Range2T& Search,
+ int Nth,
+ AlgorithmTagT const &)
+ {
+ return ::boost::algorithm::find(Input,
+ ::boost::algorithm::nth_finder_t<Range2T, Range1T,
+ typename AlgorithmTagT::type, ::boost::algorithm::is_equal>(&Search, ::boost::algorithm::is_equal(), Nth)
+ );
+ }
+
template<typename Range1T, typename Range2T>
inline iterator_range<
BOOST_STRING_TYPENAME range_iterator<Range1T>::type>
@@ -250,7 +293,8 @@
const Range2T& Search,
int Nth)
{
- return ::boost::algorithm::find(Input, ::boost::algorithm::nth_finder(Search,Nth));
+ return ::boost::algorithm::find_nth(Input, Search, Nth,
+ ::boost::algorithm::default_finder_algorithm_tag());
}
//! Find n-th algorithm ( case insensitive ).
@@ -272,6 +316,21 @@
\note This function provides the strong exception-safety guarantee
*/
+ template <typename Range1T, typename Range2T, typename AlgorithmTagT>
+ inline iterator_range<
+ BOOST_STRING_TYPENAME range_iterator<Range1T>::type>
+ ifind_nth (
+ Range1T& Input,
+ const Range2T &Search,
+ int Nth,
+ AlgorithmTagT const&,
+ const std::locale& Loc=std::locale())
+ {
+ return ::boost::algorithm::find(Input,
+ ::boost::algorithm::nth_finder_t<Range2T, Range1T,
+ typename AlgorithmTagT::type, ::boost::algorithm::is_iequal>(&Search, ::boost::algorithm::is_iequal(Loc), Nth));
+ }
+
template<typename Range1T, typename Range2T>
inline iterator_range<
BOOST_STRING_TYPENAME range_iterator<Range1T>::type>
@@ -281,7 +340,8 @@
int Nth,
const std::locale& Loc=std::locale())
{
- return ::boost::algorithm::find(Input, ::boost::algorithm::nth_finder(Search,Nth,is_iequal(Loc)));
+ return ::boost::algorithm::ifind_nth(Input, Search, Nth,
+ ::boost::algorithm::default_finder_algorithm_tag(), Loc);
}
// find_head ----------------------------------------------------------------------//
Modified: sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder.hpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder.hpp (original)
+++ sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder.hpp 2010-08-11 18:26:46 EDT (Wed, 11 Aug 2010)
@@ -8,6 +8,11 @@
// See http://www.boost.org/ for updates, documentation, and revision history.
+
+//TODO REPLACE TYPENAME EVERYWHERE WITH BOOST_STRING_TYPENAME
+//TODO maybe finder_t should have a get_internal_string() and get_internal_substring()
+//todo maybe we should replace *substring* with *pattern* and *string* with *text*
+
#ifndef BOOST_STRING_FINDER_HPP
#define BOOST_STRING_FINDER_HPP
@@ -18,11 +23,12 @@
#include <boost/range/end.hpp>
#include <boost/range/iterator.hpp>
#include <boost/range/const_iterator.hpp>
+#include <boost/range/adaptor/reversed.hpp>
+#include <boost/range/category.hpp>
#include <boost/algorithm/string/constants.hpp>
#include <boost/algorithm/string/detail/finder.hpp>
#include <boost/algorithm/string/compare.hpp>
-#include <boost/algorithm/string/string_search/knuth_morris_pratt.hpp>
#include <boost/call_traits.hpp>
@@ -39,7 +45,12 @@
#include <boost/concept_check.hpp>
-//!\todo modify this
+#include <boost/algorithm/string/finder/default_search_algorithm.hpp>
+#include <boost/algorithm/string/finder/finder.hpp>
+#include <boost/algorithm/string/finder/simplified_finder.hpp>
+#include <boost/algorithm/string/finder/generated_finders.hpp>
+
+//TODO modify this
/*! \file
Defines Finder types and Finder generators. Finder object is a functor which is able to
find a substring matching a specific criteria in the input.
@@ -48,904 +59,121 @@
for finders provided in this library.
*/
-//!\todo impl get_internal_string, get_internal_substring, use_internal_substring
+//TODO: test if get_internal_string() and get_internal_substring() are fine
namespace boost { namespace algorithm {
+
-// Finder types ---------------------------------------------//
-
- //struct finder_no_additional_behavior;
- struct finder_behavior_first_finder;
- struct finder_behavior_last_finder;
- struct finder_behavior_nth_finder;
-
- struct default_finder_algorithm_tag { typedef boost::algorithm::knuth_morris_pratt type; };
- typedef boost::algorithm::knuth_morris_pratt default_finder_algorithm;
-
- //! \todo use an allocator metafunction instead
- //! \todo derive from additionalbehaviort? use it at all?
- //! \TODO !!!!!!! IMPORTANT!!!! REMOVE THE ComparatorT template parameter and use boost::function
- //! as a ctor parameter.
- //! Also, revert the order of AllocatorT with AdditionalBehaviorT so it's easier to access
- //! deprecated finders
- //! Create template proxies for first_finder_t, last_finder_t, nth_finder_t
- template <class Range1T, class Range2T, class AlgorithmT,
- class ComparatorT = ::boost::algorithm::is_equal,
- class AllocatorT = std::allocator<std::size_t>,
- class AdditionalBehaviorT = boost::algorithm::finder_behavior_first_finder
- >
- class simplified_finder_t :
- //public boost::algorithm::detail::finder_typedefs<Range1T,Range2T,ComparatorT,AllocatorT>,
- public AlgorithmT::template algorithm<
- simplified_finder_t<Range1T, Range2T, AlgorithmT, ComparatorT, AllocatorT, AdditionalBehaviorT>,
- Range1T, Range2T, ComparatorT,AllocatorT>,
- public AdditionalBehaviorT::template apply<
- typename simplified_finder_t<Range1T, Range2T, AlgorithmT, ComparatorT, AllocatorT, AdditionalBehaviorT>,
- Range1T, Range2T, AlgorithmT, ComparatorT, AllocatorT>
- {
- //! \todo Add concept assertions here.
- private:
- typedef typename AlgorithmT::template algorithm<simplified_finder_t, Range1T,
- Range2T, ComparatorT, AllocatorT> algorithm_type;
- public:
- //!\todo remove
- void g() {
- //std::ofstream o1("D://o1.txt");
- //std::ofstream o2("D://o2.txt");
- //boost::copy(string_range_, std::ostream_iterator<char>(o1));
- //boost::copy(substring_range_, std::ostream_iterator<char>(o2));
- }
- typedef typename algorithm_type::substring_type substring_type;
- typedef typename algorithm_type::string_type string_type;
- typedef typename algorithm_type::comparator_type comparator_type;
- typedef typename algorithm_type::allocator_type allocator_type;
- typedef typename algorithm_type::substring_iterator_type substring_iterator_type;
- typedef typename algorithm_type::string_iterator_type string_iterator_type;
- typedef typename algorithm_type::substring_char_type substring_char_type;
- typedef typename algorithm_type::string_char_type string_char_type;
- typedef typename algorithm_type::substring_range_type substring_range_type;
- typedef typename algorithm_type::string_range_type string_range_type;
- typedef typename algorithm_type::string_difference_type string_difference_type;
-
- explicit simplified_finder_t(ComparatorT comparator = ComparatorT(), AllocatorT allocator = AllocatorT())
- : substring_range_(), string_range_(), substring_has_changed_(false),
- string_has_changed_(false), comparator_(comparator), allocator_(allocator),
- start_offset_()
- //!\todo remove
- //{ if(rand()==48&&rand()==49) g(); }
- { }
- simplified_finder_t(Range1T const *const substr, Range2T *str,
- ComparatorT comparator = ComparatorT(), AllocatorT allocator = AllocatorT())
- : substring_range_(boost::as_literal(*substr)),
- string_range_(boost::as_literal(*str)),
- comparator_(comparator), allocator_(allocator),
- substring_has_changed_(true), string_has_changed_(true),
- algorithm_type()
- { }
- simplified_finder_t (const simplified_finder_t &other)
- : substring_range_(other.substring_range_), string_range_(other.string_range_),
- substring_has_changed_(other.substring_has_changed_), string_has_changed_(other.string_has_changed_),
- comparator_(other.comparator_), allocator_(other.allocator_), start_offset_(other.start_offset_),
- algorithm_type(other)
- {
- }
- simplified_finder_t &operator=(const simplified_finder_t &rhs)
- {
- substring_range_ = rhs.substring_range_;
- string_range_ = rhs.string_range_;
- substring_has_changed_ = rhs.substring_has_changed_;
- string_has_changed_ = rhs.string_has_changed_;
- comparator_ = rhs.comparator_;
- allocator_ = rhs.allocator_;
- start_offset_ = rhs.start_offset_;
- return *this;
- }
-
- void set_substring (Range1T const *substr)
- { substring_range_ = boost::as_literal(*substr); substring_has_changed_ = true; }
-
- void set_string (Range2T *str)
- { string_range_ = boost::as_literal(*str); string_has_changed_ = true; }
-
- void find_reset ()
- { start_offset_ = boost::begin(string_range_); }
-
- string_range_type find_first ()
- {
- find_reset();
- return find_next();
- }
-
- //! \todo Get rid of this refresh*() idea everywhere
-
- //!\todo Assert in case this was called after an empty ctor
- string_range_type find_next()
- {
- apply_changes();
- if (start_offset_ == boost::end(string_range_))
- return string_range_type(start_offset_, start_offset_);
- string_range_type ret =
- algorithm_type::find(start_offset_);
- if (boost::begin(ret) == boost::end(string_range_))
- {
- start_offset_ = boost::end(string_range_);
- return ret;
- }
- else
- {
- start_offset_ = boost::begin(ret);
- ++start_offset_;
- return ret;
- }
- }
-
- substring_range_type get_substring_range() const { return substring_range_; }
- string_range_type get_string_range() const { return string_range_; }
-
- typename boost::call_traits<comparator_type>::const_reference get_comparator() const
- { return comparator_; }
-
- //! Gets a reference to the current allocator
- typename boost::call_traits<allocator_type>::reference get_allocator()
- { return allocator_; }
-
- /*!
- \overload
- */
- typename boost::call_traits<allocator_type>::const_reference get_allocator() const
- { return allocator_; }
-
- private:
- inline void apply_changes()
- {
- if (substring_has_changed_ || string_has_changed_) {
- find_reset();
- if (substring_has_changed_) {
- on_substring_change();
- substring_has_changed_ = false;
- }
- if (string_has_changed_) {
- on_string_change();
- string_has_changed_ = false;
- }
- }
- }
-
-
- protected:
- substring_range_type substring_range_;
- string_range_type string_range_;
- bool substring_has_changed_, string_has_changed_;
-
- comparator_type comparator_;
- allocator_type allocator_;
-
- string_iterator_type start_offset_;
- };
-
-
- //!\todo fix simplified_finder_t then uncomment this code. use these structs in finder generators return types
- /*
- template <class Range1T, class Range2T, class AlgorithmT>
- struct first_finder_t
- {
- typedef boost::algorithm::simplified_finder_t<Range1T, Range2T, AlgorithmT,
- boost::algorithm::finder_behavior_first_finder> type;
- };
-
- template <class Range1T, class Range2T, class AlgorithmT>
- struct last_finder_t
- {
- typedef boost::algorithm::simplified_finder_t<Range1T, Range2T, AlgorithmT,
- boost::algorithm::finder_behavior_last_finder> type;
- };
-
- template <class Range1T, class Range2T, class AlgorithmT>
- struct nth_finder_t
- {
- typedef boost::algorithm::simplified_finder_t<Range1T, Range2T, AlgorithmT,
- boost::algorithm::finder_behavior_nth_finder> type;
- };
- */
-
- //! \todo copyable finder type below
-
- //! A generic finder type
- /*!
- Allows simple use of various string searching algorithms.
- \tparam Sequence1T The type of the substring
- \tparam Sequence2T The type of the string
- \tparam Algorithm An algorithm class
- which will be used for performing the searches. \see string_search.hpp
- \tparam Comparator Optional template parameter passed to the algorithm.
- Used for comparing individual characters for equality.
- \tparam Allocator Optional template parameter passed to the algorithm
- in the event that additional computation on the data has to be stored.
- */
- template <
- class Sequence1T, class Sequence2T,
- class AlgorithmT,
- typename ComparatorT = ::boost::algorithm::is_equal,
- class AllocatorT = std::allocator<std::size_t>,
- class AdditionalBehaviorT = boost::algorithm::finder_behavior_first_finder
- >
- class finder_t :
- public AlgorithmT::template algorithm<
- typename finder_t<Sequence1T, Sequence2T, AlgorithmT, ComparatorT, AllocatorT, AdditionalBehaviorT>,
- Sequence1T, Sequence2T, ComparatorT, AllocatorT>,
- public AdditionalBehaviorT::template apply<
- typename finder_t<Sequence1T, Sequence2T, AlgorithmT, ComparatorT, AllocatorT, AdditionalBehaviorT>,
- Sequence1T,Sequence2T,AlgorithmT,ComparatorT,AllocatorT>//,
- //public boost::algorithm::detail::finder_typedefs<Sequence1T, Sequence2T, ComparatorT, AllocatorT>
- {
- //! \todo: Maybe write a String concept?
- //! \todo: Currently, there's a SGI Sequence Concept implemented by Boost.ConceptCheck,
- //! but std::string does not obey this concept, which means that even calling these template
- //! parameters sequences is wrong.
- BOOST_CONCEPT_ASSERT((boost::Container<Sequence1T>));
- BOOST_CONCEPT_ASSERT((boost::Container<Sequence2T>));
- public:
- /*
- //! The type of the substring
- typedef Sequence1T substring_type;
- //! The type of the string
- typedef Sequence2T string_type;
- //! The type of the comparator
- typedef Comparator comparator_type;
- //! The type of the allocator
- typedef Allocator allocator_type;
- //! The type of the substring's iterator
- typedef typename boost::range_const_iterator<Sequence1T>::type substring_iterator_type;
- //! The type of the string's iterator
- typedef typename boost::range_iterator<Sequence2T>::type string_iterator_type;
- //! The character type of the substring
- typedef typename boost::iterator_value<substring_iterator_type>::type substring_char_type;
- //! The character type of the string
- typedef typename boost::iterator_value<string_iterator_type>::type string_char_type;
- typedef typename boost::iterator_range<substring_iterator_type> substring_range_type;
- typedef typename boost::iterator_range<string_iterator_type> string_range_type;
- typedef typename boost::iterator_difference<string_iterator_type>::type string_difference_type;
- */
- //! The type of the algorithm
- typedef typename AlgorithmT::template algorithm<finder_t,
- Sequence1T, Sequence2T, ComparatorT, AllocatorT> algorithm_type;
-
- typedef typename algorithm_type::substring_type substring_type;
- typedef typename algorithm_type::string_type string_type;
- typedef typename algorithm_type::comparator_type comparator_type;
- typedef typename algorithm_type::allocator_type allocator_type;
- typedef typename algorithm_type::substring_iterator_type substring_iterator_type;
- typedef typename algorithm_type::string_iterator_type string_iterator_type;
- typedef typename algorithm_type::substring_char_type substring_char_type;
- typedef typename algorithm_type::string_char_type string_char_type;
- typedef typename algorithm_type::substring_range_type substring_range_type;
- typedef typename algorithm_type::string_range_type string_range_type;
- typedef typename algorithm_type::string_difference_type string_difference_type;
- //! Constructs a finder given a string and a substring
- /*!
- \param substring Either a range (or character array)
- of the substring to be searched, or a pointer to a sequence of type \c substring_type.
- \param string Either a range (or character array)
- of the string to be searched, or a pointer to a sequence of type \c string_type.
- \param comparator A comparator object passed on to the algorithm
- \param allocator An allocator object passed on to the algorithm
- \note Both the substring and string can be passed either as references of ranges,
- or as pointers to sequences. In the former case, the substring and/or string is copied
- inside the class. In the latter class, the pointer is used and no copy is made.
- \warning Whereas the overloads taking pointers are faster (because no strings are copied around),
- you have to guarantee that the lifetime of your pointee is at least as long as the lifetime
- of the finder. If you cannot guarantee on the lifetime, use a reference instead, which will
- force a copy.
- \note If a rvalue reference is passed as the string or substring, and your compiler supports rvalue
- references, then a move is performed as opposed to a copy.
- */
- explicit finder_t (const Sequence1T *const substring = 0, Sequence2T *const string = 0,
- ComparatorT comparator = ComparatorT(), AllocatorT allocator = AllocatorT())
- : comparator_(comparator), allocator_(allocator),
- substring_optional_copy_(), substring_range_(substring?*substring:substring_optional_copy_),
- string_optional_copy_(), string_range_(string?*string:string_optional_copy_),
- start_offset_(boost::begin(string_range_)),
- algorithm_type(),
- substring_has_changed_(true), string_has_changed_(true)
- { }
-
- //! \overload
- template <class Range2T>
- finder_t (const Sequence1T *const substring, const Range2T &string,
- ComparatorT comparator = ComparatorT(), AllocatorT allocator = AllocatorT(),
- typename boost::disable_if<typename ::boost::algorithm::detail::is_pointer_to<Range2T,Sequence2T> >::type* = 0)
- : comparator_(comparator), allocator_(allocator),
- substring_optional_copy_(), substring_range_(substring?*substring:substring_optional_copy_),
- string_optional_copy_(), string_range_(),
- start_offset_(),
- algorithm_type(),
- substring_has_changed_(true), string_has_changed_(true)
- {
- set_string(string);
- //on_substring_change();
- }
-
- //! \overload
- template <class Range1T>
- explicit finder_t (const Range1T &substring, Sequence2T *const string = 0,
- ComparatorT comparator = ComparatorT(), AllocatorT allocator = AllocatorT(),
- typename boost::disable_if<typename ::boost::algorithm::detail::is_pointer_to<Range1T,Sequence1T> >::type* = 0)
- : comparator_(comparator), allocator_(allocator),
- substring_optional_copy_(), substring_range_(),
- string_optional_copy_(), string_range_(string?boost::as_literal(*string):string_optional_copy_),
- start_offset_(boost::begin(string_range_)),
- algorithm_type(),
- substring_has_changed_(true), string_has_changed_(true)
- {
- set_substring(substring);
- //on_string_change();
- }
-
- //! \overload
- template <class Range1T, class Range2T>
- finder_t (const Range1T &substring, const Range2T &string,
- ComparatorT comparator = ComparatorT(), AllocatorT allocator = AllocatorT(),
- typename boost::disable_if<boost::mpl::or_<typename ::boost::algorithm::detail::is_pointer_to<Range1T,Sequence1T>,
- typename ::boost::algorithm::detail::is_pointer_to<Range2T,Sequence2T> > >::type* = 0)
- : comparator_(comparator), allocator_(allocator),
- substring_optional_copy_(), substring_range_(),
- string_optional_copy_(), string_range_(),
- start_offset_(),
- algorithm_type(),
- substring_has_changed_(true), string_has_changed_(true)
- {
- set_substring(substring);
- set_string(string);
- }
-
-# ifdef BOOST_HAS_RVALUE_REFS
- //! \overload
- template <class Range2T>
- explicit finder_t (
- Sequence1T const &&substring,
- Sequence2T *const string = 0,
- ComparatorT comparator = ComparatorT(), AllocatorT allocator = AllocatorT())
- : comparator_(comparator), allocator_(allocator),
- substring_optional_copy_(std::move(substring)), string_optional_copy_(),
- substring_range_(substring_optional_copy_), string_range_(string?*string:string_optional_copy_),
- start_offset_(boost::begin(string_range_)),
- algorithm_type(),
- substring_has_changed_(true), string_has_changed_(true)
- { /*on_substring_change(); on_string_change();*/ }
-
- //! \overload
- template <class Range2T>
- explicit finder_t (
- Sequence1T const &&substring,
- const Range2T &string,
- ComparatorT comparator = ComparatorT(), AllocatorT allocator = AllocatorT(),
- typename boost::disable_if<typename ::boost::algorithm::detail::is_pointer_to<Range2T,Sequence2T> >::type* = 0)
- : comparator_(comparator), allocator_(allocator),
- substring_optional_copy_(std::move(substring)), substring_range_(substring_optional_copy_),
- string_optional_copy_(), string_range_(),
- start_offset_(),
- algorithm_type(),
- substring_has_changed_(true), string_has_changed_(true)
- { set_string(string); /*on_substring_change();*/ }
-
- //! \overload
- finder_t (
- Sequence1T const &&substring,
- Sequence2T &&string,
- ComparatorT comparator = ComparatorT(), AllocatorT allocator = AllocatorT())
- : comparator_(comparator), allocator_(allocator),
- substring_optional_copy_(std::move(substring)), string_optional_copy_(std::move(string)),
- substring_range_(substring_optional_copy_), string_range_(string_optional_copy_),
- start_offset_(boost::begin(string_range_)),
- algorithm_type(),
- substring_has_changed_(true), string_has_changed_(true)
- { /*on_substring_change(); on_string_change();*/ }
-
- //! \overload
- finder_t (const Sequence1T *const substring,
- Sequence2T &&string,
- ComparatorT comparator = ComparatorT(), AllocatorT allocator = AllocatorT())
- : comparator_(comparator), allocator_(allocator),
- substring_optional_copy_(), string_optional_copy_(std::move(string)),
- substring_range_(substring?*substring:substring_optional_copy_), string_range_(string_optional_copy_),
- start_offset_(boost::begin(string_range_)),
- algorithm_type(),
- substring_has_changed_(true), string_has_changed_(true)
- { /*on_substring_change(); on_string_change();*/ }
-
- //! \overload
- template <class Range1T>
- finder_t (const Range1T &substring,
- Sequence2T &&string,
- ComparatorT comparator = ComparatorT(), AllocatorT allocator = AllocatorT(),
- typename boost::disable_if<typename ::boost::algorithm::detail::is_pointer_to<Range1T,Sequence1T> >::type* = 0)
- : comparator_(comparator), allocator_(allocator),
- substring_optional_copy_(), substring_range_(),
- string_optional_copy_(std::move(string)), string_range_(string_optional_copy_),
- start_offset_(boost::begin(string_range_)),
- algorithm_type(),
- substring_has_changed_(true), string_has_changed_(true)
- { set_substring(substring); /*on_string_change();*/ }
-
-# endif
-
-
- //! Get an iterator range of the currently stored substring
- /*!
- \return An iterator range of the currently stored substring
- */
- //! \todo This may return iterators for copies of the string, properly deal with it.
- typename substring_range_type get_substring_range() const
- { return substring_range_; }
-
- //! Get an iterator range of the currently stored string
- /*!
- \return An iterator range of the currently stored string
- */
- typename string_range_type get_string_range() const
- { return string_range_; }
-
- //! Gets a reference to an instance of the comparator in use
- typename boost::call_traits<comparator_type>::const_reference get_comparator() const
- { return comparator_; }
-
- //! \todo: any reason why stdlib get_allocator()s return value types?
-
-
- //! Gets a reference to the current allocator
- typename boost::call_traits<allocator_type>::reference get_allocator()
- { return allocator_; }
-
- /*!
- \overload
- */
- typename boost::call_traits<allocator_type>::const_reference get_allocator() const
- { return allocator_; }
-
- //! Changes the substring to be searched for.
- /*!
- \param substring Either a range (or character array) corresponding to the new substring,
- or a pointer to a sequence of type \c substring_type
- */
- template <typename RangeT>
- void set_substring(RangeT const &substring,
- typename boost::disable_if<
- typename ::boost::algorithm::detail::is_pointer_to<RangeT,Sequence1T> >::type* = 0)
- {
- boost::iterator_range<typename boost::range_const_iterator<RangeT>::type> substring_range =
- boost::as_literal(substring);
- //substring_optional_copy_.assign(boost::begin(substring_range), boost::end(substring_range));
- substring_optional_copy_.clear();
- substring_optional_copy_.insert(substring_optional_copy_.end(),
- boost::begin(substring_range), boost::end(substring_range));
- substring_range_ = substring_optional_copy_;
- substring_has_changed_ = true;
- }
-
- void set_substring (Sequence1T const *const substring = 0)
- {
- substring_optional_copy_.clear();
- if (substring)
- substring_range_ = *substring;
- else
- substring_range_ = substring_optional_copy_;
- substring_has_changed_ = true;
- }
-
-# ifdef BOOST_HAS_RVALUE_REFS
- void set_substring (
- Sequence1T const &&substring)
- {
- substring_optional_copy_ = std::move(substring);
- substring_range_ = substring_optional_copy_;
- substring_has_changed_ = true;
- }
-# endif
-
- //! Changes the string to be searched for.
- /*!
- \param string Either a range (or character array) corresponding to the new substring,
- or a pointer to a sequence of type \c string_type
- */
- template <typename RangeT>
- void set_string(RangeT const &string,
- typename boost::disable_if<typename ::boost::algorithm::detail::is_pointer_to<RangeT,Sequence2T> >::type* = 0)
- {
- boost::iterator_range<typename boost::range_const_iterator<RangeT>::type> string_range =
- boost::as_literal(string);
- //string_optional_copy_.assign(boost::begin(string_range), boost::end(string_range));
- string_optional_copy_.clear();
- string_optional_copy_.insert(string_optional_copy_.end(),
- boost::begin(string_range), boost::end(string_range));
- string_range_ = string_optional_copy_;
- string_has_changed_ = true;
- }
-
- void set_string (Sequence2T *const string = 0)
- {
- string_optional_copy_.clear();
- if (string)
- string_range_ = *string;
- else
- string_range_ = string_optional_copy_;
- string_has_changed_ = true;
- }
-
-# ifdef BOOST_HAS_RVALUE_REFS
- void set_string (
- Sequence2T &&string)
- {
- string_optional_copy_ = std::move(string);
- string_range_ = string_optional_copy_;
- string_has_changed_ = true;
- }
-# endif
-
- //! \todo Change the object's substring or just use a temporary one?
- //! \todo Maybe this shouldn't be a part of finder_t, but a part of a certain AdditionalBehaviorT
- //! Perform a search...
- /*!
- \deprecated Only implemented to preserve compatibility
- with the previous Finder concept
- \todo This should probably only exist to classes that derive from finder_t (such as first_finder_t etc.)
- */
- string_range_type operator()(string_iterator_type const &string_start,
- string_iterator_type const &string_end)
- {
- set_string( boost::make_iterator_range(string_start, string_end) );
- return find_first();
- }
-
- void use_internal_string()
- {
- string_has_changed_ = true;
- find_reset();
- string_range_ = string_optional_copy_;
- }
-
- //! Performs a search using the chosen algorithm.
- /*!
- Looks for the first match of the substring in the string.
- \return An iterator range indicating where in the string
- a match has occurred. If there is no match, an iterator range with
- begin()==end()==string.end() is returned.
- \pre The iterator ranges for the string and substring must be set.
- \post The internal find offset is set immediately after the current match starts.
- \note This is semantically equivalent to \c find_reset(); match=find_next();
- */
-
- //!\todo Must return a range of const iterators, otherwise one could modify
- //! the range's contents, range which may actually
- //! be data of our private member
- string_range_type find_first()
- {
- //assert(substring_ && string_);
- //return algorithm_type::find(boost::begin(string_));
- find_reset();
- return find_next();
- }
-
- string_difference_type find_first_index()
- {
- find_reset();
- return find_next_index();
- }
-
- string_range_type find_next()
- {
- apply_changes();
- if (start_offset_ == boost::end(string_range_))
- return boost::iterator_range<string_iterator_type>(
- start_offset_, start_offset_
- );
- string_range_type ret =
- algorithm_type::find(start_offset_);
- if (boost::begin(ret) == boost::end(string_range_))
- {
- start_offset_ = boost::end(string_range_);
- return ret;
- }
- else
- {
- start_offset_ = boost::begin(ret);
- ++start_offset_;
- return ret;
- }
- }
-
- string_difference_type find_next_index()
- {
- apply_changes();
-
- //empty substring
- if (boost::begin(substring_range_) == boost::end(substring_range_))
- {
- //empty string, empty substring
- //!\todo if this gets called more times, it always returns 0
- //! i.e. the pointer is not moved. what would be a good solution for that?
- //! maybe a special dummy value for the range?
- if (boost::begin(string_range_) == boost::end(string_range_))
- return static_cast<string_difference_type>(0);
- //empty substring, offset at the end of the range
- if (start_offset_ == boost::end(string_range_))
- return static_cast<string_difference_type>(-1);
- //empty substring, offset not at the end of range
- return std::distance(boost::begin(string_range_),start_offset_++);
- }
- else if (boost::begin(string_range_) == boost::end(string_range_))
- {
- //empty string, nonempty substring
- return static_cast<string_difference_type>(-1);
- }
-
- //perform an actual search
- string_range_type const &match = find_next();
- if (boost::begin(match) == boost::end(string_range_))
- return static_cast<string_difference_type>(-1);
- return std::distance(boost::begin(string_range_), boost::begin(match));
- }
-
- void find_reset()
- {
- start_offset_ = boost::begin(string_range_);
- }
-
- //! \todo: Figure out whether you want to make finder iterators or not. find_iterator can be used otherwise.
- //const_iterator begin() const { }
- //const_iterator end() const { }
- private:
- inline void apply_changes()
- {
- if (substring_has_changed_ || string_has_changed_) {
- find_reset();
- if (substring_has_changed_) {
- on_substring_change();
- substring_has_changed_ = false;
- }
- if (string_has_changed_) {
- on_string_change();
- string_has_changed_ = false;
- }
- }
- }
-
- substring_type substring_optional_copy_;
- string_type string_optional_copy_;
- comparator_type comparator_;
- allocator_type allocator_;
- substring_range_type substring_range_;
- string_range_type string_range_;
- string_iterator_type start_offset_;
- bool substring_has_changed_, string_has_changed_;
- };
-
- //struct finder_no_additional_behavior
- //{ template <class,class,class,class,class,class> struct apply { }; };
-
- struct finder_behavior_first_finder
- {
- template <class FinderT,class Range1T,class Range2T,class AlgorithmT,class ComparatorT,class AllocatorT>
- struct apply
- {
- private:
- typedef boost::algorithm::detail::finder_typedefs<Range1T, Range2T, ComparatorT, AllocatorT> typedefs;
- public:
- typename typedefs::string_range_type operator()
- (typename typedefs::string_iterator_type &begin, typename typedefs::string_iterator_type &end)
- {
- //!\todo impl
- //boost::iterator_range<string_iterator_type>
- //set_string();
- }
- };
- };
- struct finder_behavior_last_finder
- {
- template <class FinderT,class Range1T,class Range2T,class AlgorithmT,class ComparatorT,class AllocatorT>
- struct apply
- {
- };
- };
- struct finder_behavior_nth_finder
- {
- template <class FinderT,class Range1T,class Range2T,class AlgorithmT,class ComparatorT,class AllocatorT>
- struct apply
- {
-
- };
- };
// Finder generators ------------------------------------------//
- //! "First" finder generator
+ //! "First" finder generator
/*!
- Construct the \c first_finder_t. The finder searches for the first
- occurrence of the string in a given input.
+ Constructs a \ref first_finder_t. For backward compatibility, the finder is a
+ functor which looks for the \b first occurrence of the string in a given input.
The result is given as an \c iterator_range delimiting the match.
-
- \param Search A substring to be searched for.
- \param Comp An element comparison predicate
- \return An instance of the \c first_finder object
+ \param Search The pattern to look for
+ \param Comp A comparator used to match individual characters
+ \tparam AlgorithmTagT A tag of the search algorithm that should be used for searching
\deprecated
*/
- /*template<typename RangeT>
- inline detail::first_finderF<
- BOOST_STRING_TYPENAME range_const_iterator<RangeT>::type,
- is_equal>
- first_finder( const RangeT& Search )
- {
- return
- detail::first_finderF<
- BOOST_STRING_TYPENAME
- range_const_iterator<RangeT>::type,
- is_equal>( ::boost::as_literal(Search), is_equal() ) ;
- }*/
-
- //! "First" finder
- /*!
- \overload
- \deprecated
- */
- /*template<typename RangeT,typename PredicateT>
- inline detail::first_finderF<
- BOOST_STRING_TYPENAME range_const_iterator<RangeT>::type,
- PredicateT>
- first_finder(
- const RangeT& Search, PredicateT Comp )
- {
- return
- detail::first_finderF<
- BOOST_STRING_TYPENAME
- range_const_iterator<RangeT>::type,
- PredicateT>( ::boost::as_literal(Search), Comp );
- }*/
template<typename RangeT,typename PredicateT, typename AlgorithmTagT>
- inline boost::algorithm::simplified_finder_t<RangeT, RangeT, typename AlgorithmTagT::type,
- PredicateT, std::allocator<std::size_t>, boost::algorithm::finder_behavior_first_finder>
+ inline boost::algorithm::first_finder_t<RangeT, RangeT, typename AlgorithmTagT::type,PredicateT>
first_finder(
const RangeT& Search, PredicateT const& Comp,
AlgorithmTagT const&)
{
- boost::algorithm::simplified_finder_t<RangeT, RangeT, typename AlgorithmTagT::type,
- PredicateT, std::allocator<std::size_t>, boost::algorithm::finder_behavior_first_finder>
- finder;
- finder.set_substring(&Search);
- return finder;
+ return boost::algorithm::first_finder_t<RangeT, RangeT, typename AlgorithmTagT::type,PredicateT>(&Search, Comp);
}
+ //! \overload
template<typename RangeT,typename PredicateT>
- inline boost::algorithm::simplified_finder_t<RangeT, RangeT, boost::algorithm::default_finder_algorithm,
- PredicateT, std::allocator<std::size_t>, boost::algorithm::finder_behavior_first_finder>
+ inline boost::algorithm::first_finder_t<RangeT, RangeT, boost::algorithm::default_finder_algorithm, PredicateT>
first_finder(
const RangeT& Search, PredicateT const& Comp)
{
return boost::algorithm::first_finder(Search,Comp, boost::algorithm::default_finder_algorithm_tag());
}
+ //! \overload
template<typename RangeT>
- inline boost::algorithm::simplified_finder_t<RangeT, RangeT, boost::algorithm::default_finder_algorithm,
- boost::algorithm::is_equal, std::allocator<std::size_t>, boost::algorithm::finder_behavior_first_finder>
+ inline boost::algorithm::first_finder_t<RangeT, RangeT, boost::algorithm::default_finder_algorithm,
+ boost::algorithm::is_equal>
first_finder(
const RangeT& Search)
{
return boost::algorithm::first_finder(Search,
boost::algorithm::is_equal(), boost::algorithm::default_finder_algorithm_tag());
}
- //! "Last" finder
+
+ //! "Last" finder generator
/*!
- Construct the \c last_finder. The finder searches for the last
- occurrence of the string in a given input.
+ Constructs a \ref last_finder_t. For backward compatibility, the finder is a
+ functor which looks for the \b last occurrence of the string in a given input.
The result is given as an \c iterator_range delimiting the match.
-
- \param Search A substring to be searched for.
- \param Comp An element comparison predicate
- \return An instance of the \c last_finder object
+ \param Search The pattern to look for
+ \param Comp A comparator used to match individual characters
+ \tparam AlgorithmTagT A tag of the search algorithm that should be used for searching
\deprecated
*/
- /*template<typename RangeT>
- inline detail::last_finderF<
- BOOST_STRING_TYPENAME range_const_iterator<RangeT>::type,
- is_equal>
- last_finder( const RangeT& Search )
- {
- return
- detail::last_finderF<
- BOOST_STRING_TYPENAME
- range_const_iterator<RangeT>::type,
- is_equal>( ::boost::as_literal(Search), is_equal() );
- }*/
- //! "Last" finder
- /*!
- \overload
- */
template<typename RangeT, typename PredicateT, typename AlgorithmTagT>
- inline boost::algorithm::simplified_finder_t<RangeT, RangeT, typename AlgorithmTagT::type,
- PredicateT, std::allocator<std::size_t>, boost::algorithm::finder_behavior_last_finder>
+ inline boost::algorithm::last_finder_t<RangeT, RangeT, typename AlgorithmTagT::type,PredicateT>
last_finder( const RangeT& Search, PredicateT const &Comp,
AlgorithmTagT const&)
{
- boost::algorithm::simplified_finder_t<RangeT, RangeT, typename AlgorithmTagT::type,
- PredicateT, std::allocator<std::size_t>, boost::algorithm::finder_behavior_last_finder>
- finder;
- finder.set_substring(&Search);
- return finder;
+ return boost::algorithm::last_finder_t<RangeT, RangeT, typename AlgorithmTagT::type,PredicateT>(&Search, Comp);
}
+ //!\overload
template<typename RangeT, typename PredicateT>
- inline boost::algorithm::simplified_finder_t<RangeT, RangeT, boost::algorithm::default_finder_algorithm,
- PredicateT, std::allocator<std::size_t>, boost::algorithm::finder_behavior_last_finder>
+ inline boost::algorithm::last_finder_t<RangeT, RangeT, boost::algorithm::default_finder_algorithm, PredicateT>
last_finder( const RangeT& Search, PredicateT const &Comp)
{
return boost::algorithm::last_finder(Search, Comp,
boost::algorithm::default_finder_algorithm_tag());
}
+ //!\overload
template<typename RangeT>
- inline boost::algorithm::simplified_finder_t<RangeT, RangeT, boost::algorithm::default_finder_algorithm,
- boost::algorithm::is_equal, std::allocator<std::size_t>, boost::algorithm::finder_behavior_last_finder>
+ inline boost::algorithm::last_finder_t<RangeT, RangeT, boost::algorithm::default_finder_algorithm,
+ boost::algorithm::is_equal>
last_finder( const RangeT& Search)
{
return boost::algorithm::last_finder(Search,
boost::algorithm::is_equal(), boost::algorithm::default_finder_algorithm_tag());
}
- //! "Nth" finder
+ //! "Nth" finder generator
/*!
- Construct the \c nth_finder. The finder searches for the n-th (zero-indexed)
- occurrence of the string in a given input.
+ Constructs a \ref nth_finder_t. For backward compatibility, the finder is a
+ functor which looks for the \b Nth occurrence of the string in a given input.
The result is given as an \c iterator_range delimiting the match.
-
- \param Search A substring to be searched for.
- \param Nth An index of the match to be find
- \param Comp An element comparison predicate
- \return An instance of the \c nth_finder object
- \deprecated
- */
- /*template<typename RangeT>
- inline detail::nth_finderF<
- BOOST_STRING_TYPENAME range_const_iterator<RangeT>::type,
- is_equal>
- nth_finder(
- const RangeT& Search,
- int Nth)
- {
- return
- detail::nth_finderF<
- BOOST_STRING_TYPENAME
- range_const_iterator<RangeT>::type,
- is_equal>( ::boost::as_literal(Search), Nth, is_equal() ) ;
- }*/
- //! "Nth" finder
- /*!
- \overload
+ \param Search The pattern to look for
+ \param Comp A comparator used to match individual characters
+ \tparam AlgorithmTagT A tag of the search algorithm that should be used for searching
\deprecated
*/
template<typename RangeT, typename PredicateT, typename AlgorithmTagT>
- inline boost::algorithm::simplified_finder_t<RangeT, RangeT, typename AlgorithmTagT::type,
- PredicateT, std::allocator<std::size_t>, boost::algorithm::finder_behavior_nth_finder>
+ inline boost::algorithm::nth_finder_t<RangeT, RangeT, typename AlgorithmTagT::type,PredicateT>
nth_finder(const RangeT& Search, int Nth, PredicateT const &Comp, AlgorithmTagT const &)
{
- boost::algorithm::simplified_finder_t<RangeT, RangeT, typename AlgorithmTagT::type,
- PredicateT, std::allocator<std::size_t>, boost::algorithm::finder_behavior_nth_finder>
- finder;
- finder.set_N(Nth);
- finder.set_substring(&Search);
- return finder;
+ return boost::algorithm::nth_finder_t<RangeT, RangeT, typename AlgorithmTagT::type, PredicateT>(&Search, Comp, Nth);
}
+ //!\overload
template<typename RangeT, typename PredicateT>
- inline boost::algorithm::simplified_finder_t<RangeT, RangeT, boost::algorithm::is_equal,
- PredicateT, std::allocator<std::size_t>, boost::algorithm::finder_behavior_nth_finder>
+ inline boost::algorithm::nth_finder_t<RangeT, RangeT, boost::algorithm::default_finder_algorithm,PredicateT>
nth_finder(const RangeT& Search, int Nth, PredicateT const &Comp)
{
return boost::algorithm::nth_finder(Search, Nth, Comp,
boost::algorithm::default_finder_algorithm_tag());
}
+ //!\overload
template<typename RangeT>
- inline boost::algorithm::simplified_finder_t<RangeT, RangeT, boost::algorithm::is_equal,
- boost::algorithm::is_equal, std::allocator<std::size_t>, boost::algorithm::finder_behavior_nth_finder>
+ inline boost::algorithm::nth_finder_t<RangeT, RangeT, boost::algorithm::default_finder_algorithm,
+ boost::algorithm::is_equal>
nth_finder(const RangeT& Search, int Nth)
{
return boost::algorithm::nth_finder(Search, Nth, boost::algorithm::is_equal(),
@@ -962,6 +190,7 @@
\param N The size of the head
\return An instance of the \c head_finder object
+ \deprecated
*/
inline detail::head_finderF
head_finder( int N )
@@ -1056,16 +285,6 @@
using algorithm::tail_finder;
using algorithm::token_finder;
using algorithm::range_finder;
-
-
- //! \TODO: any other finder types?
- using algorithm::finder_t;
- using algorithm::simplified_finder_t;
- //using algorithm::finder_no_additional_behavior;
- using algorithm::finder_behavior_first_finder;
- using algorithm::finder_behavior_last_finder;
- using algorithm::finder_behavior_nth_finder;
- using algorithm::default_finder_algorithm;
} // namespace boost
Added: sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/default_search_algorithm.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/default_search_algorithm.hpp 2010-08-11 18:26:46 EDT (Wed, 11 Aug 2010)
@@ -0,0 +1,20 @@
+#ifndef BOOST_ALGORITHM_DEFAULT_SEARCH_ALGORITHM_HPP
+#define BOOST_ALGORITHM_DEFAULT_SEARCH_ALGORITHM_HPP
+
+#include <boost/algorithm/string/string_search/knuth_morris_pratt.hpp>
+
+namespace boost { namespace algorithm {
+ //! The default search algorithm used by find/replace functions.
+ typedef boost::algorithm::knuth_morris_pratt default_finder_algorithm;
+
+ //! The tag of the default search algorithm used by find/replace functions.
+ //! Instances of this type can be passed to find/replace functions.
+ struct default_finder_algorithm_tag { typedef boost::algorithm::knuth_morris_pratt type; };
+} }
+
+namespace boost
+{
+ using algorithm::default_finder_algorithm;
+}
+
+#endif
Added: sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/detail/finder_typedefs.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/detail/finder_typedefs.hpp 2010-08-11 18:26:46 EDT (Wed, 11 Aug 2010)
@@ -0,0 +1,57 @@
+#ifndef BOOST_ALGORITHM_FINDER_TYPEDEFS_HPP
+#define BOOST_ALGORITHM_FINDER_TYPEDEFS_HPP
+
+#include <boost/range/iterator_range.hpp>
+#include <boost/range/const_iterator.hpp>
+#include <boost/range/iterator.hpp>
+#include <boost/range/category.hpp>
+
+#include <boost/iterator/iterator_traits.hpp>
+
+namespace boost { namespace algorithm { namespace detail {
+
+ template <class Range1T, class Range2T, class ComparatorT, class AllocatorT>
+ struct finder_typedefs
+ {
+ //! The type of the substring
+ typedef Range1T substring_type;
+ //! The type of the string
+ typedef Range2T string_type;
+ //! The type of the comparator
+ typedef ComparatorT comparator_type;
+ //! The type of the allocator
+ typedef AllocatorT allocator_type;
+ //! The type of the substring's iterator
+ typedef typename boost::range_const_iterator<substring_type>::type
+ substring_iterator_type;
+ //! The type of the string's iterator
+ typedef typename boost::range_iterator<string_type>::type
+ string_iterator_type;
+ //! The character type of the substring
+ typedef typename boost::iterator_value<substring_iterator_type>::type
+ substring_char_type;
+ //! The character type of the string
+ typedef typename boost::iterator_value<string_iterator_type>::type
+ string_char_type;
+ //! The range type of the substring (pattern)
+ typedef typename boost::iterator_range<substring_iterator_type>
+ substring_range_type;
+ //! The range type of the text
+ typedef typename boost::iterator_range<string_iterator_type>
+ string_range_type;
+ //! A type capable of holding the difference between two iterators of the text
+ typedef typename boost::iterator_difference<string_iterator_type>::type
+ string_difference_type;
+ protected:
+ typedef typename boost::range_category<substring_type>::type substring_iterator_category;
+ typedef typename boost::range_category<string_type>::type string_iterator_category;
+
+ typedef typename boost::reverse_iterator<substring_iterator_type> substring_reverse_iterator_type;
+ typedef typename boost::reverse_iterator<string_iterator_type> string_reverse_iterator_type;
+ typedef typename boost::iterator_range<substring_reverse_iterator_type> substring_reverse_range_type;
+ typedef typename boost::iterator_range<string_reverse_iterator_type> string_reverse_range_type;
+ };
+
+} } }
+
+#endif // BOOST_ALGORITHM_FINDER_TYPEDEFS_HPP
\ No newline at end of file
Added: sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/detail/is_pointer_to.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/detail/is_pointer_to.hpp 2010-08-11 18:26:46 EDT (Wed, 11 Aug 2010)
@@ -0,0 +1,16 @@
+#ifndef BOOST_ALGORITHM_IS_POINTER_TO_HPP
+#define BOOST_ALGORITHM_IS_POINTER_TO_HPP
+
+namespace boost { namespace algorithm { namespace detail {
+
+ template <class T, class U> struct is_pointer_to :
+ boost::mpl::and_<
+ typename boost::is_pointer<T>,
+ typename boost::is_same<
+ typename boost::remove_cv<typename boost::remove_pointer<T>::type>::type,
+ U>
+ > {};
+
+} } }
+
+#endif // BOOST_ALGORITHM_IS_POINTER_TO_HPP
\ No newline at end of file
Added: sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/detail/last_finder_impl.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/detail/last_finder_impl.hpp 2010-08-11 18:26:46 EDT (Wed, 11 Aug 2010)
@@ -0,0 +1,99 @@
+#ifndef BOOST_ALGORITHM_DETAIL_LAST_FINDER_IMPL_HPP
+#define BOOST_ALGORITHM_DETAIL_LAST_FINDER_IMPL_HPP
+
+#include <boost/iterator/iterator_traits.hpp>
+#include <boost/iterator/reverse_iterator.hpp>
+
+#include <boost/mpl/and.hpp>
+#include <boost/mpl/or.hpp>
+#include <boost/mpl/not.hpp>
+#include <boost/type_traits/is_base_of.hpp>
+
+#include <boost/utility/enable_if.hpp>
+
+#include <memory>
+#include <iterator>
+
+#include <boost/range/category.hpp>
+
+#include <boost/algorithm/string/finder/simplified_finder.hpp>
+#include <boost/algorithm/string/finder/detail/finder_typedefs.hpp>
+
+
+namespace boost { namespace algorithm { namespace detail {
+
+ template <class Range1T, class Range2T, class AlgorithmT,
+ class ComparatorT, class Enable = void>
+ class last_finder_impl_t;
+
+ //Implementation of last_finder_t when both ranges are bidirectional
+ template <class Range1T, class Range2T, class AlgorithmT, class ComparatorT>
+ class last_finder_impl_t<Range1T, Range2T, AlgorithmT, ComparatorT,
+ typename boost::enable_if<
+ typename boost::mpl::and_<
+ typename boost::is_base_of<std::bidirectional_iterator_tag, typename boost::range_category<Range1T>::type>,
+ typename boost::is_base_of<std::bidirectional_iterator_tag, typename boost::range_category<Range2T>::type>
+ >
+ >::type>
+ : public boost::algorithm::detail::finder_typedefs<Range1T, Range2T, ComparatorT, std::allocator<std::size_t> >
+ {
+ public:
+ last_finder_impl_t (substring_range_type const &substr, ComparatorT comparator=ComparatorT())
+ : finder(comparator)
+ { finder.set_substring(substring_reverse_iterator_type(boost::end(substr)),
+ substring_reverse_iterator_type(boost::begin(substr))
+ ); }
+ string_range_type operator()(string_iterator_type const &string_start, string_iterator_type const &string_end)
+ {
+ finder.set_string(string_reverse_iterator_type(string_end),
+ string_reverse_iterator_type(string_start));
+ string_reverse_range_type &ret = finder.find_first();
+ //no match
+ if (boost::begin(ret) == boost::end(finder.get_string_range()))
+ return boost::make_iterator_range(string_end, string_end);
+ return boost::make_iterator_range(boost::end(ret).base(), boost::begin(ret).base());
+ }
+ private:
+ typedef typename boost::algorithm::simplified_finder_t<
+ substring_reverse_range_type, string_reverse_range_type, AlgorithmT, ComparatorT> reverse_finder_type;
+ reverse_finder_type finder;
+ };
+
+ //Implementation of last_finder_t when at least one range is not bidirectional
+ template <class Range1T, class Range2T, class AlgorithmT, class ComparatorT>
+ class last_finder_impl_t<Range1T, Range2T, AlgorithmT, ComparatorT,
+ typename boost::enable_if<
+ typename boost::mpl::or_<
+ typename boost::mpl::not_<
+ typename boost::is_base_of<std::bidirectional_iterator_tag, typename boost::range_category<Range1T>::type>
+ >,
+ typename boost::mpl::not_<
+ typename boost::is_base_of<std::bidirectional_iterator_tag, typename boost::range_category<Range2T>::type>
+ >
+ >
+ >::type>
+ : public boost::algorithm::detail::finder_typedefs<Range1T, Range2T, ComparatorT, std::allocator<std::size_t> >
+ {
+ public:
+ last_finder_impl_t (substring_range_type const &substr, ComparatorT comparator=ComparatorT())
+ : finder(comparator)
+ { finder.set_substring(boost::begin(substr), boost::end(substr)); }
+ string_range_type operator()(string_iterator_type const &string_start, string_iterator_type const &string_end)
+ {
+ finder.set_string(string_start, string_end);
+ string_iterator_type prev, crt = make_iterator_range(string_start, string_end);
+ for (;;)
+ {
+ prev = crt;
+ crt = finder.find_next();
+ if (boost::begin(crt) == string_end) break;
+ }
+ return prev;
+ }
+ private:
+ typedef boost::algorithm::simplified_finder_t<Range1T, Range2T, AlgorithmT, ComparatorT> internal_finder_type;
+ internal_finder_type finder;
+ };
+
+} } }
+#endif // BOOST_ALGORITHM_DETAIL_LAST_FINDER_IMPL_HPP
\ No newline at end of file
Added: sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/detail/nth_finder_impl.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/detail/nth_finder_impl.hpp 2010-08-11 18:26:46 EDT (Wed, 11 Aug 2010)
@@ -0,0 +1,136 @@
+#ifndef BOOST_ALGORITHM_DETAIL_NTH_FINDER_IMPL_HPP
+#define BOOST_ALGORITHM_DETAIL_NTH_FINDER_IMPL_HPP
+
+#include <boost/iterator/iterator_traits.hpp>
+#include <boost/iterator/reverse_iterator.hpp>
+
+#include <boost/mpl/and.hpp>
+#include <boost/mpl/or.hpp>
+#include <boost/mpl/not.hpp>
+#include <boost/type_traits/is_base_of.hpp>
+
+#include <boost/utility/enable_if.hpp>
+
+#include <memory>
+#include <iterator>
+#include <stdexcept>
+
+#include <boost/range/category.hpp>
+
+#include <boost/algorithm/string/finder/simplified_finder.hpp>
+#include <boost/algorithm/string/finder/detail/finder_typedefs.hpp>
+
+namespace boost { namespace algorithm { namespace detail {
+
+ template <class Range1T, class Range2T, class AlgorithmT,
+ class ComparatorT, class Enable = void>
+ class nth_finder_impl_t;
+
+ //Implementation of last_finder_t when both ranges are bidirectional
+ template <class Range1T, class Range2T, class AlgorithmT, class ComparatorT>
+ class nth_finder_impl_t<Range1T, Range2T, AlgorithmT, ComparatorT,
+ typename boost::enable_if<
+ typename boost::mpl::and_<
+ typename boost::is_base_of<std::bidirectional_iterator_tag, typename boost::range_category<Range1T>::type>,
+ typename boost::is_base_of<std::bidirectional_iterator_tag, typename boost::range_category<Range2T>::type>
+ >
+ >::type>
+ : public boost::algorithm::detail::finder_typedefs<Range1T, Range2T, ComparatorT, std::allocator<std::size_t> >
+ {
+ public:
+ nth_finder_impl_t (substring_range_type const &substr, ComparatorT comparator=ComparatorT(), int n = 0)
+ : n_(n), finder(comparator), reverse_finder(comparator)
+ {
+ reverse_finder.set_substring(substring_reverse_iterator_type(boost::end(substr)),
+ substring_reverse_iterator_type(boost::begin(substr)));
+ finder.set_substring(boost::begin(substr), boost::end(substr));
+ }
+ string_range_type operator()(string_iterator_type const &string_start, string_iterator_type const &string_end)
+ {
+ if (n_ >= 0)
+ {
+ finder.set_string(string_start, string_end);
+ string_range_type ret;
+ for (int n = 0; n <= n_; ++n)
+ {
+ ret = finder.find_next();
+ if (boost::begin(ret) == string_end)
+ return make_iterator_range(string_end, string_end);
+ }
+ return ret;
+ }
+ else
+ {
+ reverse_finder.set_string(
+ string_reverse_iterator_type(string_end), string_reverse_iterator_type(string_start));
+ string_reverse_range_type ret;
+ int n_2 = -n_ - 1;
+ for (int n = 0; n <= n_2; ++n)
+ {
+ ret = reverse_finder.find_next();
+ if (boost::begin(ret) == boost::end(reverse_finder.get_string_range()))
+ return boost::make_iterator_range(string_end, string_end);
+ }
+ return boost::make_iterator_range(boost::end(ret).base(), boost::begin(ret).base() );
+ }
+ }
+ void set_n(int n)
+ { n_ = n; }
+ private:
+ typedef typename boost::algorithm::simplified_finder_t<
+ substring_reverse_range_type, string_reverse_range_type, AlgorithmT, ComparatorT> reverse_finder_type;
+ typedef typename boost::algorithm::simplified_finder_t<
+ substring_type, string_type, AlgorithmT, ComparatorT> finder_type;
+ finder_type finder;
+ reverse_finder_type reverse_finder;
+ int n_;
+ };
+
+ //Implementation of nth_finder_t when at least one range is not bidirectional
+ template <class Range1T, class Range2T, class AlgorithmT, class ComparatorT>
+ class nth_finder_impl_t<Range1T, Range2T, AlgorithmT, ComparatorT,
+ typename boost::enable_if<
+ typename boost::mpl::or_<
+ typename boost::mpl::not_<
+ typename boost::is_base_of<std::bidirectional_iterator_tag, typename boost::range_category<Range1T>::type>
+ >,
+ typename boost::mpl::not_<
+ typename boost::is_base_of<std::bidirectional_iterator_tag, typename boost::range_category<Range2T>::type>
+ >
+ >
+ >::type>
+ : public boost::algorithm::detail::finder_typedefs<Range1T, Range2T, ComparatorT, std::allocator<std::size_t> >
+ {
+ public:
+ nth_finder_impl_t (substring_range_type const &substr, ComparatorT comparator=ComparatorT(), int n = 0)
+ : finder(comparator)
+ {
+ assert (n > = 0); // we do not have bidirectional iterators
+ finder.set_substring(boost::begin(substr), boost::end(substr));
+ }
+
+ string_range_type operator()(string_iterator_type const &string_start, string_iterator_type const &string_end)
+ {
+ finder.set_string(string_start, string_end);
+ string_range_type ret;
+ for (int n = 0; n <= n_; ++n)
+ {
+ ret = finder.find_next();
+ if (boost::begin(ret) == string_end)
+ return boost::make_iterator_range(string_end, string_end);
+ }
+ return ret;
+ }
+
+ void set_n(int n)
+ { assert(n >= 0); n_ = n; }
+ private:
+ typedef typename boost::algorithm::simplified_finder_t<
+ substring_type, string_type, AlgorithmT, ComparatorT> finder_type;
+ finder_type finder;
+ int n_;
+ };
+
+} } }
+
+#endif // BOOST_ALGORITHM_DETAIL_NTH_FINDER_IMPL_HPP
\ No newline at end of file
Added: sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/finder.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/finder.hpp 2010-08-11 18:26:46 EDT (Wed, 11 Aug 2010)
@@ -0,0 +1,577 @@
+#ifndef BOOST_ALGORITHM_FINDER_T_HPP
+#define BOOST_ALGORITHM_FINDER_T_HPP
+
+#include <boost/algorithm/string/compare.hpp>
+#include <boost/algorithm/string/finder/detail/is_pointer_to.hpp>
+
+#include <memory>
+
+#include <boost/concept_check.hpp>
+
+#include <boost/range/begin.hpp>
+#include <boost/range/end.hpp>
+#include <boost/range/as_literal.hpp>
+#include <boost/range/iterator.hpp>
+#include <boost/range/iterator_range.hpp>
+
+#include <boost/utility/enable_if.hpp>
+
+#include <boost/call_traits.hpp>
+
+namespace boost { namespace algorithm {
+
+ //TODO: copyable finder type below?
+
+ //! A generic finder type
+ /*!
+ Allows simple use of various string search algorithms.
+ \tparam Sequence1T A sequence representing the type of the substring (pattern)
+ \tparam Sequence2T A sequence representing the type of the string (text)
+ \tparam AlgorithmT The algorithm used to perform the searches
+ \tparam ComparatorT Optional template parameter passed to the algorithm.
+ Used for comparing individual characters for equality.
+ \tparam AllocatorT Optional template parameter passed to the algorithm
+ in the event that additional computation on the data has to be stored.
+ \tparam AdditionalBehaviorT Optional template parameter used to extend the functionality of
+ the finder.
+ \note This finder holds an internal sequence of type Sequence1T and Sequence2T.
+ They are used to store copies of the pattern and/or the text, when they are passed by
+ reference to the finder.
+ */
+ template <
+ class Sequence1T, class Sequence2T,
+ class AlgorithmT,
+ typename ComparatorT = ::boost::algorithm::is_equal,
+ class AllocatorT = std::allocator<std::size_t>
+ >
+ class finder_t :
+ public AlgorithmT::template algorithm<
+ typename finder_t<Sequence1T, Sequence2T, AlgorithmT, ComparatorT, AllocatorT>,
+ Sequence1T, Sequence2T, ComparatorT, AllocatorT>
+ {
+ //TODO:: Maybe write a String concept?
+ //TODO:: Currently, there's a SGI Sequence Concept implemented by Boost.ConceptCheck,
+ //! but std::string does not obey this concept, which means that even calling these template
+ //! parameters sequences is wrong.
+ BOOST_CONCEPT_ASSERT((boost::Container<Sequence1T>));
+ BOOST_CONCEPT_ASSERT((boost::Container<Sequence2T>));
+ private:
+ typedef typename AlgorithmT::template algorithm<finder_t, Sequence1T,
+ Sequence2T, ComparatorT, AllocatorT> algorithm_type;
+ public:
+ //! The type of the pattern (substring)
+ typedef typename algorithm_type::substring_type substring_type;
+ //! The type of the text (string)
+ typedef typename algorithm_type::string_type string_type;
+ //! The type of the comparator
+ typedef typename algorithm_type::comparator_type comparator_type;
+ //! The type of the allocator
+ typedef typename algorithm_type::allocator_type allocator_type;
+ //! The type of the substring's iterator
+ typedef typename algorithm_type::substring_iterator_type substring_iterator_type;
+ //! The type of the text's iterator
+ typedef typename algorithm_type::string_iterator_type string_iterator_type;
+ //! The character type of the substring
+ typedef typename algorithm_type::substring_char_type substring_char_type;
+ //! The character type of the text
+ typedef typename algorithm_type::string_char_type string_char_type;
+ //! The range type of the substring (pattern)
+ typedef typename algorithm_type::substring_range_type substring_range_type;
+ //! The range type of the text
+ typedef typename algorithm_type::string_range_type string_range_type;
+ //! A type capable of holding the difference between two iterators of the text
+ typedef typename algorithm_type::string_difference_type string_difference_type;
+
+ //! Constructs a finder given a pattern and a text
+ /*!
+ \param substring Either a range (or character array)
+ of the pattern to be searched, or a pointer to a sequence of type \ref substring_type.
+ \param string Either a range (or character array)
+ of the string to be searched, or a pointer to a sequence of type \ref string_type..
+ \param comparator ComparatorT instance used to compare individual characters
+ \param allocator AllocatorT instance used to allocate memory
+ for storing precomputed data if necessary
+ \note Both the pattern and the text can be passed either as references of ranges,
+ or as pointers to sequences. In the former case, the pattern and/or text is copied
+ internally. In the latter class, the pointer is used by the finder and no copy is made.
+ \warning Whereas the overloads taking pointers are faster (because no strings are copied around),
+ you have to guarantee that the lifetime of your pointee is at least as long as the lifetime
+ of the finder. If you cannot guarantee on the lifetime, use a reference instead, which will
+ force a copy.
+ \note If a rvalue reference is passed as the string or substring, and your compiler supports rvalue
+ references, then a move is performed as opposed to a copy.
+ */
+ explicit finder_t (const Sequence1T *const substring = 0, Sequence2T *const string = 0,
+ ComparatorT comparator = ComparatorT(), AllocatorT allocator = AllocatorT())
+ : comparator_(comparator), allocator_(allocator),
+ substring_optional_copy_(), substring_range_(substring?*substring:substring_optional_copy_),
+ string_optional_copy_(), string_range_(string?*string:string_optional_copy_),
+ start_offset_(boost::begin(string_range_)),
+ algorithm_type(),
+ substring_has_changed_(true), string_has_changed_(true)
+ { }
+
+ //! \overload
+ template <class Range2T>
+ finder_t (const Sequence1T *const substring, const Range2T &string,
+ ComparatorT comparator = ComparatorT(), AllocatorT allocator = AllocatorT(),
+ typename boost::disable_if<typename ::boost::algorithm::detail::is_pointer_to<Range2T,Sequence2T> >::type* = 0)
+ : comparator_(comparator), allocator_(allocator),
+ substring_optional_copy_(), substring_range_(substring?*substring:substring_optional_copy_),
+ string_optional_copy_(), string_range_(),
+ start_offset_(),
+ algorithm_type(),
+ substring_has_changed_(true), string_has_changed_(true)
+ {
+ set_string(string);
+ }
+
+ //! \overload
+ template <class Range1T>
+ explicit finder_t (const Range1T &substring, Sequence2T *const string = 0,
+ ComparatorT comparator = ComparatorT(), AllocatorT allocator = AllocatorT(),
+ typename boost::disable_if<typename ::boost::algorithm::detail::is_pointer_to<Range1T,Sequence1T> >::type* = 0)
+ : comparator_(comparator), allocator_(allocator),
+ substring_optional_copy_(), substring_range_(),
+ string_optional_copy_(), string_range_(string?boost::as_literal(*string):string_optional_copy_),
+ start_offset_(boost::begin(string_range_)),
+ algorithm_type(),
+ substring_has_changed_(true), string_has_changed_(true)
+ {
+ set_substring(substring);
+ }
+
+ //! \overload
+ template <class Range1T, class Range2T>
+ finder_t (const Range1T &substring, const Range2T &string,
+ ComparatorT comparator = ComparatorT(), AllocatorT allocator = AllocatorT(),
+ typename boost::disable_if<boost::mpl::or_<typename ::boost::algorithm::detail::is_pointer_to<Range1T,Sequence1T>,
+ typename ::boost::algorithm::detail::is_pointer_to<Range2T,Sequence2T> > >::type* = 0)
+ : comparator_(comparator), allocator_(allocator),
+ substring_optional_copy_(), substring_range_(),
+ string_optional_copy_(), string_range_(),
+ start_offset_(),
+ algorithm_type(),
+ substring_has_changed_(true), string_has_changed_(true)
+ {
+ set_substring(substring);
+ set_string(string);
+ }
+
+# ifdef BOOST_HAS_RVALUE_REFS
+ //! \overload
+ template <class Range2T>
+ explicit finder_t (
+ Sequence1T const &&substring,
+ Sequence2T *const string = 0,
+ ComparatorT comparator = ComparatorT(), AllocatorT allocator = AllocatorT())
+ : comparator_(comparator), allocator_(allocator),
+ substring_optional_copy_(std::move(substring)), string_optional_copy_(),
+ substring_range_(substring_optional_copy_), string_range_(string?*string:string_optional_copy_),
+ start_offset_(boost::begin(string_range_)),
+ algorithm_type(),
+ substring_has_changed_(true), string_has_changed_(true)
+ { }
+
+ //! \overload
+ template <class Range2T>
+ explicit finder_t (
+ Sequence1T const &&substring,
+ const Range2T &string,
+ ComparatorT comparator = ComparatorT(), AllocatorT allocator = AllocatorT(),
+ typename boost::disable_if<typename ::boost::algorithm::detail::is_pointer_to<Range2T,Sequence2T> >::type* = 0)
+ : comparator_(comparator), allocator_(allocator),
+ substring_optional_copy_(std::move(substring)), substring_range_(substring_optional_copy_),
+ string_optional_copy_(), string_range_(),
+ start_offset_(),
+ algorithm_type(),
+ substring_has_changed_(true), string_has_changed_(true)
+ { set_string(string); }
+
+ //! \overload
+ finder_t (
+ Sequence1T const &&substring,
+ Sequence2T &&string,
+ ComparatorT comparator = ComparatorT(), AllocatorT allocator = AllocatorT())
+ : comparator_(comparator), allocator_(allocator),
+ substring_optional_copy_(std::move(substring)), string_optional_copy_(std::move(string)),
+ substring_range_(substring_optional_copy_), string_range_(string_optional_copy_),
+ start_offset_(boost::begin(string_range_)),
+ algorithm_type(),
+ substring_has_changed_(true), string_has_changed_(true)
+ { }
+
+ //! \overload
+ finder_t (const Sequence1T *const substring,
+ Sequence2T &&string,
+ ComparatorT comparator = ComparatorT(), AllocatorT allocator = AllocatorT())
+ : comparator_(comparator), allocator_(allocator),
+ substring_optional_copy_(), string_optional_copy_(std::move(string)),
+ substring_range_(substring?*substring:substring_optional_copy_), string_range_(string_optional_copy_),
+ start_offset_(boost::begin(string_range_)),
+ algorithm_type(),
+ substring_has_changed_(true), string_has_changed_(true)
+ { }
+
+ //! \overload
+ template <class Range1T>
+ finder_t (const Range1T &substring,
+ Sequence2T &&string,
+ ComparatorT comparator = ComparatorT(), AllocatorT allocator = AllocatorT(),
+ typename boost::disable_if<typename ::boost::algorithm::detail::is_pointer_to<Range1T,Sequence1T> >::type* = 0)
+ : comparator_(comparator), allocator_(allocator),
+ substring_optional_copy_(), substring_range_(),
+ string_optional_copy_(std::move(string)), string_range_(string_optional_copy_),
+ start_offset_(boost::begin(string_range_)),
+ algorithm_type(),
+ substring_has_changed_(true), string_has_changed_(true)
+ { set_substring(substring); }
+
+# endif
+
+
+ //! Get an iterator range of the current pattern (substring)
+ /*!
+ \return Iterator range of the current pattern
+ \warning If you modify the contents in the returned range, you must manually call
+ \ref use_internal_substring() (if the used pattern was the internal pattern)
+ or .set_substring(&your_pattern) otherwise
+ */
+ typename substring_range_type get_substring_range() const
+ { return substring_range_; }
+
+ //! Get an iterator range of the current text
+ /*!
+ \return Range of the current text
+ \see get_substring_range()
+ */
+ typename string_range_type get_string_range() const
+ { return string_range_; }
+
+ //! Gets a reference to an instance of the comparator in use
+ typename boost::call_traits<comparator_type>::const_reference get_comparator() const
+ { return comparator_; }
+
+
+ //! Gets a reference to the current allocator
+ //! \return A reference to the current allocator
+ typename boost::call_traits<allocator_type>::reference get_allocator()
+ { return allocator_; }
+
+ //! Gets a reference to the current allocator
+ //! \return A reference to the current allocator
+ typename boost::call_traits<allocator_type>::const_reference get_allocator() const
+ { return allocator_; }
+
+ //! Change the pattern (substring) to be searched.
+ /*!
+ \param substring Either a range (or character array) corresponding to the new substring,
+ or a pointer to a sequence of type \c substring_type
+ \warning The same rule on the lifetime of the pointee applies. (see the constructor for details)
+ */
+ template <typename RangeT>
+ void set_substring(RangeT const &substring,
+ typename boost::disable_if<
+ typename ::boost::algorithm::detail::is_pointer_to<RangeT,Sequence1T> >::type* = 0)
+ {
+ boost::iterator_range<typename boost::range_const_iterator<RangeT>::type> substring_range =
+ boost::as_literal(substring);
+ //substring_optional_copy_.assign(boost::begin(substring_range), boost::end(substring_range));
+ substring_optional_copy_.clear();
+ substring_optional_copy_.insert(substring_optional_copy_.end(),
+ boost::begin(substring_range), boost::end(substring_range));
+ substring_range_ = substring_optional_copy_;
+ substring_has_changed_ = true;
+ }
+
+ //! \overload
+ void set_substring (Sequence1T const *const substring = 0)
+ {
+ substring_optional_copy_.clear();
+ if (substring)
+ substring_range_ = *substring;
+ else
+ substring_range_ = substring_optional_copy_;
+ substring_has_changed_ = true;
+ }
+
+# ifdef BOOST_HAS_RVALUE_REFS
+ //!\overload
+ void set_substring (
+ Sequence1T const &&substring)
+ {
+ substring_optional_copy_ = std::move(substring);
+ substring_range_ = substring_optional_copy_;
+ substring_has_changed_ = true;
+ }
+# endif
+
+ //! Change the text in which to search.
+ /*!
+ \param string Either a range (or character array) corresponding to the new substring,
+ or a pointer to a sequence of type \ref string_type
+ */
+ template <typename RangeT>
+ void set_string(RangeT const &string,
+ typename boost::disable_if<typename ::boost::algorithm::detail::is_pointer_to<RangeT,Sequence2T> >::type* = 0)
+ {
+ boost::iterator_range<typename boost::range_const_iterator<RangeT>::type> string_range =
+ boost::as_literal(string);
+ //string_optional_copy_.assign(boost::begin(string_range), boost::end(string_range));
+ string_optional_copy_.clear();
+ string_optional_copy_.insert(string_optional_copy_.end(),
+ boost::begin(string_range), boost::end(string_range));
+ string_range_ = string_optional_copy_;
+ string_has_changed_ = true;
+ }
+
+ //!\overload
+ void set_string (Sequence2T *const string = 0)
+ {
+ string_optional_copy_.clear();
+ if (string)
+ string_range_ = *string;
+ else
+ string_range_ = string_optional_copy_;
+ string_has_changed_ = true;
+ }
+
+# ifdef BOOST_HAS_RVALUE_REFS
+ //!overload
+ void set_string (
+ Sequence2T &&string)
+ {
+ string_optional_copy_ = std::move(string);
+ string_range_ = string_optional_copy_;
+ string_has_changed_ = true;
+ }
+# endif
+
+ //! Perform a search
+ /*!
+ \deprecated Implemented to preserve compatibility
+ with the previous Finder concept
+ \param string_start An iterator at the start of the text in which to perform the search.
+ \param string_end An iterator one past the end of the text in which to perform the search.
+ \return An iterator range indicating the place where the match has occurred.
+ \warning This call changes the text used by the finder, but <b>DOES NOT</b> make a
+ copy of the text. That is, the finder will still use the text given to this call in future searches.
+ Please note that once the passed iterators become invalid, trying to perform searches
+ would cause undefined behavior. Make sure you call set_string() if you want to use this finder
+ after the passed iterators become invalid.
+ \note This is equivalent to:
+ <code>finder::string_range_type range(string_start,string_end);
+ finder.set_string(&range);
+ return finder.find_first();
+ </code>
+ */
+ string_range_type operator()(string_iterator_type &string_start,
+ string_iterator_type &string_end)
+ {
+ string_range_ = boost::make_iterator_range(string_start, string_end);
+ string_has_changed_ = true;
+ return find_first();
+ }
+
+ //! Forces the finder to use its internal text for searching
+ /*!
+ \warning This is especially useful, and \b MUST be called when the internal text has been changed externally.
+ Example:
+ \code
+ finder.set_string("hello"); // the internal text is now "hello"
+ finder.get_string_range().begin()[0] = 'x'; // the first character of the internal text is now 'x' => "xello"
+ finder.use_internal_string(); // forces the finder to recompute the information on the text
+ \endcode
+ */
+ void use_internal_string()
+ {
+ set_string();
+ }
+
+ //! Forces the finder to use its internal pattern for searching
+ /*!
+ \warning The warning from \ref use_internal_string() applies here too.
+ */
+ void use_internal_substring()
+ {
+ set_substring();
+ }
+
+ //! Gets a reference to its internal pattern sequence
+ /*!
+ \note Because the finder might need to make copies of the passed data (when it gets strings
+ passed by reference), it stores an internal sequence of type Sequence1T,
+ which is used if a copy is necessary and left empty otherwise
+ \return The internal pattern sequence
+ */
+ typename boost::call_traits<substring_type>::const_reference get_internal_substring() const
+ {
+ return substring_optional_copy_;
+ }
+
+ //!\overload
+ /*!
+ \warning If you change the internal pattern, you must call \ref use_internal_substring()
+ so that the finder can ask the string search algorithm to recompute its information on the new pattern
+ */
+ typename boost::call_traits<substring_type>::reference get_internal_substring()
+ {
+ return substring_optional_copy_;
+ }
+
+ //! Gets a reference to its internal text sequence.
+ //! \sa get_internal_substring()
+ typename boost::call_traits<substring_type>::const_reference get_internal_string() const
+ {
+ return substring_optional_copy_;
+ }
+
+ //! Gets a reference to its internal text sequence.
+ //! \sa get_internal_substring()
+ typename boost::call_traits<substring_type>::reference get_internal_string()
+ {
+ return substring_optional_copy_;
+ }
+
+ //! Performs a search using the chosen algorithm, starting from the beginning.
+ /*!
+ Looks for the first match of the pattern in the text.
+ \return An iterator range indicating where in the text
+ a match has occurred. If there is no match, an iterator range with
+ begin()==end()==string.end() is returned.
+ \pre The iterator ranges for the string and substring must be set.
+ \post The internal find offset is set immediately after the current match starts.
+ \note This is semantically equivalent to \code find_reset(); match=find_next(); \endcode
+ \sa find_next()
+ */
+ string_range_type find_first()
+ {
+ find_reset();
+ return find_next();
+ }
+
+ //! Performs a search using the chosen algorithm, starting from the beginning.
+ /*!
+ Same as \ref find_first(), except it returns an index as opposed to an iterator range
+ \return An index indicating the position in the text where the match starts
+ \sa find_first()
+ */
+ string_difference_type find_first_index()
+ {
+ find_reset();
+ return find_next_index();
+ }
+
+ //! Performs a string using the chosen algorithm, starting from the internal find offset.
+ /*!
+ Looks for the next occurrence of the pattern in the text.
+ \return An iterator range indicating where in the text the next occurrence of the pattern has been found,
+ or an empty range otherwise.
+ \pre The iterator ranges for the string and substring must be set.
+ \post The internal find offset is set immediately after the current match starts.
+ \warning If the match is performed against the internal text, then an iterator range in the
+ internal text will be returned. Modifying the contents of that range will modify the internal text,
+ making it necessary to call \ref use_internal_string() afterwards. This call will switch to using the internal
+ text (in our case, it already does that, so it will just "refresh") and will force the string search algorithm
+ to recompute its information on the new text.
+ */
+ string_range_type find_next()
+ {
+ apply_changes();
+ if (start_offset_ == boost::end(string_range_))
+ return boost::iterator_range<string_iterator_type>(
+ start_offset_, start_offset_
+ );
+ string_range_type ret =
+ algorithm_type::find(start_offset_);
+ if (boost::begin(ret) == boost::end(string_range_))
+ {
+ start_offset_ = boost::end(string_range_);
+ return ret;
+ }
+ else
+ {
+ start_offset_ = boost::begin(ret);
+ ++start_offset_;
+ return ret;
+ }
+ }
+
+ //! Performs a search using the chosen algorithm, starting from the internal find offset.
+ /*!
+ Same as \ref find_next(), except it returns an index as opposed to an iterator range
+ \return An index indicating the position in the text where the match starts
+ \sa find_next()
+ */
+ string_difference_type find_next_index()
+ {
+ apply_changes();
+
+ //empty substring
+ if (boost::begin(substring_range_) == boost::end(substring_range_))
+ {
+ //empty string, empty substring
+ // TODO if this gets called more times, it always returns 0
+ // i.e. the pointer is not moved. what would be a good solution for that?
+ // maybe a special dummy value for the range?
+ if (boost::begin(string_range_) == boost::end(string_range_))
+ return static_cast<string_difference_type>(0);
+ //empty substring, offset at the end of the range
+ if (start_offset_ == boost::end(string_range_))
+ return static_cast<string_difference_type>(-1);
+ //empty substring, offset not at the end of range
+ return std::distance(boost::begin(string_range_),start_offset_++);
+ }
+ else if (boost::begin(string_range_) == boost::end(string_range_))
+ {
+ //empty string, nonempty substring
+ return static_cast<string_difference_type>(-1);
+ }
+
+ //perform an actual search
+ string_range_type const &match = find_next();
+ if (boost::begin(match) == boost::end(string_range_))
+ return static_cast<string_difference_type>(-1);
+ return std::distance(boost::begin(string_range_), boost::begin(match));
+ }
+
+ //! Reset the internal offset to the beginning of the text.
+ void find_reset()
+ {
+ start_offset_ = boost::begin(string_range_);
+ }
+
+ private:
+ inline void apply_changes()
+ {
+ if (substring_has_changed_ || string_has_changed_) {
+ find_reset();
+ if (substring_has_changed_) {
+ on_substring_change();
+ substring_has_changed_ = false;
+ }
+ if (string_has_changed_) {
+ on_string_change();
+ string_has_changed_ = false;
+ }
+ }
+ }
+
+ substring_type substring_optional_copy_;
+ string_type string_optional_copy_;
+ comparator_type comparator_;
+ allocator_type allocator_;
+ substring_range_type substring_range_;
+ string_range_type string_range_;
+ string_iterator_type start_offset_;
+ bool substring_has_changed_, string_has_changed_;
+ };
+
+
+} }
+
+namespace boost
+{
+ using algorithm::finder_t;
+}
+#endif // BOOST_ALGORITHM_FINDER_T_HPP
\ No newline at end of file
Added: sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/generated_finders.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/generated_finders.hpp 2010-08-11 18:26:46 EDT (Wed, 11 Aug 2010)
@@ -0,0 +1,84 @@
+#ifndef BOOST_ALGORITHM_GENERATED_FINDERS_HPP
+#define BOOST_ALGORITHM_GENERATED_FINDERS_HPP
+
+#include <boost/algorithm/string/finder/detail/last_finder_impl.hpp>
+#include <boost/algorithm/string/finder/detail/nth_finder_impl.hpp>
+#include <boost/algorithm/string/finder/simplified_finder.hpp>
+#include <boost/algorithm/string/finder/detail/finder_typedefs.hpp>
+
+#include <boost/range/begin.hpp>
+#include <boost/range/end.hpp>
+#include <boost/range/as_literal.hpp>
+
+#include <memory>
+
+namespace boost { namespace algorithm {
+
+ template <class Range1T, class Range2T, class AlgorithmT, class ComparatorT>
+ class first_finder_t
+ : public boost::algorithm::detail::finder_typedefs<Range1T, Range2T, ComparatorT, std::allocator<std::size_t> >
+ {
+ public:
+ first_finder_t (Range1T const *const substr, ComparatorT comparator=ComparatorT())
+ : finder(comparator) { finder.set_substring(substr); }
+ string_range_type operator()(string_iterator_type const &string_start, string_iterator_type const &string_end)
+ {
+ finder.set_string(string_start, string_end);
+ return finder.find_first();
+ }
+ private:
+ typedef boost::algorithm::simplified_finder_t<Range1T, Range2T, AlgorithmT, ComparatorT> internal_finder_type;
+ internal_finder_type finder;
+ };
+
+ template <class Range1T, class Range2T, class AlgorithmT, class ComparatorT>
+ class last_finder_t
+ : public boost::algorithm::detail::last_finder_impl_t<Range1T, Range2T, AlgorithmT, ComparatorT>
+ {
+ private:
+ typedef boost::algorithm::detail::last_finder_impl_t<Range1T, Range2T, AlgorithmT, ComparatorT> impl_type;
+ public:
+ last_finder_t (Range1T const *const substr, ComparatorT comparator=ComparatorT())
+ : impl_type(boost::as_literal(*substr), comparator) { }
+ };
+
+ template <class Range1T, class Range2T, class AlgorithmT, class ComparatorT>
+ class nth_finder_t
+ : public boost::algorithm::detail::nth_finder_impl_t<Range1T, Range2T, AlgorithmT, ComparatorT>
+ {
+ private:
+ typedef boost::algorithm::detail::nth_finder_impl_t<Range1T, Range2T, AlgorithmT, ComparatorT> impl_type;
+ public:
+ nth_finder_t (Range1T const *const substr, ComparatorT comparator=ComparatorT(), int n = 0)
+ : impl_type(boost::as_literal(*substr), comparator, n)
+ // : finder(comparator), n_(n) { finder.set_substring(substr); }
+ {
+ }
+ /*void set_n(int n) { n_ = n; }
+ string_range_type operator()(string_iterator_type const &string_start, string_iterator_type const &string_end)
+ {
+ //IMPORTANT TODO: THIS ONLY TREATS THE CASE OF N>=0, MAKE IT SO IT WORKS WITH N<=0 too
+ string_range_type ret;
+ finder.set_string(string_start, string_end);
+ for (int n = 0; n <= n_; ++n)
+ {
+ ret = finder.find_next();
+ if (boost::begin(ret) == boost::end(finder.get_string_range())) return ret;
+ }
+ return ret;
+ }
+ private:
+ typedef boost::algorithm::simplified_finder_t<Range1T, Range2T, AlgorithmT, ComparatorT> internal_finder_type;
+ int n_; // TODO: better type?
+ internal_finder_type finder;*/
+ };
+} }
+
+namespace boost
+{
+ using algorithm::first_finder_t;
+ using algorithm::last_finder_t;
+ using algorithm::nth_finder_t;
+}
+
+#endif // BOOST_ALGORITHM_GENERATED_FINDERS_HPP
\ No newline at end of file
Added: sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/simplified_finder.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/simplified_finder.hpp 2010-08-11 18:26:46 EDT (Wed, 11 Aug 2010)
@@ -0,0 +1,286 @@
+#ifndef BOOST_ALGORITHM_SIMPLIFIED_FINDER_HPP
+#define BOOST_ALGORITHM_SIMPLIFIED_FINDER_HPP
+
+#include <boost/algorithm/string/finder/detail/finder_typedefs.hpp>
+#include <boost/algorithm/string/compare.hpp>
+
+#include <boost/range/as_literal.hpp>
+#include <boost/range/iterator_range.hpp>
+#include <boost/range/begin.hpp>
+#include <boost/range/end.hpp>
+
+#include <boost/call_traits.hpp>
+
+#include <memory>
+
+namespace boost { namespace algorithm {
+
+ //! A generic finder type
+ /*!
+ Allows simple use of various string search algorithms.
+ It has a similar interface to that of \ref boost::algorithm::finder_t, except the constructors and setters
+ of this type can only take pointers to strings (thus avoiding any data copying).
+ \tparam Range1T A range representing the type of the substring (pattern)
+ \tparam Range2T A range representing the type of the string (text)
+ \tparam AlgorithmT The algorithm used to perform the searches
+ \tparam ComparatorT Optional template parameter passed to the algorithm.
+ Used for comparing individual characters for equality.
+ \tparam AllocatorT Optional template parameter passed to the algorithm
+ in the event that additional computation on the data has to be stored.
+ \tparam AdditionalBehaviorT Optional template parameter used to extend the functionality of
+ the finder.
+ */
+ template <class Range1T, class Range2T, class AlgorithmT,
+ class ComparatorT = ::boost::algorithm::is_equal,
+ class AllocatorT = std::allocator<std::size_t>
+ >
+ class simplified_finder_t :
+ public AlgorithmT::template algorithm<
+ simplified_finder_t<Range1T, Range2T, AlgorithmT, ComparatorT, AllocatorT>,
+ Range1T, Range2T, ComparatorT,AllocatorT>
+ {
+ // TODO Add concept assertions here.
+ private:
+ typedef typename AlgorithmT::template algorithm<simplified_finder_t, Range1T,
+ Range2T, ComparatorT, AllocatorT> algorithm_type;
+ public:
+ //! The type of the pattern (substring)
+ typedef typename algorithm_type::substring_type substring_type;
+ //! The type of the text (string)
+ typedef typename algorithm_type::string_type string_type;
+ //! The type of the comparator
+ typedef typename algorithm_type::comparator_type comparator_type;
+ //! The type of the allocator
+ typedef typename algorithm_type::allocator_type allocator_type;
+ //! The type of the substring's iterator
+ typedef typename algorithm_type::substring_iterator_type substring_iterator_type;
+ //! The type of the text's iterator
+ typedef typename algorithm_type::string_iterator_type string_iterator_type;
+ //! The character type of the substring
+ typedef typename algorithm_type::substring_char_type substring_char_type;
+ //! The character type of the text
+ typedef typename algorithm_type::string_char_type string_char_type;
+ //! The range type of the substring (pattern)
+ typedef typename algorithm_type::substring_range_type substring_range_type;
+ //! The range type of the text
+ typedef typename algorithm_type::string_range_type string_range_type;
+ //! A type capable of holding the difference between two iterators of the text
+ typedef typename algorithm_type::string_difference_type string_difference_type;
+
+ //! Constructs a finder.
+ /*!
+ \param comparator ComparatorT instance used to compare individual characters
+ \param allocator AllocatorT instance used to allocate memory
+ for storing precomputed data if necessary
+ */
+ explicit simplified_finder_t(ComparatorT comparator = ComparatorT(), AllocatorT allocator = AllocatorT())
+ : substring_range_(), string_range_(), substring_has_changed_(false),
+ string_has_changed_(false), comparator_(comparator), allocator_(allocator),
+ start_offset_()
+ { }
+ /*!
+ Constructs a finder given a pattern and a text
+ \param substr A pointer to a range (or a character array) representing the sought string
+ \param str A pointer to a range (or a character array) representing the text
+ in which to search
+ \param comparator ComparatorT instance used to compare individual characters
+ \param allocator AllocatorT instance used to allocate memory
+ for storing precomputed data if necessary
+ \warning The ranges that substr and str point to must not change during the lifetime of the finder,
+ otherwise one would have to re-set the ranges:
+ <example> <code>
+ string substr("a"), str("b");
+ simplified_finder_t<string,string,..> finder(&substr, &str);
+ substr = "b"; // substr has changed, invalidating the internally stored range
+ finder.set_substring(&substr); // re-set the substring so the finder now uses the new, valid range
+ </code> </example>
+ */
+ simplified_finder_t(Range1T const *const substr, Range2T *str,
+ ComparatorT comparator = ComparatorT(), AllocatorT allocator = AllocatorT())
+ : substring_range_(boost::as_literal(*substr)),
+ string_range_(boost::as_literal(*str)),
+ comparator_(comparator), allocator_(allocator),
+ substring_has_changed_(true), string_has_changed_(true),
+ algorithm_type()
+ { }
+
+
+ simplified_finder_t (const simplified_finder_t &other)
+ : substring_range_(other.substring_range_), string_range_(other.string_range_),
+ substring_has_changed_(other.substring_has_changed_), string_has_changed_(other.string_has_changed_),
+ comparator_(other.comparator_), allocator_(other.allocator_), start_offset_(other.start_offset_),
+ algorithm_type(other)
+ {
+ }
+ simplified_finder_t &operator=(const simplified_finder_t &rhs)
+ {
+ substring_range_ = rhs.substring_range_;
+ string_range_ = rhs.string_range_;
+ substring_has_changed_ = rhs.substring_has_changed_;
+ string_has_changed_ = rhs.string_has_changed_;
+ comparator_ = rhs.comparator_;
+ allocator_ = rhs.allocator_;
+ start_offset_ = rhs.start_offset_;
+ return *this;
+ }
+
+ //! Change the pattern (substring) to be searched.
+ /*!
+ \param substr A pointer to a range (or a character array) representing the sought string
+ */
+ void set_substring (substring_type const *const substr)
+ { substring_range_ = boost::as_literal(*substr); substring_has_changed_ = true; }
+
+ void set_substring (substring_iterator_type const &substring_begin, substring_iterator_type const &substring_end)
+ {
+ substring_range_ = boost::make_iterator_range(substring_begin, substring_end);
+ substring_has_changed_ = true;
+ }
+
+ //! Change the text in which to search.
+ /*!
+ \param str A pointer to a range (or a character array) representing the text
+ in which to search
+ */
+ void set_string (string_type *const str)
+ { string_range_ = boost::as_literal(*str); string_has_changed_ = true; }
+
+ void set_string (string_iterator_type const &string_begin, string_iterator_type const &string_end)
+ {
+ string_range_ = boost::make_iterator_range(string_begin, string_end);
+ string_has_changed_ = true;
+ }
+
+ //! Reset the internal offset to the beginning of the text.
+ void find_reset ()
+ { start_offset_ = boost::begin(string_range_); }
+
+ //! Finds the first occurrence of the pattern in the text (substring in the string)
+ /*!
+ Equivalent to:
+ \code
+ find_reset(); return find_next();
+ \endcode
+ */
+ string_range_type find_first ()
+ {
+ find_reset();
+ return find_next();
+ }
+
+ //! Perform a search
+ /*!
+ \deprecated Implemented to preserve compatibility
+ with the previous Finder concept
+ \param string_start An iterator at the start of the text in which to perform the search.
+ \param string_end An iterator one past the end of the text in which to perform the search.
+ \return An iterator range indicating the place where the match has occurred.
+ \warning This call changes the text used by the finder, but <b>DOES NOT</b> make a
+ copy of the text. That is, the finder will still use the text given to this call in future searches.
+ Please note that once the passed iterators become invalid, trying to perform searches
+ would cause undefined behavior. Make sure you call set_string() if you want to use this finder
+ after the passed iterators become invalid.
+ \note This is equivalent to:
+ <code>
+ finder.set_string(string_start, string_end);
+ return finder.find_first();
+ </code>
+ */
+ string_range_type operator()(string_iterator_type &string_start,
+ string_iterator_type &string_end)
+ {
+ set_string(string_start, string_end);
+ return find_first();
+ }
+
+
+ // TODO: Assert in case this was called after an empty ctor
+
+ //! Finds the next occurrence of the pattern in the text (starts searching at the current internal offset)
+ //! \sa \ref find_next(), \ref find_first()
+ string_range_type find_next()
+ {
+ apply_changes();
+ if (start_offset_ == boost::end(string_range_))
+ return string_range_type(start_offset_, start_offset_);
+ string_range_type ret =
+ algorithm_type::find(start_offset_);
+ if (boost::begin(ret) == boost::end(string_range_))
+ {
+ start_offset_ = boost::end(string_range_);
+ return ret;
+ }
+ else
+ {
+ start_offset_ = boost::begin(ret);
+ ++start_offset_;
+ return ret;
+ }
+ }
+
+ //! Get an iterator range of the current pattern (substring)
+ /*!
+ \return Iterator range of the current pattern
+ \warning If you modify the contents in this range, you must manually call
+ \ref use_internal_substring(), so that the finder can perform any required precomputation on the pattern
+ */
+ substring_range_type get_substring_range() const { return substring_range_; }
+
+ //! Get an iterator range of the current text
+ /*!
+ \return Range of the current text
+ \warning If you modify the contents in this range, you must manually call
+ \ref use_internal_string(), so that the finder can perform any required precomputation on the text
+ */
+ string_range_type get_string_range() const { return string_range_; }
+
+ //! Gets a reference to the current comparator
+ typename boost::call_traits<comparator_type>::const_reference get_comparator() const
+ { return comparator_; }
+
+ //! Gets a reference to the current allocator
+ //! \return A reference to the current allocator
+ typename boost::call_traits<allocator_type>::reference get_allocator()
+ { return allocator_; }
+
+ //! Gets a reference to the current allocator
+ //! \return A reference to the current allocator
+ typename boost::call_traits<allocator_type>::const_reference get_allocator() const
+ { return allocator_; }
+
+ private:
+ inline void apply_changes()
+ {
+ if (substring_has_changed_ || string_has_changed_) {
+ find_reset();
+ if (substring_has_changed_) {
+ on_substring_change();
+ substring_has_changed_ = false;
+ }
+ if (string_has_changed_) {
+ on_string_change();
+ string_has_changed_ = false;
+ }
+ }
+ }
+
+
+ protected:
+ substring_range_type substring_range_;
+ string_range_type string_range_;
+ bool substring_has_changed_, string_has_changed_;
+
+ comparator_type comparator_;
+ allocator_type allocator_;
+
+ string_iterator_type start_offset_;
+ };
+
+} }
+
+namespace boost
+{
+ using algorithm::simplified_finder_t;
+}
+
+#endif // BOOST_ALGORITHM_SIMPLIFIED_FINDER_HPP
\ No newline at end of file
Modified: sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder_aliases.hpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder_aliases.hpp (original)
+++ sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder_aliases.hpp 2010-08-11 18:26:46 EDT (Wed, 11 Aug 2010)
@@ -1,6 +1,9 @@
#ifndef BOOST_STRING_FINDER_ALIASES_HPP
#define BOOST_STRING_FINDER_ALIASES_HPP
+#include <boost/algorithm/string/finder/finder.hpp>
+#include <boost/algorithm/string/string_search.hpp>
+
namespace boost { namespace algorithm {
//Naive Search
typedef boost::algorithm::finder_t<std::string, std::string,
Modified: sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search.hpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search.hpp (original)
+++ sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search.hpp 2010-08-11 18:26:46 EDT (Wed, 11 Aug 2010)
@@ -1,7 +1,7 @@
#ifndef BOOST_ALGORITHM_STRING_SEARCH_HPP
#define BOOST_ALGORITHM_STRING_SEARCH_HPP
-//! \todo Make sure this header is included by boost/algorithm/string.hpp
+//todo Make sure this header is included by boost/algorithm/string.hpp
#include <boost/algorithm/string/string_search/naive_search.hpp>
#include <boost/algorithm/string/string_search/rabin_karp.hpp>
Modified: sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/boyer_moore.hpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/boyer_moore.hpp (original)
+++ sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/boyer_moore.hpp 2010-08-11 18:26:46 EDT (Wed, 11 Aug 2010)
@@ -16,15 +16,26 @@
#include <boost/static_assert.hpp>
#include <map>
#include <string>
-#include <boost/algorithm/string/finder.hpp>
-#include <boost/algorithm/string/detail/finder.hpp>
+
+#include <boost/algorithm/string/finder/detail/finder_typedefs.hpp>
#include <boost/unordered_map.hpp>
#include <boost/functional/hash.hpp>
#include <boost/utility/enable_if.hpp>
#include <locale>
+/*!
+ \file
+ Implements the Boyer-Moore string search algorithm
+*/
+
namespace boost { namespace algorithm {
+ //! An implementation of the string search algorithm Boyer-Moore
+ //! \warning This algorithm can only work with the equality comparator and the inequality comparator
+ //! \warning For charsets where tolower(a)==tolower(b) is not equivalent to a case-insensitive match,
+ //! you \b MUST \b NOT use the inequality comparator with this algorithm.
+ //! It is best to avoid case-insensitive matches using Boyer-Moore for anything but
+ //! CharT=char
struct boyer_moore
{
@@ -35,15 +46,6 @@
RandomAccessRange1T,RandomAccessRange2T,ComparatorT,AllocatorT>
{
public:
- /*typedef ForwardIterator1T substring_iterator_type;
- typedef ForwardIterator2T string_iterator_type;
- typedef typename
- std::iterator_traits<substring_iterator_type>::value_type substring_char_type;
- typedef typename std::iterator_traits<string_iterator_type>::value_type string_char_type;
- typedef typename boost::iterator_range<substring_iterator_type> substring_range_type;
- typedef typename boost::iterator_range<string_iterator_type> string_range_type;
- typedef Comparator comparator_type;
- typedef Allocator allocator_type;*/
std::string get_algorithm_name () const { return "Boyer-Moore"; }
protected:
algorithm () {
@@ -94,7 +96,7 @@
//Case insensitive matches are supported properly for char (in case of Boyer-Moore)
BOOST_STATIC_ASSERT((boost::is_same<substring_char_type,char>::value));
- //!\todo get locale from user?
+ //todo get locale from user?
if (idx_ != 0) alg_.table1.insert(std::make_pair(
std::tolower(c, std::locale()), idx_
));
@@ -150,10 +152,12 @@
substring_iterator_type const &pattern = boost::begin(substr);
- //!\todo find a better solution for this
+
+ //todo find a better solution for this
for (unsigned int i = substr_size_-1;i--;)
{
- if (!comp(pattern[i],pattern[substr_size_-1]))
+ //pattern[i] != pattern[m-1]
+ if (!comp(*(pattern+i),*(pattern+(substr_size_-1))))
{
table2[substr_size_-1] = substr_size_ - 1 - i;
break;
@@ -171,18 +175,20 @@
{
//Invariant: P[i+1..m-1] = P[j+1..m-1]
//try to align with pattern indexed by j (by sliding the pattern indexed by i)
- while (i != substr_size_ - 1 && !comp(pattern[i],pattern[j]))
+ while (i != substr_size_ - 1 && !comp(*(pattern+i),*(pattern+j)))
i = substr_size_ - 1 - failure_func[i + 1];
//Invariant: Either i=m-1 or P[i..m-1] = P[j..m-1]
- while (i == substr_size_-1 && j > 0 && !comp(pattern[substr_size_-1],pattern[j]))
+ while (i == substr_size_-1 && j > 0 &&
+ !comp(*(pattern+(substr_size_-1)),*(pattern+j)))
{
//couldn't align the given j with any i
failure_func[j] = 0;
--j;
}
//Invariant: either (j==0 and i=m-1) or P[i..m-1] = P[j..m-1]
- if (j == 0 && i == substr_size_-1 && !comp(pattern[0],pattern[substr_size_-1]))
+ if (j == 0 && i == substr_size_-1 &&
+ !comp(*(pattern+0),*(pattern+(substr_size_-1))))
{
failure_func[0] = 0;
}
@@ -218,7 +224,8 @@
//a = m-1-x <=> x = m-1-a
//j = x+1-k <=> k = m-a-j
unsigned int a = failure_func[j];
- while (a > 0 && !comp(pattern[substr_size_-1-a], pattern[j-1]))
+ while (a > 0 && !comp(*(pattern+(substr_size_-1-a)), *(pattern+(j-1))))
+ //while (a > 0 && !compare_range_nth(comp, substr, substr_size_-1-a, substr, j-1))
{
assert(substr_size_-1-a >= substr_size_-a-j); // x >= k
if (table2[substr_size_-1-a] > 2*substr_size_-i-1 -a-j)
@@ -269,10 +276,11 @@
str_size = boost::end(str) - start;
str_idx = substr_size_ - 1; substr_idx = substr_size_ - 1;
+
while (str_idx < str_size)
{
- if (comp(start[str_idx],
- boost::begin(substr)[substr_idx]))
+ if (comp(*(start+str_idx), *(boost::begin(substr)+substr_idx)))
+ //if (compare_range_nth(comp, start[str_idx], boost::begin(substr)[substr_idx]))
{
if (substr_idx == 0)
{
@@ -310,8 +318,7 @@
return string_range_type(boost::end(str), boost::end(str));
}
- //!\todo Get a better data structure here (hash table?)
- //Maybe optimize for sizeof(substring_char_type)==1?
+ //TODO Maybe optimize for sizeof(substring_char_type)==1?
typedef typename boost::unordered_map<substring_char_type, std::size_t,
boost::hash<substring_char_type>, ComparatorT,
typename AllocatorT::template
@@ -347,6 +354,8 @@
};
};
+ //! Instances of this type can be passed to find functions to require them to
+ //! use the Boyer-Moore algorithm.
struct boyer_moore_tag { typedef boost::algorithm::boyer_moore type; };
} }
Deleted: sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/boyer_moore_horspool.hpp
==============================================================================
Modified: sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/detail/rabin_karp.hpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/detail/rabin_karp.hpp (original)
+++ sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/detail/rabin_karp.hpp 2010-08-11 18:26:46 EDT (Wed, 11 Aug 2010)
@@ -16,7 +16,7 @@
#include <cassert>
#include <limits>
-//!\todo add proper overflow assertions here. also try to find if these aren't already in boost
+//todo add proper overflow assertions here. also try to find if these aren't already in boost
#define BOOST_ALGORITHM_DETAIL_ASSERTED_ADD(a, b, T) \
assert((boost::uintmax_t)(a)+(boost::uintmax_t)(b) <= std::numeric_limits<T>::max()),((a)+(b))
#define BOOST_ALGORITHM_DETAIL_ASSERTED_SUBSTRACT(a, b, T) \
@@ -102,19 +102,12 @@
>
>::type
>
- //!\todo this generates possibly invalid allocator_type typedefs, although this is internally not relevant
- //! because rabin_karp doesn't need an allocator. however, this may be nasty externally
- //! possibly fix, although it's minor.
+ //todo this generates possibly invalid allocator_type typedefs, although this is internally not relevant
+ // because rabin_karp doesn't need an allocator. however, this may be nasty externally
+ // possibly fix, although it's minor.
: public boost::algorithm::detail::finder_typedefs<
Range1T,RandomAccessRange2T,boost::algorithm::is_equal,std::allocator<std::size_t> >
{
- public:
- /*typedef ForwardRange1T substring_iterator_type;
- typedef ForwardRange2T string_iterator_type;
- typedef typename std::iterator_traits<substring_iterator_type>::value_type substring_char_type;
- typedef typename std::iterator_traits<string_iterator_type>::value_type string_char_type;
- typedef typename boost::iterator_range<substring_iterator_type> substring_range_type;
- typedef typename boost::iterator_range<string_iterator_type> string_range_type;*/
protected:
rabin_karp_algorithm() :
@@ -124,7 +117,7 @@
first_inverse_(0), second_inverse_(0), string_size_(0), substring_size_(0), string_computed_upto_(0)
{ }
- //!\todo this the right name? the right way to do it?
+ //\todo this the right name? the right way to do it?
template <class T>
inline HashType integer_promotion(T i)
{ return static_cast<HashType>(static_cast<boost::make_unsigned<T>::type>(i)); }
@@ -144,7 +137,7 @@
first = (first * FirstBase + integer_promotion(*it) ) % FirstModulo;
second = (second * SecondBase + integer_promotion(*it) ) % SecondModulo;
}
- //! \todo Optimize here (by precomputing all powers FirstBase^(2^k) and SecondBase^(2^k))
+ // \todo Optimize here? (by precomputing all powers FirstBase^(2^k) and SecondBase^(2^k))
//compute (-(FirstBase)^substring_size_) % FirstModulo
first_inverse_ = FirstModulo - ::boost::algorithm::detail::logarithmic_exponentiation(
@@ -174,7 +167,7 @@
}
//note: use the loop above to calculate part of the string size and then only finish the rest
//(when having a forward iterator)
- //!\todo figure out how to avoid necessity of string_size_ when you have an input iterator only
+ //todo figure out how to avoid necessity of string_size_ when you have an input iterator only
string_size_ = boost::end(str) - boost::begin(str);
first_string_hash_beginning_ = first;
@@ -247,7 +240,7 @@
return boost::make_tuple(first, second);
}*/
- //!\todo compatible force inline? __attribute__((force_inline)) in GCC
+ //todo compatible force inline? __attribute__((force_inline)) in GCC
//inline void roll_string_hash()
__forceinline void roll_string_hash()
{
@@ -292,7 +285,6 @@
return a%b;
}
- //! \todo zero-initialize all of these, just in case
HashType first_substring_hash_, second_substring_hash_;
HashType first_string_hash_current_, second_string_hash_current_;
HashType first_string_hash_beginning_, second_string_hash_beginning_;
Modified: sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/knuth_morris_pratt.hpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/knuth_morris_pratt.hpp (original)
+++ sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/knuth_morris_pratt.hpp 2010-08-11 18:26:46 EDT (Wed, 11 Aug 2010)
@@ -2,16 +2,22 @@
#define BOOST_ALGORITHM_KNUTH_MORRIS_PRATT_HPP
#include <iterator>
+#include <vector>
+#include <memory>
+
#include <boost/range/iterator_range.hpp>
#include <boost/range/begin.hpp>
#include <boost/range/end.hpp>
-#include <boost/algorithm/string/finder.hpp>
-#include <string>
-#include <vector>
-#include <memory>
-#include <boost/algorithm/string/detail/finder.hpp>
+
+#include <boost/algorithm/string/finder/detail/finder_typedefs.hpp>
+
+/*!
+ \file
+ Implements the Knuth-Morris-Pratt string search algorithm
+*/
namespace boost { namespace algorithm {
+ //! An implementation of the string search algorithm Knuth-Morris-Pratt
struct knuth_morris_pratt
{
@@ -22,11 +28,6 @@
RandomAccessRange1T,RandomAccessRange2T,ComparatorT,AllocatorT>
{
public:
- /*typedef RandomAccessIterator1T substring_iterator_type;
- typedef RandomAccessIterator2T string_iterator_type;
- typedef boost::iterator_range<RandomAccessIterator1T> substring_range_type;
- typedef boost::iterator_range<RandomAccessIterator2T> string_range_type;
- typedef Comparator comparator_type;*/
std::string get_algorithm_name () const { return "Knuth-Morris-Pratt"; }
protected:
string_range_type find(string_iterator_type start)
@@ -61,11 +62,14 @@
return boost::iterator_range<string_iterator_type>(
start, start);
+ std::size_t substr_last_index = substr_size-1;
+
//substring bigger than string
if (substr_size > str_size-str_idx)
return make_iterator_range(boost::end(str), boost::end(str));
- //!\todo step by step run for substr_size=1.
+
+ //TODO step by step run for substr_size=1.
//while (idx < str_size)
std::size_t compare_against = str_size - substr_size + 1;
@@ -75,39 +79,23 @@
//Slide the pattern to the right until we manage to find a match for the current char
while (substr_idx > 0 &&
- !comp(boost::begin(str)[str_idx],boost::begin(substr)[substr_idx]))
+ !comp(*(boost::begin(str)+str_idx),*(boost::begin(substr)+substr_idx)))
substr_idx = failure_func[substr_idx-1];
// Invariant: Either substr_idx==0 or string[str_idx]==substr[substr_idx]
while (substr_idx == 0 && str_idx < compare_against
- && !comp(boost::begin(str)[str_idx],boost::begin(substr)[0]))
+ && !comp(*(boost::begin(str)+str_idx),*(boost::begin(substr)+0)))
++str_idx;
//Invariant: string[str_idx]==substr[substr_idx] or (str_idx=0 and str_idx >= str_size)
- if (substr_idx == substr_size - 1 && str_idx-substr_idx < compare_against)
+ if (substr_idx == substr_last_index && str_idx-substr_idx < compare_against)
return make_iterator_range(
- boost::begin(str)+(str_idx+1-substr_size),
+ //boost::begin(str)+(str_idx+1-substr_size),
+ boost::begin(str)+(str_idx-substr_last_index),
boost::begin(str)+(str_idx+1));
++substr_idx; ++str_idx;
- /*
- //if (boost::begin(substr)[q] == boost::begin(str)[idx])
- if (comp(boost::begin(substr)[substr_idx], boost::begin(str)[str_idx]))
- {
- if (str_idx == substr_size-1)
- return boost::iterator_range<string_iterator_type>(
- boost::begin(str)+(idx-substr_size),
- boost::begin(str)+idx
- );
- ++substr_idx; ++str_idx;
- }
- else
- {
- if (q == 0) ++idx;
- else q = failure_func[q];
- }
- */
}
return boost::iterator_range<string_iterator_type>(
boost::end(str), boost::end(str));
@@ -122,38 +110,20 @@
// of P[0..i], that's different from itself.
//failure_func[i] = q <=> P[0..q-1] = P[..m-1] (first q chars equal to last q chars)
- //0 <= failure_func[i] <= i
- failure_func.clear();
- failure_func.reserve(boost::end(substr) - boost::begin(substr));
- /*std::size_t idx, q, substr_size = boost::end(substr) - boost::begin(substr);
- failure_func.push_back(0); failure_func.push_back(0);
-
- if (boost::begin(substr) == boost::end(substr)) return;
-
- for (idx = 2; idx < substr_size; ++idx)
- {
- q = failure_func[idx-1];
- for (;;)
- {
- //if (boost::begin(substr)[q] == boost::begin(substr)[idx-1])
- if (comp(boost::begin(substr)[q], boost::begin(substr)[idx-1]))
- {
- failure_func.push_back(q+1);
- break;
- }
- else if (q == 0) { failure_func.push_back(0); break; }
- q = failure_func[q];
- }
- }*/
+ //Invariant: 0 <= failure_func[i] <= i, i=0..m-1
+
- //!\TODO write failure func
std::size_t i = 0, j = 1, substr_size = boost::end(substr) - boost::begin(substr);
+ failure_func.clear();
+ failure_func.reserve(substr_size);
failure_func.push_back(0); // failure_func[0] = 0
+ //std::size_t capacity = failure_func.capacity();
while (j < substr_size)
{
- while (i > 0 && !comp(boost::begin(substr)[i], boost::begin(substr)[j]))
+ while (i > 0 && !comp(*(boost::begin(substr)+i), *(boost::begin(substr)+j)))
i = failure_func[i-1];
- while (i == 0 && j < substr_size && !comp(boost::begin(substr)[0],boost::begin(substr)[j]))
+ while (i == 0 && j < substr_size &&
+ !comp(*(boost::begin(substr)+0),*(boost::begin(substr)+j)))
{
//Invariant: i == 0 and substr[0] != substr[j], which means failure_func[j]=0
failure_func.push_back(0);
@@ -163,10 +133,13 @@
if (j < substr_size) failure_func.push_back(i+1);
++j; ++i;
}
+ //assert(failure_func.capacity() == capacity);
}
};
};
+ //! Instances of this type can be passed to find functions to require them to
+ //! use the Knuth-Morris-Pratt algorithm.
struct knuth_morris_pratt_tag { typedef boost::algorithm::knuth_morris_pratt type; };
} }
Modified: sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/naive_search.hpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/naive_search.hpp (original)
+++ sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/naive_search.hpp 2010-08-11 18:26:46 EDT (Wed, 11 Aug 2010)
@@ -7,11 +7,18 @@
#include <boost/range/begin.hpp>
#include <boost/range/end.hpp>
#include <string>
-#include <boost/algorithm/string/finder.hpp>
-#include <boost/algorithm/string/detail/finder.hpp>
+
+#include <boost/algorithm/string/finder/detail/finder_typedefs.hpp>
+
+/*!
+ \file
+ Implements the naive string search algorithm
+*/
namespace boost { namespace algorithm {
- //! \todo Copyable
+ // todo Copyable
+
+ //! An implementation of the naive string search algorithm
struct naive_search
{
@@ -35,7 +42,8 @@
typedef typename Finder::comparator_type comparator_type;*/
string_range_type const &str = static_cast<Finder*>(this)->get_string_range();
substring_range_type const &substr = static_cast<Finder*>(this)->get_substring_range();
- comparator_type comparator = static_cast<Finder*>(this)->get_comparator();
+ comparator_type const &comparator = static_cast<Finder*>(this)->get_comparator();
+
for (;
start != boost::end(str); ++start)
@@ -67,6 +75,8 @@
};
};
+ //! Instances of this type can be passed to find functions to require them to
+ //! use the Boyer-Moore algorithm.
struct naive_search_tag { typedef boost::algorithm::naive_search type; };
} }
Modified: sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/rabin_karp.hpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/rabin_karp.hpp (original)
+++ sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/rabin_karp.hpp 2010-08-11 18:26:46 EDT (Wed, 11 Aug 2010)
@@ -13,24 +13,31 @@
#include <boost/range/end.hpp>
#include <string>
#include <boost/lexical_cast.hpp>
-#include <boost/algorithm/string/finder.hpp>
-#include <boost/algorithm/string/detail/finder.hpp>
#include <boost/algorithm/string/string_search/detail/rabin_karp.hpp>
+#include <boost/algorithm/string/finder/detail/finder_typedefs.hpp>
#include <cassert>
#include <limits>
#include <boost/type_traits/is_same.hpp>
+/*!
+ \file
+ Implements the Rabin-Karp string search algorithm
+*/
+
namespace boost { namespace algorithm {
- //!\todo document the fact that it's approximate, how to make it deterministic
- // the limited comparators
- //!\todo Make it work with case insensitive. Find a way to allow providing locales.
-
- //Note: this only works with comparator ==
- //! \todo Implement a version that works with Input iterators?
- //! \todo Make sure this only works with char and wchar_t
+ //todo Make it work with case insensitive. Find a way to allow providing locales.
+
+ //TODO: Implement a version that works with Input iterators
+ //TODO: Make sure this only works with integral char types
+ //! A generic implementation of the string search algorithm Rabin-Karp
+ //! \warning This algorithm is approximate, meaning it can yield false positives (but not false negatives).
+ //! In order to turn it into an exact matching algorithm, an extra equality check
+ //! needs to be performed after a match has occurred.
+ //! \warning This algorithm is limited to using integral character types with
+ //! the equality comparator only (this is because "rolling" hash
+ //! functions need to be computed on the pattern and portions of text)
template <
- //bool Heuristic = true,
class HashType,
HashType FirstBase, HashType FirstModulo,
HashType SecondBase, HashType SecondModulo>
@@ -51,7 +58,7 @@
protected:
//construct the algorithm given iterator ranges for the substring and the string
algorithm () {
- //!\todo add more assertions here
+ //todo add more assertions here
BOOST_STATIC_ASSERT((
sizeof(boost::range_value<Range1T>::type)*2 <= sizeof(HashType)
));
@@ -62,7 +69,7 @@
private:
inline void assert_overflow(HashType B, HashType M)
{
- //!\todo fix this
+ //todo fix this
//char_range_size = CHAR_MAX-CHAR_MIN+1
/*static const boost::uintmax_t char_range_size =
BOOST_ALGORITHM_DETAIL_ASSERTED_ADD(BOOST_ALGORITHM_DETAIL_ASSERTED_SUBSTRACT(
@@ -78,13 +85,18 @@
};
};
- //1/3732152659 odds of collision. useful with char
- //!\todo replace with old one
+
+ //todo try to find better pairs for better efficiency?
+ //! An implementation of a 32bit version of Rabin-Karp
typedef rabin_karp_algorithm<boost::uint_fast32_t,257,64433,277,57923> rabin_karp32;
//1/150167080229379589 odds of collision. useful with wchar_t
+ //! An implementation of a 64bit version of Rabin-Karp
typedef rabin_karp_algorithm<boost::uint64_t,337515847,373587883,255150899,401959183> rabin_karp64;
-
+ //! Instances of this type can be passed to find functions to require them to
+ //! use the predefined 32bit Rabin-Karp algorithm.
struct rabin_karp32_tag { typedef boost::algorithm::rabin_karp32 type; };
+ //! Instances of this type can be passed to find functions to require them to
+ //! use the predefined 64bit Rabin-Karp algorithm.
struct rabin_karp64_tag { typedef boost::algorithm::rabin_karp64 type; };
} } // namespace algorithm, namespace boost
Modified: sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/suffix_array.hpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/suffix_array.hpp (original)
+++ sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/suffix_array.hpp 2010-08-11 18:26:46 EDT (Wed, 11 Aug 2010)
@@ -4,20 +4,29 @@
#include <iterator>
#include <vector>
#include <algorithm>
+#include <string>
+
#include <boost/range/begin.hpp>
#include <boost/range/end.hpp>
#include <boost/range/iterator_range.hpp>
#include <boost/range/algorithm/sort.hpp>
-#include <boost/algorithm/string/finder.hpp>
-#include <string>
-#include <boost/algorithm/string/detail/finder.hpp>
+
+#include <boost/algorithm/string/finder/detail/finder_typedefs.hpp>
+
+/*!
+ \file
+ Implements a string search algorithm based on the suffix array data structure
+*/
namespace boost { namespace algorithm {
+ //! An implementation of a string search algorithm using the suffix array data structure
+ //! \warning This algorithm can only work with the equality comparator (boost::algorithm::is_equal)
struct suffix_array_search
{
//! \TODO this currently only works for boost::algorithm::is_equal as comparator because we don't yet have a template
//! parameter for LessThanComparator. Maybe we should pass two comparators, give it some thought.
+
template <class Finder,class RandomAccessRange1T,
class RandomAccessRange2T,class ComparatorT,class AllocatorT>
class algorithm;
@@ -209,6 +218,8 @@
};
};
+ //! Instances of this type can be passed to find functions to require them to
+ //! use the Suffix Array Search algorithm.
struct suffix_array_search_tag { typedef boost::algorithm::suffix_array_search type; };
} }
Modified: sandbox/SOC/2010/stringalgos/libs/algorithm/string/benchmark/string_search.cpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/libs/algorithm/string/benchmark/string_search.cpp (original)
+++ sandbox/SOC/2010/stringalgos/libs/algorithm/string/benchmark/string_search.cpp 2010-08-11 18:26:46 EDT (Wed, 11 Aug 2010)
@@ -301,10 +301,10 @@
boost::benchmark_finder<std::string, std::string,
boost::mpl::vector<
boost::naive_search,
- boost::knuth_morris_pratt,
- boost::boyer_moore,
+ boost::knuth_morris_pratt//,
+ //boost::boyer_moore,
//boost::suffix_array_search,
- boost::rabin_karp32//,
+ //boost::rabin_karp32//,
//boost::rabin_karp64
>,
boost::is_equal> b;
Modified: sandbox/SOC/2010/stringalgos/libs/algorithm/string/doc/Jamfile.v2
==============================================================================
--- sandbox/SOC/2010/stringalgos/libs/algorithm/string/doc/Jamfile.v2 (original)
+++ sandbox/SOC/2010/stringalgos/libs/algorithm/string/doc/Jamfile.v2 2010-08-11 18:26:46 EDT (Wed, 11 Aug 2010)
@@ -59,7 +59,7 @@
<doxygen:param>MACRO_EXPANSION=YES
<doxygen:param>EXPAND_ONLY_PREDEF=YES
<doxygen:param>SEARCH_INCLUDES=YES
- <doxygen:param>PREDEFINED="BOOST_STRING_TYPENAME=typename \"BOOST_STATIC_CONSTANT(type,var)=static const type var;\""
+ <doxygen:param>PREDEFINED="BOOST_STRING_TYPENAME=typename \"BOOST_STATIC_CONSTANT(type,var)=static const type var; BOOST_HAS_RVALUE_REFS\""
;
Modified: sandbox/SOC/2010/stringalgos/libs/algorithm/string/doc/quickref.xml
==============================================================================
--- sandbox/SOC/2010/stringalgos/libs/algorithm/string/doc/quickref.xml (original)
+++ sandbox/SOC/2010/stringalgos/libs/algorithm/string/doc/quickref.xml 2010-08-11 18:26:46 EDT (Wed, 11 Aug 2010)
@@ -1,744 +1,853 @@
-<?xml version="1.0" encoding="utf-8"?>
-<!DOCTYPE library PUBLIC "-//Boost//DTD BoostBook XML V1.0//EN"
-"http://www.boost.org/tools/boostbook/dtd/boostbook.dtd">
-
+<?xml version="1.0" encoding="utf-8"?>
+<!DOCTYPE library PUBLIC "-//Boost//DTD BoostBook XML V1.0//EN" "http://www.boost.org/tools/boostbook/dtd/boostbook.dtd"[]>
<!-- Copyright (c) 2002-2006 Pavol Droba.
Subject to the Boost Software License, Version 1.0.
(See accompanying file LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
-->
-
<section id="string_algo.quickref" last-revision="$Date$">
- <title>Quick Reference</title>
-
- <using-namespace name="boost"/>
- <using-namespace name="boost::algorithm"/>
-
- <section>
- <title>Algorithms</title>
-
- <table>
- <title>Case Conversion</title>
- <tgroup cols="3" align="left">
- <thead>
- <row>
- <entry>Algorithm name</entry>
- <entry>Description</entry>
- <entry>Functions</entry>
- </row>
- </thead>
- <tbody>
- <row>
- <entry><code>to_upper</code></entry>
- <entry>Convert a string to upper case</entry>
- <entry>
- <functionname>to_upper_copy()</functionname>
- <sbr/>
- <functionname>to_upper()</functionname>
- </entry>
- </row>
- <row>
- <entry><code>to_lower</code></entry>
- <entry>Convert a string to lower case</entry>
- <entry>
- <functionname>to_lower_copy()</functionname>
- <sbr/>
- <functionname>to_lower()</functionname>
- </entry>
- </row>
- </tbody>
- </tgroup>
- </table>
- <table>
- <title>Trimming</title>
- <tgroup cols="3" align="left">
- <thead>
- <row>
- <entry>Algorithm name</entry>
- <entry>Description</entry>
- <entry>Functions</entry>
- </row>
- </thead>
- <tbody>
- <row>
- <entry><code>trim_left</code></entry>
- <entry>Remove leading spaces from a string</entry>
- <entry>
- <functionname>trim_left_copy_if()</functionname>
- <sbr/>
- <functionname>trim_left_if()</functionname>
- <sbr/>
- <functionname>trim_left_copy()</functionname>
- <sbr/>
- <functionname>trim_left()</functionname>
- </entry>
- </row>
- <row>
- <entry><code>trim_right</code></entry>
- <entry>Remove trailing spaces from a string</entry>
- <entry>
- <functionname>trim_right_copy_if()</functionname>
- <sbr/>
- <functionname>trim_right_if()</functionname>
- <sbr/>
- <functionname>trim_right_copy()</functionname>
- <sbr/>
- <functionname>trim_right()</functionname>
- </entry>
- </row>
- <row>
- <entry><code>trim</code></entry>
- <entry>Remove leading and trailing spaces from a string</entry>
- <entry>
- <functionname>trim_copy_if()</functionname>
- <sbr/>
- <functionname>trim_if()</functionname>
- <sbr/>
- <functionname>trim_copy()</functionname>
- <sbr/>
- <functionname>trim()</functionname>
- </entry>
- </row>
-
- </tbody>
- </tgroup>
- </table>
- <table>
- <title>Predicates</title>
- <tgroup cols="3" align="left">
- <thead>
- <row>
- <entry>Algorithm name</entry>
- <entry>Description</entry>
- <entry>Functions</entry>
- </row>
- </thead>
- <tbody>
- <row>
- <entry><code>starts_with</code></entry>
- <entry>Check if a string is a prefix of the other one</entry>
- <entry>
- <functionname>starts_with()</functionname>
- <sbr/>
- <functionname>istarts_with()</functionname>
- </entry>
- </row>
- <row>
- <entry><code>ends_with</code></entry>
- <entry>Check if a string is a suffix of the other one</entry>
- <entry>
- <functionname>ends_with()</functionname>
- <sbr/>
- <functionname>iends_with()</functionname>
- </entry>
- </row>
- <row>
- <entry><code>contains</code></entry>
- <entry>Check if a string is contained of the other one</entry>
- <entry>
- <functionname>contains()</functionname>
- <sbr/>
- <functionname>icontains()</functionname>
- </entry>
- </row>
- <row>
- <entry><code>equals</code></entry>
- <entry>Check if two strings are equal</entry>
- <entry>
- <functionname>equals()</functionname>
- <sbr/>
- <functionname>iequals()</functionname>
- </entry>
- </row>
- <row>
- <entry><code>lexicographical_compare</code></entry>
- <entry>Check if a string is lexicographically less than another one</entry>
- <entry>
- <functionname>lexicographical_compare()</functionname>
- <sbr/>
- <functionname>ilexicographical_compare()</functionname>
- </entry>
- </row>
-
- <row>
- <entry><code>all</code></entry>
- <entry>Check if all elements of a string satisfy the given predicate</entry>
- <entry>
- <functionname>all()</functionname>
- </entry>
- </row>
- </tbody>
- </tgroup>
- </table>
- <table>
- <title>Find algorithms</title>
- <tgroup cols="3" align="left">
- <thead>
- <row>
- <entry>Algorithm name</entry>
- <entry>Description</entry>
- <entry>Functions</entry>
- </row>
- </thead>
- <tbody>
- <row>
- <entry>find_first</entry>
- <entry>Find the first occurrence of a string in the input</entry>
- <entry>
- <functionname>find_first()</functionname>
- <sbr/>
- <functionname>ifind_first()</functionname>
- </entry>
- </row>
- <row>
- <entry>find_last</entry>
- <entry>Find the last occurrence of a string in the input</entry>
- <entry>
- <functionname>find_last()</functionname>
- <sbr/>
- <functionname>ifind_last()</functionname>
- </entry>
- </row>
- <row>
- <entry>find_nth</entry>
- <entry>Find the nth (zero-indexed) occurrence of a string in the input</entry>
- <entry>
- <functionname>find_nth()</functionname>
- <sbr/>
- <functionname>ifind_nth()</functionname>
- </entry>
- </row>
- <row>
- <entry>find_head</entry>
- <entry>Retrieve the head of a string</entry>
- <entry>
- <functionname>find_head()</functionname>
- </entry>
- </row>
- <row>
- <entry>find_tail</entry>
- <entry>Retrieve the tail of a string</entry>
- <entry>
- <functionname>find_tail()</functionname>
- </entry>
- </row>
- <row>
- <entry>find_token</entry>
- <entry>Find first matching token in the string</entry>
- <entry>
- <functionname>find_token()</functionname>
- </entry>
- </row>
- <row>
- <entry>find_regex</entry>
- <entry>Use the regular expression to search the string</entry>
- <entry>
- <functionname>find_regex()</functionname>
- </entry>
- </row>
- <row>
- <entry>find</entry>
- <entry>Generic find algorithm</entry>
- <entry>
- <functionname>find()</functionname>
- </entry>
- </row>
- </tbody>
- </tgroup>
- </table>
- <table>
- <title>Erase/Replace</title>
- <tgroup cols="3" align="left">
- <thead>
- <row>
- <entry>Algorithm name</entry>
- <entry>Description</entry>
- <entry>Functions</entry>
- </row>
- </thead>
- <tbody>
- <row>
- <entry>replace/erase_first</entry>
- <entry>Replace/Erase the first occurrence of a string in the input</entry>
- <entry>
- <functionname>replace_first()</functionname>
- <sbr/>
- <functionname>replace_first_copy()</functionname>
- <sbr/>
- <functionname>ireplace_first()</functionname>
- <sbr/>
- <functionname>ireplace_first_copy()</functionname>
- <sbr/>
- <functionname>erase_first()</functionname>
- <sbr/>
- <functionname>erase_first_copy()</functionname>
- <sbr/>
- <functionname>ierase_first()</functionname>
- <sbr/>
- <functionname>ierase_first_copy()</functionname>
- </entry>
- </row>
- <row>
- <entry>replace/erase_last</entry>
- <entry>Replace/Erase the last occurrence of a string in the input</entry>
- <entry>
- <functionname>replace_last()</functionname>
- <sbr/>
- <functionname>replace_last_copy()</functionname>
- <sbr/>
- <functionname>ireplace_last()</functionname>
- <sbr/>
- <functionname>ireplace_last_copy()</functionname>
- <sbr/>
- <functionname>erase_last()</functionname>
- <sbr/>
- <functionname>erase_last_copy()</functionname>
- <sbr/>
- <functionname>ierase_last()</functionname>
- <sbr/>
- <functionname>ierase_last_copy()</functionname>
- </entry>
- </row>
- <row>
- <entry>replace/erase_nth</entry>
- <entry>Replace/Erase the nth (zero-indexed) occurrence of a string in the input</entry>
- <entry>
- <functionname>replace_nth()</functionname>
- <sbr/>
- <functionname>replace_nth_copy()</functionname>
- <sbr/>
- <functionname>ireplace_nth()</functionname>
- <sbr/>
- <functionname>ireplace_nth_copy()</functionname>
- <sbr/>
- <functionname>erase_nth()</functionname>
- <sbr/>
- <functionname>erase_nth_copy()</functionname>
- <sbr/>
- <functionname>ierase_nth()</functionname>
- <sbr/>
- <functionname>ierase_nth_copy()</functionname>
- </entry>
- </row>
- <row>
- <entry>replace/erase_all</entry>
- <entry>Replace/Erase the all occurrences of a string in the input</entry>
- <entry>
- <functionname>replace_all()</functionname>
- <sbr/>
- <functionname>replace_all_copy()</functionname>
- <sbr/>
- <functionname>ireplace_all()</functionname>
- <sbr/>
- <functionname>ireplace_all_copy()</functionname>
- <sbr/>
- <functionname>erase_all()</functionname>
- <sbr/>
- <functionname>erase_all_copy()</functionname>
- <sbr/>
- <functionname>ierase_all()</functionname>
- <sbr/>
- <functionname>ierase_all_copy()</functionname>
- </entry>
- </row>
- <row>
- <entry>replace/erase_head</entry>
- <entry>Replace/Erase the head of the input</entry>
- <entry>
- <functionname>replace_head()</functionname>
- <sbr/>
- <functionname>replace_head_copy()</functionname>
- <sbr/>
- <functionname>erase_head()</functionname>
- <sbr/>
- <functionname>erase_head_copy()</functionname>
- <sbr/>
- </entry>
- </row>
- <row>
- <entry>replace/erase_tail</entry>
- <entry>Replace/Erase the tail of the input</entry>
- <entry>
- <functionname>replace_tail()</functionname>
- <sbr/>
- <functionname>replace_tail_copy()</functionname>
- <sbr/>
- <functionname>erase_tail()</functionname>
- <sbr/>
- <functionname>erase_tail_copy()</functionname>
- <sbr/>
- </entry>
- </row>
- <row>
- <entry>replace/erase_regex</entry>
- <entry>Replace/Erase a substring matching the given regular expression</entry>
- <entry>
- <functionname>replace_regex()</functionname>
- <sbr/>
- <functionname>replace_regex_copy()</functionname>
- <sbr/>
- <functionname>erase_regex()</functionname>
- <sbr/>
- <functionname>erase_regex_copy()</functionname>
- <sbr/>
- </entry>
- </row>
- <row>
- <entry>replace/erase_regex_all</entry>
- <entry>Replace/Erase all substrings matching the given regular expression</entry>
- <entry>
- <functionname>replace_all_regex()</functionname>
- <sbr/>
- <functionname>replace_all_regex_copy()</functionname>
- <sbr/>
- <functionname>erase_all_regex()</functionname>
- <sbr/>
- <functionname>erase_all_regex_copy()</functionname>
- <sbr/>
- </entry>
- </row>
- <row>
- <entry>find_format</entry>
- <entry>Generic replace algorithm</entry>
- <entry>
- <functionname>find_format()</functionname>
- <sbr/>
- <functionname>find_format_copy()</functionname>
- <sbr/>
- <functionname>find_format_all()</functionname>
- <sbr/>
- <functionname>find_format_all_copy()()</functionname>
- </entry>
- </row>
- </tbody>
- </tgroup>
- </table>
- <table>
- <title>Split</title>
- <tgroup cols="3" align="left">
- <thead>
- <row>
- <entry>Algorithm name</entry>
- <entry>Description</entry>
- <entry>Functions</entry>
- </row>
- </thead>
- <tbody>
- <row>
- <entry>find_all</entry>
- <entry>Find/Extract all matching substrings in the input</entry>
- <entry>
- <functionname>find_all()</functionname>
- <sbr/>
- <functionname>ifind_all()</functionname>
- <sbr/>
- <functionname>find_all_regex()</functionname>
- </entry>
- </row>
- <row>
- <entry>split</entry>
- <entry>Split input into parts</entry>
- <entry>
- <functionname>split()</functionname>
- <sbr/>
- <functionname>split_regex()</functionname>
- </entry>
- </row>
- <row>
- <entry>iter_find</entry>
- <entry>Iteratively apply the finder to the input to find all matching substrings</entry>
- <entry>
- <functionname>iter_find()</functionname>
- </entry>
- </row>
- <row>
- <entry>iter_split</entry>
- <entry>Use the finder to find matching substrings in the input and use them as separators to split the input into parts</entry>
- <entry>
- <functionname>iter_split()</functionname>
- </entry>
- </row>
- </tbody>
- </tgroup>
- </table>
- <table>
- <title>Join</title>
- <tgroup cols="3" align="left">
- <thead>
- <row>
- <entry>Algorithm name</entry>
- <entry>Description</entry>
- <entry>Functions</entry>
- </row>
- </thead>
- <tbody>
- <row>
- <entry>join</entry>
- <entry>Join all elements in a container into a single string</entry>
- <entry>
- <functionname>join</functionname>
- </entry>
- </row>
- <row>
- <entry>join_if</entry>
- <entry>Join all elements in a container that satisfies the condition into a single string</entry>
- <entry>
- <functionname>join_if()</functionname>
- </entry>
- </row>
- </tbody>
- </tgroup>
- </table>
- </section>
- <section>
- <title>Finders and Formatters</title>
-
- <table>
- <title>Finders</title>
- <tgroup cols="3" align="left">
- <thead>
- <row>
- <entry>Finder</entry>
- <entry>Description</entry>
- <entry>Generators</entry>
- </row>
- </thead>
- <tbody>
- <row>
- <entry>first_finder</entry>
- <entry>Search for the first match of the string in an input</entry>
- <entry>
- <functionname>first_finder()</functionname>
- </entry>
- </row>
- <row>
- <entry>last_finder</entry>
- <entry>Search for the last match of the string in an input</entry>
- <entry>
- <functionname>last_finder()</functionname>
- </entry>
- </row>
- <row>
- <entry>nth_finder</entry>
- <entry>Search for the nth (zero-indexed) match of the string in an input</entry>
- <entry>
- <functionname>nth_finder()</functionname>
- </entry>
- </row>
- <row>
- <entry>head_finder</entry>
- <entry>Retrieve the head of an input</entry>
- <entry>
- <functionname>head_finder()</functionname>
- </entry>
- </row>
- <row>
- <entry>tail_finder</entry>
- <entry>Retrieve the tail of an input</entry>
- <entry>
- <functionname>tail_finder()</functionname>
- </entry>
- </row>
- <row>
- <entry>token_finder</entry>
- <entry>Search for a matching token in an input</entry>
- <entry>
- <functionname>token_finder()</functionname>
- </entry>
- </row>
- <row>
- <entry>range_finder</entry>
- <entry>Do no search, always returns the given range</entry>
- <entry>
- <functionname>range_finder()</functionname>
- </entry>
- </row>
- <row>
- <entry>regex_finder</entry>
- <entry>Search for a substring matching the given regex</entry>
- <entry>
- <functionname>regex_finder()</functionname>
- </entry>
- </row>
- </tbody>
- </tgroup>
- </table>
-
- <table>
- <title>Formatters</title>
- <tgroup cols="3" align="left">
- <thead>
- <row>
- <entry>Formatter</entry>
- <entry>Description</entry>
- <entry>Generators</entry>
- </row>
- </thead>
- <tbody>
- <row>
- <entry>const_formatter</entry>
- <entry>Constant formatter. Always return the specified string</entry>
- <entry>
- <functionname>const_formatter()</functionname>
- </entry>
- </row>
- <row>
- <entry>identity_formatter</entry>
- <entry>Identity formatter. Return unmodified input input</entry>
- <entry>
- <functionname>identity_formatter()</functionname>
- </entry>
- </row>
- <row>
- <entry>empty_formatter</entry>
- <entry>Null formatter. Always return an empty string</entry>
- <entry>
- <functionname>empty_formatter()</functionname>
- </entry>
- </row>
- <row>
- <entry>regex_formatter</entry>
- <entry>Regex formatter. Format regex match using the specification in the format string</entry>
- <entry>
- <functionname>regex_formatter()</functionname>
- </entry>
- </row>
- </tbody>
- </tgroup>
- </table>
- </section>
- <section>
- <title>Iterators</title>
-
- <table>
- <title>Find Iterators</title>
- <tgroup cols="3" align="left">
- <thead>
- <row>
- <entry>Iterator name</entry>
- <entry>Description</entry>
- <entry>Iterator class</entry>
- </row>
- </thead>
- <tbody>
- <row>
- <entry>find_iterator</entry>
- <entry>Iterates through matching substrings in the input</entry>
- <entry>
- <classname>find_iterator</classname>
- </entry>
- </row>
- <row>
- <entry>split_iterator</entry>
- <entry>Iterates through gaps between matching substrings in the input</entry>
- <entry>
- <classname>split_iterator</classname>
- </entry>
- </row>
- </tbody>
- </tgroup>
- </table>
- </section>
-
- <section>
- <title>Classification</title>
-
- <table>
- <title>Predicates</title>
- <tgroup cols="3" align="left">
- <thead>
- <row>
- <entry>Predicate name</entry>
- <entry>Description</entry>
- <entry>Generator</entry>
- </row>
- </thead>
- <tbody>
- <row>
- <entry>is_classified</entry>
- <entry>Generic <code>ctype</code> mask based classification</entry>
- <entry>
- <functionname>is_classified()</functionname>
- </entry>
- </row>
- <row>
- <entry>is_space</entry>
- <entry>Recognize spaces</entry>
- <entry>
- <functionname>is_space()</functionname>
- </entry>
- </row>
- <row>
- <entry>is_alnum</entry>
- <entry>Recognize alphanumeric characters</entry>
- <entry>
- <functionname>is_alnum()</functionname>
- </entry>
- </row>
- <row>
- <entry>is_alpha</entry>
- <entry>Recognize letters</entry>
- <entry>
- <functionname>is_alpha()</functionname>
- </entry>
- </row>
- <row>
- <entry>is_cntrl</entry>
- <entry>Recognize control characters</entry>
- <entry>
- <functionname>is_cntrl()</functionname>
- </entry>
- </row>
- <row>
- <entry>is_digit</entry>
- <entry>Recognize decimal digits</entry>
- <entry>
- <functionname>is_digit()</functionname>
- </entry>
- </row>
- <row>
- <entry>is_graph</entry>
- <entry>Recognize graphical characters</entry>
- <entry>
- <functionname>is_graph()</functionname>
- </entry>
- </row>
- <row>
- <entry>is_lower</entry>
- <entry>Recognize lower case characters</entry>
- <entry>
- <functionname>is_lower()</functionname>
- </entry>
- </row>
- <row>
- <entry>is_print</entry>
- <entry>Recognize printable characters</entry>
- <entry>
- <functionname>is_print()</functionname>
- </entry>
- </row>
- <row>
- <entry>is_punct</entry>
- <entry>Recognize punctuation characters</entry>
- <entry>
- <functionname>is_punct()</functionname>
- </entry>
- </row>
- <row>
- <entry>is_upper</entry>
- <entry>Recognize uppercase characters</entry>
- <entry>
- <functionname>is_upper()</functionname>
- </entry>
- </row>
- <row>
- <entry>is_xdigit</entry>
- <entry>Recognize hexadecimal digits</entry>
- <entry>
- <functionname>is_xdigit()</functionname>
- </entry>
- </row>
- </tbody>
- </tgroup>
- </table>
- </section>
-</section>
+ <title>Quick Reference</title>
+ <using-namespace name="boost" />
+ <using-namespace name="boost::algorithm" />
+ <section>
+ <title>Algorithms</title>
+ <table>
+ <title>Case Conversion</title>
+ <tgroup cols="3" align="left">
+ <thead>
+ <row>
+ <entry>Algorithm name</entry>
+ <entry>Description</entry>
+ <entry>Functions</entry>
+ </row>
+ </thead>
+ <tbody>
+ <row>
+ <entry>
+ <code>to_upper</code>
+ </entry>
+ <entry>Convert a string to upper case</entry>
+ <entry>
+ <functionname>to_upper_copy()</functionname>
+ <sbr />
+ <functionname>to_upper()</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>
+ <code>to_lower</code>
+ </entry>
+ <entry>Convert a string to lower case</entry>
+ <entry>
+ <functionname>to_lower_copy()</functionname>
+ <sbr />
+ <functionname>to_lower()</functionname>
+ </entry>
+ </row>
+ </tbody>
+ </tgroup>
+ </table>
+ <table>
+ <title>Trimming</title>
+ <tgroup cols="3" align="left">
+ <thead>
+ <row>
+ <entry>Algorithm name</entry>
+ <entry>Description</entry>
+ <entry>Functions</entry>
+ </row>
+ </thead>
+ <tbody>
+ <row>
+ <entry>
+ <code>trim_left</code>
+ </entry>
+ <entry>Remove leading spaces from a string</entry>
+ <entry>
+ <functionname>trim_left_copy_if()</functionname>
+ <sbr />
+ <functionname>trim_left_if()</functionname>
+ <sbr />
+ <functionname>trim_left_copy()</functionname>
+ <sbr />
+ <functionname>trim_left()</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>
+ <code>trim_right</code>
+ </entry>
+ <entry>Remove trailing spaces from a string</entry>
+ <entry>
+ <functionname>trim_right_copy_if()</functionname>
+ <sbr />
+ <functionname>trim_right_if()</functionname>
+ <sbr />
+ <functionname>trim_right_copy()</functionname>
+ <sbr />
+ <functionname>trim_right()</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>
+ <code>trim</code>
+ </entry>
+ <entry>Remove leading and trailing spaces from a string</entry>
+ <entry>
+ <functionname>trim_copy_if()</functionname>
+ <sbr />
+ <functionname>trim_if()</functionname>
+ <sbr />
+ <functionname>trim_copy()</functionname>
+ <sbr />
+ <functionname>trim()</functionname>
+ </entry>
+ </row>
+ </tbody>
+ </tgroup>
+ </table>
+ <table>
+ <title>Predicates</title>
+ <tgroup cols="3" align="left">
+ <thead>
+ <row>
+ <entry>Algorithm name</entry>
+ <entry>Description</entry>
+ <entry>Functions</entry>
+ </row>
+ </thead>
+ <tbody>
+ <row>
+ <entry>
+ <code>starts_with</code>
+ </entry>
+ <entry>Check if a string is a prefix of the other one</entry>
+ <entry>
+ <functionname>starts_with()</functionname>
+ <sbr />
+ <functionname>istarts_with()</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>
+ <code>ends_with</code>
+ </entry>
+ <entry>Check if a string is a suffix of the other one</entry>
+ <entry>
+ <functionname>ends_with()</functionname>
+ <sbr />
+ <functionname>iends_with()</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>
+ <code>contains</code>
+ </entry>
+ <entry>Check if a string is contained of the other one</entry>
+ <entry>
+ <functionname>contains()</functionname>
+ <sbr />
+ <functionname>icontains()</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>
+ <code>equals</code>
+ </entry>
+ <entry>Check if two strings are equal</entry>
+ <entry>
+ <functionname>equals()</functionname>
+ <sbr />
+ <functionname>iequals()</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>
+ <code>lexicographical_compare</code>
+ </entry>
+ <entry>Check if a string is lexicographically less than another one</entry>
+ <entry>
+ <functionname>lexicographical_compare()</functionname>
+ <sbr />
+ <functionname>ilexicographical_compare()</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>
+ <code>all</code>
+ </entry>
+ <entry>Check if all elements of a string satisfy the given predicate</entry>
+ <entry>
+ <functionname>all()</functionname>
+ </entry>
+ </row>
+ </tbody>
+ </tgroup>
+ </table>
+ <table>
+ <title>Find algorithms</title>
+ <tgroup cols="3" align="left">
+ <thead>
+ <row>
+ <entry>Algorithm name</entry>
+ <entry>Description</entry>
+ <entry>Functions</entry>
+ </row>
+ </thead>
+ <tbody>
+ <row>
+ <entry>find_first</entry>
+ <entry>Find the first occurrence of a string in the input</entry>
+ <entry>
+ <functionname>find_first()</functionname>
+ <sbr />
+ <functionname>ifind_first()</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>find_last</entry>
+ <entry>Find the last occurrence of a string in the input</entry>
+ <entry>
+ <functionname>find_last()</functionname>
+ <sbr />
+ <functionname>ifind_last()</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>find_nth</entry>
+ <entry>Find the nth (zero-indexed) occurrence of a string in the input</entry>
+ <entry>
+ <functionname>find_nth()</functionname>
+ <sbr />
+ <functionname>ifind_nth()</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>find_head</entry>
+ <entry>Retrieve the head of a string</entry>
+ <entry>
+ <functionname>find_head()</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>find_tail</entry>
+ <entry>Retrieve the tail of a string</entry>
+ <entry>
+ <functionname>find_tail()</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>find_token</entry>
+ <entry>Find first matching token in the string</entry>
+ <entry>
+ <functionname>find_token()</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>find_regex</entry>
+ <entry>Use the regular expression to search the string</entry>
+ <entry>
+ <functionname>find_regex()</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>find</entry>
+ <entry>Generic find algorithm</entry>
+ <entry>
+ <functionname>find()</functionname>
+ </entry>
+ </row>
+ </tbody>
+ </tgroup>
+ </table>
+ <table>
+ <title>Erase/Replace</title>
+ <tgroup cols="3" align="left">
+ <thead>
+ <row>
+ <entry>Algorithm name</entry>
+ <entry>Description</entry>
+ <entry>Functions</entry>
+ </row>
+ </thead>
+ <tbody>
+ <row>
+ <entry>replace/erase_first</entry>
+ <entry>Replace/Erase the first occurrence of a string in the input</entry>
+ <entry>
+ <functionname>replace_first()</functionname>
+ <sbr />
+ <functionname>replace_first_copy()</functionname>
+ <sbr />
+ <functionname>ireplace_first()</functionname>
+ <sbr />
+ <functionname>ireplace_first_copy()</functionname>
+ <sbr />
+ <functionname>erase_first()</functionname>
+ <sbr />
+ <functionname>erase_first_copy()</functionname>
+ <sbr />
+ <functionname>ierase_first()</functionname>
+ <sbr />
+ <functionname>ierase_first_copy()</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>replace/erase_last</entry>
+ <entry>Replace/Erase the last occurrence of a string in the input</entry>
+ <entry>
+ <functionname>replace_last()</functionname>
+ <sbr />
+ <functionname>replace_last_copy()</functionname>
+ <sbr />
+ <functionname>ireplace_last()</functionname>
+ <sbr />
+ <functionname>ireplace_last_copy()</functionname>
+ <sbr />
+ <functionname>erase_last()</functionname>
+ <sbr />
+ <functionname>erase_last_copy()</functionname>
+ <sbr />
+ <functionname>ierase_last()</functionname>
+ <sbr />
+ <functionname>ierase_last_copy()</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>replace/erase_nth</entry>
+ <entry>Replace/Erase the nth (zero-indexed) occurrence of a string in the input</entry>
+ <entry>
+ <functionname>replace_nth()</functionname>
+ <sbr />
+ <functionname>replace_nth_copy()</functionname>
+ <sbr />
+ <functionname>ireplace_nth()</functionname>
+ <sbr />
+ <functionname>ireplace_nth_copy()</functionname>
+ <sbr />
+ <functionname>erase_nth()</functionname>
+ <sbr />
+ <functionname>erase_nth_copy()</functionname>
+ <sbr />
+ <functionname>ierase_nth()</functionname>
+ <sbr />
+ <functionname>ierase_nth_copy()</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>replace/erase_all</entry>
+ <entry>Replace/Erase the all occurrences of a string in the input</entry>
+ <entry>
+ <functionname>replace_all()</functionname>
+ <sbr />
+ <functionname>replace_all_copy()</functionname>
+ <sbr />
+ <functionname>ireplace_all()</functionname>
+ <sbr />
+ <functionname>ireplace_all_copy()</functionname>
+ <sbr />
+ <functionname>erase_all()</functionname>
+ <sbr />
+ <functionname>erase_all_copy()</functionname>
+ <sbr />
+ <functionname>ierase_all()</functionname>
+ <sbr />
+ <functionname>ierase_all_copy()</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>replace/erase_head</entry>
+ <entry>Replace/Erase the head of the input</entry>
+ <entry>
+ <functionname>replace_head()</functionname>
+ <sbr />
+ <functionname>replace_head_copy()</functionname>
+ <sbr />
+ <functionname>erase_head()</functionname>
+ <sbr />
+ <functionname>erase_head_copy()</functionname>
+ <sbr />
+ </entry>
+ </row>
+ <row>
+ <entry>replace/erase_tail</entry>
+ <entry>Replace/Erase the tail of the input</entry>
+ <entry>
+ <functionname>replace_tail()</functionname>
+ <sbr />
+ <functionname>replace_tail_copy()</functionname>
+ <sbr />
+ <functionname>erase_tail()</functionname>
+ <sbr />
+ <functionname>erase_tail_copy()</functionname>
+ <sbr />
+ </entry>
+ </row>
+ <row>
+ <entry>replace/erase_regex</entry>
+ <entry>Replace/Erase a substring matching the given regular expression</entry>
+ <entry>
+ <functionname>replace_regex()</functionname>
+ <sbr />
+ <functionname>replace_regex_copy()</functionname>
+ <sbr />
+ <functionname>erase_regex()</functionname>
+ <sbr />
+ <functionname>erase_regex_copy()</functionname>
+ <sbr />
+ </entry>
+ </row>
+ <row>
+ <entry>replace/erase_regex_all</entry>
+ <entry>Replace/Erase all substrings matching the given regular expression</entry>
+ <entry>
+ <functionname>replace_all_regex()</functionname>
+ <sbr />
+ <functionname>replace_all_regex_copy()</functionname>
+ <sbr />
+ <functionname>erase_all_regex()</functionname>
+ <sbr />
+ <functionname>erase_all_regex_copy()</functionname>
+ <sbr />
+ </entry>
+ </row>
+ <row>
+ <entry>find_format</entry>
+ <entry>Generic replace algorithm</entry>
+ <entry>
+ <functionname>find_format()</functionname>
+ <sbr />
+ <functionname>find_format_copy()</functionname>
+ <sbr />
+ <functionname>find_format_all()</functionname>
+ <sbr />
+ <functionname>find_format_all_copy()()</functionname>
+ </entry>
+ </row>
+ </tbody>
+ </tgroup>
+ </table>
+ <table>
+ <title>Split</title>
+ <tgroup cols="3" align="left">
+ <thead>
+ <row>
+ <entry>Algorithm name</entry>
+ <entry>Description</entry>
+ <entry>Functions</entry>
+ </row>
+ </thead>
+ <tbody>
+ <row>
+ <entry>find_all</entry>
+ <entry>Find/Extract all matching substrings in the input</entry>
+ <entry>
+ <functionname>find_all()</functionname>
+ <sbr />
+ <functionname>ifind_all()</functionname>
+ <sbr />
+ <functionname>find_all_regex()</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>split</entry>
+ <entry>Split input into parts</entry>
+ <entry>
+ <functionname>split()</functionname>
+ <sbr />
+ <functionname>split_regex()</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>iter_find</entry>
+ <entry>Iteratively apply the finder to the input to find all matching substrings</entry>
+ <entry>
+ <functionname>iter_find()</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>iter_split</entry>
+ <entry>Use the finder to find matching substrings in the input and use them as separators to split the input into parts</entry>
+ <entry>
+ <functionname>iter_split()</functionname>
+ </entry>
+ </row>
+ </tbody>
+ </tgroup>
+ </table>
+ <table>
+ <title>Join</title>
+ <tgroup cols="3" align="left">
+ <thead>
+ <row>
+ <entry>Algorithm name</entry>
+ <entry>Description</entry>
+ <entry>Functions</entry>
+ </row>
+ </thead>
+ <tbody>
+ <row>
+ <entry>join</entry>
+ <entry>Join all elements in a container into a single string</entry>
+ <entry>
+ <functionname>join</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>join_if</entry>
+ <entry>Join all elements in a container that satisfies the condition into a single string</entry>
+ <entry>
+ <functionname>join_if()</functionname>
+ </entry>
+ </row>
+ </tbody>
+ </tgroup>
+ </table>
+ </section>
+ <section>
+ <title>Finders</title>
+ <table>
+ <title>Finder generators</title>
+ <tgroup cols="3" align="left">
+ <thead>
+ <row>
+ <entry>Finder</entry>
+ <entry>Description</entry>
+ <entry>Generators</entry>
+ </row>
+ </thead>
+ <tbody>
+ <row>
+ <entry>first_finder</entry>
+ <entry>Search for the first match of the string in an input</entry>
+ <entry>
+ <functionname>first_finder()</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>last_finder</entry>
+ <entry>Search for the last match of the string in an input</entry>
+ <entry>
+ <functionname>last_finder()</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>nth_finder</entry>
+ <entry>Search for the nth (zero-indexed) match of the string in an input</entry>
+ <entry>
+ <functionname>nth_finder()</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>head_finder</entry>
+ <entry>Retrieve the head of an input</entry>
+ <entry>
+ <functionname>head_finder()</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>tail_finder</entry>
+ <entry>Retrieve the tail of an input</entry>
+ <entry>
+ <functionname>tail_finder()</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>token_finder</entry>
+ <entry>Search for a matching token in an input</entry>
+ <entry>
+ <functionname>token_finder()</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>range_finder</entry>
+ <entry>Do no search, always returns the given range</entry>
+ <entry>
+ <functionname>range_finder()</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>regex_finder</entry>
+ <entry>Search for a substring matching the given regex</entry>
+ <entry>
+ <functionname>regex_finder()</functionname>
+ </entry>
+ </row>
+ </tbody>
+ </tgroup>
+ </table>
+ <table>
+ <title>Finder types</title>
+ <tgroup cols="2" align="left">
+ <thead>
+ <row>
+ <entry>Type</entry>
+ <entry>Description</entry>
+ </row>
+ </thead>
+ <tbody>
+ <row>
+ <entry>
+ <classname>finder_t</classname>
+ </entry>
+ <entry>Allows the user to perform multiple searches using a given string search algorithm.
+The precomputed data (either on the text, the pattern, or both, depending on the chosen search algorithm) is kept from one search to another, potentially making future searches faster if either the pattern or the text remain unchanged.
+The interface of this finder provides constructors and setters taking both references (in which case copies are made) and pointers.</entry>
+ </row>
+ <row>
+ <entry>
+ <classname>simplified_finder_t</classname>
+ </entry>
+ <entry>Behaves very similarly to <classname>finder_t</classname>, but it supports a more limited set of constructors and setters (only the ones taking pointers).</entry>
+ </row>
+ </tbody>
+ </tgroup>
+ </table>
+ <para>For information on the string search algorithms, see <xref linkend="string_algo.quickref.string_search_algorithms"></xref></para>
+ </section>
+ <section>
+ <title>Formatters</title>
+ <table>
+ <title>Formatters</title>
+ <tgroup cols="3" align="left">
+ <thead>
+ <row>
+ <entry>Formatter</entry>
+ <entry>Description</entry>
+ <entry>Generators</entry>
+ </row>
+ </thead>
+ <tbody>
+ <row>
+ <entry>const_formatter</entry>
+ <entry>Constant formatter. Always return the specified string</entry>
+ <entry>
+ <functionname>const_formatter()</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>identity_formatter</entry>
+ <entry>Identity formatter. Return unmodified input input</entry>
+ <entry>
+ <functionname>identity_formatter()</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>empty_formatter</entry>
+ <entry>Null formatter. Always return an empty string</entry>
+ <entry>
+ <functionname>empty_formatter()</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>regex_formatter</entry>
+ <entry>Regex formatter. Format regex match using the specification in the format string</entry>
+ <entry>
+ <functionname>regex_formatter()</functionname>
+ </entry>
+ </row>
+ </tbody>
+ </tgroup>
+ </table>
+ </section>
+ <section>
+ <title>Iterators</title>
+ <table>
+ <title>Find Iterators</title>
+ <tgroup cols="3" align="left">
+ <thead>
+ <row>
+ <entry>Iterator name</entry>
+ <entry>Description</entry>
+ <entry>Iterator class</entry>
+ </row>
+ </thead>
+ <tbody>
+ <row>
+ <entry>find_iterator</entry>
+ <entry>Iterates through matching substrings in the input</entry>
+ <entry>
+ <classname>find_iterator</classname>
+ </entry>
+ </row>
+ <row>
+ <entry>split_iterator</entry>
+ <entry>Iterates through gaps between matching substrings in the input</entry>
+ <entry>
+ <classname>split_iterator</classname>
+ </entry>
+ </row>
+ </tbody>
+ </tgroup>
+ </table>
+ </section>
+ <section>
+ <title>Classification</title>
+ <table>
+ <title>Predicates</title>
+ <tgroup cols="3" align="left">
+ <thead>
+ <row>
+ <entry>Predicate name</entry>
+ <entry>Description</entry>
+ <entry>Generator</entry>
+ </row>
+ </thead>
+ <tbody>
+ <row>
+ <entry>is_classified</entry>
+ <entry>Generic <code>ctype</code> mask based classification</entry>
+ <entry>
+ <functionname>is_classified()</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>is_space</entry>
+ <entry>Recognize spaces</entry>
+ <entry>
+ <functionname>is_space()</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>is_alnum</entry>
+ <entry>Recognize alphanumeric characters</entry>
+ <entry>
+ <functionname>is_alnum()</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>is_alpha</entry>
+ <entry>Recognize letters</entry>
+ <entry>
+ <functionname>is_alpha()</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>is_cntrl</entry>
+ <entry>Recognize control characters</entry>
+ <entry>
+ <functionname>is_cntrl()</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>is_digit</entry>
+ <entry>Recognize decimal digits</entry>
+ <entry>
+ <functionname>is_digit()</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>is_graph</entry>
+ <entry>Recognize graphical characters</entry>
+ <entry>
+ <functionname>is_graph()</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>is_lower</entry>
+ <entry>Recognize lower case characters</entry>
+ <entry>
+ <functionname>is_lower()</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>is_print</entry>
+ <entry>Recognize printable characters</entry>
+ <entry>
+ <functionname>is_print()</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>is_punct</entry>
+ <entry>Recognize punctuation characters</entry>
+ <entry>
+ <functionname>is_punct()</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>is_upper</entry>
+ <entry>Recognize uppercase characters</entry>
+ <entry>
+ <functionname>is_upper()</functionname>
+ </entry>
+ </row>
+ <row>
+ <entry>is_xdigit</entry>
+ <entry>Recognize hexadecimal digits</entry>
+ <entry>
+ <functionname>is_xdigit()</functionname>
+ </entry>
+ </row>
+ </tbody>
+ </tgroup>
+ </table>
+ </section>
+ <section id="string_search_algorithms">
+ <title>String search algorithms</title>
+ <table>
+ <title>String search algorithms</title>
+ <tgroup cols="5" align="left">
+ <thead>
+ <row>
+ <entry>Algorithm name</entry>
+ <entry>Iterator requirements</entry>
+ <entry>Comparators</entry>
+ <entry>Complexity</entry>
+ <entry>Type</entry>
+ </row>
+ </thead>
+ <tbody>
+ <row>
+ <entry>Naive search</entry>
+ <entry>Forward Iterator</entry>
+ <entry>Any</entry>
+ <entry>O(n*m) worst-case</entry>
+ <entry>
+ <classname alt="boost::algorithm::naive_search">naive_search</classname>
+ </entry>
+ </row>
+ <row>
+ <entry>Knuth-Morris-Pratt</entry>
+ <entry>Random Access Iterators</entry>
+ <entry>Any</entry>
+ <entry>Pattern preprocessing: O(m)
+Finding: O(n)</entry>
+ <entry>
+ <classname alt="boost::algorithm::knuth_morris_pratt">knuth_morris_pratt</classname>
+ </entry>
+ </row>
+ <row>
+ <entry>Boyer-Moore</entry>
+ <entry>Random Access Iterators</entry>
+ <entry>
+ <functionname>is_equal()</functionname>for any CharT and <functionname>is_iequal()</functionname> only for CharT=char</entry>
+ <entry>Pattern preprocessing: O(m)
+Finding: O(n/m) average, O(n) worst-case</entry>
+ <entry>
+ <classname alt="boost::algorithm::boyer_moore">boyer_moore</classname>
+ </entry>
+ </row>
+ <row>
+ <entry>Rabin-Karp</entry>
+ <entry>Random Access Iterators
+Note: will support Input Iterators</entry>
+ <entry>Only <functionname>is_equal()</functionname> , with CharT an integral type</entry>
+ <entry>Pattern preprocessing: O(m)
+Finding: O(n) average, O(n*m) worst-case</entry>
+ <entry>
+ <classname alt="boost::algorithm::rabin_karp">rabin_karp32</classname>, <classname alt="boost::algorithm::rabin_karp64">rabin_karp64</classname>, <classname alt="boost::algorithm::rabin_karp_algorithm">rabin_karp_algorithm</classname></entry>
+ </row>
+ <row>
+ <entry>Suffix array</entry>
+ <entry>Random Access Iterators</entry>
+ <entry>Only <classname>is_equal()</classname></entry>
+ <entry>Text preprocessing: O(n)
+Find: ...?</entry>
+ <entry>
+ <classname alt="boost::algorithm::suffix_array">suffix_array</classname>
+ </entry>
+ </row>
+ </tbody>
+ </tgroup>
+ </table>
+ </section>
+</section>
\ No newline at end of file
Modified: sandbox/SOC/2010/stringalgos/libs/algorithm/string/doc/usage.xml
==============================================================================
--- sandbox/SOC/2010/stringalgos/libs/algorithm/string/doc/usage.xml (original)
+++ sandbox/SOC/2010/stringalgos/libs/algorithm/string/doc/usage.xml 2010-08-11 18:26:46 EDT (Wed, 11 Aug 2010)
@@ -348,7 +348,21 @@
</section>
<section>
<title>Finders</title>
- <para>Finders offer a greater degree of control over what string search algorithms you would like to use for finding.</para>
- <para>There are two finder types,<classname>finder</classname>and<classname>simplified_finder</classname>, as well as some finder generators:<functionname>first_finder</functionname>,<functionname>last_finder</functionname>,<functionname>nth_finder</functionname>,</para>
+ <para>Finders offer a greater degree of control over what string search algorithms you would like to use for finding. </para>
+ <para>They are especially useful if multiple searches are to be performed and the string or the substring do not change every iteration (because most string search algorithms precompute information on either the sought string or the text, meaning subsequent searches on the pattern or the text can be faster).</para>
+ <para>There are two finder types, <classname alt="boost::algorithm::finder_t">finder_t </classname>and <classname alt="boost::algorithm::simplified_finder_t">simplified_finder_t </classname>, as well as some finder generators: <functionname>first_finder</functionname>, <functionname>last_finder</functionname>, <functionname>nth_finder</functionname>etc.<programlisting>std::string random_saying =
+ "Speak when you are angry and you will make the best speech you'll ever regret.";
+
+boost::finder_t<std::string, std::string, boost::knuth_morris_pratt> finder("angry", &random_saying);
+
+boost::to_upper(finder.find_first()); // we modified the internal text
+std::cout << random_saying << std::cout; // Outputs "Speak when you are ANGRY..."
+
+boost::boyer_moore_finder finder2; // a typedef for finder_t<string,string,boyer_moore>
+finder2.set_substring("Speak"); // makes an internal copy of the substring
+finder2.set_string(&random_saying); // passing as a pointer allows the finder to not make a copy
+
+boost::to_upper(finder2.find_first()); // turn the match into uppercase
+std::cout << random_saying << std::endl; // Outputs "SPEAK when you are ANGRY..."</programlisting>For more information, consult the reference: <headername>boost/algorithm/string/finder.hpp</headername>.</para>
</section>
</section>
\ No newline at end of file
Modified: sandbox/SOC/2010/stringalgos/libs/algorithm/string/test/finder_test.cpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/libs/algorithm/string/test/finder_test.cpp (original)
+++ sandbox/SOC/2010/stringalgos/libs/algorithm/string/test/finder_test.cpp 2010-08-11 18:26:46 EDT (Wed, 11 Aug 2010)
@@ -631,8 +631,7 @@
BOOST_CHECK(( (ch_result.begin() - pch1 ) == 3) && ( (ch_result.end() - pch1 ) == 6 ) );
- //!\todo uncomment after finishing impl
- /*
+
// find_last
BOOST_CHECKPOINT( "find_last" );
@@ -691,7 +690,6 @@
ch_result=find_nth( pch1, "abc", 1 );
BOOST_CHECK(( (ch_result.begin() - pch1 ) == 9) && ( (ch_result.end() - pch1 ) == 12 ) );
- */
// find_head
BOOST_CHECKPOINT( "find_head" );
@@ -764,17 +762,19 @@
// generic find
BOOST_CHECKPOINT( "generic find" );
- /*
nc_result=find(str1, first_finder(string("abc")));
BOOST_CHECK(
( (nc_result.begin()-str1.begin()) == 3) &&
( (nc_result.end()-str1.begin()) == 6) );
+ //TODO: this one cannot work, what should we do about it?
+ /*
cv_result=find(const_cast<const string&>(str1), first_finder(str2) );
BOOST_CHECK(
( (cv_result.begin()-str1.begin()) == 3) &&
( (cv_result.end()-str1.begin()) == 6) );
*/
+
// multi-type comparison test
BOOST_CHECKPOINT( "multi-type" );
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk