Subject: [Boost-commit] svn:boost r64296 - in sandbox/SOC/2010/stringalgos: boost/algorithm/string boost/algorithm/string/detail boost/algorithm/string/string_search boost/algorithm/string/string_search/detail libs/algorithm/string/benchmark libs/algorithm/string/example libs/algorithm/string/test
From: mstefanro_at_[hidden]
Date: 2010-07-23 08:18:13
Author: mstefanro
Date: 2010-07-23 08:18:12 EDT (Fri, 23 Jul 2010)
New Revision: 64296
URL: http://svn.boost.org/trac/boost/changeset/64296
Log:
[GSoC2010][StringAlgo] Interface fixes, benchmarking finder, benchmarking code, other improvements etc
Added:
sandbox/SOC/2010/stringalgos/boost/algorithm/string/benchmark_finder.hpp (contents, props changed)
sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/suffix_array2.hpp
- copied, changed from r64056, /sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/suffix_array.hpp
sandbox/SOC/2010/stringalgos/libs/algorithm/string/benchmark/
sandbox/SOC/2010/stringalgos/libs/algorithm/string/benchmark/string_search.cpp (contents, props changed)
Text files modified:
sandbox/SOC/2010/stringalgos/boost/algorithm/string/detail/finder.hpp | 4
sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder.hpp | 174 +++++++++++++++++++++++++--------------
sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/boyer_moore.hpp | 50 ++++++-----
sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/detail/rabin_karp.hpp | 75 ++++++++++++----
sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/knuth_morris_pratt.hpp | 24 +++--
sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/naive_search.hpp | 14 ++-
sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/rabin_karp.hpp | 49 ++++++++--
sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/suffix_array.hpp | 25 +++--
sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/suffix_array2.hpp | 30 ++---
sandbox/SOC/2010/stringalgos/libs/algorithm/string/example/finder_example.cpp | 9 +
sandbox/SOC/2010/stringalgos/libs/algorithm/string/test/finder_test.cpp | 3
11 files changed, 291 insertions(+), 166 deletions(-)
Added: sandbox/SOC/2010/stringalgos/boost/algorithm/string/benchmark_finder.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/stringalgos/boost/algorithm/string/benchmark_finder.hpp 2010-07-23 08:18:12 EDT (Fri, 23 Jul 2010)
@@ -0,0 +1,291 @@
+#ifndef BOOST_STRING_BENCHMARK_FINDER_HPP
+#define BOOST_STRING_BENCHMARK_FINDER_HPP
+
+
+//Our finder has 6 template params, which means we cannot use it in a placeholder expression
+//unless MPL supports metafunctions with arity >= 6
+#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. " \
+ "Either configure MPL to have metafunction arity >= 6 or include benchmark_finder.hpp " \
+ "before any other header."
+# endif
+#else
+#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/string_search/naive_search.hpp>
+
+#include <boost/tuple/tuple.hpp>
+
+//#include <boost/mpl/transform.hpp>
+//#include <boost/mpl/vector/vector0.hpp>
+//#include <boost/mpl/push_back.hpp>
+#include <boost/mpl/void.hpp>
+#include <boost/mpl/placeholders.hpp>
+
+#include <boost/range/value_type.hpp>
+#include <boost/range/algorithm/equal.hpp>
+#include <boost/range/algorithm/copy.hpp>
+#include <boost/range/distance.hpp>
+
+#include <boost/fusion/adapted/mpl.hpp>
+#include <boost/fusion/algorithm/transformation/transform.hpp>
+#include <boost/fusion/algorithm/iteration/for_each.hpp>
+#include <boost/fusion/algorithm/iteration/fold.hpp>
+#include <boost/fusion/container/vector.hpp>
+#include <boost/fusion/container/vector/convert.hpp>
+
+
+#include <boost/spirit/home/phoenix/function.hpp>
+#include <boost/spirit/home/phoenix/core/argument.hpp>
+#include <boost/spirit/home/phoenix/core/reference.hpp>
+
+
+#include <deque>
+#include <string>
+#include <iostream>
+#include <algorithm>
+#include <cmath>
+#include <stdexcept>
+#include <sstream>
+
+#include <boost/throw_exception.hpp>
+
+//!\todo use something more accurate
+#include <boost/timer.hpp>
+
+namespace boost { namespace algorithm {
+
+ template <class Range1T, class Range2T, class AlgorithmSequenceT,
+ class ComparatorT/*,
+ template <class,class,class,class,class,class> class AdditionalBehaviorT*/>
+ 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)
+ {
+ boost::phoenix::function<finder_set_substring> f;
+ boost::fusion::for_each(finders,
+ f(boost::phoenix::arg_names::arg1, substring)
+ );
+ trusted_finder.set_substring(substring);
+ }
+
+ void set_string (Range2T *const string)
+ {
+ boost::phoenix::function<finder_set_string> f;
+ boost::fusion::for_each(
+ finders,
+ f(boost::phoenix::arg_names::arg1, string)
+ );
+ trusted_finder.set_string(string);
+ }
+
+ void clear ()
+ { boost::fusion::for_each(finders, clear_stats()); }
+
+ void find_reset()
+ {
+ boost::fusion::for_each(finders, finder_reset());
+ trusted_finder.find_reset();
+ }
+
+ string_range_type find_next()
+ {
+ return boost::fusion::fold(finders, trusted_finder.find_next(),
+ finder_benchmark_and_test());
+ }
+
+ 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();
+ }*/
+
+ template <class CharT, class TraitsT>
+ void output_stats (std::basic_ostream<CharT, TraitsT> &os)
+ {
+ boost::phoenix::function<output_stats_> f;
+ boost::fusion::for_each(finders, f(boost::phoenix::ref(os), 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
+ typedef typename boost::mpl::transform<AlgorithmSequenceT,
+ std::pair<
+ typename boost::algorithm::simplified_finder_t<Range1T,Range2T,
+ boost::mpl::_, ComparatorT>,
+ std::deque<double>
+ >
+ >::type finders_sequence;
+ typename boost::simplified_finder_t<Range1T, Range2T, boost::naive_search,
+ ComparatorT> trusted_finder;
+
+ typename boost::fusion::result_of::as_vector< finders_sequence >::type finders;
+
+ struct finder_set_substring
+ {
+ template <class,class> struct result { typedef void type; };
+
+ template <class Finder>
+ void operator() (Finder &finder, Range1T const *const substring) const
+ { finder.first.set_substring(substring); }
+ };
+
+ struct finder_set_string
+ {
+ template <class,class> struct result { typedef void type; };
+
+ template <class Finder>
+ void operator() (Finder &finder, Range2T *const string) const
+ { finder.first.set_string(string); }
+ };
+
+ struct clear_stats
+ {
+ template <class Finder>
+ void operator() (Finder &finder) const { finder.second.clear(); }
+ };
+
+ //template <class Finder>
+ //static void finder_reset (Finder &finder) { finder.first.find_reset(); }
+
+ struct finder_reset
+ {
+ template <class Finder>
+ void operator() (Finder &finder) const { finder.first.find_reset(); }
+ };
+
+ //!\todo Make sure tests are performed properly (via returning etc.)
+ struct finder_benchmark_and_test
+ {
+ template <class> struct result { typedef string_range_type type; };
+
+ template <class Finder>
+ string_range_type operator() (string_range_type correct, Finder &finder) const
+ {
+ string_range_type ret;
+ double time;
+ try {
+ boost::timer t;
+ ret = finder.first.find_next();
+ time = t.elapsed();
+ } catch (std::exception const &e) { BOOST_THROW_EXCEPTION(e); }
+ bool is_correct = boost::equal(correct, ret);
+ //assert(is_correct);
+ if (!is_correct)
+ {
+ std::ostringstream ss;
+
+ ss << "Match failed on " << finder.first.get_algorithm_name()
+ << " with:\n\tstr["<<boost::distance(finder.first.get_string_range())
+ << "]=";
+ boost::copy(finder.first.get_string_range(), std::ostream_iterator<char>(ss));
+
+ ss << "\n\tsubstr["<<boost::distance(finder.first.get_substring_range())
+ << "]=";
+ boost::copy(finder.first.get_substring_range(), std::ostream_iterator<char>(ss));
+
+ BOOST_THROW_EXCEPTION( std::runtime_error(ss.str()) );
+ }
+ finder.second.push_back(time);
+ return correct;
+ }
+ };
+
+ /*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; };
+
+ template <class CharT, class Finder, class TraitsT>
+ void operator() (std::basic_ostream<CharT, TraitsT> &os, Finder &finder) const
+ {
+ std::deque<double> &t = finder.second;
+ std::deque<double>::size_type size = finder.second.size();
+ typedef std::deque<double>::const_iterator It;
+ if (!size) return;
+ double min = *t.begin(), max = *t.begin(), avg=0., stddev=0.;//, median;
+ //std::sort(t.begin(), t.end());
+
+ //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;
+ if (*it > max) max = *it;
+ avg += *it;
+ //os << *it << ' ';
+ }
+ avg /= size;
+ for (It it = t.begin(); it != t.end(); ++it)
+ stddev += (avg - *it) * (avg - *it); // square of absolute deviation of *it w.r.t. avg
+ stddev /= size;
+ stddev = std::sqrt(stddev); // stddev is square root of variance
+ os << finder.first.get_algorithm_name() << "\n";
+ os << "Min : " << min << "\n"
+ << "Max : " << max << "\n"
+ << "Avg : " << avg << "\n"
+ << "Stddev: " << stddev << "\n"
+ << "Smples: " << size << "\n";
+ os << "==========================================" << std::endl;
+ }
+ };
+
+ };
+} }
+
+namespace boost { using algorithm::benchmark_finder; }
+
+#endif
\ No newline at end of file
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-07-23 08:18:12 EDT (Fri, 23 Jul 2010)
@@ -20,6 +20,7 @@
#include <boost/range/end.hpp>
#include <boost/range/empty.hpp>
#include <boost/range/as_literal.hpp>
+#include <boost/range/category.hpp>
#include <boost/iterator/iterator_traits.hpp>
@@ -63,6 +64,9 @@
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;
};
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-07-23 08:18:12 EDT (Fri, 23 Jul 2010)
@@ -29,6 +29,8 @@
#include <boost/utility/enable_if.hpp>
+#include <boost/mpl/placeholders.hpp>
+
#include <cassert>
#include <iterator>
#include <vector>
@@ -45,42 +47,60 @@
for finders provided in this library.
*/
+//!\todo impl get_internal_string, get_internal_substring, use_internal_substring
+
namespace boost { namespace algorithm {
// Finder types ---------------------------------------------//
- template <class,class,class,class,class,class> struct finder_no_additional_behavior;
- template <class,class,class,class,class,class> class finder_profiling_behavior;
- template <class,class,class,class,class,class> class finder_functor_first_finder;
- template <class,class,class,class,class,class> class finder_functor_last_finder;
- template <class,class,class,class,class,class> class finder_functor_nth_finder;
-
+ struct finder_no_additional_behavior;
+ struct finder_functor_first_finder;
+ struct finder_functor_last_finder;
+ struct finder_functor_nth_finder;
+ //! \todo use an allocator metafunction instead
+ //! \todo derive from additionalbehaviort? use it at all?
template <class Range1T, class Range2T, class AlgorithmT,
- class ComparatorT = ::boost::algorithm_is_equal,
- class AllocatorT = typename AlgorithmT::default_allocator_type,
- template <class,class,class,class,class,class> class AdditionalBehaviorT =
- boost::algorithm::finder_no_additional_behavior
+ class ComparatorT = ::boost::algorithm::is_equal,
+ class AllocatorT = std::allocator<std::size_t>/*,
+ class AdditionalBehaviorT = boost::algorithm::finder_no_additional_behavior*/
>
class simplified_finder_t :
- public boost::algorithm::detail::finder_typedefs<Range1T,Range2T,ComparatorT,AllocatorT>,
- private AlgorithmT::algorithm<
- simplified_finder_t<Range1T, Range2T, AlgorithmT, ComparatorT, AllocatorT, AdditionalBehaviorT>,
- typename boost::range_const_iterator<Range1T>::type,
- typename boost::range_iterator<Range2T>::type,
- ComparatorT,AllocatorT>
+ //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>
{
//! \todo Add concept assertions here.
-
+ private:
+ typedef typename AlgorithmT::template algorithm<simplified_finder_t, Range1T,
+ Range2T, ComparatorT, AllocatorT> algorithm_type;
public:
+ 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;
+
+ 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_()
+ { }
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()
+ algorithm_type()
{ }
void set_substring (Range1T const *substr)
@@ -98,12 +118,9 @@
return find_next();
}
- void refresh()
- {
- string_has_changed_ = true;
- find_reset();
- }
+ //! \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();
@@ -143,6 +160,22 @@
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_;
@@ -170,21 +203,19 @@
*/
template <
class Sequence1T, class Sequence2T,
- class Algorithm,
- typename Comparator = ::boost::algorithm::is_equal,
- class Allocator = typename Algorithm::default_allocator_type,
- template <class,class,class,class,class,class> class AdditionalBehavior =
- boost::algorithm::finder_no_additional_behavior
+ class AlgorithmT,
+ typename ComparatorT = ::boost::algorithm::is_equal,
+ class AllocatorT = std::allocator<std::size_t>,
+ class AdditionalBehaviorT = boost::algorithm::finder_no_additional_behavior
>
class finder_t :
- private Algorithm::algorithm<
- typename finder_t<Sequence1T, Sequence2T, Algorithm, Comparator, Allocator, AdditionalBehavior>,
- typename boost::range_const_iterator<Sequence1T>::type,
- typename boost::range_iterator<Sequence2T>::type,
- Comparator, Allocator>,
- private AdditionalBehavior<
- typename finder_t<Sequence1T, Sequence2T, Algorithm, Comparator, Allocator, AdditionalBehavior>,
- Sequence1T,Sequence2T,Algorithm,Comparator,Allocator>
+ 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,
@@ -193,6 +224,7 @@
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
@@ -209,15 +241,25 @@
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 type of the algorithm
- typedef typename Algorithm::algorithm<finder_t,
- substring_iterator_type,
- string_iterator_type,
- Comparator, Allocator> algorithm_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)
@@ -237,7 +279,7 @@
references, then a move is performed as opposed to a copy.
*/
explicit finder_t (const Sequence1T *const substring = 0, Sequence2T *const string = 0,
- Comparator comparator = Comparator(), Allocator allocator = Allocator())
+ 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_),
@@ -249,7 +291,7 @@
//! \overload
template <class Range2T>
finder_t (const Sequence1T *const substring, const Range2T &string,
- Comparator comparator = Comparator(), Allocator allocator = Allocator(),
+ 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_),
@@ -265,7 +307,7 @@
//! \overload
template <class Range1T>
explicit finder_t (const Range1T &substring, Sequence2T *const string = 0,
- Comparator comparator = Comparator(), Allocator allocator = Allocator(),
+ 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_(),
@@ -281,7 +323,7 @@
//! \overload
template <class Range1T, class Range2T>
finder_t (const Range1T &substring, const Range2T &string,
- Comparator comparator = Comparator(), Allocator allocator = Allocator(),
+ 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),
@@ -301,7 +343,7 @@
explicit finder_t (
Sequence1T const &&substring,
Sequence2T *const string = 0,
- Comparator comparator = Comparator(), Allocator allocator = Allocator())
+ 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_),
@@ -315,7 +357,7 @@
explicit finder_t (
Sequence1T const &&substring,
const Range2T &string,
- Comparator comparator = Comparator(), Allocator allocator = Allocator(),
+ 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_),
@@ -329,7 +371,7 @@
finder_t (
Sequence1T const &&substring,
Sequence2T &&string,
- Comparator comparator = Comparator(), Allocator allocator = Allocator())
+ 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_),
@@ -341,7 +383,7 @@
//! \overload
finder_t (const Sequence1T *const substring,
Sequence2T &&string,
- Comparator comparator = Comparator(), Allocator allocator = Allocator())
+ 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_),
@@ -354,7 +396,7 @@
template <class Range1T>
finder_t (const Range1T &substring,
Sequence2T &&string,
- Comparator comparator = Comparator(), Allocator allocator = Allocator(),
+ 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_(),
@@ -382,23 +424,24 @@
typename string_range_type get_string_range() const
{ return string_range_; }
- typename boost::call_traits<Comparator>::reference get_comparator()
+ //! Gets a reference to an instance of the comparator in use
+ typename boost::call_traits<comparator_type>::reference get_comparator()
{ return comparator_; }
- typename boost::call_traits<Comparator>::const_reference get_comparator() const
+ 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>::reference get_allocator()
+ typename boost::call_traits<allocator_type>::reference get_allocator()
{ return allocator_; }
/*!
\overload
*/
- typename boost::call_traits<Allocator>::const_reference get_allocator() const
+ typename boost::call_traits<allocator_type>::const_reference get_allocator() const
{ return allocator_; }
//! Changes the substring to be searched for.
@@ -494,7 +537,14 @@
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.
@@ -506,12 +556,6 @@
\note This is semantically equivalent to \c find_reset(); match=find_next();
*/
- void refresh()
- {
- string_has_changed_ = true;
- find_reset();
- }
-
//!\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
@@ -603,7 +647,11 @@
bool substring_has_changed_, string_has_changed_;
};
- template <class,class,class,class,class,class> struct finder_no_additional_behavior { };
+ struct finder_no_additional_behavior
+ { template <class,class,class,class,class,class> struct apply { }; };
+ //struct finder_functor_first_finder {};
+ //struct finder_functor_last_finder {};
+ //struct finder_functor_nth_finder {};
// Finder generators ------------------------------------------//
@@ -839,7 +887,7 @@
//! \TODO: any other finder types?
using algorithm::finder_t;
-
+ using algorithm::simplified_finder_t;
} // namespace boost
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-07-23 08:18:12 EDT (Fri, 23 Jul 2010)
@@ -2,7 +2,7 @@
#define BOOST_ALGORITHM_BOYER_MOORE_HPP
#include <iterator>
-#include <allocators>
+#include <memory>
#include <utility>
#include <vector>
#include <boost/range/begin.hpp>
@@ -10,24 +10,30 @@
#include <boost/range/adaptor/reversed.hpp>
#include <boost/range/algorithm/for_each.hpp>
#include <boost/range/distance.hpp>
+#include <boost/range/category.hpp>
#include <boost/call_traits.hpp>
#include <boost/type_traits/is_same.hpp>
#include <boost/static_assert.hpp>
#include <map>
#include <string>
#include <boost/algorithm/string/finder.hpp>
+#include <boost/algorithm/string/detail/finder.hpp>
+
+#include <boost/unordered_map.hpp>
+#include <boost/functional/hash.hpp>
namespace boost { namespace algorithm {
struct boyer_moore
{
- typedef std::allocator<std::size_t> default_allocator_type;
- template <class Finder, class ForwardIterator1T,class ForwardIterator2T,
- class Comparator,class Allocator>
+ template <class Finder, class RandomAccessRange1T,class RandomAccessRange2T,
+ class ComparatorT,class AllocatorT>
class algorithm
+ : public boost::algorithm::detail::finder_typedefs<
+ RandomAccessRange1T,RandomAccessRange2T,ComparatorT,AllocatorT>
{
public:
- typedef ForwardIterator1T substring_iterator_type;
+ /*typedef ForwardIterator1T substring_iterator_type;
typedef ForwardIterator2T string_iterator_type;
typedef typename
std::iterator_traits<substring_iterator_type>::value_type substring_char_type;
@@ -35,7 +41,8 @@
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;
+ typedef Allocator allocator_type;*/
+ std::string get_algorithm_name () const { return "Boyer-Moore"; }
protected:
algorithm () {
BOOST_STATIC_ASSERT((boost::is_same<substring_char_type,string_char_type>::value));
@@ -43,13 +50,13 @@
string_range_type find(string_iterator_type start)
{
- return find(start, std::iterator_traits<ForwardIterator2T>::iterator_category());
+ return find(start, string_iterator_category());
}
//Compute the two tables
void on_substring_change()
{
- on_substring_change(std::iterator_traits<ForwardIterator1T>::iterator_category());
+ on_substring_change(substring_iterator_category());
}
//No precomputation to be done on the string
inline void on_string_change()
@@ -131,16 +138,11 @@
str_idx += substr_size_ - substr_idx;
substr_idx = substr_size_ - 1;
}
- else if (iter->second > substr_idx)
- {
- str_idx += iter->second;
- substr_idx = substr_size_ - 1;
- //str_idx += iter->second - substr_idx + substr_size_ - 1 - substr_idx;
- //substr_idx = substr_size_ - 1;
- //substr_idx = substr_size_ - 1 - iter->second;
- //str_idx += substr_size_ - 1 - substr_idx;
- //substr_idx = substr_size_ - 1;
- }
+ //else if (iter->second > substr_idx)
+ //{
+ // str_idx += iter->second;
+ // substr_idx = substr_size_ - 1;
+ //}
else
{
assert(substr_size_ >= substr_idx);
@@ -153,13 +155,15 @@
}
//!\todo Get a better data structure here (hash table?)
- //!\todo Find a better way for custom allocators here
- typedef typename std::map<substring_char_type, std::size_t,
- std::less<substring_char_type>,
- typename std::allocator<std::pair<const substring_char_type, std::size_t> >
+ //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
+ rebind<substring_char_type>::other
> table1_type;
-
table1_type table1;
+
+ //std::vector<std::pair<substring_char_type, std::size_t> > table1;
std::size_t substr_size_;
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-07-23 08:18:12 EDT (Fri, 23 Jul 2010)
@@ -4,13 +4,26 @@
#include <boost/utility/enable_if.hpp>
#include <boost/type_traits/is_base_of.hpp>
#include <boost/type_traits/make_unsigned.hpp>
+#include <boost/mpl/void.hpp>
#include <boost/mpl/and.hpp>
#include <boost/mpl/not.hpp>
#include <boost/range/iterator.hpp>
+#include <boost/range/category.hpp>
#include <boost/call_traits.hpp>
#include <iterator>
#include <boost/range/begin.hpp>
#include <boost/range/end.hpp>
+#include <cassert>
+#include <limits>
+
+//!\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) \
+ assert((boost::uintmax_t)(a)-(boost::uintmax_t)(b) <= std::numeric_limits<T>::max()),((a)-(b))
+#define BOOST_ALGORITHM_DETAIL_ASSERTED_MULTIPLY(a, b, T) \
+ assert((boost::uintmax_t)(a)*(boost::uintmax_t)(b) <= std::numeric_limits<T>::max()),((a)*(b))
+
namespace boost { namespace algorithm { namespace detail {
@@ -34,69 +47,74 @@
return ret;
}
- template <class Finder, class ForwardIterator1T,class ForwardIterator2T, class HashType,
+ template <class Finder, class Range1T,class Range2T, class HashType,
HashType FirstBase, HashType FirstModulo,
HashType SecondBase, HashType SecondModulo, class Enable = void>
class rabin_karp_algorithm;
// Implementation of Rabin Karp for text supporting Input Iterators
- template <class Finder, class ForwardIterator1T,class ForwardIterator2T, class HashType,
+ template <class Finder, class Range1T,class Range2T, class HashType,
HashType FirstBase, HashType FirstModulo,
HashType SecondBase, HashType SecondModulo>
class rabin_karp_algorithm<Finder,
- ForwardIterator1T, ForwardIterator2T, HashType,
+ Range1T, Range2T, HashType,
FirstBase, FirstModulo, SecondBase, SecondModulo,
typename boost::enable_if<
typename boost::mpl::and_<
typename boost::is_base_of<std::input_iterator_tag,
- typename std::iterator_traits<ForwardIterator2T>::iterator_category>,
+ typename boost::range_category<Range2T>::type>,
typename boost::mpl::not_<typename boost::is_base_of<std::forward_iterator_tag,
- typename std::iterator_traits<ForwardIterator2T>::iterator_category> >
+ typename boost::range_category<Range2T>::type> >
>
>::type
>
;
// Implementation of Rabin Karp for text supporting Forward Iterators
- template <class Finder, class ForwardIterator1T,class ForwardIterator2T, class HashType,
+ template <class Finder, class Range1T,class ForwardRange2T, class HashType,
HashType FirstBase, HashType FirstModulo,
HashType SecondBase, HashType SecondModulo>
class rabin_karp_algorithm<Finder,
- ForwardIterator1T, ForwardIterator2T, HashType,
+ Range1T, ForwardRange2T, HashType,
FirstBase, FirstModulo, SecondBase, SecondModulo,
typename boost::enable_if<
typename boost::mpl::and_<
typename boost::is_base_of<std::forward_iterator_tag,
- typename std::iterator_traits<ForwardIterator2T>::iterator_category>,
+ typename boost::range_category<ForwardRange2T>::type>,
typename boost::mpl::not_<typename boost::is_base_of<std::random_access_iterator_tag,
- typename std::iterator_traits<ForwardIterator2T>::iterator_category> >
+ typename boost::range_category<ForwardRange2T>::type> >
>
>::type
>
;
//Implementation of Rabin Karp for text supporting Random Access Iterators
- template <class Finder, class ForwardIterator1T,class ForwardIterator2T, class HashType,
+ template <class Finder, class Range1T,class RandomAccessRange2T, class HashType,
HashType FirstBase, HashType FirstModulo,
HashType SecondBase, HashType SecondModulo>
class rabin_karp_algorithm<
- Finder, ForwardIterator1T, ForwardIterator2T, HashType,
+ Finder, Range1T, RandomAccessRange2T, HashType,
FirstBase, FirstModulo, SecondBase, SecondModulo,
typename boost::enable_if<
typename boost::is_base_of<
std::random_access_iterator_tag,
- typename std::iterator_traits<ForwardIterator2T>::iterator_category
+ typename boost::range_category<RandomAccessRange2T>::type
>
>::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.
+ : public boost::algorithm::detail::finder_typedefs<
+ Range1T,RandomAccessRange2T,boost::algorithm::is_equal,std::allocator<std::size_t> >
{
public:
- typedef ForwardIterator1T substring_iterator_type;
- typedef ForwardIterator2T string_iterator_type;
+ /*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;
+ typedef typename boost::iterator_range<string_iterator_type> string_range_type;*/
protected:
rabin_karp_algorithm() :
@@ -106,7 +124,7 @@
first_inverse_(0), second_inverse_(0), string_size_(0), substring_size_(0), string_computed_upto_(0)
{ }
- //!\todo this the right name?
+ //!\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)); }
@@ -120,7 +138,7 @@
std::size_t old_substring_size = substring_size_;
substring_size_ = 0;
- for (ForwardIterator1T it = boost::begin(substr);
+ for (substring_iterator_type it = boost::begin(substr);
it != boost::end(substr); ++it, ++substring_size_)
{
first = (first * FirstBase + integer_promotion(*it) ) % FirstModulo;
@@ -147,7 +165,7 @@
HashType first = static_cast<HashType>(0), second = static_cast<HashType>(0);
std::size_t computed = 0;
- for (ForwardIterator2T it = boost::begin(str);
+ for (string_iterator_type it = boost::begin(str);
it != boost::end(str) && computed < substring_size_;
++it, ++computed)
{
@@ -229,7 +247,9 @@
return boost::make_tuple(first, second);
}*/
- inline void roll_string_hash()
+ //!\todo compatible force inline? __attribute__((force_inline)) in GCC
+ //inline void roll_string_hash()
+ __forceinline void roll_string_hash()
{
string_range_type const &str = static_cast<Finder*>(this)->get_string_range();
@@ -242,15 +262,28 @@
boost::begin(str)[string_computed_upto_]
));
- first_string_hash_current_ = mod(
+ /*first_string_hash_current_ = mod(
mod(FirstBase * first_string_hash_current_ + add,FirstModulo) +
mod(first_inverse_ * remove,FirstModulo),
+ FirstModulo);*/
+
+ //In order to not overflow: (M1-1)*b1 + X + (M1-1)*X <= MAX(HashType)
+ first_string_hash_current_ = mod(
+ FirstBase * first_string_hash_current_ + add +
+ first_inverse_ * remove,
FirstModulo);
- second_string_hash_current_ = mod(
+ /*second_string_hash_current_ = mod(
mod(SecondBase * second_string_hash_current_ + add,SecondModulo) +
mod(second_inverse_ * remove,SecondModulo),
SecondModulo);
+ */
+ //In order to not overflow: (M2-1)*b2 + X + (M2-1)*X <= MAX(HashType)
+ second_string_hash_current_ = mod(
+ SecondBase * second_string_hash_current_ + add +
+ second_inverse_ * remove,
+ SecondModulo);
+
++string_computed_upto_;
}
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-07-23 08:18:12 EDT (Fri, 23 Jul 2010)
@@ -8,38 +8,44 @@
#include <boost/algorithm/string/finder.hpp>
#include <string>
#include <vector>
-#include <allocators>
+#include <memory>
+#include <boost/algorithm/string/detail/finder.hpp>
namespace boost { namespace algorithm {
struct knuth_morris_pratt
{
- typedef std::allocator<std::size_t> default_allocator_type;
- template <class Finder,class RandomAccessIterator1T,
- class RandomAccessIterator2T,class Comparator,class Allocator>
+
+ template <class Finder,class RandomAccessRange1T,
+ class RandomAccessRange2T,class ComparatorT,class AllocatorT>
class algorithm
+ : public boost::algorithm::detail::finder_typedefs<
+ RandomAccessRange1T,RandomAccessRange2T,ComparatorT,AllocatorT>
{
public:
- typedef RandomAccessIterator1T substring_iterator_type;
+ /*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;
+ typedef Comparator comparator_type;*/
+ std::string get_algorithm_name () const { return "Knuth-Morris-Pratt"; }
protected:
string_range_type find(string_iterator_type start)
{
- return find(start, std::iterator_traits<RandomAccessIterator2T>::iterator_category());
+ return find(start, string_iterator_category());
}
void on_substring_change()
{
- on_substring_change(std::iterator_traits<RandomAccessIterator1T>::iterator_category());
+ on_substring_change(substring_iterator_category());
}
void on_string_change()
{
}
private:
- std::vector<std::size_t, Allocator> failure_func;
+
+ std::vector<std::size_t,
+ typename AllocatorT::template rebind<std::size_t>::other > failure_func;
string_range_type find(string_iterator_type start, std::random_access_iterator_tag)
{
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-07-23 08:18:12 EDT (Fri, 23 Jul 2010)
@@ -8,27 +8,31 @@
#include <boost/range/end.hpp>
#include <string>
#include <boost/algorithm/string/finder.hpp>
+#include <boost/algorithm/string/detail/finder.hpp>
namespace boost { namespace algorithm {
//! \todo Copyable
struct naive_search
{
- typedef boost::mpl::void_ default_allocator_type;
- template <class Finder, class Iterator1T, class Iterator2T, class ComparatorT, class AllocatorT>
+ template <class Finder, class ForwardRange1T, class ForwardRange2T, class ComparatorT, class AllocatorT>
struct algorithm
+ : public boost::algorithm::detail::finder_typedefs<
+ ForwardRange1T,ForwardRange2T,ComparatorT,AllocatorT>
{
+ public:
+ std::string get_algorithm_name () const { return "Naive search"; }
protected:
algorithm () { }
- typename boost::iterator_range<Iterator2T> find(Iterator2T start)
+ string_range_type find(string_iterator_type start)
{
- typedef typename Finder::string_iterator_type string_iterator_type;
+ /*typedef typename Finder::string_iterator_type string_iterator_type;
typedef typename Finder::substring_iterator_type substring_iterator_type;
typedef typename Finder::substring_range_type substring_range_type;
typedef typename Finder::string_range_type string_range_type;
- typedef typename Finder::comparator_type comparator_type;
+ 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();
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-07-23 08:18:12 EDT (Fri, 23 Jul 2010)
@@ -12,10 +12,13 @@
#include <boost/range/begin.hpp>
#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 <cassert>
+#include <limits>
+#include <boost/type_traits/is_same.hpp>
namespace boost { namespace algorithm {
@@ -33,31 +36,51 @@
HashType SecondBase, HashType SecondModulo>
struct rabin_karp_algorithm
{
- typedef boost::mpl::void_ default_allocator_type;
- template <class Finder, class Iterator1T, class Iterator2T, class ComparatorT, class AllocatorT>
+ template <class Finder, class Range1T, class Range2T, class ComparatorT, class AllocatorT>
class algorithm;
- template <class Finder, class Iterator1T, class Iterator2T, class AllocatorT>
- class algorithm<Finder, Iterator1T, Iterator2T, boost::algorithm::is_equal, AllocatorT>
+ template <class Finder, class Range1T, class Range2T, class AllocatorT>
+ class algorithm<Finder, Range1T, Range2T, boost::algorithm::is_equal, AllocatorT>
: public ::boost::algorithm::detail::rabin_karp_algorithm<Finder,
- Iterator1T, Iterator2T, HashType,
- FirstBase, FirstModulo, SecondBase, SecondModulo>
+ Range1T, Range2T, HashType, FirstBase, FirstModulo, SecondBase, SecondModulo>
{
+ public:
+ std::string get_algorithm_name () const
+ { return "Rabin-Karp (" + boost::lexical_cast<std::string>(sizeof(HashType)) + ")"; }
protected:
//construct the algorithm given iterator ranges for the substring and the string
algorithm () {
//!\todo add more assertions here
- BOOST_STATIC_ASSERT(
- sizeof(boost::iterator_value<Iterator1T>::type)*2 <= sizeof(HashType)
- );
+ BOOST_STATIC_ASSERT((
+ sizeof(boost::range_value<Range1T>::type)*2 <= sizeof(HashType)
+ ));
+ BOOST_STATIC_ASSERT(( boost::is_same<substring_char_type,string_char_type>::value ));
+ assert_overflow(FirstBase, FirstModulo);
+ assert_overflow(SecondBase, SecondModulo);
+ }
+ private:
+ inline void assert_overflow(HashType B, HashType M)
+ {
+ //!\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(
+ (boost::uintmax_t)std::numeric_limits<substring_char_type>::max(),
+ (boost::uintmax_t)std::numeric_limits<substring_char_type>::min(), HashType
+ ), 1, HashType);
+ //(M-1)*b + X + (M1-1)*X <= MAX(HashType)
+ BOOST_ALGORITHM_DETAIL_ASSERTED_ADD(
+ BOOST_ALGORITHM_DETAIL_ASSERTED_ADD(
+ BOOST_ALGORITHM_DETAIL_ASSERTED_MULTIPLY(M-1, B, HashType), char_range_size, HashType),
+ BOOST_ALGORITHM_DETAIL_ASSERTED_MULTIPLY(M-1,char_range_size, HashType), HashType );*/
}
-
};
};
//1/3732152659 odds of collision. useful with char
- typedef rabin_karp_algorithm<boost::uint32_t,257,64433,277,57923> rabin_karp32;
+ //!\todo replace with old one
+ typedef rabin_karp_algorithm<boost::uint_fast32_t,257,64433,277,57923> rabin_karp32;
//1/150167080229379589 odds of collision. useful with wchar_t
typedef rabin_karp_algorithm<boost::uint64_t,337515847,373587883,255150899,401959183> rabin_karp64;
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-07-23 08:18:12 EDT (Fri, 23 Jul 2010)
@@ -8,20 +8,24 @@
#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>
namespace boost { namespace algorithm {
struct suffix_array_search
{
- typedef std::allocator<std::size_t> default_allocator_type;
//! \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 RandomAccessIterator1T,
- class RandomAccessIterator2T,class Comparator,class Allocator>
+ template <class Finder,class RandomAccessRange1T,
+ class RandomAccessRange2T,class ComparatorT,class AllocatorT>
class algorithm
+ : public boost::algorithm::detail::finder_typedefs<
+ RandomAccessRange1T,RandomAccessRange2T,ComparatorT,AllocatorT>
{
public:
- typedef RandomAccessIterator1T substring_iterator_type;
+ /*typedef RandomAccessIterator1T substring_iterator_type;
typedef RandomAccessIterator2T string_iterator_type;
typedef typename
std::iterator_traits<substring_iterator_type>::value_type substring_char_type;
@@ -29,15 +33,16 @@
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;
+ typedef Allocator allocator_type;*/
+ std::string get_algorithm_name () const { return "Suffix array"; }
protected:
algorithm () : found_matches_(false), pos_(), matches_() { }
void on_substring_change()
- { on_substring_change(std::iterator_traits<substring_iterator_type>::iterator_category()); }
+ { on_substring_change(substring_iterator_category()); }
void on_string_change()
- { on_string_change(std::iterator_traits<string_iterator_type>::iterator_category()); }
+ { on_string_change(string_iterator_category()); }
string_range_type find (string_iterator_type start)
{
@@ -131,7 +136,7 @@
string_range_type const &str = static_cast<Finder*>(this)->get_string_range();
substring_range_type const &substr = static_cast<Finder*>(this)->get_substring_range();
- std::vector<std::size_t, Allocator>::const_iterator first_match =
+ std::vector<std::size_t, AllocatorT>::const_iterator first_match =
std::lower_bound(matches_.begin(), matches_.end(), start_offset);
if (first_match == matches_.end())
return string_range_type(
@@ -185,9 +190,9 @@
return std::equal(substr.begin(), substr.end(), boost::begin(str)+start_offset);
}
- std::vector<std::size_t, Allocator> pos_;
+ std::vector<std::size_t, typename AllocatorT::template rebind<std::size_t>::other> pos_;
bool found_matches_;
- std::vector<std::size_t, Allocator> matches_;
+ std::vector<std::size_t, typename AllocatorT::template rebind<std::size_t>::other> matches_;
struct increasing_generator
Copied: sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/suffix_array2.hpp (from r64056, /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_array2.hpp 2010-07-23 08:18:12 EDT (Fri, 23 Jul 2010)
@@ -8,36 +8,32 @@
#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>
namespace boost { namespace algorithm {
struct suffix_array_search
{
- typedef std::allocator<std::size_t> default_allocator_type;
//! \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 RandomAccessIterator1T,
- class RandomAccessIterator2T,class Comparator,class Allocator>
+ template <class Finder,class RandomAccessRange1T,
+ class RandomAccessRange2T,class ComparatorT,class AllocatorT>
class algorithm
+ : public boost::algorithm::detail::finder_typedefs<
+ RandomAccessRange1T,RandomAccessRange2T,ComparatorT,AllocatorT>
{
public:
- typedef RandomAccessIterator1T substring_iterator_type;
- typedef RandomAccessIterator2T 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 "Suffix array II"; }
protected:
algorithm () : found_matches_(false), pos_(), matches_() { }
void on_substring_change()
- { on_substring_change(std::iterator_traits<substring_iterator_type>::iterator_category()); }
+ { on_substring_change(substring_iterator_category()); }
void on_string_change()
- { on_string_change(std::iterator_traits<string_iterator_type>::iterator_category()); }
+ { on_string_change(string_iterator_category()); }
string_range_type find (string_iterator_type start)
{
@@ -131,7 +127,7 @@
string_range_type const &str = static_cast<Finder*>(this)->get_string_range();
substring_range_type const &substr = static_cast<Finder*>(this)->get_substring_range();
- std::vector<std::size_t, Allocator>::const_iterator first_match =
+ std::vector<std::size_t, AllocatorT>::const_iterator first_match =
std::lower_bound(matches_.begin(), matches_.end(), start_offset);
if (first_match == matches_.end())
return string_range_type(
@@ -185,9 +181,9 @@
return std::equal(substr.begin(), substr.end(), boost::begin(str)+start_offset);
}
- std::vector<std::size_t, Allocator> pos_;
+ std::vector<std::size_t, typename AllocatorT::template rebind<std::size_t>::other> pos_;
bool found_matches_;
- std::vector<std::size_t, Allocator> matches_;
+ std::vector<std::size_t, typename AllocatorT::template rebind<std::size_t>::other> matches_;
struct increasing_generator
Added: sandbox/SOC/2010/stringalgos/libs/algorithm/string/benchmark/string_search.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/stringalgos/libs/algorithm/string/benchmark/string_search.cpp 2010-07-23 08:18:12 EDT (Fri, 23 Jul 2010)
@@ -0,0 +1,374 @@
+/*
+#if defined(BOOST_MPL_LIMIT_METAFUNCTION_ARITY) && BOOST_MPL_LIMIT_METAFUNCTION_ARITY < 6
+#undef BOOST_MPL_LIMIT_METAFUNCTION_ARITY
+#define BOOST_MPL_LIMIT_METAFUNCTION_ARITY 10
+#elif !defined(BOOST_MPL_LIMIT_METAFUNCTION_ARITY)
+#define BOOST_MPL_LIMIT_METAFUNCTION_ARITY 10
+#endif
+*/
+
+
+#if 0
+
+#include <boost/type_traits.hpp>
+
+
+#include <boost/mpl/lambda.hpp>
+#include <boost/mpl/placeholders.hpp>
+#include <boost/mpl/transform.hpp>
+#include <boost/mpl/vector_c.hpp>
+#include <boost/mpl/equal.hpp>
+#include <boost/mpl/fold.hpp>
+#include <boost/mpl/vector.hpp>
+
+
+#include <iostream>
+#include <string>
+
+
+using namespace std;
+using namespace boost;
+
+/*
+template <class F, class X>
+struct twice : boost::mpl::apply<F, typename boost::mpl::apply<F, X>::type> {};
+
+using namespace boost::mpl;
+using namespace boost::mpl::placeholders;
+
+template <class S1, class S2>
+struct cross_product
+{
+ template <class OldS, class T>
+ struct inner_cross_product
+ {
+ typedef typename boost::mpl::fold<S2, OldS,
+ boost::mpl::push_back<boost::mpl::_1, std::pair<T, boost::mpl::_2> > >::type type;
+ };
+
+ typedef typename boost::mpl::fold<S1, boost::mpl::vector0<>,
+ inner_cross_product<boost::mpl::_1,boost::mpl::_2> >::type type;
+};
+
+int main ()
+{
+ using namespace boost;
+ using namespace boost::mpl::placeholders;
+ typedef twice<boost::add_pointer<boost::mpl::_1>,int>::type A;
+ static_assert(is_same<A, int**>::value,"a");
+ static_assert(
+ boost::mpl::equal<
+ boost::mpl::transform<
+ boost::mpl::vector_c<int, 1,2,3>,
+ boost::mpl::plus<_,boost::mpl::int_<1> >
+ >::type,
+ boost::mpl::vector_c<int,2,3,4>
+ >::value, "c");
+ static_assert(
+ boost::mpl::equal<
+ boost::mpl::transform<
+ boost::mpl::vector_c<int,1,2,3>,
+ boost::mpl::vector_c<int,1,1,1>,
+ boost::mpl::plus<_,_>
+ >::type,
+ boost::mpl::vector_c<int,2,3,4>
+ >::value, "b");
+ static_assert(
+ boost::mpl::equal<
+ boost::mpl::fold<
+ boost::mpl::vector<int>, boost::mpl::vector0<>,
+ boost::mpl::push_back<boost::mpl::_1,std::pair<boost::mpl::_2,boost::mpl::_2> > >::type,
+ boost::mpl::vector<std::pair<int,int>>
+ >::value, "c");
+ static_assert(
+ boost::mpl::equal<
+ cross_product<
+ boost::mpl::vector<char>, boost::mpl::vector<char>
+ >::type,
+ boost::mpl::vector<std::pair<char,char>>
+ >::value, "ohai"
+ );
+
+
+ std::cin.get();
+ return 0;
+}
+*/
+
+
+
+
+
+
+#include <boost/mpl/lambda.hpp>
+#include <boost/mpl/placeholders.hpp>
+#include <boost/mpl/transform.hpp>
+#include <boost/mpl/vector_c.hpp>
+#include <boost/mpl/equal.hpp>
+#include <boost/mpl/fold.hpp>
+#include <boost/mpl/vector.hpp>
+#include <boost/mpl/apply.hpp>
+#include <boost/fusion/adapted/mpl.hpp>
+
+
+template <class T, class U, class V> struct A : T::template X<U> {};
+
+#if 0
+template <class Range1T, class Range2T, class AlgorithmT/*,
+ class ComparatorT = ::boost::algorithm::is_equal,*/
+ //class AllocatorT = /*typename AlgorithmT::default_allocator_type*/std::allocator<std::size_t>/*,
+ //class AdditionalBehaviorT = boost::algorithm::finder_no_additional_behavior*/
+>
+class simplified_finder_t2 :
+ //public boost::algorithm::detail::finder_typedefs<Range1T,Range2T,ComparatorT,AllocatorT>,
+ private AlgorithmT::template algorithm<
+ simplified_finder_t<Range1T, Range2T, AlgorithmT>,
+ typename boost::range_const_iterator<Range1T>::type,
+ typename boost::range_iterator<Range2T>::type//,
+ //ComparatorT,AllocatorT>
+ >
+{ };
+#endif
+
+#endif
+
+//#define BOOST_MPL_CFG_NO_PREPROCESSED_HEADERS
+//#define BOOST_MPL_LIMIT_METAFUNCTION_ARITY 10
+#include <boost/algorithm/string/benchmark_finder.hpp>
+
+#include <boost/algorithm/string/finder.hpp>
+#include <boost/algorithm/string/string_search.hpp>
+
+#include <boost/mpl/lambda.hpp>
+#include <boost/fusion/algorithm/transformation/transform.hpp>
+#include <boost/fusion/container/vector/convert.hpp>
+
+#include <boost/range/algorithm/for_each.hpp>
+#include <boost/range/distance.hpp>
+#include <boost/cstdint.hpp>
+
+#include <boost/mpl/vector.hpp>
+
+#include <fstream>
+#include <cstdlib>
+#include <limits>
+
+#include <boost/random/mersenne_twister.hpp>
+#include <boost/random/uniform_int.hpp>
+#include <boost/random/variate_generator.hpp>
+
+#include <boost/assign/list_of.hpp>
+
+#include <boost/foreach.hpp>
+
+#include <boost/spirit/home/phoenix/function.hpp>
+#include <boost/spirit/home/phoenix/core/argument.hpp>
+#include <boost/spirit/home/phoenix/core/reference.hpp>
+#include <boost/spirit/home/phoenix/operator.hpp>
+
+#include <boost/exception/exception.hpp>
+#include <boost/exception/diagnostic_information.hpp>
+#include <boost/throw_exception.hpp>
+
+#include <boost/format.hpp>
+
+
+unsigned int mrand (unsigned int min, unsigned int max)
+{
+ static boost::mt19937 rng;
+ assert(min <= max);
+ boost::uniform_int<> distrib(min, max);
+ boost::variate_generator<boost::mt19937&, boost::uniform_int<> > gen(rng, distrib);
+ return gen();
+}
+
+std::string rand_str (int max)
+{
+ std::string ret;
+ max = mrand(max/2,max);
+ for (int i = 0; i < max; ++i) ret += (unsigned char)mrand(0,255);
+ assert(ret.size() == max);
+ return ret;
+}
+
+//get a random substring out of a string
+std::string rand_substr(std::string const &str)
+{
+ unsigned int size = mrand(1,str.size());
+ unsigned int offset = mrand(0, str.size()-size-1);
+ return std::string(str.begin()+offset, str.begin()+offset+size);
+}
+
+std::string rand_obfuscate_end (std::string const &str)
+{
+ unsigned int start;
+ if (str.size() < 10) start = 0;
+ else start = str.size() - 10;
+ unsigned int offset = mrand(start, str.size()-1);
+ return str.substr(0, offset) + (char)mrand(0,255) + str.substr(offset+1);
+}
+
+std::string rand_obfuscate_beginning (std::string const &str)
+{
+ unsigned int end = 10;
+ if (end >= str.size()) end = str.size()-1;
+ unsigned int offset = mrand(0, end);
+ return str.substr(0, offset) + (char)mrand(0,256) + str.substr(offset+1);
+}
+
+char find_most_frequent(std::string const &str)
+{
+ static const unsigned int char_range_size =
+ std::numeric_limits<char>::max() -
+ std::numeric_limits<char>::min() + 1;
+ std::vector<unsigned int> freq(char_range_size);
+ for (std::string::const_iterator it = str.begin(); it != str.end(); ++it)
+ {
+ //!\todo reuse old one
+ //++freq[*it - std::numeric_limits<char>::min()];
+ try
+ {
+ ++freq.at((int)*it - std::numeric_limits<char>::min());
+ }
+ catch (std::exception const &)
+ {
+ BOOST_THROW_EXCEPTION(std::runtime_error(
+ (boost::format("Tried to increment index %1% of the vector") % ((int)*it - std::numeric_limits<char>::min())).str()
+ ));
+ }
+
+ }
+ unsigned int max_idx = 0, max = freq[0];
+ for (unsigned int i = 1; i < char_range_size; ++i)
+ if (freq[i] > max) { max = freq[i]; max_idx = i; }
+ return max_idx + std::numeric_limits<char>::min();
+}
+
+
+void unit_test()
+{
+ assert(find_most_frequent("hello world") == 'l');
+ assert(find_most_frequent("aaabb") == 'a');
+ assert(find_most_frequent("aaabbccc") != 'b');
+ assert(find_most_frequent("aaaaaaaaaaa") == 'a');
+ assert(find_most_frequent("abababb") == 'b');
+}
+
+int main ()
+{
+ using namespace boost;
+ using namespace boost::mpl;
+ using namespace boost::fusion;
+ using namespace boost::phoenix;
+ using namespace boost::phoenix::arg_names;
+ using namespace boost::random;
+ using namespace boost::assign;
+
+ std::string substr("hello world"), str("hello world");
+
+ boost::benchmark_finder<std::string, std::string,
+ boost::mpl::vector<
+ boost::naive_search,
+ boost::knuth_morris_pratt,
+ boost::boyer_moore,
+ //boost::suffix_array_search,
+ boost::rabin_karp32/*,
+ boost::rabin_karp64*/
+ >,
+ boost::is_equal> b;
+
+ b.set_substring(&substr); b.set_string(&str);
+ std::cout << "Doing almost no work:" << std::endl;
+ for (unsigned int i=0; i<5000; ++i) b.find_first();
+ b.output_stats(std::cout);
+
+ b.clear();
+
+ std::string const &benchmark_path = "E:/gsoc-boost/benchmarks";
+
+ std::vector<std::string> benchmark_files = list_of
+ ("dblp.xml.200MB") ("dna.200MB") ("english.200MB") ("pitches.50MB")
+ ("proteins.200MB") ("sources.200MB") ("random1.50MB");
+ boost::for_each(benchmark_files, arg1 = benchmark_path + "/" + arg1);
+
+ unit_test();
+
+ //Category 1: The text
+ // Test 1: Against long nonmatching substring
+ // Test 2: Against almost matching substrings (differing in ending only)
+ // Test 3: Against almost matching substrings (differing in beginning only)
+ // Test 4: Against matching substrings
+ // Test 5: Against the most frequent character
+ bool substr_change = false;
+ try {
+ //!\todo move back to starting at step 1
+ for (unsigned int test = 1; test <= 5; ++test)
+ {
+
+ BOOST_FOREACH(std::string fn, benchmark_files)
+ {
+ try {
+ b.clear();
+ if (test == 1) { substr = rand_str(10000); b.set_substring(&substr); }
+ } catch (std::exception const &e) { BOOST_THROW_EXCEPTION(e); }
+
+ std::cout << "Test " << test << " (" << fn << "):" << std::endl;
+
+ std::ifstream bf(fn, std::ios::binary);
+ if (!bf) { std::cerr << "Error opening " << fn << std::endl; return -1; }
+
+ std::vector<char> buf(1<<20);
+ while (bf.read(&buf[0], mrand(1000,1000000)))
+ {
+ //Note: Only reading the first 10MB of the file!!
+ if (bf.tellg() > 10*1024*1024) break;
+
+ try {
+ assert(bf.gcount() <= buf.size());
+ str.assign(buf.begin(), buf.begin()+static_cast<std::size_t>(bf.gcount()));
+ } catch (std::exception const &e) { BOOST_THROW_EXCEPTION(e); }
+
+ substr_change = false;
+ try {
+ switch (test)
+ {
+ case 1:
+ break;
+ case 2:
+ substr = rand_obfuscate_end(rand_substr(str));
+ substr_change = true;
+ break;
+ case 3:
+ substr = rand_obfuscate_beginning(rand_substr(str));
+ substr_change = true;
+ break;
+ case 4:
+ substr = rand_substr(str);
+ substr_change = true;
+ break;
+ case 5:
+ substr = find_most_frequent(str);
+ substr_change = true;
+ break;
+ }
+ } catch (std::exception const &e) { BOOST_THROW_EXCEPTION(e); }
+ try {
+ if (substr_change) b.set_substring(&substr);
+ b.set_string(&str);
+ } catch (std::exception const &e) { BOOST_THROW_EXCEPTION(e); }
+ while (boost::distance(b.find_next()));
+ } // end while (read)
+ b.output_stats(std::cout);
+ } // end foreach file
+ } // end for(test)
+ } // end try
+ catch (boost::exception const &e)
+ {
+ std::cerr << boost::diagnostic_information(e);
+ }
+ catch (std::exception const &e)
+ {
+ std::cerr << boost::diagnostic_information(e);
+ }
+ return 0;
+}
Modified: sandbox/SOC/2010/stringalgos/libs/algorithm/string/example/finder_example.cpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/libs/algorithm/string/example/finder_example.cpp (original)
+++ sandbox/SOC/2010/stringalgos/libs/algorithm/string/example/finder_example.cpp 2010-07-23 08:18:12 EDT (Fri, 23 Jul 2010)
@@ -67,9 +67,9 @@
// then makes it uppercase
// Changes have occured in the internal copy of the string from the outside, the finder
- // has no way of knowing. Call refresh() in order for the finder to perform any computation
- // required on the modified string
- f2.refresh();
+ // has no way of knowing. Call use_internal_string() in order for the finder to
+ // obtain a new range from its internal string
+ f2.use_internal_string();
//turns all occurences of letter e into uppercase
f2.set_substring(L"e");
@@ -79,7 +79,8 @@
boost::to_upper(range);
}
- //display the internal copy of the text
+ //display the internal copy of the text, after updating the internal range
+ f2.use_internal_string();
boost::copy(f2.get_string_range(), std::ostream_iterator<wchar_t,wchar_t>(std::wcout));
std::wcout << std::endl;
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-07-23 08:18:12 EDT (Fri, 23 Jul 2010)
@@ -244,7 +244,7 @@
# endif
////////////////////////////////////////////////////
- //Testing correctness of various input data on the algorithm and refresh()
+ //Testing correctness of various input data on the algorithm
////////////////////////////////////////////////////
//f2.set_substring(
@@ -607,6 +607,7 @@
boost::algorithm::boyer_moore,
boost::algorithm::suffix_array_search
> algorithm_list;
+
boost::unit_test::framework::master_test_suite().add(
BOOST_TEST_CASE_TEMPLATE(test_finders, algorithm_list)
);