|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r64835 - 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/test
From: mstefanro_at_[hidden]
Date: 2010-08-15 15:25:44
Author: mstefanro
Date: 2010-08-15 15:25:38 EDT (Sun, 15 Aug 2010)
New Revision: 64835
URL: http://svn.boost.org/trac/boost/changeset/64835
Log:
[GSoC2010][StringAlgo] Refactoring, documenting etc.
Added:
sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/detail/generated_finders.hpp
- copied unchanged from r64808, /sandbox/SOC/2010/stringalgos/boost/algorithm/string/detail/finder.hpp
sandbox/SOC/2010/stringalgos/libs/algorithm/string/benchmark/Jamfile (contents, props changed)
Removed:
sandbox/SOC/2010/stringalgos/boost/algorithm/string/detail/finder.hpp
Text files modified:
sandbox/SOC/2010/stringalgos/boost/algorithm/string/benchmark_finder.hpp | 102 ++++++++---------
sandbox/SOC/2010/stringalgos/boost/algorithm/string/case_conv.hpp | 12 +-
sandbox/SOC/2010/stringalgos/boost/algorithm/string/config.hpp | 2
sandbox/SOC/2010/stringalgos/boost/algorithm/string/detail/classification.hpp | 2
sandbox/SOC/2010/stringalgos/boost/algorithm/string/find.hpp | 224 +++++++++++++++++++++++++++----------
sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder.hpp | 40 ------
sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/default_search_algorithm.hpp | 15 ++
sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/detail/finder_typedefs.hpp | 10 +
sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/detail/is_pointer_to.hpp | 10 +
sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/detail/string_search_ranges.hpp | 10 +
sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/finder.hpp | 83 ++++++++-----
sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/finder_generators.hpp | 36 ++++-
sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/generated_finders.hpp | 231 +++++++++++++++++++++++++++++----------
sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/simplified_finder.hpp | 62 +++++++---
sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder_aliases.hpp | 44 +++++++
sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search.hpp | 12 +
sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/boyer_moore.hpp | 70 ++++++-----
sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/detail/rabin_karp.hpp | 46 ++++---
sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/knuth_morris_pratt.hpp | 14 +
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 | 12 +
sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/suffix_array.hpp | 36 +++--
sandbox/SOC/2010/stringalgos/libs/algorithm/string/benchmark/string_search.cpp | 7
sandbox/SOC/2010/stringalgos/libs/algorithm/string/test/finder_test.cpp | 17 +-
24 files changed, 738 insertions(+), 377 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-15 15:25:38 EDT (Sun, 15 Aug 2010)
@@ -1,32 +1,26 @@
+// Boost string_algo library benchmark_finder.hpp header file ---------------------------//
+
+// Copyright Stefan Mihaila 2010
+//
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+// See http://www.boost.org/ for updates, documentation, and revision history.
+
#ifndef BOOST_STRING_BENCHMARK_FINDER_HPP
#define BOOST_STRING_BENCHMARK_FINDER_HPP
+#include <boost/config.hpp>
-//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. " \
- "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/config.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/algorithm/string/compare.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>
@@ -42,7 +36,6 @@
#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>
@@ -50,6 +43,8 @@
//\todo pretty messy, Boost.Chrono?
#ifdef BOOST_WINDOWS
#include <windows.h>
+#else
+#include <boost/timer.hpp>
#endif
#include <deque>
@@ -62,11 +57,10 @@
#include <boost/throw_exception.hpp>
-//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.
+Defines a generic finder type with an iterface similar to that of \ref simplified_finder_t.
+This finder type is useful for comparing the performance of various string search algorithms.
*/
namespace boost { namespace algorithm {
@@ -79,20 +73,19 @@
\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 = boost::algorithm::is_equal>
- class benchmark_finder /*:
- public boost::algorithm::detail::finder_typedefs<Range1T, Range2T,
- ComparatorT, std::allocator<std::size_t> >*/
- {
- typedef std::allocator<std::size_t> allocator_type_;
- public:
- BOOST_ALGORITHM_DETAIL_FINDER_TYPEDEFS(Range1T,Range2T);
- BOOST_ALGORITHM_DETAIL_FINDER_TYPEDEFS2(ComparatorT, allocator_type_);
- public:
+ */
+ template <class Range1T, class Range2T, class AlgorithmSequenceT,
+ class ComparatorT = boost::algorithm::is_equal>
+ class benchmark_finder
+ {
+ typedef std::allocator<std::size_t> allocator_type_;
+ public:
+ BOOST_ALGORITHM_DETAIL_FINDER_TYPEDEFS(Range1T,Range2T);
+ BOOST_ALGORITHM_DETAIL_FINDER_TYPEDEFS2(ComparatorT, allocator_type_);
+ public:
- //! See \ref simplified_finder_t::set_substring
+ //! \copydoc simplified_finder_t::set_substring
+ //! \see \ref simplified_finder_t::set_substring
void set_substring (substring_type
const *const substring)
{
@@ -103,7 +96,8 @@
trusted_finder.set_substring(substring);
}
- //! See \ref simplified_finder_t::set_string
+ //! \copydoc simplified_finder_t::set_string
+ //! \see \ref simplified_finder_t::set_string
void set_string (string_type *const string)
{
boost::phoenix::function<finder_set_string> f;
@@ -118,27 +112,30 @@
void clear ()
{ boost::fusion::for_each(finders, clear_stats()); }
- //! See \ref simplified_finder_t::find_reset
+ //! \copydoc simplified_finder_t::find_reset
+ //! \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
+ //! \copydoc simplified_finder_t::find_next
+ //! \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());
}
+ //! \copydoc simplified_finder_t::find_first
//! See \ref simplified_finder_t::find_first
string_range_type find_first()
{ find_reset(); return find_next(); }
//! Output the benchmark data to a stream
/*!
- \param output The stream to which the benchmark results are to be outputted
+ \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> &output)
@@ -147,20 +144,17 @@
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
- typedef typename boost::mpl::transform<AlgorithmSequenceT,
+ typedef BOOST_STRING_TYPENAME boost::mpl::transform<AlgorithmSequenceT,
std::pair<
- typename boost::algorithm::simplified_finder_t<substring_type,string_type,
+ BOOST_STRING_TYPENAME boost::algorithm::simplified_finder_t<substring_type,string_type,
boost::mpl::_, ComparatorT>,
std::deque<double>
>
>::type finders_sequence;
- typename boost::simplified_finder_t<substring_type, string_type, boost::naive_search,
+ BOOST_STRING_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;
+ BOOST_STRING_TYPENAME boost::fusion::result_of::as_vector< finders_sequence >::type finders;
struct finder_set_substring
{
@@ -231,12 +225,12 @@
std::ostringstream ss;
ss << "Match failed on " << finder.first.get_algorithm_name()
- << " with:\n\tstr["<<boost::distance(finder.first.get_string_range())
- << "]=";
+ << " 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()) );
@@ -278,10 +272,10 @@
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";
+ << "Max : " << max << "\n"
+ << "Avg : " << avg << "\n"
+ << "Stddev: " << stddev << "\n"
+ << "Smples: " << size << "\n";
os << "==========================================" << std::endl;
}
};
Modified: sandbox/SOC/2010/stringalgos/boost/algorithm/string/case_conv.hpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/boost/algorithm/string/case_conv.hpp (original)
+++ sandbox/SOC/2010/stringalgos/boost/algorithm/string/case_conv.hpp 2010-08-15 15:25:38 EDT (Sun, 15 Aug 2010)
@@ -61,7 +61,7 @@
Output,
::boost::as_literal(Input),
::boost::algorithm::detail::to_lowerF<
- typename range_value<RangeT>::type >(Loc));
+ BOOST_STRING_TYPENAME range_value<RangeT>::type >(Loc));
}
//! Convert to lower case
@@ -76,7 +76,7 @@
return ::boost::algorithm::detail::transform_range_copy<SequenceT>(
Input,
::boost::algorithm::detail::to_lowerF<
- typename range_value<SequenceT>::type >(Loc));
+ BOOST_STRING_TYPENAME range_value<SequenceT>::type >(Loc));
}
//! Convert to lower case
@@ -95,7 +95,7 @@
::boost::algorithm::detail::transform_range(
::boost::as_literal(Input),
::boost::algorithm::detail::to_lowerF<
- typename range_value<WritableRangeT>::type >(Loc));
+ BOOST_STRING_TYPENAME range_value<WritableRangeT>::type >(Loc));
}
// to_upper -----------------------------------------------//
@@ -126,7 +126,7 @@
Output,
::boost::as_literal(Input),
::boost::algorithm::detail::to_upperF<
- typename range_value<RangeT>::type >(Loc));
+ BOOST_STRING_TYPENAME range_value<RangeT>::type >(Loc));
}
//! Convert to upper case
@@ -141,7 +141,7 @@
return ::boost::algorithm::detail::transform_range_copy<SequenceT>(
Input,
::boost::algorithm::detail::to_upperF<
- typename range_value<SequenceT>::type >(Loc));
+ BOOST_STRING_TYPENAME range_value<SequenceT>::type >(Loc));
}
//! Convert to upper case
@@ -160,7 +160,7 @@
::boost::algorithm::detail::transform_range(
::boost::as_literal(Input),
::boost::algorithm::detail::to_upperF<
- typename range_value<WritableRangeT>::type >(Loc));
+ BOOST_STRING_TYPENAME range_value<WritableRangeT>::type >(Loc));
}
} // namespace algorithm
Modified: sandbox/SOC/2010/stringalgos/boost/algorithm/string/config.hpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/boost/algorithm/string/config.hpp (original)
+++ sandbox/SOC/2010/stringalgos/boost/algorithm/string/config.hpp 2010-08-15 15:25:38 EDT (Sun, 15 Aug 2010)
@@ -20,7 +20,7 @@
#define BOOST_STRING_TYPENAME BOOST_DEDUCED_TYPENAME
-//TODO maybe force inline exists for other compilers? like __inline__ for GCC/ICC?
+//TODO maybe force inline exists for other compilers? like __inline__ or __attribute__((force_inline)) for GCC/ICC?
#ifdef BOOST_MSVC
#define BOOST_STRING_FORCE_INLINE __forceinline
#else
Modified: sandbox/SOC/2010/stringalgos/boost/algorithm/string/detail/classification.hpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/boost/algorithm/string/detail/classification.hpp (original)
+++ sandbox/SOC/2010/stringalgos/boost/algorithm/string/detail/classification.hpp 2010-08-15 15:25:38 EDT (Sun, 15 Aug 2010)
@@ -69,7 +69,7 @@
{
private:
// set cannot operate on const value-type
- typedef typename ::boost::remove_const<CharT>::type set_value_type;
+ typedef BOOST_STRING_TYPENAME ::boost::remove_const<CharT>::type set_value_type;
public:
// Boost.ResultOf support
Deleted: sandbox/SOC/2010/stringalgos/boost/algorithm/string/detail/finder.hpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/boost/algorithm/string/detail/finder.hpp 2010-08-15 15:25:38 EDT (Sun, 15 Aug 2010)
+++ (empty file)
@@ -1,651 +0,0 @@
-// Boost string_algo library finder.hpp header file ---------------------------//
-
-// Copyright Pavol Droba 2002-2006.
-//
-// Distributed under the Boost Software License, Version 1.0.
-// (See accompanying file LICENSE_1_0.txt or copy at
-// http://www.boost.org/LICENSE_1_0.txt)
-
-// See http://www.boost.org/ for updates, documentation, and revision history.
-
-#ifndef BOOST_STRING_FINDER_DETAIL_HPP
-#define BOOST_STRING_FINDER_DETAIL_HPP
-
-#include <boost/algorithm/string/config.hpp>
-#include <boost/algorithm/string/constants.hpp>
-#include <boost/detail/iterator.hpp>
-
-#include <boost/range/iterator_range.hpp>
-#include <boost/range/begin.hpp>
-#include <boost/range/end.hpp>
-#include <boost/range/empty.hpp>
-#include <boost/range/as_literal.hpp>
-#include <boost/range/category.hpp>
-
-#include <boost/type_traits/remove_cv.hpp>
-
-#include <iterator>
-
-
-namespace boost { namespace algorithm { namespace detail {
-
-
-
-// find first functor -----------------------------------------------//
-
- // find a subsequence in the sequence ( functor )
- /*
- Returns a pair <begin,end> marking the subsequence in the sequence.
- If the find fails, functor returns <End,End>
- */
- template<typename SearchIteratorT,typename PredicateT>
- struct first_finderF
- {
- typedef SearchIteratorT search_iterator_type;
-
- // Construction
- template< typename SearchT >
- first_finderF( const SearchT& Search, PredicateT Comp ) :
- m_Search(::boost::begin(Search), ::boost::end(Search)), m_Comp(Comp) {}
- first_finderF(
- search_iterator_type SearchBegin,
- search_iterator_type SearchEnd,
- PredicateT Comp ) :
- m_Search(SearchBegin, SearchEnd), m_Comp(Comp) {}
-
- // Operation
- template< typename ForwardIteratorT >
- iterator_range<ForwardIteratorT>
- operator()(
- ForwardIteratorT Begin,
- ForwardIteratorT End ) const
- {
- typedef iterator_range<ForwardIteratorT> result_type;
- typedef ForwardIteratorT input_iterator_type;
-
- // Outer loop
- for(input_iterator_type OuterIt=Begin;
- OuterIt!=End;
- ++OuterIt)
- {
- // Sanity check
- if( boost::empty(m_Search) )
- return result_type( End, End );
-
- input_iterator_type InnerIt=OuterIt;
- search_iterator_type SubstrIt=m_Search.begin();
- for(;
- InnerIt!=End && SubstrIt!=m_Search.end();
- ++InnerIt,++SubstrIt)
- {
- if( !( m_Comp(*InnerIt,*SubstrIt) ) )
- break;
- }
-
- // Substring matching succeeded
- if ( SubstrIt==m_Search.end() )
- return result_type( OuterIt, InnerIt );
- }
-
- return result_type( End, End );
- }
-
- private:
- iterator_range<search_iterator_type> m_Search;
- PredicateT m_Comp;
- };
-
-// find last functor -----------------------------------------------//
-
- // find the last match a subseqeunce in the sequence ( functor )
- /*
- Returns a pair <begin,end> marking the subsequence in the sequence.
- If the find fails, returns <End,End>
- */
- template<typename SearchIteratorT, typename PredicateT>
- struct last_finderF
- {
- typedef SearchIteratorT search_iterator_type;
- typedef first_finderF<
- search_iterator_type,
- PredicateT> first_finder_type;
-
- // Construction
- template< typename SearchT >
- last_finderF( const SearchT& Search, PredicateT Comp ) :
- m_Search(::boost::begin(Search), ::boost::end(Search)), m_Comp(Comp) {}
- last_finderF(
- search_iterator_type SearchBegin,
- search_iterator_type SearchEnd,
- PredicateT Comp ) :
- m_Search(SearchBegin, SearchEnd), m_Comp(Comp) {}
-
- // Operation
- template< typename ForwardIteratorT >
- iterator_range<ForwardIteratorT>
- operator()(
- ForwardIteratorT Begin,
- ForwardIteratorT End ) const
- {
- typedef iterator_range<ForwardIteratorT> result_type;
-
- if( boost::empty(m_Search) )
- return result_type( End, End );
-
- typedef BOOST_STRING_TYPENAME boost::detail::
- iterator_traits<ForwardIteratorT>::iterator_category category;
-
- return findit( Begin, End, category() );
- }
-
- private:
- // forward iterator
- template< typename ForwardIteratorT >
- iterator_range<ForwardIteratorT>
- findit(
- ForwardIteratorT Begin,
- ForwardIteratorT End,
- std::forward_iterator_tag ) const
- {
- typedef ForwardIteratorT input_iterator_type;
- typedef iterator_range<ForwardIteratorT> result_type;
-
- first_finder_type first_finder(
- m_Search.begin(), m_Search.end(), m_Comp );
-
- result_type M=first_finder( Begin, End );
- result_type Last=M;
-
- while( M )
- {
- Last=M;
- M=first_finder( ::boost::end(M), End );
- }
-
- return Last;
- }
-
- // bidirectional iterator
- template< typename ForwardIteratorT >
- iterator_range<ForwardIteratorT>
- findit(
- ForwardIteratorT Begin,
- ForwardIteratorT End,
- std::bidirectional_iterator_tag ) const
- {
- typedef iterator_range<ForwardIteratorT> result_type;
- typedef ForwardIteratorT input_iterator_type;
-
- // Outer loop
- for(input_iterator_type OuterIt=End;
- OuterIt!=Begin; )
- {
- input_iterator_type OuterIt2=--OuterIt;
-
- input_iterator_type InnerIt=OuterIt2;
- search_iterator_type SubstrIt=m_Search.begin();
- for(;
- InnerIt!=End && SubstrIt!=m_Search.end();
- ++InnerIt,++SubstrIt)
- {
- if( !( m_Comp(*InnerIt,*SubstrIt) ) )
- break;
- }
-
- // Substring matching succeeded
- if( SubstrIt==m_Search.end() )
- return result_type( OuterIt2, InnerIt );
- }
-
- return result_type( End, End );
- }
-
- private:
- iterator_range<search_iterator_type> m_Search;
- PredicateT m_Comp;
- };
-
-// find n-th functor -----------------------------------------------//
-
- // find the n-th match of a subsequence in the sequence ( functor )
- /*
- Returns a pair <begin,end> marking the subsequence in the sequence.
- If the find fails, returns <End,End>
- */
- template<typename SearchIteratorT, typename PredicateT>
- struct nth_finderF
- {
- typedef SearchIteratorT search_iterator_type;
- typedef first_finderF<
- search_iterator_type,
- PredicateT> first_finder_type;
- typedef last_finderF<
- search_iterator_type,
- PredicateT> last_finder_type;
-
- // Construction
- template< typename SearchT >
- nth_finderF(
- const SearchT& Search,
- int Nth,
- PredicateT Comp) :
- m_Search(::boost::begin(Search), ::boost::end(Search)),
- m_Nth(Nth),
- m_Comp(Comp) {}
- nth_finderF(
- search_iterator_type SearchBegin,
- search_iterator_type SearchEnd,
- int Nth,
- PredicateT Comp) :
- m_Search(SearchBegin, SearchEnd),
- m_Nth(Nth),
- m_Comp(Comp) {}
-
- // Operation
- template< typename ForwardIteratorT >
- iterator_range<ForwardIteratorT>
- operator()(
- ForwardIteratorT Begin,
- ForwardIteratorT End ) const
- {
- if(m_Nth>=0)
- {
- return find_forward(Begin, End, m_Nth);
- }
- else
- {
- return find_backward(Begin, End, -m_Nth);
- }
-
- }
-
- private:
- // Implementation helpers
- template< typename ForwardIteratorT >
- iterator_range<ForwardIteratorT>
- find_forward(
- ForwardIteratorT Begin,
- ForwardIteratorT End,
- unsigned int N) const
- {
- typedef ForwardIteratorT input_iterator_type;
- typedef iterator_range<ForwardIteratorT> result_type;
-
- // Sanity check
- if( boost::empty(m_Search) )
- return result_type( End, End );
-
- // Instantiate find functor
- first_finder_type first_finder(
- m_Search.begin(), m_Search.end(), m_Comp );
-
- result_type M( Begin, Begin );
-
- for( unsigned int n=0; n<=N; ++n )
- {
- // find next match
- M=first_finder( ::boost::end(M), End );
-
- if ( !M )
- {
- // Subsequence not found, return
- return M;
- }
- }
-
- return M;
- }
-
- template< typename ForwardIteratorT >
- iterator_range<ForwardIteratorT>
- find_backward(
- ForwardIteratorT Begin,
- ForwardIteratorT End,
- unsigned int N) const
- {
- typedef ForwardIteratorT input_iterator_type;
- typedef iterator_range<ForwardIteratorT> result_type;
-
- // Sanity check
- if( boost::empty(m_Search) )
- return result_type( End, End );
-
- // Instantiate find functor
- last_finder_type last_finder(
- m_Search.begin(), m_Search.end(), m_Comp );
-
- result_type M( End, End );
-
- for( unsigned int n=1; n<=N; ++n )
- {
- // find next match
- M=last_finder( Begin, ::boost::begin(M) );
-
- if ( !M )
- {
- // Subsequence not found, return
- return M;
- }
- }
-
- return M;
- }
-
-
- private:
- iterator_range<search_iterator_type> m_Search;
- int m_Nth;
- PredicateT m_Comp;
- };
-
-// find head/tail implementation helpers ---------------------------//
-
- template<typename ForwardIteratorT>
- iterator_range<ForwardIteratorT>
- find_head_impl(
- ForwardIteratorT Begin,
- ForwardIteratorT End,
- unsigned int N,
- std::forward_iterator_tag )
- {
- typedef ForwardIteratorT input_iterator_type;
- typedef iterator_range<ForwardIteratorT> result_type;
-
- input_iterator_type It=Begin;
- for(
- unsigned int Index=0;
- Index<N && It!=End; ++Index,++It ) {};
-
- return result_type( Begin, It );
- }
-
- template< typename ForwardIteratorT >
- iterator_range<ForwardIteratorT>
- find_head_impl(
- ForwardIteratorT Begin,
- ForwardIteratorT End,
- unsigned int N,
- std::random_access_iterator_tag )
- {
- typedef ForwardIteratorT input_iterator_type;
- typedef iterator_range<ForwardIteratorT> result_type;
-
- if ( (End<=Begin) || ( static_cast<unsigned int>(End-Begin) < N ) )
- return result_type( Begin, End );
-
- return result_type(Begin,Begin+N);
- }
-
- // Find head implementation
- template<typename ForwardIteratorT>
- iterator_range<ForwardIteratorT>
- find_head_impl(
- ForwardIteratorT Begin,
- ForwardIteratorT End,
- unsigned int N )
- {
- typedef BOOST_STRING_TYPENAME boost::detail::
- iterator_traits<ForwardIteratorT>::iterator_category category;
-
- return ::boost::algorithm::detail::find_head_impl( Begin, End, N, category() );
- }
-
- template< typename ForwardIteratorT >
- iterator_range<ForwardIteratorT>
- find_tail_impl(
- ForwardIteratorT Begin,
- ForwardIteratorT End,
- unsigned int N,
- std::forward_iterator_tag )
- {
- typedef ForwardIteratorT input_iterator_type;
- typedef iterator_range<ForwardIteratorT> result_type;
-
- unsigned int Index=0;
- input_iterator_type It=Begin;
- input_iterator_type It2=Begin;
-
- // Advance It2 by N increments
- for( Index=0; Index<N && It2!=End; ++Index,++It2 ) {};
-
- // Advance It, It2 to the end
- for(; It2!=End; ++It,++It2 ) {};
-
- return result_type( It, It2 );
- }
-
- template< typename ForwardIteratorT >
- iterator_range<ForwardIteratorT>
- find_tail_impl(
- ForwardIteratorT Begin,
- ForwardIteratorT End,
- unsigned int N,
- std::bidirectional_iterator_tag )
- {
- typedef ForwardIteratorT input_iterator_type;
- typedef iterator_range<ForwardIteratorT> result_type;
-
- input_iterator_type It=End;
- for(
- unsigned int Index=0;
- Index<N && It!=Begin; ++Index,--It ) {};
-
- return result_type( It, End );
- }
-
- template< typename ForwardIteratorT >
- iterator_range<ForwardIteratorT>
- find_tail_impl(
- ForwardIteratorT Begin,
- ForwardIteratorT End,
- unsigned int N,
- std::random_access_iterator_tag )
- {
- typedef ForwardIteratorT input_iterator_type;
- typedef iterator_range<ForwardIteratorT> result_type;
-
- if ( (End<=Begin) || ( static_cast<unsigned int>(End-Begin) < N ) )
- return result_type( Begin, End );
-
- return result_type( End-N, End );
- }
-
- // Operation
- template< typename ForwardIteratorT >
- iterator_range<ForwardIteratorT>
- find_tail_impl(
- ForwardIteratorT Begin,
- ForwardIteratorT End,
- unsigned int N )
- {
- typedef BOOST_STRING_TYPENAME boost::detail::
- iterator_traits<ForwardIteratorT>::iterator_category category;
-
- return ::boost::algorithm::detail::find_tail_impl( Begin, End, N, category() );
- }
-
-
-
-// find head functor -----------------------------------------------//
-
-
- // find a head in the sequence ( functor )
- /*
- This functor find a head of the specified range. For
- a specified N, the head is a subsequence of N starting
- elements of the range.
- */
- struct head_finderF
- {
- // Construction
- head_finderF( int N ) : m_N(N) {}
-
- // Operation
- template< typename ForwardIteratorT >
- iterator_range<ForwardIteratorT>
- operator()(
- ForwardIteratorT Begin,
- ForwardIteratorT End ) const
- {
- if(m_N>=0)
- {
- return ::boost::algorithm::detail::find_head_impl( Begin, End, m_N );
- }
- else
- {
- iterator_range<ForwardIteratorT> Res=
- ::boost::algorithm::detail::find_tail_impl( Begin, End, -m_N );
-
- return ::boost::make_iterator_range(Begin, Res.begin());
- }
- }
-
- private:
- int m_N;
- };
-
-// find tail functor -----------------------------------------------//
-
-
- // find a tail in the sequence ( functor )
- /*
- This functor find a tail of the specified range. For
- a specified N, the head is a subsequence of N starting
- elements of the range.
- */
- struct tail_finderF
- {
- // Construction
- tail_finderF( int N ) : m_N(N) {}
-
- // Operation
- template< typename ForwardIteratorT >
- iterator_range<ForwardIteratorT>
- operator()(
- ForwardIteratorT Begin,
- ForwardIteratorT End ) const
- {
- if(m_N>=0)
- {
- return ::boost::algorithm::detail::find_tail_impl( Begin, End, m_N );
- }
- else
- {
- iterator_range<ForwardIteratorT> Res=
- ::boost::algorithm::detail::find_head_impl( Begin, End, -m_N );
-
- return ::boost::make_iterator_range(Res.end(), End);
- }
- }
-
- private:
- int m_N;
- };
-
-// find token functor -----------------------------------------------//
-
- // find a token in a sequence ( functor )
- /*
- This find functor finds a token specified be a predicate
- in a sequence. It is equivalent of std::find algorithm,
- with an exception that it return range instead of a single
- iterator.
-
- If bCompress is set to true, adjacent matching tokens are
- concatenated into one match.
- */
- template< typename PredicateT >
- struct token_finderF
- {
- // Construction
- token_finderF(
- PredicateT Pred,
- token_compress_mode_type eCompress=token_compress_off ) :
- m_Pred(Pred), m_eCompress(eCompress) {}
-
- // Operation
- template< typename ForwardIteratorT >
- iterator_range<ForwardIteratorT>
- operator()(
- ForwardIteratorT Begin,
- ForwardIteratorT End ) const
- {
- typedef iterator_range<ForwardIteratorT> result_type;
-
- ForwardIteratorT It=std::find_if( Begin, End, m_Pred );
-
- if( It==End )
- {
- return result_type( End, End );
- }
- else
- {
- ForwardIteratorT It2=It;
-
- if( m_eCompress==token_compress_on )
- {
- // Find first non-matching character
- while( It2!=End && m_Pred(*It2) ) ++It2;
- }
- else
- {
- // Advance by one position
- ++It2;
- }
-
- return result_type( It, It2 );
- }
- }
-
- private:
- PredicateT m_Pred;
- token_compress_mode_type m_eCompress;
- };
-
-// find range functor -----------------------------------------------//
-
- // find a range in the sequence ( functor )
- /*
- This functor actually does not perform any find operation.
- It always returns given iterator range as a result.
- */
- template<typename ForwardIterator1T>
- struct range_finderF
- {
- typedef ForwardIterator1T input_iterator_type;
- typedef iterator_range<input_iterator_type> result_type;
-
- // Construction
- range_finderF(
- input_iterator_type Begin,
- input_iterator_type End ) : m_Range(Begin, End) {}
-
- range_finderF(const iterator_range<input_iterator_type>& Range) :
- m_Range(Range) {}
-
- // Operation
- template< typename ForwardIterator2T >
- iterator_range<ForwardIterator2T>
- operator()(
- ForwardIterator2T,
- ForwardIterator2T ) const
- {
-#if BOOST_WORKAROUND( __MWERKS__, <= 0x3003 )
- return iterator_range<const ForwardIterator2T>(this->m_Range);
-#elif BOOST_WORKAROUND(BOOST_MSVC, <= 1300)
- return iterator_range<ForwardIterator2T>(m_Range.begin(), m_Range.end());
-#else
- return m_Range;
-#endif
- }
-
- private:
- iterator_range<input_iterator_type> m_Range;
- };
-
-
- } // namespace detail
- } // namespace algorithm
-} // namespace boost
-
-#endif // BOOST_STRING_FINDER_DETAIL_HPP
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-15 15:25:38 EDT (Sun, 15 Aug 2010)
@@ -1,6 +1,7 @@
// Boost string_algo library find.hpp header file ---------------------------//
// Copyright Pavol Droba 2002-2003.
+// Copyright Stefan Mihaila 2010.
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
@@ -8,9 +9,12 @@
// See http://www.boost.org/ for updates, documentation, and revision history.
+
#ifndef BOOST_STRING_FIND_HPP
#define BOOST_STRING_FIND_HPP
+#include <boost/config.hpp>
+
#include <boost/algorithm/string/config.hpp>
#include <boost/range/iterator_range.hpp>
@@ -31,7 +35,6 @@
delimiting the substring.
*/
-//todo update doc here
namespace boost {
namespace algorithm {
@@ -44,9 +47,7 @@
\param Input A string which will be searched.
\param Finder Finder object used for searching.
- \return
- An \c iterator_range delimiting the match.
- Returned iterator is either \c RangeT::iterator or
+ \return An \c iterator_range delimiting the match. Returned iterator is either \c RangeT::iterator or
\c RangeT::const_iterator, depending on the constness of
the input parameter.
\deprecated
@@ -56,7 +57,31 @@
BOOST_STRING_TYPENAME range_iterator<RangeT>::type>
find(
RangeT& Input,
- FinderT& Finder)
+ FinderT const &Finder)
+ {
+ FinderT Finder_(Finder); // unfortunately, copying the finder is currently the only workaround for this situation
+ iterator_range<BOOST_STRING_TYPENAME range_iterator<RangeT>::type> lit_input(
+ ::boost::as_literal(Input));
+ return Finder_(::boost::begin(lit_input), ::boost::end(lit_input));
+ }
+
+ //! Generic find algorithm
+ /*!
+ Search the input using the given finder.
+
+ \param Input A string which will be searched.
+ \param Finder Finder object used for searching.
+ \return An \c iterator_range delimiting the match. Returned iterator is either \c RangeT::iterator or
+ \c RangeT::const_iterator, depending on the constness of
+ the input parameter.
+ \deprecated
+ */
+ template<typename RangeT, typename FinderT>
+ inline iterator_range<
+ BOOST_STRING_TYPENAME range_iterator<RangeT>::type>
+ find(
+ RangeT& Input,
+ FinderT &Finder)
{
iterator_range<BOOST_STRING_TYPENAME range_iterator<RangeT>::type> lit_input(
@@ -66,17 +91,16 @@
// find_first -----------------------------------------------//
- //! Find first algorithm (not deprecated)
+ //! Find first algorithm
/*!
Search for the first occurrence of the substring in the input.
\param Input A string which will be searched.
\param Search A substring to be searched for.
- \return
- An \c iterator_range delimiting the match.
- Returned iterator is either \c RangeT::iterator or
- \c RangeT::const_iterator, depending on the constness of
- the input parameter.
+ \param Algorithm A tag representing the search algorithm to be used.
+ \return An \c iterator_range delimiting the match. Returned iterator is either \c Range1T::iterator or
+ \c Range1T::const_iterator, depending on the constness of
+ the input parameter.
\note This function provides the strong exception-safety guarantee
*/
@@ -86,17 +110,27 @@
find_first(
Range1T& Input,
const Range2T& Search,
- AlgorithmTagT const &algorithm)
+ AlgorithmTagT const &Algorithm)
{
//we want to generate finders taking const ranges for text (thus the const Range1T)
//this only allows the finder to return matches as const ranges,
//but find() can convert those to mutable ranges if they are provided by the user
- return ::boost::algorithm::find(Input,
- ::boost::algorithm::first_finder_t<Range2T,
- typename AlgorithmTagT::type,::boost::algorithm::is_equal>(&Search)
- );
+ ::boost::algorithm::first_finder_t<Range2T,
+ BOOST_STRING_TYPENAME AlgorithmTagT::type,::boost::algorithm::is_equal> Finder(&Search);
+ return ::boost::algorithm::find(Input, Finder);
}
+ /*!
+ Search for the first occurrence of the substring in the input.
+
+ \param Input A string which will be searched.
+ \param Search A substring to be searched for.
+ \return An \c iterator_range delimiting the match. Returned iterator is either \c Range1T::iterator or
+ \c Range1T::const_iterator, depending on the constness of
+ the input parameter.
+
+ \note This function provides the strong exception-safety guarantee
+ */
template<typename Range1T, typename Range2T>
inline iterator_range<
BOOST_STRING_TYPENAME range_iterator<Range1T>::type>
@@ -110,11 +144,12 @@
//! Find first algorithm ( case insensitive )
/*!
- Search for the first occurence of the substring in the input.
+ Search for the first occurrence of the substring in the input.
Searching is case insensitive.
\param Input A string which will be searched.
\param Search A substring to be searched for.
+ \param Algorithm A tag representing the search algorithm to be used.
\param Loc A locale used for case insensitive comparison
\return
An \c iterator_range delimiting the match.
@@ -130,19 +165,31 @@
ifind_first(
Range1T& Input,
const Range2T& Search,
- AlgorithmTagT const &,
+ AlgorithmTagT const &Algorithm,
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();
-
- return ::boost::algorithm::find(Input,
- ::boost::algorithm::first_finder_t<Range2T,
- typename AlgorithmTagT::type,::boost::algorithm::is_iequal>(&Search, ::boost::algorithm::is_iequal(Loc))
- );
+ ::boost::algorithm::first_finder_t<Range2T,
+ BOOST_STRING_TYPENAME AlgorithmTagT::type,::boost::algorithm::is_iequal>
+ Finder(&Search, ::boost::algorithm::is_iequal(Loc));
+ return ::boost::algorithm::find(Input,Finder);
}
+ //! Find first algorithm ( case insensitive )
+ /*!
+ Search for the first occurrence of the substring in the input.
+ Searching is case insensitive.
+
+ \param Input A string which will be searched.
+ \param Search A substring to be searched for.
+ \param Loc A locale used for case insensitive comparison
+ \return
+ An \c iterator_range delimiting the match.
+ Returned iterator is either \c Range1T::iterator or
+ \c Range1T::const_iterator, depending on the constness of
+ the input parameter.
+
+ \note This function provides the strong exception-safety guarantee
+ */
template<typename Range1T, typename Range2T>
inline iterator_range<
BOOST_STRING_TYPENAME range_iterator<Range1T>::type>
@@ -163,6 +210,7 @@
\param Input A string which will be searched.
\param Search A substring to be searched for.
+ \param Algorithm A tag representing the search algorithm to be used.
\return
An \c iterator_range delimiting the match.
Returned iterator is either \c Range1T::iterator or
@@ -177,33 +225,28 @@
find_last(
Range1T& Input,
const Range2T& Search,
- AlgorithmTagT const &)
+ AlgorithmTagT const &Algorithm)
{
- /*
- simplified_finder_t<Range2T, Range1T, typename AlgorithmTagT::type>
- finder(&Search, &Input);
- boost::iterator_range<typename boost::range_iterator<Range1T>::type>
- crt = make_iterator_range(boost::end(Input), boost::end(Input)),
- prev;
- for (;;)
- {
- prev=crt;
- crt=finder.find_next();
- //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,
- typename AlgorithmTagT::type,::boost::algorithm::is_equal>(&Search)
- );
- //return ::boost::algorithm::find(Input, ::boost::algorithm::last_finder(Search));
+ ::boost::algorithm::last_finder_t<Range2T,
+ BOOST_STRING_TYPENAME AlgorithmTagT::type,::boost::algorithm::is_equal> Finder(&Search);
+ return ::boost::algorithm::find(Input, Finder);
}
+
+ //! Find last algorithm
+ /*!
+ Search for the last occurrence of the substring in the input.
+
+ \param Input A string which will be searched.
+ \param Search A substring to be searched for.
+ \return
+ An \c iterator_range delimiting the match.
+ Returned iterator is either \c Range1T::iterator or
+ \c Range1T::const_iterator, depending on the constness of
+ the input parameter.
+
+ \note This function provides the strong exception-safety guarantee
+ */
template<typename Range1T, typename Range2T>
inline iterator_range<
BOOST_STRING_TYPENAME range_iterator<Range1T>::type>
@@ -222,6 +265,7 @@
\param Input A string which will be searched.
\param Search A substring to be searched for.
+ \param Algorithm A tag representing the search algorithm to be used.
\param Loc A locale used for case insensitive comparison
\return
An \c iterator_range delimiting the match.
@@ -237,14 +281,31 @@
ifind_last(
Range1T& Input,
const Range2T& Search,
- AlgorithmTagT const &,
+ AlgorithmTagT const &Algorithm,
const std::locale& Loc=std::locale())
{
- return ::boost::algorithm::find(Input,
- ::boost::algorithm::last_finder_t<Range2T,
- typename AlgorithmTagT::type,::boost::algorithm::is_iequal>(&Search, ::boost::algorithm::is_iequal(Loc)));
+ ::boost::algorithm::last_finder_t<Range2T,
+ BOOST_STRING_TYPENAME AlgorithmTagT::type,::boost::algorithm::is_iequal>
+ Finder(&Search, ::boost::algorithm::is_iequal(Loc));
+ return ::boost::algorithm::find(Input,Finder);
}
+ //! Find last algorithm ( case insensitive )
+ /*!
+ Search for the last match a string in the input.
+ Searching is case insensitive.
+
+ \param Input A string which will be searched.
+ \param Search A substring to be searched for.
+ \param Loc A locale used for case insensitive comparison
+ \return
+ An \c iterator_range delimiting the match.
+ Returned iterator is either \c Range1T::iterator or
+ \c Range1T::const_iterator, depending on the constness of
+ the input parameter.
+
+ \note This function provides the strong exception-safety guarantee
+ */
template<typename Range1T, typename Range2T>
inline iterator_range<
BOOST_STRING_TYPENAME range_iterator<Range1T>::type>
@@ -268,6 +329,7 @@
\param Search A substring to be searched for.
\param Nth An index (zero-indexed) of the match to be found.
For negative N, the matches are counted from the end of string.
+ \param Algorithm A tag representing the search algorithm to be used.
\return
An \c iterator_range delimiting the match.
Returned iterator is either \c Range1T::iterator or
@@ -283,14 +345,29 @@
Range1T& Input,
const Range2T& Search,
int Nth,
- AlgorithmTagT const &)
+ AlgorithmTagT const &Algorithm)
{
- return ::boost::algorithm::find(Input,
- ::boost::algorithm::nth_finder_t<Range2T,
- typename AlgorithmTagT::type, ::boost::algorithm::is_equal>(&Search, ::boost::algorithm::is_equal(), Nth)
- );
+ ::boost::algorithm::nth_finder_t<Range2T,
+ BOOST_STRING_TYPENAME AlgorithmTagT::type, ::boost::algorithm::is_equal>
+ Finder(&Search, Nth, ::boost::algorithm::is_equal());
+ return ::boost::algorithm::find(Input, Finder);
}
+ //! Find n-th algorithm
+ /*!
+ Search for the n-th (zero-indexed) occurrence of the substring in the
+ input.
+
+ \param Input A string which will be searched.
+ \param Search A substring to be searched for.
+ \param Nth An index (zero-indexed) of the match to be found.
+ For negative N, the matches are counted from the end of string.
+ \return
+ An \c iterator_range delimiting the match.
+ Returned iterator is either \c Range1T::iterator or
+ \c Range1T::const_iterator, depending on the constness of
+ the input parameter.
+ */
template<typename Range1T, typename Range2T>
inline iterator_range<
BOOST_STRING_TYPENAME range_iterator<Range1T>::type>
@@ -312,6 +389,7 @@
\param Search A substring to be searched for.
\param Nth An index (zero-indexed) of the match to be found.
For negative N, the matches are counted from the end of string.
+ \param Algorithm A tag representing the search algorithm to be used.
\param Loc A locale used for case insensitive comparison
\return
An \c iterator_range delimiting the match.
@@ -329,14 +407,34 @@
Range1T& Input,
const Range2T &Search,
int Nth,
- AlgorithmTagT const&,
+ AlgorithmTagT const &Algorithm,
const std::locale& Loc=std::locale())
{
- return ::boost::algorithm::find(Input,
- ::boost::algorithm::nth_finder_t<Range2T,
- typename AlgorithmTagT::type, ::boost::algorithm::is_iequal>(&Search, ::boost::algorithm::is_iequal(Loc), Nth));
+ ::boost::algorithm::nth_finder_t<Range2T,
+ BOOST_STRING_TYPENAME AlgorithmTagT::type, ::boost::algorithm::is_iequal>
+ Finder(&Search, Nth, ::boost::algorithm::is_iequal(Loc));
+ return ::boost::algorithm::find(Input, Finder);
}
+ //! Find n-th algorithm ( case insensitive ).
+ /*!
+ Search for the n-th (zero-indexed) occurrence of the substring in the
+ input. Searching is case insensitive.
+
+ \param Input A string which will be searched.
+ \param Search A substring to be searched for.
+ \param Nth An index (zero-indexed) of the match to be found.
+ For negative N, the matches are counted from the end of string.
+ \param Loc A locale used for case insensitive comparison
+ \return
+ An \c iterator_range delimiting the match.
+ Returned iterator is either \c Range1T::iterator or
+ \c Range1T::const_iterator, depending on the constness of
+ the input parameter.
+
+
+ \note This function provides the strong exception-safety guarantee
+ */
template<typename Range1T, typename Range2T>
inline iterator_range<
BOOST_STRING_TYPENAME range_iterator<Range1T>::type>
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-15 15:25:38 EDT (Sun, 15 Aug 2010)
@@ -1,6 +1,7 @@
// Boost string_algo library finder.hpp header file ---------------------------//
// Copyright Pavol Droba 2002-2006.
+// Copyright Stefan Mihaila 2010.
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
@@ -10,7 +11,6 @@
//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
@@ -18,49 +18,17 @@
#include <boost/algorithm/string/config.hpp>
-#include <boost/range/iterator_range.hpp>
-#include <boost/range/begin.hpp>
-#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/call_traits.hpp>
-
-#include <boost/type_traits/is_same.hpp>
-
-#include <boost/utility/enable_if.hpp>
-
-#include <boost/mpl/placeholders.hpp>
-
-#include <cassert>
-#include <iterator>
-#include <vector>
-#include <algorithm>
-
-#include <boost/concept_check.hpp>
-
#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>
#include <boost/algorithm/string/finder/finder_generators.hpp>
-//TODO modify this
/*! \file
- Defines Finder types and Finder generators. Finder object is a functor which is able to
+ Defines Finder types and Finder generators. A Finder is an object which is able to
find a substring matching a specific criteria in the input.
- Finders are used as a pluggable components for replace, find
- and split facilities. This header contains generator functions
- for finders provided in this library.
+ Finders can be used directly, or as pluggable components for replace, find
+ and split facilities.
*/
-//TODO: test if get_internal_string() and get_internal_substring() are fine
-
-
#endif // BOOST_STRING_FINDER_HPP
Modified: sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/default_search_algorithm.hpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/default_search_algorithm.hpp (original)
+++ sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/default_search_algorithm.hpp 2010-08-15 15:25:38 EDT (Sun, 15 Aug 2010)
@@ -1,9 +1,24 @@
+// Boost string_algo library default_search_algorithm.hpp header file ---------------------------//
+
+// Copyright Stefan Mihaila 2010
+//
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+// See http://www.boost.org/ for updates, documentation, and revision history.
+
#ifndef BOOST_ALGORITHM_DEFAULT_SEARCH_ALGORITHM_HPP
#define BOOST_ALGORITHM_DEFAULT_SEARCH_ALGORITHM_HPP
//#include <boost/algorithm/string/string_search/knuth_morris_pratt.hpp>
#include <boost/algorithm/string/string_search/naive_search.hpp>
+/*! \file
+ Defines the string search algorithm that is to be used when the algorithm parameter
+ is omitted in creating a finder.
+ */
+
namespace boost { namespace algorithm {
//! The default search algorithm used by find/replace functions.
typedef boost::algorithm::naive_search default_finder_algorithm;
Modified: sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/detail/finder_typedefs.hpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/detail/finder_typedefs.hpp (original)
+++ sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/detail/finder_typedefs.hpp 2010-08-15 15:25:38 EDT (Sun, 15 Aug 2010)
@@ -1,3 +1,13 @@
+// Boost string_algo library finder_typedefs.hpp header file ---------------------------//
+
+// Copyright Stefan Mihaila 2010.
+//
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+// See http://www.boost.org/ for updates, documentation, and revision history.
+
#ifndef BOOST_ALGORITHM_FINDER_TYPEDEFS_HPP
#define BOOST_ALGORITHM_FINDER_TYPEDEFS_HPP
Modified: sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/detail/is_pointer_to.hpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/detail/is_pointer_to.hpp (original)
+++ sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/detail/is_pointer_to.hpp 2010-08-15 15:25:38 EDT (Sun, 15 Aug 2010)
@@ -1,3 +1,13 @@
+// Boost string_algo library is_pointer_to.hpp header file ---------------------------//
+
+// Copyright Stefan Mihaila 2010.
+//
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+// See http://www.boost.org/ for updates, documentation, and revision history.
+
#ifndef BOOST_ALGORITHM_IS_POINTER_TO_HPP
#define BOOST_ALGORITHM_IS_POINTER_TO_HPP
Modified: sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/detail/string_search_ranges.hpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/detail/string_search_ranges.hpp (original)
+++ sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/detail/string_search_ranges.hpp 2010-08-15 15:25:38 EDT (Sun, 15 Aug 2010)
@@ -1,3 +1,13 @@
+// Boost string_algo library string_search_ranges.hpp header file ---------------------------//
+
+// Copyright Stefan Mihaila 2010.
+//
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+// See http://www.boost.org/ for updates, documentation, and revision history.
+
#ifndef BOOST_ALGORITHM_DETAIL_STRING_SEARCH_RANGES_HPP
#define BOOST_ALGORITHM_DETAIL_STRING_SEARCH_RANGES_HPP
Modified: sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/finder.hpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/finder.hpp (original)
+++ sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/finder.hpp 2010-08-15 15:25:38 EDT (Sun, 15 Aug 2010)
@@ -1,3 +1,13 @@
+// Boost string_algo library finder.hpp header file ---------------------------//
+
+// Copyright Stefan Mihaila 2010.
+//
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+// See http://www.boost.org/ for updates, documentation, and revision history.
+
#ifndef BOOST_ALGORITHM_FINDER_T_HPP
#define BOOST_ALGORITHM_FINDER_T_HPP
@@ -18,8 +28,20 @@
#include <boost/call_traits.hpp>
+#include <boost/algorithm/string/config.hpp>
+#include <boost/algorithm/string/finder/default_search_algorithm.hpp>
#include <boost/algorithm/string/finder/detail/finder_typedefs.hpp>
+/*! \file
+ Defines \ref finder_t, a finder type used for finding occurrences of a pattern in a string.
+ This finder allows passing both references and pointers to strings. The overloads taking references
+ will make an internal copy of the passed string, whereas the pointer overloads will rely on the lifetime
+ of the passed string being longer than that of the finder.
+ If you are not planning on passing temporaries as strings and you can always guarantee on the lifetime of your
+ strings, you might want to use \ref simplified_finder_t instead, which only has the pointer overloads (and
+ cannot possess any internal copies). Likewise, if efficiency is very important, \ref simplified_finder_t is preferred.
+*/
+
namespace boost { namespace algorithm {
@@ -45,16 +67,11 @@
*/
template <
class Sequence1T, class Sequence2T,
- class AlgorithmT,
- typename ComparatorT = ::boost::algorithm::is_equal,
+ class AlgorithmT = ::boost::algorithm::default_finder_algorithm,
+ class 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>*/
- /*public AlgorithmT::template algorithm<
- typename finder_t<Sequence1T, Sequence2T, AlgorithmT, ComparatorT, AllocatorT> >*/
+ class finder_t
{
//TODO:: Maybe write a String concept?
//TODO:: Currently, there's a SGI Sequence Concept implemented by Boost.ConceptCheck,
@@ -66,9 +83,7 @@
BOOST_ALGORITHM_DETAIL_COMMON_FINDER_TYPEDEFS(Sequence1T, Sequence2T);
BOOST_ALGORITHM_DETAIL_FINDER_TYPEDEFS2(ComparatorT, AllocatorT);
private:
- /*typedef typename AlgorithmT::template algorithm<finder_t, Sequence1T,
- Sequence2T, ComparatorT, AllocatorT> algorithm_type;*/
- typedef typename AlgorithmT::template algorithm<substring_char_type, string_char_type,
+ typedef BOOST_STRING_TYPENAME AlgorithmT::template algorithm<substring_char_type, string_char_type,
comparator_type, allocator_type> algorithm_type;
public:
@@ -103,7 +118,7 @@
template <class Range2T>
finder_t (const Sequence1T *const substring, Range2T &string,
ComparatorT const &comparator = ComparatorT(), AllocatorT const &allocator = AllocatorT(),
- typename boost::disable_if<typename ::boost::algorithm::detail::is_pointer_to<Range2T,Sequence2T> >::type* = 0)
+ BOOST_STRING_TYPENAME boost::disable_if<BOOST_STRING_TYPENAME ::boost::algorithm::detail::is_pointer_to<Range2T,Sequence2T> >::type* = 0)
: algorithm_(comparator, allocator), substring_optional_copy_(), string_optional_copy_(), ranges_(),
substring_has_changed_(true)
{
@@ -115,7 +130,7 @@
template <class Range1T>
explicit finder_t (const Range1T &substring, Sequence2T *const string = 0,
ComparatorT const &comparator = ComparatorT(), AllocatorT const &allocator = AllocatorT(),
- typename boost::disable_if<typename ::boost::algorithm::detail::is_pointer_to<Range1T,Sequence1T> >::type* = 0)
+ BOOST_STRING_TYPENAME boost::disable_if<BOOST_STRING_TYPENAME ::boost::algorithm::detail::is_pointer_to<Range1T,Sequence1T> >::type* = 0)
: algorithm_(comparator, allocator),
substring_optional_copy_(), string_optional_copy_(), ranges_(),
string_has_changed_(true)
@@ -128,8 +143,8 @@
template <class Range1T, class Range2T>
finder_t (const Range1T &substring, 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)
+ BOOST_STRING_TYPENAME boost::disable_if<boost::mpl::or_<BOOST_STRING_TYPENAME ::boost::algorithm::detail::is_pointer_to<Range1T,Sequence1T>,
+ BOOST_STRING_TYPENAME ::boost::algorithm::detail::is_pointer_to<Range2T,Sequence2T> > >::type* = 0)
: algorithm_(comparator, allocator),
substring_optional_copy_(), string_optional_copy_(), ranges_()
{
@@ -156,7 +171,7 @@
Sequence1T const &&substring,
Range2T &string,
ComparatorT const &comparator = ComparatorT(), AllocatorT const &allocator = AllocatorT(),
- typename boost::disable_if<typename ::boost::algorithm::detail::is_pointer_to<Range2T,Sequence2T> >::type* = 0)
+ BOOST_STRING_TYPENAME boost::disable_if<BOOST_STRING_TYPENAME ::boost::algorithm::detail::is_pointer_to<Range2T,Sequence2T> >::type* = 0)
: algorithm_(comparator, allocator),
substring_optional_copy_(std::move(substring)),
string_optional_copy_(), ranges_(),
@@ -189,7 +204,7 @@
finder_t (const Range1T &substring,
Sequence2T &&string,
ComparatorT const &comparator = ComparatorT(), AllocatorT const &allocator = AllocatorT(),
- typename boost::disable_if<typename ::boost::algorithm::detail::is_pointer_to<Range1T,Sequence1T> >::type* = 0)
+ BOOST_STRING_TYPENAME boost::disable_if<BOOST_STRING_TYPENAME ::boost::algorithm::detail::is_pointer_to<Range1T,Sequence1T> >::type* = 0)
: algorithm_(comparator, allocator),
substring_optional_copy_(), string_optional_copy_(std::move(string)),
ranges_(), string_has_changed_(true)
@@ -218,21 +233,22 @@
/*
//! Gets a reference to an instance of the comparator in use
- typename boost::call_traits<comparator_type>::const_reference get_comparator() const
+ BOOST_STRING_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()
+ BOOST_STRING_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
+ BOOST_STRING_TYPENAME boost::call_traits<allocator_type>::const_reference get_allocator() const
{ return allocator_; }
*/
+ //! Returns a string indicating the name of the string search algorithm used for performing the searches.
std::string get_algorithm_name() const { return algorithm_.get_algorithm_name(); }
//! Change the pattern (substring) to be searched.
@@ -243,10 +259,10 @@
*/
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_STRING_TYPENAME boost::disable_if<
+ BOOST_STRING_TYPENAME ::boost::algorithm::detail::is_pointer_to<RangeT,Sequence1T> >::type* = 0)
{
- boost::iterator_range<typename boost::range_const_iterator<RangeT>::type> substring_range =
+ boost::iterator_range<BOOST_STRING_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();
@@ -285,9 +301,9 @@
*/
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_STRING_TYPENAME boost::disable_if<BOOST_STRING_TYPENAME ::boost::algorithm::detail::is_pointer_to<RangeT,Sequence2T> >::type* = 0)
{
- boost::iterator_range<typename boost::range_const_iterator<RangeT>::type> string_range =
+ boost::iterator_range<BOOST_STRING_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();
@@ -322,7 +338,7 @@
/*!
\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_begin 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
@@ -331,15 +347,15 @@
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);
+ <code>finder::string_range_type range(string_begin,string_end);
finder.set_string(&range);
return finder.find_first();
</code>
*/
- string_range_type operator()(string_iterator_type &string_start,
+ string_range_type operator()(string_iterator_type &string_begin,
string_iterator_type &string_end)
{
- ranges_.str = boost::make_iterator_range(string_start, string_end);
+ ranges_.str = boost::make_iterator_range(string_begin, string_end);
string_has_changed_ = true;
return find_first();
}
@@ -377,7 +393,7 @@
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
+ BOOST_STRING_TYPENAME boost::call_traits<substring_type>::const_reference get_internal_substring() const
{
return substring_optional_copy_;
}
@@ -387,21 +403,21 @@
\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()
+ BOOST_STRING_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
+ BOOST_STRING_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()
+ BOOST_STRING_TYPENAME boost::call_traits<substring_type>::reference get_internal_string()
{
return substring_optional_copy_;
}
@@ -532,6 +548,7 @@
algorithm_type algorithm_;
substring_type substring_optional_copy_;
string_type string_optional_copy_;
+ // TODO should we use the allocator here too?
boost::algorithm::detail::string_search_ranges<Sequence1T, Sequence2T> ranges_;
bool substring_has_changed_, string_has_changed_;
};
Modified: sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/finder_generators.hpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/finder_generators.hpp (original)
+++ sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/finder_generators.hpp 2010-08-15 15:25:38 EDT (Sun, 15 Aug 2010)
@@ -1,16 +1,32 @@
+// Boost string_algo library finder_generators.hpp header file ---------------------------//
+
+// Copyright Pavol Droba 2002-2003.
+// Copyright Stefan Mihaila 2010.
+//
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+// See http://www.boost.org/ for updates, documentation, and revision history.
+
#ifndef BOOST_ALGORITHM_FINDER_GENERATORS_HPP
#define BOOST_ALGORITHM_FINDER_GENERATORS_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/detail/finder.hpp>
+
+/*! \file
+ Defines finder generators. They are mostly deprecated functions
+ returning instances of finder types defined in \headername generated_finders.hpp.
+ Finder generators are preserved for backward compatibility, but their use is discouraged.
+*/
namespace boost { namespace algorithm {
//! "First" finder generator
/*!
- Constructs a \ref first_finder_t. For backward compatibility, the finder is a
+ Constructs a \ref first_finder_t. \ref first_finder_t 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 The pattern to look for
@@ -19,12 +35,12 @@
\deprecated
*/
template<typename RangeT,typename PredicateT, typename AlgorithmTagT>
- inline boost::algorithm::first_finder_t<RangeT, typename AlgorithmTagT::type,PredicateT>
+ inline boost::algorithm::first_finder_t<RangeT, BOOST_STRING_TYPENAME AlgorithmTagT::type,PredicateT>
first_finder(
const RangeT& Search, PredicateT const& Comp,
AlgorithmTagT const&)
{
- return boost::algorithm::first_finder_t<RangeT, typename AlgorithmTagT::type,PredicateT>(&Search, Comp);
+ return boost::algorithm::first_finder_t<RangeT, BOOST_STRING_TYPENAME AlgorithmTagT::type,PredicateT>(&Search, Comp);
}
//! \overload
@@ -50,7 +66,7 @@
//! "Last" finder generator
/*!
- Constructs a \ref last_finder_t. For backward compatibility, the finder is a
+ Constructs a \ref last_finder_t. \ref last_finder_t 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 The pattern to look for
@@ -59,11 +75,11 @@
\deprecated
*/
template<typename RangeT, typename PredicateT, typename AlgorithmTagT>
- inline boost::algorithm::last_finder_t<RangeT, typename AlgorithmTagT::type,PredicateT>
+ inline boost::algorithm::last_finder_t<RangeT, BOOST_STRING_TYPENAME AlgorithmTagT::type,PredicateT>
last_finder( const RangeT& Search, PredicateT const &Comp,
AlgorithmTagT const&)
{
- return boost::algorithm::last_finder_t<RangeT, typename AlgorithmTagT::type,PredicateT>(&Search, Comp);
+ return boost::algorithm::last_finder_t<RangeT, BOOST_STRING_TYPENAME AlgorithmTagT::type,PredicateT>(&Search, Comp);
}
//!\overload
@@ -88,7 +104,7 @@
//! "Nth" finder generator
/*!
- Constructs a \ref nth_finder_t. For backward compatibility, the finder is a
+ Constructs a \ref nth_finder_t. \ref nth_finder_t 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 The pattern to look for
@@ -98,11 +114,11 @@
*/
template<typename RangeT, typename PredicateT, typename AlgorithmTagT>
inline boost::algorithm::nth_finder_t<RangeT,
- typename AlgorithmTagT::type,PredicateT>
+ BOOST_STRING_TYPENAME AlgorithmTagT::type,PredicateT>
nth_finder(const RangeT& Search, int Nth, PredicateT const &Comp, AlgorithmTagT const &)
{
return boost::algorithm::nth_finder_t<RangeT,
- typename AlgorithmTagT::type, PredicateT>(&Search, Comp, Nth);
+ BOOST_STRING_TYPENAME AlgorithmTagT::type, PredicateT>(&Search, Nth, Comp);
}
//!\overload
Modified: sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/generated_finders.hpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/generated_finders.hpp (original)
+++ sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/generated_finders.hpp 2010-08-15 15:25:38 EDT (Sun, 15 Aug 2010)
@@ -1,10 +1,21 @@
+// Boost string_algo library generated_finders.hpp header file ---------------------------//
+
+// Copyright Stefan Mihaila 2010.
+//
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+// See http://www.boost.org/ for updates, documentation, and revision history.
+
#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/compare.hpp>
#include <boost/algorithm/string/finder/detail/string_search_ranges.hpp>
#include <boost/algorithm/string/finder/detail/finder_typedefs.hpp>
+#include <boost/algorithm/string/finder/detail/generated_finders.hpp>
+#include <boost/algorithm/string/finder/default_search_algorithm.hpp>
#include <boost/range/begin.hpp>
#include <boost/range/end.hpp>
@@ -16,69 +27,126 @@
#include <memory>
+/*! \file
+ Defines a few useful finder types (\ref first_finder_t, \ref last_finder_t, \ref nth_finder_t).
+ These finder objects are functors which get constructed with a pattern to search for, and can afterwards
+ be called using a pair of iterators representing the text in which the search is to be performed.
+*/
+
namespace boost { namespace algorithm {
- template <class Range1T, class AlgorithmT, class ComparatorT>
+ //! A generic "first" finder type.
+ /*!
+ Instances of this type can be called with a pair of iterators,
+ representing the range of the text (the string in which to search).
+ This functor returns the first occurrence of the pattern in the given text.
+
+ \tparam Range1T A range representing the type of the substring (pattern)
+ \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.
+ */
+ template <class Range1T, class AlgorithmT = boost::algorithm::default_finder_algorithm,
+ class ComparatorT = boost::algorithm::is_equal, class AllocatorT = std::allocator<std::size_t> >
class first_finder_t
{
public:
- first_finder_t (Range1T const *const substr, ComparatorT const &comparator=ComparatorT())
- : substring_range_(boost::as_literal(*substr)), algorithm_(comparator,std::allocator<std::size_t>()),
+
+ //! Constructs a \ref first_finder_t.
+ /*!
+ \param substr A pointer to a range indicating the pattern that is to be searched.
+ \param comparator An instance of \c ComparatorT
+ \param allocator An instance of \c AllocatorT
+ */
+ first_finder_t (Range1T const *const substr, ComparatorT const &comparator=ComparatorT(),
+ AllocatorT const &allocator=AllocatorT())
+ : substring_range_(boost::as_literal(*substr)), algorithm_(comparator,allocator),
first_call_(true) { }
+ //! Searches for a pattern in the given text
+ /*!
+ Searches for the first occurrence of the pattern in [string_begin,string_end).
+ */
template <class Iterator2T>
- typename boost::iterator_range<Iterator2T>
- operator()(Iterator2T const &string_start, Iterator2T const &string_end)
+ BOOST_STRING_TYPENAME boost::iterator_range<Iterator2T>
+ operator()(Iterator2T const &string_begin, Iterator2T const &string_end)
{
- typedef typename boost::iterator_range<Iterator2T> Range2T;
+ typedef BOOST_STRING_TYPENAME boost::iterator_range<Iterator2T> Range2T;
- typename boost::algorithm::detail::string_search_ranges<Range1T, Range2T> ranges;
- ranges.str = boost::make_iterator_range(string_start, string_end);
+ BOOST_STRING_TYPENAME boost::algorithm::detail::string_search_ranges<Range1T, Range2T> ranges;
+ ranges.str = boost::make_iterator_range(string_begin, string_end);
ranges.substr = substring_range_;
- ranges.offset = string_start;
+ ranges.offset = string_begin;
if (first_call_) { algorithm_.on_substring_change(ranges); first_call_ = false; }
algorithm_.on_string_change(ranges);
return algorithm_.find(ranges);
}
private:
- typedef typename boost::range_value<Range1T>::type char_type;
- typedef typename boost::range_const_iterator<Range1T>::type substring_iterator_type;
- typedef typename AlgorithmT::template algorithm<char_type, char_type,
+ typedef BOOST_STRING_TYPENAME boost::range_value<Range1T>::type char_type;
+ typedef BOOST_STRING_TYPENAME boost::range_const_iterator<Range1T>::type substring_iterator_type;
+ typedef BOOST_STRING_TYPENAME AlgorithmT::template algorithm<char_type, char_type,
ComparatorT, std::allocator<std::size_t> > algorithm_type;
- typename boost::iterator_range<substring_iterator_type> substring_range_;
+ BOOST_STRING_TYPENAME boost::iterator_range<substring_iterator_type> substring_range_;
algorithm_type algorithm_;
bool first_call_;
};
- template <class Range1T, class AlgorithmT, class ComparatorT>
+ //! A generic "last" finder type.
+ /*!
+ Instances of this type can be called with a pair of iterators,
+ representing the range of the text (the string in which to search).
+ This functor returns the last occurrence of the pattern in the given text.
+
+ \tparam Range1T A range representing the type of the substring (pattern)
+ \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.
+ */
+ template <class Range1T, class AlgorithmT = boost::algorithm::default_finder_algorithm,
+ class ComparatorT = boost::algorithm::is_equal, class AllocatorT = std::allocator<std::size_t> >
class last_finder_t
{
public:
- last_finder_t (Range1T const *const substr, ComparatorT const &comparator=ComparatorT())
- : substring_range_(boost::as_literal(*substr)), algorithm_(comparator,std::allocator<std::size_t>()),
+ //! Constructs a \ref last_finder_t.
+ /*!
+ \param substr A pointer to a range indicating the pattern that is to be searched.
+ \param comparator An instance of \c ComparatorT
+ \param allocator An instance of \c AllocatorT
+ */
+ last_finder_t (Range1T const *const substr, ComparatorT const &comparator=ComparatorT(),
+ AllocatorT const &allocator=AllocatorT())
+ : substring_range_(boost::as_literal(*substr)), algorithm_(comparator, allocator),
first_call_bidi_(true), first_call_forw_(true) { }
+ //! Searches for a pattern in the given text
+ /*!
+ Searches for the last occurrence of the pattern in [string_begin,string_end).
+ */
template <class Iterator2T>
- typename boost::iterator_range<Iterator2T>
- operator()(Iterator2T const &string_start, Iterator2T const &string_end)
+ BOOST_STRING_TYPENAME boost::iterator_range<Iterator2T>
+ operator()(Iterator2T const &string_begin, Iterator2T const &string_end)
{
- return find(string_start, string_end,
- typename boost::range_category<Range1T>::type(),
- typename boost::iterator_category<Iterator2T>::type());
+ return find(string_begin, string_end,
+ BOOST_STRING_TYPENAME boost::range_category<Range1T>::type(),
+ BOOST_STRING_TYPENAME boost::iterator_category<Iterator2T>::type());
}
private:
//implementation of last_finder_t for when bidirectional iterators are available
template <class Iterator2T>
- typename boost::iterator_range<Iterator2T>
- find (Iterator2T const &string_start, Iterator2T const &string_end,
+ BOOST_STRING_TYPENAME boost::iterator_range<Iterator2T>
+ find (Iterator2T const &string_begin, Iterator2T const &string_end,
std::bidirectional_iterator_tag, std::bidirectional_iterator_tag)
{
- typedef typename boost::iterator_range<Iterator2T> Range2T;
+ typedef BOOST_STRING_TYPENAME boost::iterator_range<Iterator2T> Range2T;
BOOST_ALGORITHM_DETAIL_COMMON_FINDER_TYPEDEFS(Range1T, Range2T);
BOOST_ALGORITHM_DETAIL_UNCOMMON_FINDER_TYPEDEFS(Range1T, Range2T);
- typename boost::algorithm::detail::string_search_ranges<substring_reverse_range_type,
+ BOOST_STRING_TYPENAME boost::algorithm::detail::string_search_ranges<substring_reverse_range_type,
string_reverse_range_type> ranges;
ranges.substr = boost::make_iterator_range(
substring_reverse_iterator_type(boost::end(substring_range_)),
@@ -86,7 +154,7 @@
);
ranges.str = boost::make_iterator_range(
string_reverse_iterator_type(string_end),
- string_reverse_iterator_type(string_start)
+ string_reverse_iterator_type(string_begin)
);
ranges.offset = string_reverse_iterator_type(string_end);
if (first_call_bidi_)
@@ -96,10 +164,10 @@
first_call_forw_ = true;
}
algorithm_.on_string_change(ranges);
- string_reverse_range_type &ret = algorithm_.find(ranges);
+ string_reverse_range_type const &ret = algorithm_.find(ranges);
//no match
- if (boost::begin(ret) == string_reverse_iterator_type(string_start))
+ if (boost::begin(ret) == string_reverse_iterator_type(string_begin))
return boost::make_iterator_range(string_end, string_end);
//found a match, convert into direct iterators
@@ -107,17 +175,18 @@
}
//implementation of last_finder_t when all we have are forward iterators
+ //todo test if this works properly
template <class Iterator2T>
- typename boost::iterator_range<Iterator2T>
- find (Iterator2T const &string_start, Iterator2T const &string_end,
+ BOOST_STRING_TYPENAME boost::iterator_range<Iterator2T>
+ find (Iterator2T const &string_begin, Iterator2T const &string_end,
std::forward_iterator_tag, std::forward_iterator_tag)
{
- typedef typename boost::iterator_range<Iterator2T> Range2T;
+ typedef BOOST_STRING_TYPENAME boost::iterator_range<Iterator2T> Range2T;
- typename boost::algorithm::detail::string_search_ranges<Range1T, Range2T> ranges;
- ranges.str = boost::make_iterator_range(string_start, string_end);
+ BOOST_STRING_TYPENAME boost::algorithm::detail::string_search_ranges<Range1T, Range2T> ranges;
+ ranges.str = boost::make_iterator_range(string_begin, string_end);
ranges.substr = substring_range_;
- ranges.offset = string_start;
+ ranges.offset = string_begin;
if (first_call_forw_)
{
@@ -136,45 +205,81 @@
}
return prev;
}
- typedef typename boost::range_value<Range1T>::type char_type;
- typedef typename boost::range_const_iterator<Range1T>::type substring_iterator_type;
- typedef typename AlgorithmT::template algorithm<char_type, char_type,
+ typedef BOOST_STRING_TYPENAME boost::range_value<Range1T>::type char_type;
+ typedef BOOST_STRING_TYPENAME boost::range_const_iterator<Range1T>::type substring_iterator_type;
+ typedef BOOST_STRING_TYPENAME AlgorithmT::template algorithm<char_type, char_type,
ComparatorT, std::allocator<std::size_t> > algorithm_type;
- typename boost::iterator_range<substring_iterator_type> substring_range_;
+ BOOST_STRING_TYPENAME boost::iterator_range<substring_iterator_type> substring_range_;
algorithm_type algorithm_;
bool first_call_bidi_, first_call_forw_;
};
- template <class Range1T, class AlgorithmT, class ComparatorT>
+ //! A generic "nth" finder type.
+ /*!
+ Instances of this type can be called with a pair of iterators,
+ representing the range of the text (the string in which to search).
+ This functor returns the N-th occurrence of the pattern in the given text
+ For negative N, the matches are looked up starting from the back (assuming the pattern
+ and text support bidirectional ranges). I.e. N = -1 finds the last match.
+
+ \tparam Range1T A range representing the type of the substring (pattern)
+ \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.
+ */
+ template <class Range1T, class AlgorithmT = boost::algorithm::default_finder_algorithm,
+ class ComparatorT = boost::algorithm::is_equal, class AllocatorT = std::allocator<std::size_t> >
class nth_finder_t
{
public:
- nth_finder_t (Range1T const *const substr, ComparatorT const &comparator=ComparatorT(), int n=0)
- : substring_range_(boost::as_literal(*substr)), algorithm_(comparator,std::allocator<std::size_t>()), n_(n),
+
+ //! Constructs a \ref nth_finder_t.
+ /*!
+ \param substr A pointer to a range indicating the pattern that is to be searched.
+ \param n The value of n (indicating which match we are interested in)
+ \param comparator An instance of \c ComparatorT
+ \param allocator An instance of \c AllocatorT
+ */
+ nth_finder_t (Range1T const *const substr, int n=0,
+ ComparatorT const &comparator=ComparatorT(), AllocatorT const &allocator=AllocatorT())
+ : substring_range_(boost::as_literal(*substr)), n_(n), algorithm_(comparator,allocator),
first_call_forw_(true), first_call_bidi_(true) { }
+ //! Searches for a pattern in the given text
+ /*!
+ Searches for the nth occurrence of the pattern in [string_begin,string_end).
+ */
template <class Iterator2T>
- typename boost::iterator_range<Iterator2T>
- operator()(Iterator2T const &string_start, Iterator2T const &string_end)
+ BOOST_STRING_TYPENAME boost::iterator_range<Iterator2T>
+ operator()(Iterator2T const &string_begin, Iterator2T const &string_end)
{
if (n_ < 0)
- return find_backwards(string_start, string_end,
- typename boost::range_category<Range1T>::type(), typename boost::iterator_category<Iterator2T>::type());
- else return find(string_start, string_end);
+ return find_backwards(string_begin, string_end,
+ BOOST_STRING_TYPENAME boost::range_category<Range1T>::type(), BOOST_STRING_TYPENAME boost::iterator_category<Iterator2T>::type());
+ else return find(string_begin, string_end);
}
+
+ //! Changes the value of n.
+ /*!
+ \warning Every time the sign of n changes (from n>=0 to n<0 or vice-versa), the information
+ on the pattern is recomputed.
+ */
+ void set_n(int n) { n_ = n; }
private:
//find nth, for n>=0
template <class Iterator2T>
- typename boost::iterator_range<Iterator2T>
- find(Iterator2T const &string_start, Iterator2T const &string_end)
+ BOOST_STRING_TYPENAME boost::iterator_range<Iterator2T>
+ find(Iterator2T const &string_begin, Iterator2T const &string_end)
{
- typedef typename boost::iterator_range<Iterator2T> Range2T;
+ typedef BOOST_STRING_TYPENAME boost::iterator_range<Iterator2T> Range2T;
boost::algorithm::detail::string_search_ranges<Range1T, Range2T> ranges;
ranges.substr = substring_range_;
- ranges.str = boost::make_iterator_range(string_start, string_end);
- ranges.offset = string_start;
+ ranges.str = boost::make_iterator_range(string_begin, string_end);
+ ranges.offset = string_begin;
if (first_call_forw_)
{
@@ -197,11 +302,11 @@
//find nth, for n < 0
template <class Iterator2T>
- typename boost::iterator_range<Iterator2T>
- find_backwards(Iterator2T const &string_start, Iterator2T const &string_end,
+ BOOST_STRING_TYPENAME boost::iterator_range<Iterator2T>
+ find_backwards(Iterator2T const &string_begin, Iterator2T const &string_end,
std::bidirectional_iterator_tag, std::bidirectional_iterator_tag)
{
- typedef typename boost::iterator_range<Iterator2T> Range2T;
+ typedef BOOST_STRING_TYPENAME boost::iterator_range<Iterator2T> Range2T;
BOOST_ALGORITHM_DETAIL_COMMON_FINDER_TYPEDEFS(Range1T, Range2T);
BOOST_ALGORITHM_DETAIL_UNCOMMON_FINDER_TYPEDEFS(Range1T, Range2T);
@@ -213,7 +318,7 @@
);
ranges.str = boost::make_iterator_range(
string_reverse_iterator_type(string_end),
- string_reverse_iterator_type(string_start)
+ string_reverse_iterator_type(string_begin)
);
ranges.offset = string_reverse_iterator_type(string_end);
@@ -230,22 +335,22 @@
for (int n = 0; n <= n_2; ++n)
{
ret = algorithm_.find(ranges);
- if (boost::begin(ret) == string_reverse_iterator_type(string_start))
+ if (boost::begin(ret) == string_reverse_iterator_type(string_begin))
return boost::make_iterator_range(string_end, string_end);
else { ranges.offset = boost::begin(ret); ++ranges.offset; }
}
return boost::make_iterator_range(boost::end(ret).base(), boost::begin(ret).base());
}
- typedef typename boost::range_value<Range1T>::type char_type;
- typedef typename boost::range_const_iterator<Range1T>::type substring_iterator_type;
- typedef typename AlgorithmT::template algorithm<char_type, char_type,
+ typedef BOOST_STRING_TYPENAME boost::range_value<Range1T>::type char_type;
+ typedef BOOST_STRING_TYPENAME boost::range_const_iterator<Range1T>::type substring_iterator_type;
+ typedef BOOST_STRING_TYPENAME AlgorithmT::template algorithm<char_type, char_type,
ComparatorT, std::allocator<std::size_t> > algorithm_type;
- typename boost::iterator_range<substring_iterator_type> substring_range_;
+ BOOST_STRING_TYPENAME boost::iterator_range<substring_iterator_type> substring_range_;
+ int n_;
algorithm_type algorithm_;
bool first_call_forw_, first_call_bidi_;
- int n_;
};
} }
Modified: sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/simplified_finder.hpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/simplified_finder.hpp (original)
+++ sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/simplified_finder.hpp 2010-08-15 15:25:38 EDT (Sun, 15 Aug 2010)
@@ -1,9 +1,20 @@
+// Boost string_algo library simplified_finder.hpp header file ---------------------------//
+
+// Copyright Stefan Mihaila 2010.
+//
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+// See http://www.boost.org/ for updates, documentation, and revision history.
+
#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/algorithm/string/finder/detail/string_search_ranges.hpp>
+#include <boost/algorithm/string/finder/default_search_algorithm.hpp>
#include <boost/range/as_literal.hpp>
#include <boost/range/iterator_range.hpp>
@@ -14,6 +25,14 @@
#include <memory>
+/*! \file
+ Defines \ref simplified_finder_t, a finder type uesd for finding occurrences of a pattern in a string.
+ This finder is a more limited version of \ref finder_t, because it only allows passing pointers to ranges,
+ which means no internal copies of the strings are made (\see finder_t for details). While this offers additional
+ efficiency, it requires the caller to guarantee that the lifetime of a passed string is at least as long
+ as the lifetime of the finder.
+*/
+
namespace boost { namespace algorithm {
//! A generic finder type
@@ -24,14 +43,12 @@
\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.
+ \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,
+ template <class Range1T, class Range2T, class AlgorithmT = boost::algorithm::default_finder_algorithm,
class ComparatorT = ::boost::algorithm::is_equal,
class AllocatorT = std::allocator<std::size_t>
>
@@ -42,10 +59,10 @@
BOOST_ALGORITHM_DETAIL_COMMON_FINDER_TYPEDEFS(Range1T, Range2T);
BOOST_ALGORITHM_DETAIL_FINDER_TYPEDEFS2(ComparatorT, AllocatorT);
private:
- typedef typename AlgorithmT::template algorithm<substring_char_type, string_char_type,
+ typedef BOOST_STRING_TYPENAME AlgorithmT::template algorithm<substring_char_type, string_char_type,
comparator_type, allocator_type> algorithm_type;
public:
- //! Constructs a finder.
+ //! Constructs the finder.
/*!
\param comparator ComparatorT instance used to compare individual characters
\param allocator AllocatorT instance used to allocate memory
@@ -53,11 +70,11 @@
*/
explicit simplified_finder_t(ComparatorT const &comparator = ComparatorT(),
AllocatorT const &allocator = AllocatorT())
- : ranges_(), substring_has_changed_(false), string_has_changed_(false),
- algorithm_(comparator, allocator)
+ : ranges_(), algorithm_(comparator, allocator),
+ substring_has_changed_(false), string_has_changed_(false)
{ }
/*!
- Constructs a finder given a pattern and a text
+ Constructs the 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
@@ -80,7 +97,7 @@
substring_has_changed_(true), string_has_changed_(true)
{ }
-
+ //! Copies the finder
simplified_finder_t (const simplified_finder_t &other)
: ranges_(other.ranges_), algorithm_(other.algorithm_),
substring_has_changed_(other.substring_has_changed_),
@@ -104,6 +121,7 @@
void set_substring (substring_type const *const substr)
{ ranges_.substr = boost::as_literal(*substr); substring_has_changed_ = true; }
+ //! \overload
void set_substring (substring_iterator_type const &substring_begin, substring_iterator_type const &substring_end)
{
ranges_.substr = boost::make_iterator_range(substring_begin, substring_end);
@@ -118,6 +136,7 @@
void set_string (string_type *const str)
{ ranges_.str = boost::as_literal(*str); string_has_changed_ = true; }
+ //!\overload
void set_string (string_iterator_type const &string_begin, string_iterator_type const &string_end)
{
ranges_.str = boost::make_iterator_range(string_begin, string_end);
@@ -145,7 +164,7 @@
/*!
\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_begin 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
@@ -155,14 +174,14 @@
after the passed iterators become invalid.
\note This is equivalent to:
<code>
- finder.set_string(string_start, string_end);
+ finder.set_string(string_begin, string_end);
return finder.find_first();
</code>
*/
- string_range_type operator()(string_iterator_type const &string_start,
+ string_range_type operator()(string_iterator_type const &string_begin,
string_iterator_type const &string_end)
{
- set_string(string_start, string_end);
+ set_string(string_begin, string_end);
return find_first();
}
@@ -194,35 +213,36 @@
//! 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
+ \warning If you modify the contents in this range externally, you must manually call
+ <code>set_substring(&substr);</code> afterwards
*/
substring_range_type get_substring_range() const { return ranges_.substr; }
//! 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
+ \warning If you modify the contents in this range externally, you must manually call
+ <code>set_string(&str);</code> afterwards
*/
string_range_type get_string_range() const { return ranges_.str; }
/*
//! Gets a reference to the current comparator
- typename boost::call_traits<comparator_type>::const_reference get_comparator() const
+ BOOST_STRING_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()
+ BOOST_STRING_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
+ BOOST_STRING_TYPENAME boost::call_traits<allocator_type>::const_reference get_allocator() const
{ return allocator_; }
*/
+
std::string get_algorithm_name() const { return algorithm_.get_algorithm_name(); }
private:
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-15 15:25:38 EDT (Sun, 15 Aug 2010)
@@ -1,42 +1,86 @@
+// Boost string_algo library finder_aliases.hpp header file ---------------------------//
+
+// Copyright Stefan Mihaila 2010.
+//
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+// See http://www.boost.org/ for updates, documentation, and revision history.
+
#ifndef BOOST_STRING_FINDER_ALIASES_HPP
#define BOOST_STRING_FINDER_ALIASES_HPP
+/*! \file
+ Defines useful typedefs for a easier creation of \ref finder_t finders.
+*/
+
#include <boost/algorithm/string/finder/finder.hpp>
#include <boost/algorithm/string/string_search.hpp>
namespace boost { namespace algorithm {
+
//Naive Search
+
+ //! A template class of \ref finder_t using std::strings as types for pattern and text
+ //! and naive search as the string search algorithm.
typedef boost::algorithm::finder_t<std::string, std::string,
boost::algorithm::naive_search> naive_search_finder;
+ //! A template class of \ref finder_t using std::wstrings as types for pattern and text
+ //! and naive search as the string search algorithm.
typedef boost::algorithm::finder_t<std::wstring, std::wstring,
boost::algorithm::naive_search> wnaive_search_finder;
+
//Knuth-Morris-Pratt
+ //! A template class of \ref finder_t using std::strings as types for pattern and text
+ //! and Knuth-Morris-Pratt as the string search algorithm.
typedef boost::algorithm::finder_t<std::string, std::string,
boost::algorithm::knuth_morris_pratt> knuth_morris_pratt_finder;
+ //! A template class of \ref finder_t using std::wstrings as types for pattern and text
+ //! and Knuth-Morris-Pratt as the string search algorithm.
typedef boost::algorithm::finder_t<std::wstring, std::wstring,
boost::algorithm::knuth_morris_pratt> wknuth_morris_pratt_finder;
+
//Boyer Moore
+ //! A template class of \ref finder_t using std::strings as types for pattern and text
+ //! and Boyer-Moore as the string search algorithm.
typedef boost::algorithm::finder_t<std::string, std::string,
boost::algorithm::boyer_moore> boyer_moore_finder;
+ //! A template class of \ref finder_t using std::wstrings as types for pattern and text
+ //! and Boyer-Moore as the string search algorithm.
typedef boost::algorithm::finder_t<std::wstring, std::wstring,
boost::algorithm::boyer_moore> wboyer_moore_finder;
+
//Rabin Karp
+ //! A template class of \ref finder_t using std::strings as types for pattern and text
+ //! and 32bit Rabin-Karp as the string search algorithm.
typedef boost::algorithm::finder_t<std::string, std::string,
boost::algorithm::rabin_karp32> rabin_karp32_finder;
+ //! A template class of \ref finder_t using std::wstrings as types for pattern and text
+ //! and 32bit Rabin-Karp as the string search algorithm.
typedef boost::algorithm::finder_t<std::wstring, std::wstring,
boost::algorithm::rabin_karp32> wrabin_karp32_finder;
+ //! A template class of \ref finder_t using std::strings as types for pattern and text
+ //! and 64bit Rabin-Karp as the string search algorithm.
typedef boost::algorithm::finder_t<std::string, std::string,
boost::algorithm::rabin_karp64> rabin_karp64_finder;
+ //! A template class of \ref finder_t using std::wstrings as types for pattern and text
+ //! and 64bit Rabin-Karp as the string search algorithm.
typedef boost::algorithm::finder_t<std::wstring, std::wstring,
boost::algorithm::rabin_karp64> wrabin_karp64_finder;
+
//Suffix array
+ //! A template class of \ref finder_t using std::strings as types for pattern and text
+ //! and suffix array search as the string search algorithm.
typedef boost::algorithm::finder_t<std::string, std::string,
boost::algorithm::suffix_array_search> suffix_array_finder;
+ //! A template class of \ref finder_t using std::wstrings as types for pattern and text
+ //! and suffix array search as the string search algorithm.
typedef boost::algorithm::finder_t<std::wstring, std::wstring,
boost::algorithm::suffix_array_search> wsuffix_array_finder;
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-15 15:25:38 EDT (Sun, 15 Aug 2010)
@@ -1,7 +1,17 @@
+// Boost string_algo library string_search.hpp header file ---------------------------//
+
+// Copyright Stefan Mihaila 2010.
+//
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+// See http://www.boost.org/ for updates, documentation, and revision history.
+
#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 (also benchmark_finder.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-15 15:25:38 EDT (Sun, 15 Aug 2010)
@@ -1,3 +1,13 @@
+// Boost string_algo library boyer_moore.hpp header file ---------------------------//
+
+// Copyright Stefan Mihaila 2010
+//
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+// See http://www.boost.org/ for updates, documentation, and revision history.
+
#ifndef BOOST_ALGORITHM_BOYER_MOORE_HPP
#define BOOST_ALGORITHM_BOYER_MOORE_HPP
@@ -22,6 +32,7 @@
#include <utility>
#include <vector>
+#include <boost/algorithm/string/config.hpp>
#include <boost/algorithm/string/finder/detail/finder_typedefs.hpp>
#include <boost/algorithm/string/finder/detail/string_search_ranges.hpp>
@@ -38,7 +49,7 @@
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 This algorithm can only work with the equality comparator and in certain cases 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
@@ -63,19 +74,19 @@
}
template <class Range1T, class Range2T>
- inline typename boost::iterator_range<typename boost::range_iterator<Range2T>::type>
- find(typename boost::algorithm::detail::string_search_ranges<Range1T, Range2T> const &ranges)
+ inline BOOST_STRING_TYPENAME boost::iterator_range<BOOST_STRING_TYPENAME boost::range_iterator<Range2T>::type>
+ find(BOOST_STRING_TYPENAME boost::algorithm::detail::string_search_ranges<Range1T, Range2T> const &ranges)
{
- return find(ranges, typename boost::range_category<Range2T>::type());
+ return find(ranges, BOOST_STRING_TYPENAME boost::range_category<Range2T>::type());
}
//Compute the two tables
template <class Range1T, class Range2T>
inline void on_substring_change(
- typename boost::algorithm::detail::string_search_ranges<Range1T, Range2T> const &ranges)
+ BOOST_STRING_TYPENAME boost::algorithm::detail::string_search_ranges<Range1T, Range2T> const &ranges)
{
- on_substring_change(ranges.substr, typename boost::range_category<Range1T>::type());
+ on_substring_change(ranges.substr, BOOST_STRING_TYPENAME boost::range_category<Range1T>::type());
}
//No precomputation to be done on the string
@@ -85,15 +96,15 @@
comparator_type comp_; allocator_type alloc_;
//TODO Maybe optimize for sizeof(substring_char_type)==1, or substring_char_type=char?
- typedef typename boost::unordered_map<substring_char_type, std::size_t,
- typename boost::hash<substring_char_type>, comparator_type,
- typename allocator_type::template
+ typedef BOOST_STRING_TYPENAME boost::unordered_map<substring_char_type, std::size_t,
+ BOOST_STRING_TYPENAME boost::hash<substring_char_type>, comparator_type,
+ BOOST_STRING_TYPENAME allocator_type::template
rebind<substring_char_type>::other
> table1_type;
table1_type table1;
- typedef typename std::vector<std::size_t,
- typename allocator_type::template rebind<std::size_t>::other
+ typedef BOOST_STRING_TYPENAME std::vector<std::size_t,
+ BOOST_STRING_TYPENAME allocator_type::template rebind<std::size_t>::other
> table2_type;
table2_type table2;
@@ -102,7 +113,7 @@
struct compute_first_table_functor
{
//Case 1: ComparatorT=boost::algorithm::is_equal
- void operator()(typename boost::call_traits<substring_char_type>::param_type c)
+ void operator()(BOOST_STRING_TYPENAME boost::call_traits<substring_char_type>::param_type c)
{
compute_first_table<comparator_type>(c);
}
@@ -110,9 +121,9 @@
{ alg_.table1.clear(); }
template <class ComparatorTT>
- void compute_first_table(typename boost::call_traits<substring_char_type>::param_type c,
- typename boost::enable_if<
- typename boost::is_same<ComparatorTT, boost::algorithm::is_equal> >::type* =0)
+ void compute_first_table(BOOST_STRING_TYPENAME boost::call_traits<substring_char_type>::param_type c,
+ BOOST_STRING_TYPENAME boost::enable_if<
+ BOOST_STRING_TYPENAME boost::is_same<ComparatorTT, boost::algorithm::is_equal> >::type* =0)
{
//alg_.table1.insert( std::make_pair(c, alg_.substr_size_ - 1 - idx_) );
if (idx_ != 0) alg_.table1.insert(std::make_pair(c, idx_));
@@ -122,9 +133,9 @@
//Case 2: ComparatorT=boost::algorithm::is_iequal
template <class ComparatorTT>
- void compute_first_table(typename boost::call_traits<substring_char_type>::param_type c,
- typename boost::enable_if<
- typename boost::is_same<ComparatorTT, boost::algorithm::is_iequal> >::type* =0)
+ void compute_first_table(BOOST_STRING_TYPENAME boost::call_traits<substring_char_type>::param_type c,
+ BOOST_STRING_TYPENAME boost::enable_if<
+ BOOST_STRING_TYPENAME boost::is_same<ComparatorTT, boost::algorithm::is_iequal> >::type* =0)
{
//Case insensitive matches are supported properly for char (in case of Boyer-Moore)
BOOST_STATIC_ASSERT((boost::is_same<substring_char_type,char>::value));
@@ -156,7 +167,7 @@
//failure_func[i]=k means k is the size of the biggest boundary of the string P[i..m-1]
//(which is not the string itself)
//i.e. P[i..i+k+1] = P[..m-1]
- std::vector<std::size_t, typename allocator_type::template rebind<std::size_t>::other>
+ std::vector<std::size_t, BOOST_STRING_TYPENAME allocator_type::template rebind<std::size_t>::other>
failure_func(substr_size_);
@@ -168,7 +179,7 @@
if (substr_size_ < 2) return;
- typename boost::range_iterator<RangeT>::type const &pattern = boost::begin(substr);
+ BOOST_STRING_TYPENAME boost::range_iterator<RangeT>::type const &pattern = boost::begin(substr);
//todo find a better solution for this
@@ -263,7 +274,6 @@
//equivalent to:
//d2(i) = min { k-1 | (k=m+1) OR (m-k+1 \in B_P(0) AND i+2 <= k <= m) }
- //!\TODO IMPORTANT!! MUST REMOVE THE LOOP BELOW, IT'S ONLY FOR DEBUGGING PURPOSES
//for (std::size_t i = 0; i < substr_size_; ++i)
// table2[i] = substr_size_;
@@ -281,8 +291,8 @@
//finding in text=random access range
template <class Range1T, class Range2T>
- inline typename boost::iterator_range<typename boost::range_iterator<Range2T>::type>
- find(typename boost::algorithm::detail::string_search_ranges<Range1T, Range2T> const &ranges,
+ inline BOOST_STRING_TYPENAME boost::iterator_range<BOOST_STRING_TYPENAME boost::range_iterator<Range2T>::type>
+ find(BOOST_STRING_TYPENAME boost::algorithm::detail::string_search_ranges<Range1T, Range2T> const &ranges,
std::random_access_iterator_tag)
{
BOOST_ALGORITHM_DETAIL_COMMON_FINDER_TYPEDEFS(Range1T, Range2T);
@@ -316,7 +326,7 @@
}
else
{
- typename table1_type::const_iterator iter = table1_find<comparator_type>(start[str_idx]);
+ BOOST_STRING_TYPENAME table1_type::const_iterator iter = table1_find<comparator_type>(start[str_idx]);
std::size_t step = substr_size_ - substr_idx;
if (iter == table1.end())
{
@@ -346,18 +356,18 @@
//Case 1: ComparatorT=boost::algorithm::is_equal
template <class ComparatorTT>
- typename table1_type::iterator table1_find (string_char_type const &chr,
- typename boost::enable_if<
- typename boost::is_same<ComparatorTT, boost::algorithm::is_equal> >::type* = 0)
+ BOOST_STRING_TYPENAME table1_type::iterator table1_find (string_char_type const &chr,
+ BOOST_STRING_TYPENAME boost::enable_if<
+ BOOST_STRING_TYPENAME boost::is_same<ComparatorTT, boost::algorithm::is_equal> >::type* = 0)
{
return table1.find(chr);
}
//Case 2: ComparatorT=boost::algorithm::is_iequal
template <class ComparatorTT>
- typename table1_type::iterator table1_find (string_char_type const &chr,
- typename boost::enable_if<
- typename boost::is_same<ComparatorTT, boost::algorithm::is_iequal> >::type* = 0)
+ BOOST_STRING_TYPENAME table1_type::iterator table1_find (string_char_type const &chr,
+ BOOST_STRING_TYPENAME boost::enable_if<
+ BOOST_STRING_TYPENAME boost::is_same<ComparatorTT, boost::algorithm::is_iequal> >::type* = 0)
{
return table1.find(std::tolower(chr, std::locale()));
}
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-15 15:25:38 EDT (Sun, 15 Aug 2010)
@@ -1,3 +1,13 @@
+// Boost string_algo library rabin_karp.hpp header file ---------------------------//
+
+// Copyright Stefan Mihaila 2010.
+//
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+// See http://www.boost.org/ for updates, documentation, and revision history.
+
#ifndef BOOST_ALGORITHM_RABIN_KARP_DETAIL_HPP
#define BOOST_ALGORITHM_RABIN_KARP_DETAIL_HPP
@@ -67,10 +77,10 @@
HashType SecondBase, HashType SecondModulo, class StringIteratorCategory>
class rabin_karp_algorithm<Range1CharT, Range2CharT, HashType,
FirstBase, FirstModulo, SecondBase, SecondModulo, StringIteratorCategory,
- typename boost::enable_if<
- typename boost::mpl::and_<
- typename boost::is_base_of<std::input_iterator_tag, StringIteratorCategory>,
- typename boost::mpl::not_<typename boost::is_base_of<std::forward_iterator_tag, StringIteratorCategory> >
+ BOOST_STRING_TYPENAME boost::enable_if<
+ BOOST_STRING_TYPENAME boost::mpl::and_<
+ BOOST_STRING_TYPENAME boost::is_base_of<std::input_iterator_tag, StringIteratorCategory>,
+ BOOST_STRING_TYPENAME boost::mpl::not_<BOOST_STRING_TYPENAME boost::is_base_of<std::forward_iterator_tag, StringIteratorCategory> >
>
>::type
>
@@ -82,10 +92,10 @@
HashType SecondBase, HashType SecondModulo, class StringIteratorCategory>
class rabin_karp_algorithm<Range1CharT, Range2CharT, HashType,
FirstBase, FirstModulo, SecondBase, SecondModulo, StringIteratorCategory,
- typename boost::enable_if<
- typename boost::mpl::and_<
- typename boost::is_base_of<std::forward_iterator_tag, StringIteratorCategory>,
- typename boost::mpl::not_<typename boost::is_base_of<std::random_access_iterator_tag, StringIteratorCategory> >
+ BOOST_STRING_TYPENAME boost::enable_if<
+ BOOST_STRING_TYPENAME boost::mpl::and_<
+ BOOST_STRING_TYPENAME boost::is_base_of<std::forward_iterator_tag, StringIteratorCategory>,
+ BOOST_STRING_TYPENAME boost::mpl::not_<BOOST_STRING_TYPENAME boost::is_base_of<std::random_access_iterator_tag, StringIteratorCategory> >
>
>::type
>
@@ -97,8 +107,8 @@
HashType SecondBase, HashType SecondModulo, class StringIteratorCategory>
class rabin_karp_algorithm<Range1CharT, Range2CharT, HashType,
FirstBase, FirstModulo, SecondBase, SecondModulo, StringIteratorCategory,
- typename boost::enable_if<
- typename boost::is_base_of<
+ BOOST_STRING_TYPENAME boost::enable_if<
+ BOOST_STRING_TYPENAME boost::is_base_of<
std::random_access_iterator_tag,
StringIteratorCategory
>
@@ -120,13 +130,13 @@
//\todo this the right name? the right way to do it?
template <class T>
BOOST_STRING_FORCE_INLINE HashType integer_promotion(T i)
- { return static_cast<HashType>(static_cast<typename boost::make_unsigned<T>::type>(i)); }
+ { return static_cast<HashType>(static_cast<BOOST_STRING_TYPENAME boost::make_unsigned<T>::type>(i)); }
public:
template <class Range1T, class Range2T>
inline void on_substring_change(
- typename boost::algorithm::detail::string_search_ranges<Range1T, Range2T> const &ranges)
+ BOOST_STRING_TYPENAME boost::algorithm::detail::string_search_ranges<Range1T, Range2T> const &ranges)
{
BOOST_ALGORITHM_DETAIL_COMMON_FINDER_TYPEDEFS(Range1T, Range2T);
@@ -160,7 +170,7 @@
template <class Range1T, class Range2T>
inline void on_string_change(
- typename boost::algorithm::detail::string_search_ranges<Range1T, Range2T> const &ranges)
+ BOOST_STRING_TYPENAME boost::algorithm::detail::string_search_ranges<Range1T, Range2T> const &ranges)
{
BOOST_ALGORITHM_DETAIL_COMMON_FINDER_TYPEDEFS(Range1T, Range2T);
@@ -188,8 +198,8 @@
}
template <class Range1T, class Range2T>
- inline typename boost::iterator_range<typename boost::range_iterator<Range2T>::type>
- find(typename boost::algorithm::detail::string_search_ranges<Range1T, Range2T> const &ranges)
+ inline BOOST_STRING_TYPENAME boost::iterator_range<BOOST_STRING_TYPENAME boost::range_iterator<Range2T>::type>
+ find(BOOST_STRING_TYPENAME boost::algorithm::detail::string_search_ranges<Range1T, Range2T> const &ranges)
{
BOOST_ALGORITHM_DETAIL_COMMON_FINDER_TYPEDEFS(Range1T, Range2T);
@@ -256,18 +266,16 @@
return boost::make_tuple(first, second);
}*/
- //todo compatible force inline? __attribute__((force_inline)) in GCC
- //inline void roll_string_hash()
template <class StrT>
BOOST_STRING_FORCE_INLINE void roll_string_hash(StrT const &str)
{
HashType remove = static_cast<HashType>(
- static_cast<typename boost::make_unsigned<string_char_type>::type>(
+ static_cast<BOOST_STRING_TYPENAME boost::make_unsigned<string_char_type>::type>(
boost::begin(str)[string_computed_upto_-substring_size_]
));
HashType add = static_cast<HashType>(
- static_cast<typename boost::make_unsigned<string_char_type>::type>(
+ static_cast<BOOST_STRING_TYPENAME boost::make_unsigned<string_char_type>::type>(
boost::begin(str)[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-08-15 15:25:38 EDT (Sun, 15 Aug 2010)
@@ -1,3 +1,13 @@
+// Boost string_algo library knuth_morris_pratt.hpp header file ---------------------------//
+
+// Copyright Stefan Mihaila 2010.
+//
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+// See http://www.boost.org/ for updates, documentation, and revision history.
+
#ifndef BOOST_ALGORITHM_KNUTH_MORRIS_PRATT_HPP
#define BOOST_ALGORITHM_KNUTH_MORRIS_PRATT_HPP
@@ -25,11 +35,7 @@
template <class Range1CharT, class Range2CharT, class ComparatorT, class AllocatorT>
class algorithm
- /*: public boost::algorithm::detail::finder_typedefs<
- RandomAccessRange1T,RandomAccessRange2T,ComparatorT,AllocatorT>*/
{
- //BOOST_ALGORITHM_DETAIL_FINDER_TYPEDEFS(RandomAccessRange1T, RandomAccessRange2T,
- // ComparatorT, AllocatorT)
private:
typedef Range1CharT substring_char_type;
typedef Range2CharT string_char_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-15 15:25:38 EDT (Sun, 15 Aug 2010)
@@ -1,3 +1,13 @@
+// Boost string_algo library naive_search.hpp header file ---------------------------//
+
+// Copyright Stefan Mihaila 2010.
+//
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+// See http://www.boost.org/ for updates, documentation, and revision history.
+
#ifndef BOOST_ALGORITHM_NAIVE_SEARCH_HPP
#define BOOST_ALGORITHM_NAIVE_SEARCH_HPP
@@ -25,8 +35,6 @@
template <class Range1CharT, class Range2CharT, class ComparatorT, class AllocatorT>
class algorithm
- /*: public boost::algorithm::detail::finder_typedefs<
- ForwardRange1T,ForwardRange2T,ComparatorT,AllocatorT>*/
{
private:
typedef Range1CharT substring_char_type;
@@ -65,12 +73,14 @@
return boost::iterator_range<string_iterator_type>(
boost::end(str),boost::end(str));
}
- //! It is guaranteed that each of these two functions will get called at least once before find()
- //! is used.
+
//No precomputation to be done on the substring
+ //It is guaranteed that each of these two functions will get called at least once before find()
+ //is used.
template <class T> inline void on_substring_change(T const&)
{
}
+
//No precomputation to be done on the string
template <class T> inline void on_string_change(T const&)
{
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-15 15:25:38 EDT (Sun, 15 Aug 2010)
@@ -1,3 +1,13 @@
+// Boost string_algo library rabin_karp.hpp header file ---------------------------//
+
+// Copyright Stefan Mihaila 2010.
+//
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+// See http://www.boost.org/ for updates, documentation, and revision history.
+
#ifndef BOOST_ALGORITHM_RABIN_KARP_HPP
#define BOOST_ALGORITHM_RABIN_KARP_HPP
@@ -36,7 +46,7 @@
namespace boost { namespace algorithm {
- //todo Make it work with case insensitive. Find a way to allow providing locales.
+ //todo Make it work with case insensitive for CharT=char? or locales for which tolower(x)==tolower(y)<=>x=(caseins)=y.
//TODO: Implement a version that works with Input iterators
//TODO: Make sure this only works with integral char types
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-15 15:25:38 EDT (Sun, 15 Aug 2010)
@@ -1,3 +1,13 @@
+// Boost string_algo library suffix_array.hpp header file ---------------------------//
+
+// Copyright Stefan Mihaila 2010.
+//
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+// See http://www.boost.org/ for updates, documentation, and revision history.
+
#ifndef BOOST_ALGORITHM_SUFFIX_ARRAY_HPP
#define BOOST_ALGORITHM_SUFFIX_ARRAY_HPP
@@ -27,15 +37,11 @@
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 Range1CharT, class Range2CharT, class ComparatorT, class AllocatorT>
class algorithm;
template <class Range1CharT, class Range2CharT, class AllocatorT>
class algorithm<Range1CharT, Range2CharT, boost::algorithm::is_equal, AllocatorT>
- /*: public boost::algorithm::detail::finder_typedefs<
- RandomAccessRange1T,RandomAccessRange2T,boost::algorithm::is_equal,AllocatorT>*/
{
private:
typedef Range1CharT substring_char_type;
@@ -51,16 +57,16 @@
// no precomputation done on substring
template <class Range1T, class Range2T> void on_substring_change(
- typename boost::algorithm::detail::string_search_ranges<Range1T, Range2T> const &)
- { on_substring_change(typename boost::range_category<Range1T>::type()); }
+ BOOST_STRING_TYPENAME boost::algorithm::detail::string_search_ranges<Range1T, Range2T> const &)
+ { on_substring_change(BOOST_STRING_TYPENAME boost::range_category<Range1T>::type()); }
template <class Range1T, class Range2T>
- inline void on_string_change(typename boost::algorithm::detail::string_search_ranges<Range1T, Range2T> const &ranges)
- { on_string_change(ranges, typename boost::range_category<Range2T>::type()); }
+ inline void on_string_change(BOOST_STRING_TYPENAME boost::algorithm::detail::string_search_ranges<Range1T, Range2T> const &ranges)
+ { on_string_change(ranges, BOOST_STRING_TYPENAME boost::range_category<Range2T>::type()); }
template <class Range1T, class Range2T>
- inline typename boost::iterator_range<typename boost::range_iterator<Range2T>::type>
- find(typename boost::algorithm::detail::string_search_ranges<Range1T, Range2T> const &ranges)
+ inline BOOST_STRING_TYPENAME boost::iterator_range<BOOST_STRING_TYPENAME boost::range_iterator<Range2T>::type>
+ find(BOOST_STRING_TYPENAME boost::algorithm::detail::string_search_ranges<Range1T, Range2T> const &ranges)
{
BOOST_ALGORITHM_DETAIL_COMMON_FINDER_TYPEDEFS(Range1T, Range2T);
@@ -86,7 +92,7 @@
//the substring is smaller than the smallest lexicographic suffix, therefore no matches
//if (std::lexicographical_compare(substr.begin(), substr.end(),str.begin()+pos[0],str.begin()+firstsuffix_end))
- //! \TODO Is this really correct? Just because it starts before other suffix it does not mean there are no matches
+ // TODO Is this really correct? Just because it starts before other suffix it does not mean there are no matches
if (suffix_less(substr, str, 0) ||
std::lexicographical_compare(str.begin()+pos_.back(),str.begin()+lastsuffix_end,substr.begin(),substr.end())
)
@@ -155,7 +161,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();
- typename std::vector<std::size_t, allocator_type>::const_iterator first_match =
+ BOOST_STRING_TYPENAME std::vector<std::size_t, allocator_type>::const_iterator first_match =
std::lower_bound(matches_.begin(), matches_.end(), start_offset);
if (first_match == matches_.end())
return StrT(
@@ -173,7 +179,7 @@
}
template <class Range1T, class Range2T>
- void on_string_change(typename boost::algorithm::detail::string_search_ranges<Range1T, Range2T> const &ranges,
+ void on_string_change(BOOST_STRING_TYPENAME boost::algorithm::detail::string_search_ranges<Range1T, Range2T> const &ranges,
std::random_access_iterator_tag)
{
BOOST_ALGORITHM_DETAIL_COMMON_FINDER_TYPEDEFS(Range1T, Range2T);
@@ -236,8 +242,8 @@
comparator_type comp_;
allocator_type alloc_;
bool found_matches_;
- std::vector<std::size_t, typename allocator_type::template rebind<std::size_t>::other> pos_;
- std::vector<std::size_t, typename allocator_type::template rebind<std::size_t>::other> matches_;
+ std::vector<std::size_t, BOOST_STRING_TYPENAME allocator_type::template rebind<std::size_t>::other> pos_;
+ std::vector<std::size_t, BOOST_STRING_TYPENAME allocator_type::template rebind<std::size_t>::other> matches_;
};
Added: sandbox/SOC/2010/stringalgos/libs/algorithm/string/benchmark/Jamfile
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/stringalgos/libs/algorithm/string/benchmark/Jamfile 2010-08-15 15:25:38 EDT (Sun, 15 Aug 2010)
@@ -0,0 +1 @@
+exe string_search : string_search.cpp ;
\ No newline at end of file
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-15 15:25:38 EDT (Sun, 15 Aug 2010)
@@ -124,8 +124,8 @@
//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//,
+ BOOST_STRING_TYPENAME boost::range_const_iterator<Range1T>::type,
+ BOOST_STRING_TYPENAME boost::range_iterator<Range2T>::type//,
//ComparatorT,AllocatorT>
>
{ };
@@ -313,8 +313,7 @@
b.set_substring(&substr); b.set_string(&str);
std::cout << "Doing almost no work:" << std::endl;
- //!\todo uncomment
- //for (unsigned int i=0; i<5000; ++i) b.find_first();
+ for (unsigned int i=0; i<5000; ++i) b.find_first();
b.output_stats(std::cout);
b.clear();
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-15 15:25:38 EDT (Sun, 15 Aug 2010)
@@ -26,9 +26,9 @@
#include <list>
-#if !defined(BOOST_HAS_RVALUE_REFS) && !defined(BOOST_NO_RVALUE_REFS)
-#define BOOST_HAS_RVALUE_REFS
-#endif
+//#if !defined(BOOST_HAS_RVALUE_REFS) && !defined(BOOST_NO_RVALUE_REFS)
+//#define BOOST_HAS_RVALUE_REFS
+//#endif
//#define BOOST_TEST_ALTERNATIVE_INIT_API
//#define BOOST_TEST_DYN_LINK
@@ -60,7 +60,7 @@
T
range_to_T(RangeT const &range)
{
- typename boost::iterator_range<boost::range_const_iterator<RangeT>::type> range2 = boost::as_literal(range);
+ BOOST_STRING_TYPENAME boost::iterator_range<BOOST_STRING_TYPENAME boost::range_const_iterator<RangeT>::type> range2 = boost::as_literal(range);
return T(
boost::begin(range2),
boost::end(range2)
@@ -137,8 +137,8 @@
//typedef std::string Sequence2T;
typedef std::vector<char> Sequence1T;
typedef std::vector<char> Sequence2T;
- typedef typename boost::finder_t<Sequence1T, Sequence2T, Algorithm> f_t;
- f_t::string_range_type i;
+ typedef BOOST_STRING_TYPENAME boost::finder_t<Sequence1T, Sequence2T, Algorithm> f_t;
+ BOOST_STRING_TYPENAME f_t::string_range_type i;
Sequence1T s1 = range_to_T<Sequence1T>("some test substring"),
s2 = range_to_T<Sequence1T>("another test substring");
@@ -191,7 +191,6 @@
BOOST_CHECK(boost::equal(f5.get_string_range(), S1));
BOOST_CHECK_EQUAL(f5.find_next_index(), 27);
- //!\todo fix
# ifdef BOOST_HAS_RVALUE_REFS
f_t f6( (Sequence1T(s1)), &S1); // rvalue, ptr
BOOST_CHECK(boost::equal(f6.get_substring_range(),s1));
@@ -256,7 +255,6 @@
// (0, 0)
f.set_substring(&substr);
f.set_string(&str);
- //!\todo deal with these
//BOOST_CHECK_EQUAL(f.find_first_index(), 0);
//BOOST_CHECK_EQUAL(f.find_next_index(), -1);
@@ -292,7 +290,6 @@
BOOST_CHECK_EQUAL(boost::distance(f.find_first()), 44);
BOOST_CHECK_EQUAL(boost::distance(f.find_next()), 0);
- //!\todo remove the useless checkpoints 'n stuff
// (0, 1) (1, 2) (2, 3) (3, 4) (4, 5) (5, 6) (6, 7) (7, 8) (8, 9) (9, 10) (10, 11) (11, 12) (12, 13) (13, 14) (14, 15) (15, 16) (16, 17)
assign_literal(substr,
@@ -307,7 +304,6 @@
f.find_reset();
for (unsigned int i=0; i<=16; ++i)
BOOST_CHECK_EQUAL(f.find_next_index(), i);
- BOOST_CHECKPOINT("WIN0");
//
assign_literal(substr,
@@ -327,7 +323,6 @@
f.find_reset();
for (unsigned int i=0; i<=21; i += 3)
BOOST_CHECK_EQUAL(f.find_next_index(), i);
- BOOST_CHECKPOINT("WIN");
// (0, 7) (1, 8) (2, 9) (3, 10) (4, 11) (5, 12) (6, 13) (7, 14) (8, 15) (9, 16) (10, 17)
assign_literal(substr,
"AAAAAAA",7);
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