Boost-Commit :

Date view	Thread view	Subject view	Author view

Subject: [Boost-commit] svn:boost r64839 - in sandbox/SOC/2010/stringalgos: boost/algorithm/string boost/algorithm/string/finder boost/algorithm/string/finder/detail boost/algorithm/string/string_search libs/algorithm/string/benchmark libs/algorithm/string/doc libs/algorithm/string/test
From: mstefanro_at_[hidden]
Date: 2010-08-15 21:12:02

Next message: barend.gehrels_at_[hidden]: "[Boost-commit] svn:boost r64840 - sandbox/geometry/boost/geometry/iterators"
Previous message: vicente.botet_at_[hidden]: "[Boost-commit] svn:boost r64838 - sandbox/chrono/boost/chrono"

Author: mstefanro
Date: 2010-08-15 21:11:58 EDT (Sun, 15 Aug 2010)
New Revision: 64839
URL: http://svn.boost.org/trac/boost/changeset/64839

Log:
[GSoC2010][StringAlgo] More doc and refactoring
Added:
   sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/detail/functor_finders.hpp
      - copied unchanged from r64835, /sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/detail/generated_finders.hpp
   sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/functor_finders.hpp
      - copied unchanged from r64835, /sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/generated_finders.hpp
Removed:
   sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/detail/generated_finders.hpp
   sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/generated_finders.hpp
Text files modified:
   sandbox/SOC/2010/stringalgos/boost/algorithm/string/benchmark_finder.hpp | 24 ++++----
   sandbox/SOC/2010/stringalgos/boost/algorithm/string/find.hpp | 2
   sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder.hpp | 2
   sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/finder.hpp | 13 ++--
   sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/finder_generators.hpp | 4
   sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/simplified_finder.hpp | 35 +++++++-----
   sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/boyer_moore.hpp | 2
   sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/knuth_morris_pratt.hpp | 50 ++++++++++++++-----
   sandbox/SOC/2010/stringalgos/libs/algorithm/string/benchmark/string_search.cpp | 10 +-
   sandbox/SOC/2010/stringalgos/libs/algorithm/string/doc/Jamfile.v2 | 12 +++-
   sandbox/SOC/2010/stringalgos/libs/algorithm/string/doc/intro.xml | 29 ++++------
   sandbox/SOC/2010/stringalgos/libs/algorithm/string/doc/quickref.xml | 101 ++++++++++++++++++++++++++-------------
   sandbox/SOC/2010/stringalgos/libs/algorithm/string/doc/usage.xml | 51 +++++++++++++++----
   sandbox/SOC/2010/stringalgos/libs/algorithm/string/test/finder_test.cpp | 1
   14 files changed, 214 insertions(+), 122 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 21:11:58 EDT (Sun, 15 Aug 2010)
@@ -76,7 +76,7 @@
     */
     template <class Range1T, class Range2T, class AlgorithmSequenceT,
     class ComparatorT = boost::algorithm::is_equal>
- class benchmark_finder
+ class benchmark_finder_t
     {
         typedef std::allocator<std::size_t> allocator_type_;
     public:
@@ -84,8 +84,8 @@
         BOOST_ALGORITHM_DETAIL_FINDER_TYPEDEFS2(ComparatorT, allocator_type_);
     public:

- //! \copydoc simplified_finder_t::set_substring
- //! \see \ref simplified_finder_t::set_substring
+ //! \copydoc boost::algorithm::simplified_finder_t::set_substring
+ //! \see boost::algorithm::simplified_finder_t::set_substring
         void set_substring (substring_type
             const *const substring)
         {
@@ -96,8 +96,8 @@
             trusted_finder.set_substring(substring);
         }

- //! \copydoc simplified_finder_t::set_string
- //! \see \ref simplified_finder_t::set_string
+ //! \copydoc boost::algorithm::simplified_finder_t::set_string
+ //! \see boost::algorithm::simplified_finder_t::set_string
         void set_string (string_type *const string)
         {
             boost::phoenix::function<finder_set_string> f;
@@ -112,24 +112,24 @@
         void clear ()
         { boost::fusion::for_each(finders, clear_stats()); }

- //! \copydoc simplified_finder_t::find_reset
- //! \see \ref simplified_finder_t::find_reset
+ //! \copydoc boost::algorithm::simplified_finder_t::find_reset
+ //! \see boost::algorithm::simplified_finder_t::find_reset
         void find_reset()
         {
             boost::fusion::for_each(finders, finder_reset());
             trusted_finder.find_reset();
         }

- //! \copydoc simplified_finder_t::find_next
- //! \see \ref simplified_finder_t::find_next
+ //! \copydoc boost::algorithm::simplified_finder_t::find_next
+ //! \see boost::algorithm::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
+ //! \copydoc boost::algorithm::simplified_finder_t::find_first
+ //! \sa boost::algorithm::simplified_finder_t::find_first
         string_range_type find_first()
         { find_reset(); return find_next(); }

@@ -283,6 +283,6 @@
     };
} }

-namespace boost { using algorithm::benchmark_finder; }
+namespace boost { using algorithm::benchmark_finder_t; }

#endif

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 21:11:58 EDT (Sun, 15 Aug 2010)
@@ -24,7 +24,7 @@
#include <boost/range/as_literal.hpp>

#include <boost/algorithm/string/finder/finder_generators.hpp>
-#include <boost/algorithm/string/finder/generated_finders.hpp>
+#include <boost/algorithm/string/finder/functor_finders.hpp>
#include <boost/algorithm/string/finder/default_search_algorithm.hpp>
#include <boost/algorithm/string/compare.hpp>
#include <boost/algorithm/string/constants.hpp>

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 21:11:58 EDT (Sun, 15 Aug 2010)
@@ -21,7 +21,7 @@
#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/functor_finders.hpp>
#include <boost/algorithm/string/finder/finder_generators.hpp>

/*! \file

Deleted: sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/detail/generated_finders.hpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/detail/generated_finders.hpp 2010-08-15 21:11:58 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/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 21:11:58 EDT (Sun, 15 Aug 2010)
@@ -75,8 +75,9 @@
     {
         //TODO:: Maybe write a String concept?
         //TODO:: Currently, there's a SGI Sequence Concept implemented by Boost.ConceptCheck,
- //! but std::string does not obey this concept, which means that even calling these template
- //! parameters sequences is wrong.
+ // but std::string does not obey this concept, which means that even calling these template
+ // parameters sequences is wrong.
+ private:
         BOOST_CONCEPT_ASSERT((boost::Container<Sequence1T>));
         BOOST_CONCEPT_ASSERT((boost::Container<Sequence2T>));
     public:
@@ -348,8 +349,8 @@
                 after the passed iterators become invalid.
             \note This is equivalent to:
                 <code>finder::string_range_type range(string_begin,string_end);
- finder.set_string(&range);
- return finder.find_first();
+finder.set_string(&range);
+return finder.find_first();
                 </code>
                 */
         string_range_type operator()(string_iterator_type &string_begin,
@@ -460,8 +461,8 @@
             \post The internal find offset is set immediately after the current match starts.
             \warning If the match is performed against the internal text, then an iterator range in the
                 internal text will be returned. Modifying the contents of that range will modify the internal text,
- making it necessary to call \ref use_internal_string() afterwards. This call will switch to using the internal
- text (in our case, it already does that, so it will just "refresh") and will force the string search algorithm
+ making it necessary to call \ref use_internal_string() afterwards. \ref use_internal_string() will switch to using the internal
+ text (or, in case it's already using it, update the range with new, valid, iterators) and will force the string search algorithm
                 to recompute its information on the new text.
         */
         string_range_type find_next()

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 21:11:58 EDT (Sun, 15 Aug 2010)
@@ -12,13 +12,13 @@
#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/functor_finders.hpp>
#include <boost/algorithm/string/finder/default_search_algorithm.hpp>
#include <boost/algorithm/string/compare.hpp>

/*! \file
Defines finder generators. They are mostly deprecated functions
- returning instances of finder types defined in \headername generated_finders.hpp.
+ returning instances of finder types defined in \headername functor_finders.hpp.
Finder generators are preserved for backward compatibility, but their use is discouraged.
*/

Deleted: sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/generated_finders.hpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/generated_finders.hpp 2010-08-15 21:11:58 EDT (Sun, 15 Aug 2010)
+++ (empty file)
@@ -1,364 +0,0 @@
-// 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/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>
-#include <boost/range/as_literal.hpp>
-#include <boost/range/value_type.hpp>
-#include <boost/range/iterator_range.hpp>
-
-#include <boost/iterator/iterator_traits.hpp>
-
-#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 {
-
- //! 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:
-
- //! 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>
- BOOST_STRING_TYPENAME boost::iterator_range<Iterator2T>
- operator()(Iterator2T const &string_begin, Iterator2T const &string_end)
- {
- typedef BOOST_STRING_TYPENAME boost::iterator_range<Iterator2T> Range2T;
-
- 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_begin;
- if (first_call_) { algorithm_.on_substring_change(ranges); first_call_ = false; }
- algorithm_.on_string_change(ranges);
- return algorithm_.find(ranges);
- }
- private:
- 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;
-
- BOOST_STRING_TYPENAME boost::iterator_range<substring_iterator_type> substring_range_;
- algorithm_type algorithm_;
- bool first_call_;
- };
-
- //! 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:
- //! 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>
- BOOST_STRING_TYPENAME boost::iterator_range<Iterator2T>
- operator()(Iterator2T const &string_begin, Iterator2T const &string_end)
- {
- 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>
- 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 BOOST_STRING_TYPENAME boost::iterator_range<Iterator2T> Range2T;
- BOOST_ALGORITHM_DETAIL_COMMON_FINDER_TYPEDEFS(Range1T, Range2T);
- BOOST_ALGORITHM_DETAIL_UNCOMMON_FINDER_TYPEDEFS(Range1T, Range2T);
-
- 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_)),
- substring_reverse_iterator_type(boost::begin(substring_range_))
- );
- ranges.str = boost::make_iterator_range(
- string_reverse_iterator_type(string_end),
- string_reverse_iterator_type(string_begin)
- );
- ranges.offset = string_reverse_iterator_type(string_end);
- if (first_call_bidi_)
- {
- algorithm_.on_substring_change(ranges);
- first_call_bidi_ = false;
- first_call_forw_ = true;
- }
- algorithm_.on_string_change(ranges);
- string_reverse_range_type const &ret = algorithm_.find(ranges);
-
- //no match
- 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
- return boost::make_iterator_range(boost::end(ret).base(), boost::begin(ret).base());
- }
-
- //implementation of last_finder_t when all we have are forward iterators
- //todo test if this works properly
- template <class Iterator2T>
- 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 BOOST_STRING_TYPENAME boost::iterator_range<Iterator2T> Range2T;
-
- 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_begin;
-
- if (first_call_forw_)
- {
- algorithm_.on_substring_change(ranges);
- first_call_forw_ = false;
- first_call_bidi_ = true;
- }
- algorithm_.on_string_change(ranges);
- Range2T prev, crt = boost::make_iterator_range(string_end, string_end);
- for (;;)
- {
- prev = crt;
- crt = algorithm_.find(ranges);
- if (boost::begin(crt) == string_end) break;
- else { ranges.offset = boost::begin(crt); ++ranges.offset; }
- }
- return prev;
- }
- 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;
-
- BOOST_STRING_TYPENAME boost::iterator_range<substring_iterator_type> substring_range_;
- algorithm_type algorithm_;
- bool first_call_bidi_, first_call_forw_;
- };
-
- //! 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:
-
- //! 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>
- BOOST_STRING_TYPENAME boost::iterator_range<Iterator2T>
- operator()(Iterator2T const &string_begin, Iterator2T const &string_end)
- {
- if (n_ < 0)
- 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>
- BOOST_STRING_TYPENAME boost::iterator_range<Iterator2T>
- find(Iterator2T const &string_begin, Iterator2T const &string_end)
- {
- 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_begin, string_end);
- ranges.offset = string_begin;
-
- if (first_call_forw_)
- {
- algorithm_.on_substring_change(ranges);
- first_call_forw_ = false;
- first_call_bidi_ = true;
- }
- algorithm_.on_string_change(ranges);
-
- Range2T ret;
- for (int n = 0; n <= n_; ++n)
- {
- ret = algorithm_.find(ranges);
- if (boost::begin(ret) == string_end)
- return boost::make_iterator_range(string_end, string_end);
- else { ranges.offset=boost::begin(ret); ++ranges.offset; }
- }
- return ret;
- }
-
- //find nth, for n < 0
- template <class Iterator2T>
- 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 BOOST_STRING_TYPENAME boost::iterator_range<Iterator2T> Range2T;
- BOOST_ALGORITHM_DETAIL_COMMON_FINDER_TYPEDEFS(Range1T, Range2T);
- BOOST_ALGORITHM_DETAIL_UNCOMMON_FINDER_TYPEDEFS(Range1T, Range2T);
-
- 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_)),
- substring_reverse_iterator_type(boost::begin(substring_range_))
- );
- ranges.str = boost::make_iterator_range(
- string_reverse_iterator_type(string_end),
- string_reverse_iterator_type(string_begin)
- );
- ranges.offset = string_reverse_iterator_type(string_end);
-
- if (first_call_bidi_)
- {
- algorithm_.on_substring_change(ranges);
- first_call_bidi_ = false;
- first_call_forw_ = true;
- }
- algorithm_.on_string_change(ranges);
-
- string_reverse_range_type ret;
- int n_2 = -n_ - 1;
- for (int n = 0; n <= n_2; ++n)
- {
- ret = algorithm_.find(ranges);
- 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 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;
-
- BOOST_STRING_TYPENAME boost::iterator_range<substring_iterator_type> substring_range_;
- int n_;
- algorithm_type algorithm_;
- bool first_call_forw_, first_call_bidi_;
- };
-} }
-
-namespace boost
-{
- using algorithm::first_finder_t;
- using algorithm::last_finder_t;
- using algorithm::nth_finder_t;
-}
-
-#endif // BOOST_ALGORITHM_GENERATED_FINDERS_HPP

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 21:11:58 EDT (Sun, 15 Aug 2010)
@@ -83,12 +83,14 @@
                 for storing precomputed data if necessary
             \warning The ranges that substr and str point to must not change during the lifetime of the finder,
                 otherwise one would have to re-set the ranges:
- <example> <code>
- string substr("a"), str("b");
- simplified_finder_t<string,string,..> finder(&substr, &str);
- substr = "b"; // substr has changed, invalidating the internally stored range
- finder.set_substring(&substr); // re-set the substring so the finder now uses the new, valid range
- </code> </example>
+ <example>
+<code>
+string substr("a"), str("b");
+simplified_finder_t<string,string,..> finder(&substr, &str);
+substr = "b"; // substr has changed, invalidating the internally stored range
+finder.set_substring(&substr); // re-set the substring so the finder now uses the new, valid range
+</code>
+ </example>
         */
         simplified_finder_t(Range1T const *const substr, Range2T *const str,
             ComparatorT comparator = ComparatorT(), AllocatorT allocator = AllocatorT())
@@ -121,7 +123,11 @@
         void set_substring (substring_type const *const substr)
         { ranges_.substr = boost::as_literal(*substr); substring_has_changed_ = true; }

- //! \overload
+ //! Change the pattern (substring) to be searched.
+ /*!
+ \param string_begin An iterator indicating the beginning of the pattern to be searched.
+ \param string_end An iterator indicating the end of the pattern to be searched.
+ */
         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);
@@ -136,7 +142,11 @@
         void set_string (string_type *const str)
         { ranges_.str = boost::as_literal(*str); string_has_changed_ = true; }

- //!\overload
+ //! Change the text in which to search.
+ /*!
+ \param string_begin An iterator indicating the beginning of the text to be searched.
+ \param string_end An iterator indicating the end of the text to be searched.
+ */
         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);
@@ -150,9 +160,7 @@
         //! Finds the first occurrence of the pattern in the text (substring in the string)
         /*!
             Equivalent to:
- \code
- find_reset(); return find_next();
- \endcode
+ <code>find_reset(); return find_next();</code>
         */
         string_range_type find_first ()
         {
@@ -173,10 +181,7 @@
                 would cause undefined behavior. Make sure you call set_string() if you want to use this finder
                 after the passed iterators become invalid.
             \note This is equivalent to:
- <code>
- finder.set_string(string_begin, string_end);
- return finder.find_first();
- </code>
+ <code>finder.set_string(string_begin, string_end); return finder.find_first();</code>
             */
         string_range_type operator()(string_iterator_type const &string_begin,
             string_iterator_type const &string_end)

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 21:11:58 EDT (Sun, 15 Aug 2010)
@@ -152,7 +152,7 @@

             //precomputation on pattern=bidirectional range
             template <class RangeT>
- void on_substring_change(RangeT const &substr, std::bidirectional_iterator_tag)
+ void on_substring_change(RangeT const &substr, std::random_access_iterator_tag)
             {

                 substr_size_ = boost::distance(substr);

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 21:11:58 EDT (Sun, 15 Aug 2010)
@@ -85,9 +85,9 @@
                 substring_range_type const &substr = ranges.substr;
                 string_iterator_type start = ranges.offset;

- std::size_t str_idx = start - boost::begin(str),
- str_size = boost::end(str) - boost::begin(str), substr_idx = 0,
+ std::size_t str_size = boost::end(str) - boost::begin(str),
                     substr_size = boost::end(substr) - boost::begin(substr);
+ std::size_t str_idx = start - boost::begin(str), substr_idx = 0;

                 if (boost::begin(substr) == boost::end(substr))
                     return boost::iterator_range<string_iterator_type>(
@@ -144,28 +144,50 @@

                 //Invariant: 0 <= failure_func[i] <= i, i=0..m-1

-
- std::size_t i = 0, j = 1, substr_size = boost::end(substr) - boost::begin(substr);
+ typedef typename boost::range_const_iterator<RangeT>::type substring_iterator_type;
+
+ std::size_t substr_size = boost::end(substr) - boost::begin(substr);
                 failure_func.clear();
                 failure_func.reserve(substr_size);
                 failure_func.push_back(0); // failure_func[0] = 0
- //std::size_t capacity = failure_func.capacity();
- while (j < substr_size)
+
+ if (substr_size < 2) return;
+
+ //std::size_t i = 0, j = 1;
+ substring_iterator_type i = boost::begin(substr), j = boost::begin(substr)+1;
+
+ //while (j < substr_size)
+ do
                 {
- while (i > 0 && !comp_(*(boost::begin(substr)+i), *(boost::begin(substr)+j)))
- i = failure_func[i-1];
- while (i == 0 && j < substr_size &&
- !comp_(*(boost::begin(substr)+0),*(boost::begin(substr)+j)))
+ //while (i > 0 && !comp_(*(boost::begin(substr)+i), *(boost::begin(substr)+j)))
+ // i = failure_func[i-1];
+ while (i != boost::begin(substr) && !comp_(*i,*j))
+ i = boost::begin(substr) + failure_func[(i-boost::begin(substr))-1];
+
+ //while (i == 0 && j < substr_size &&
+ // !comp_(*(boost::begin(substr)+0),*(boost::begin(substr)+j)))
+ while (i == boost::begin(substr) && j != boost::end(substr) &&
+ !comp_(*i,*j))
                     {
                         //Invariant: i == 0 and substr[0] != substr[j], which means failure_func[j]=0
                         failure_func.push_back(0);
                         ++j;
                     }
                     //Invariant: j is out of bounds or P[i]==P[j], meaning failure_func[j]=i+1
- if (j < substr_size) failure_func.push_back(i+1);
- ++j; ++i;
- }
- //assert(failure_func.capacity() == capacity);
+ /*if (j < substr_size)
+ {
+ failure_func.push_back(i+1);
+ ++j; ++i;
+ }
+ else break;*/
+ if (j != boost::end(substr))
+ {
+ failure_func.push_back((i-boost::begin(substr))+1);
+ ++j; ++i;
+ }
+ else break;
+ } while (j != boost::end(substr));
+ //while (j < substr_size);
             }

         };

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 21:11:58 EDT (Sun, 15 Aug 2010)
@@ -298,9 +298,9 @@

     std::string substr("hello world"), str("hello world");

- boost::benchmark_finder<std::string, std::string,
+ boost::benchmark_finder_t<std::string, std::string,
         boost::mpl::vector<
- boost::naive_search,
+ //boost::naive_search,
             boost::knuth_morris_pratt//,
             //boost::boyer_moore,
             //boost::suffix_array_search,
@@ -321,8 +321,8 @@
     std::string const &benchmark_path = "E:/gsoc-boost/benchmarks";

     std::vector<std::string> benchmark_files = list_of
- ("dblp.xml.200MB") ("dna.200MB") ("english.200MB") ("pitches.50MB")
- ("proteins.200MB") ("sources.200MB") ("random1.50MB") ("binary.50MB");
+ /*("dblp.xml.200MB")*/ ("dna.200MB") /*("english.200MB") ("pitches.50MB")
+ ("proteins.200MB") ("sources.200MB") ("random1.50MB") ("binary.50MB")*/;
     boost::for_each(benchmark_files, arg1 = benchmark_path + "/" + arg1);

@@ -337,7 +337,7 @@
     bool substr_change = false;
     try {
         //Category 1
- for (unsigned int test = 0; test <= 5; ++test)
+ for (unsigned int test = 4; test <= 4; ++test)
         {

             BOOST_FOREACH(std::string fn, benchmark_files)

Modified: sandbox/SOC/2010/stringalgos/libs/algorithm/string/doc/Jamfile.v2
==============================================================================
--- sandbox/SOC/2010/stringalgos/libs/algorithm/string/doc/Jamfile.v2 (original)
+++ sandbox/SOC/2010/stringalgos/libs/algorithm/string/doc/Jamfile.v2 2010-08-15 21:11:58 EDT (Sun, 15 Aug 2010)
@@ -29,17 +29,21 @@
     [ glob ../../../../boost/algorithm/string/compare.hpp ]
     [ glob ../../../../boost/algorithm/string/constants.hpp ]
     [ glob ../../../../boost/algorithm/string/case_conv.hpp ]
- [ glob ../../../../boost/algorithm/string/find.hpp ]
+ [ glob ../../../../boost/algorithm/string/finder/default_search_algorithm.hpp ]
+ [ glob ../../../../boost/algorithm/string/finder/simplified_finder.hpp ]
+ [ glob ../../../../boost/algorithm/string/finder/finder.hpp ]
+ [ glob ../../../../boost/algorithm/string/finder/functor_finders.hpp ]
+ [ glob ../../../../boost/algorithm/string/finder/finder_generators.hpp ]
     [ glob ../../../../boost/algorithm/string/finder.hpp ]
     [ glob ../../../../boost/algorithm/string/finder_aliases.hpp ]
     [ glob ../../../../boost/algorithm/string/benchmark_finder.hpp ]
- [ glob ../../../../boost/algorithm/string/string_search.hpp ]
     [ glob ../../../../boost/algorithm/string/string_search/boyer_moore.hpp ]
     [ glob ../../../../boost/algorithm/string/string_search/knuth_morris_pratt.hpp ]
     [ glob ../../../../boost/algorithm/string/string_search/naive_search.hpp ]
     [ glob ../../../../boost/algorithm/string/string_search/rabin_karp.hpp ]
     [ glob ../../../../boost/algorithm/string/string_search/suffix_array.hpp ]
-
+ [ glob ../../../../boost/algorithm/string/string_search.hpp ]
+ [ glob ../../../../boost/algorithm/string/find.hpp ]
     [ glob ../../../../boost/algorithm/string/find_iterator.hpp ]
     [ glob ../../../../boost/algorithm/string/trim.hpp ]
     [ glob ../../../../boost/algorithm/string/predicate.hpp ]
@@ -59,7 +63,7 @@
     <doxygen:param>MACRO_EXPANSION=YES
     <doxygen:param>EXPAND_ONLY_PREDEF=YES
     <doxygen:param>SEARCH_INCLUDES=YES
- <doxygen:param>PREDEFINED="BOOST_STRING_TYPENAME=typename \"BOOST_STATIC_CONSTANT(type,var)=static const type var; BOOST_HAS_RVALUE_REFS\""
+ <doxygen:param>PREDEFINED="BOOST_STRING_TYPENAME=typename; BOOST_STATIC_CONSTANT(type,var)=static const type var; BOOST_HAS_RVALUE_REFS;"
     ;

Modified: sandbox/SOC/2010/stringalgos/libs/algorithm/string/doc/intro.xml
==============================================================================
--- sandbox/SOC/2010/stringalgos/libs/algorithm/string/doc/intro.xml (original)
+++ sandbox/SOC/2010/stringalgos/libs/algorithm/string/doc/intro.xml 2010-08-15 21:11:58 EDT (Sun, 15 Aug 2010)
@@ -1,32 +1,27 @@
-<?xml version="1.0" encoding="utf-8"?>
-<!DOCTYPE library PUBLIC "-//Boost//DTD BoostBook XML V1.0//EN"
-"http://www.boost.org/tools/boostbook/dtd/boostbook.dtd">
-
-
+ï»¿<?xml version="1.0" encoding="utf-8"?>
+<!DOCTYPE library PUBLIC "-//Boost//DTD BoostBook XML V1.0//EN" "http://www.boost.org/tools/boostbook/dtd/boostbook.dtd"[]>

-
<section id="string_algo.intro" last-revision="$Date$">
- <title>Introduction</title>
-
- <para>
+ <title>Introduction</title>
+ <para>
         The String Algorithm Library provides a generic implementation of
         string-related algorithms which are missing in STL. It is an extension
         to the algorithms library of STL and it includes trimming, case conversion,
- predicates and find/replace functions. All of them come in different variants
- so it is easier to choose the best fit for a particular need.
+ predicates and find/replace/split functions. All of them come in different variants
+ so it is easy to choose the best fit for a particular need.
     </para>
- <para>
+ <para>
         The implementation is not restricted to work with a particular container
         (like <code>std::basic_string</code>), rather it is as generic as
         possible. This generalization is not compromising the performance since
         algorithms are using container specific features when it means a performance
         gain.
     </para>
- <para>
- <emphasis role="bold">
+ <para>
+ <emphasis role="bold">
             Important note: In this documentation we use term <emphasis>string</emphasis> to
             designate a sequence of <emphasis>characters</emphasis> stored in an arbitrary container.
             A <emphasis>string</emphasis> is not restricted to <code>std::basic_string</code> and
@@ -36,11 +31,11 @@
         Consult the <link linkend="string_algo.design">design chapter</link> to see precise specification of
         supported string types.
     </para>
- <para>
+ <para>
         The library interface functions and classes are defined in namespace <code>boost::algorithm</code>, and
         they are lifted into namespace <code>boost</code> via using declaration.
     </para>
- <para>
+ <para>
         The documentation is divided into several sections. For a quick start read the
         <link linkend="string_algo.usage">Usage</link> section followed by
         <link linkend="string_algo.quickref">Quick Reference</link>.
@@ -51,4 +46,4 @@
         and algorithms. Functions and classes in the reference are organized by the headers in which they are defined.
         The reference contains links to the detailed description for every entity in the library.
     </para>
-</section>
+</section>
\ No newline at end of file

Modified: sandbox/SOC/2010/stringalgos/libs/algorithm/string/doc/quickref.xml
==============================================================================
--- sandbox/SOC/2010/stringalgos/libs/algorithm/string/doc/quickref.xml (original)
+++ sandbox/SOC/2010/stringalgos/libs/algorithm/string/doc/quickref.xml 2010-08-15 21:11:58 EDT (Sun, 15 Aug 2010)
@@ -1,6 +1,7 @@
ï»¿<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE library PUBLIC "-//Boost//DTD BoostBook XML V1.0//EN" "http://www.boost.org/tools/boostbook/dtd/boostbook.dtd"[]>

@@ -505,8 +506,62 @@
   </section>
   <section>
     <title>Finders</title>
+ <table id="string_algo.quickref.finder_types">
+ <title>Finder types</title>
+ <tgroup cols="2" align="left">
+ <thead>
+ <row>
+ <entry>Type</entry>
+ <entry>Description</entry>
+ </row>
+ </thead>
+ <tbody>
+ <row>
+ <entry>
+ <classname>finder_t</classname>
+ </entry>
+ <entry>Allows the user to perform multiple searches using a given string search algorithm.
+The precomputed data (either on the text, the pattern, or both, depending on the chosen search algorithm) is kept from one search to another, potentially making future searches faster if either the pattern or the text remain unchanged.
+The interface of this finder provides constructors and setters taking both references (in which case copies are made) and pointers.</entry>
+ </row>
+ <row>
+ <entry>
+ <classname>simplified_finder_t</classname>
+ </entry>
+ <entry>Behaves very similarly to <classname>finder_t</classname>, but it supports a more limited set of constructors and setters (only the ones taking pointers). When efficiency is very important, this should be preferred over <classname>finder_t</classname>.</entry>
+ </row>
+ <row>
+ <entry>
+ <classname>benchmark_finder_t</classname>
+ </entry>
+ <entry>Finder with a similar interface to that of <classname>simplified_finder_t</classname>, whose purpose is to benchmark various string search algorithms.</entry>
+ </row>
+ <row>
+ <entry>
+ <classname>first_finder_t</classname>
+ </entry>
+ <entry>Functor finder that can be passed to find/replace/split algorithms.
+Works as a function object returning the first occurrence of a pattern in a string.</entry>
+ </row>
+ <row>
+ <entry>
+ <classname>nth_finder_t</classname>
+ </entry>
+ <entry>Functor finder that can be passed to find/replace/split algorithms.
+Works as a function object returning the N-th occurrence of a pattern in a string.</entry>
+ </row>
+ <row>
+ <entry>
+ <classname>last_finder_t</classname>
+ </entry>
+ <entry>Functor finder that can be passed to find/replace/split algorithms.
+Works as a function object returning the last occurrence of a pattern in a string.</entry>
+ </row>
+ </tbody>
+ </tgroup>
+ </table>
     <table>
- <title>Finder generators</title>
+ <title>Finder generators <emphasis>(deprecated)</emphasis></title>
       <tgroup cols="3" align="left">
         <thead>
           <row>
@@ -575,33 +630,6 @@
         </tbody>
       </tgroup>
     </table>
- <table>
- <title>Finder types</title>
- <tgroup cols="2" align="left">
- <thead>
- <row>
- <entry>Type</entry>
- <entry>Description</entry>
- </row>
- </thead>
- <tbody>
- <row>
- <entry>
- <classname>finder_t</classname>
- </entry>
- <entry>Allows the user to perform multiple searches using a given string search algorithm.
-The precomputed data (either on the text, the pattern, or both, depending on the chosen search algorithm) is kept from one search to another, potentially making future searches faster if either the pattern or the text remain unchanged.
-The interface of this finder provides constructors and setters taking both references (in which case copies are made) and pointers.</entry>
- </row>
- <row>
- <entry>
- <classname>simplified_finder_t</classname>
- </entry>
- <entry>Behaves very similarly to <classname>finder_t</classname>, but it supports a more limited set of constructors and setters (only the ones taking pointers).</entry>
- </row>
- </tbody>
- </tgroup>
- </table>
     <para>For information on the string search algorithms, see <xref linkend="string_algo.quickref.string_search_algorithms"></xref></para>
   </section>
   <section>
@@ -781,7 +809,7 @@
       </tgroup>
     </table>
   </section>
- <section id="string_search_algorithms">
+ <section id="string_algo.quickref.string_search_algorithms">
     <title>String search algorithms</title>
     <table>
       <title>String search algorithms</title>
@@ -792,6 +820,7 @@
             <entry>Iterator requirements</entry>
             <entry>Comparators</entry>
             <entry>Complexity</entry>
+ <entry>Exact</entry>
             <entry>Type</entry>
           </row>
         </thead>
@@ -801,6 +830,7 @@
             <entry>Forward Iterator</entry>
             <entry>Any</entry>
             <entry>O(n*m) worst-case</entry>
+ <entry>Yes</entry>
             <entry>
               <classname alt="boost::algorithm::naive_search">naive_search</classname>
             </entry>
@@ -811,6 +841,7 @@
             <entry>Any</entry>
             <entry>Pattern preprocessing: O(m)
Finding: O(n)</entry>
+ <entry>Yes</entry>
             <entry>
               <classname alt="boost::algorithm::knuth_morris_pratt">knuth_morris_pratt</classname>
             </entry>
@@ -822,6 +853,7 @@
               <functionname>is_equal()</functionname>for any CharT and <functionname>is_iequal()</functionname> only for CharT=char</entry>
             <entry>Pattern preprocessing: O(m)
Finding: O(n/m) average, O(n) worst-case</entry>
+ <entry>Yes</entry>
             <entry>
               <classname alt="boost::algorithm::boyer_moore">boyer_moore</classname>
             </entry>
@@ -831,10 +863,12 @@
             <entry>Random Access Iterators
Note: will support Input Iterators</entry>
             <entry>Only <functionname>is_equal()</functionname> , with CharT an integral type</entry>
- <entry>Pattern preprocessing: O(m)
-Finding: O(n) average, O(n*m) worst-case</entry>
+ <entry>Pattern preprocessing: O(m) Finding: O(n)</entry>
+ <entry>
+ <emphasis>No (can yield false negatives, but not false positives)</emphasis>
+ </entry>
             <entry>
- <classname alt="boost::algorithm::rabin_karp">rabin_karp32</classname>, <classname alt="boost::algorithm::rabin_karp64">rabin_karp64</classname>, <classname alt="boost::algorithm::rabin_karp_algorithm">rabin_karp_algorithm</classname></entry>
+ <classname alt="boost::algorithm::rabin_karp32">rabin_karp32</classname>, <classname alt="boost::algorithm::rabin_karp64">rabin_karp64</classname>, <classname alt="boost::algorithm::rabin_karp_algorithm">rabin_karp_algorithm</classname></entry>
           </row>
           <row>
             <entry>Suffix array</entry>
@@ -842,8 +876,9 @@
             <entry>Only <classname>is_equal()</classname></entry>
             <entry>Text preprocessing: O(n)
Find: ...?</entry>
+ <entry>Yes</entry>
             <entry>
- <classname alt="boost::algorithm::suffix_array">suffix_array</classname>
+ <classname alt="boost::algorithm::suffix_array_search">suffix_array_search</classname>
             </entry>
           </row>
         </tbody>

Modified: sandbox/SOC/2010/stringalgos/libs/algorithm/string/doc/usage.xml
==============================================================================
--- sandbox/SOC/2010/stringalgos/libs/algorithm/string/doc/usage.xml (original)
+++ sandbox/SOC/2010/stringalgos/libs/algorithm/string/doc/usage.xml 2010-08-15 21:11:58 EDT (Sun, 15 Aug 2010)
@@ -1,6 +1,7 @@
ï»¿<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE library PUBLIC "-//Boost//DTD BoostBook XML V1.0//EN" "http://www.boost.org/tools/boostbook/dtd/boostbook.dtd"[]>

@@ -348,21 +349,49 @@
   </section>
   <section>
     <title>Finders</title>
- <para>Finders offer a greater degree of control over what string search algorithms you would like to use for finding. </para>
- <para>They are especially useful if multiple searches are to be performed and the string or the substring do not change every iteration (because most string search algorithms precompute information on either the sought string or the text, meaning subsequent searches on the pattern or the text can be faster).</para>
- <para>There are two finder types, <classname alt="boost::algorithm::finder_t">finder_t </classname>and <classname alt="boost::algorithm::simplified_finder_t">simplified_finder_t </classname>, as well as some finder generators: <functionname>first_finder</functionname>, <functionname>last_finder</functionname>, <functionname>nth_finder</functionname>etc.<programlisting>std::string random_saying =
+ <para>Finders offer a greater degree of control over what string search algorithms you would like to use for finding. Some of them may also be used as parameters to find/replace/split functions. </para>
+ <para>They are especially useful if multiple searches are to be performed and the string or the substring do not change every iteration (because most string search algorithms precompute information on either the sought string or the text, meaning subsequent searches can be faster).</para>
+ <para>There currently are 6 supported finder types: <classname alt="boost::algorithm::finder_t">finder_t</classname>, <classname alt="boost::algorithm::simplified_finder_t">simplified_finder_t</classname><classname alt="boost::algorithm::benchmark_finder_t">benchmark_finder_t</classname>, <classname alt="boost::algorithm::first_finder_t">first_finder_t</classname>, <classname alt="boost::algorithm::nth_finder_t">nth_finder_t</classname> and <classname alt="boost::algorithm::last_finder_t">last_finder_t</classname>.<programlisting>std::string random_saying =
     "Speak when you are angry and you will make the best speech you'll ever regret.";

+//Create a finder_t object that will search using the Knuth-Morris-Pratt algorithm.
+//Rule of thumb for finder_t is:
+// pass a pointer and no copy is made, pass a reference and an internal copy is made.
+//Note that finder_t is the only finder to support passing references (other finders only support
+// passing pointers)
+//In this example, we pass a temporary as the pattern (which will be copied internally), and a pointer to a range
+//as the text (and no copy will be made).
boost::finder_t<std::string, std::string, boost::knuth_morris_pratt> finder("angry", &random_saying);

-boost::to_upper(finder.find_first()); // we modified the internal text
-std::cout << random_saying << std::cout; // Outputs "Speak when you are ANGRY..."
+//Look for the first match of the pattern in the text using our finder
+boost::iterator_range<std::string::iterator> &match = finder.find_first();
+boost::to_upper(match); // turn the matching range into uppercase
+std::cout << random_saying << std::endl; // Outputs "Speak when you are ANGRY..."
+
+//Create a functor finder (first_finder_t, last_finder_t, nth_finder_t are functor finders)
+//which looks for the last occurrence of pattern "you" in a string using the Boyer-Moore algorithm.
+std::string pattern = "you";
+boost::last_finder_t<std::string, boost::boyer_moore> finder2(&pattern);
+//Call the functor using the string in which to search
+match = finder2(random_saying.begin(), random_saying.end());
+//Turn the last occurrence of "you" in random_saying to uppercase
+boost::to_upper(match);
+std::cout << random_saying << std::endl; // Outputs "... YOU'll ever regret."
+
+//Create a simplified_finder_t. Very similar to finder_t, except it only accepts
+//pointers (no references, which means it never attempts to make copies).
+pattern = "Speak";
+boost::simplified_finder_t<std::string, std::string,
+ boost::suffix_array_search> finder3;
+finder3.set_string(&random_saying);
+finder3.set_substring(&pattern);
+match = finder3.find_first();
+boost::to_upper(match);
+//Important:
+//if we want to use finder3 at this point, we have to call set_string again,
+//because the string has changed (we turned some of it into uppercase and the finder has no idea we did that)
+finder3.set_string(&random_saying);

-boost::boyer_moore_finder finder2; // a typedef for finder_t<string,string,boyer_moore>
-finder2.set_substring("Speak"); // makes an internal copy of the substring
-finder2.set_string(&random_saying); // passing as a pointer allows the finder to not make a copy
-
-boost::to_upper(finder2.find_first()); // turn the match into uppercase
-std::cout << random_saying << std::endl; // Outputs "SPEAK when you are ANGRY..."</programlisting>For more information, consult the reference: <headername>boost/algorithm/string/finder.hpp</headername>.</para>
+std::cout << random_saying << std::endl; // Outputs "SPEAK when you are ANGRY and you will make the best speech YOU'll ever regret."</programlisting>For more information on the features and functionality of various finder types, see <xref linkend="string_algo.quickref.finder_types"></xref>.</para>
   </section>
</section>
\ No newline at end of file

Modified: sandbox/SOC/2010/stringalgos/libs/algorithm/string/test/finder_test.cpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/libs/algorithm/string/test/finder_test.cpp (original)
+++ sandbox/SOC/2010/stringalgos/libs/algorithm/string/test/finder_test.cpp 2010-08-15 21:11:58 EDT (Sun, 15 Aug 2010)
@@ -866,6 +866,7 @@
     \todo test the non-match of nonempty substring in empty string
     \todo test the unique match of empty substring in empty string
     \todo test more strings with consecutive substring matches
+ \todo some tests that check correctness of kmp (patterns with unusual failure functions), bm and suffix arrays
     */

     typedef boost::mpl::list<

Next message: barend.gehrels_at_[hidden]: "[Boost-commit] svn:boost r64840 - sandbox/geometry/boost/geometry/iterators"
Previous message: vicente.botet_at_[hidden]: "[Boost-commit] svn:boost r64838 - sandbox/chrono/boost/chrono"

Date view	Thread view	Subject view	Author view

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