Subject: [Boost-commit] svn:boost r64809 - in sandbox/SOC/2010/stringalgos: boost/algorithm/string boost/algorithm/string/finder boost/algorithm/string/finder/detail boost/algorithm/string/string_search boost/algorithm/string/string_search/detail libs/algorithm/string libs/algorithm/string/benchmark libs/algorithm/string/example libs/algorithm/string/test
From: mstefanro_at_[hidden]
Date: 2010-08-14 20:20:42
Author: mstefanro
Date: 2010-08-14 20:20:26 EDT (Sat, 14 Aug 2010)
New Revision: 64809
URL: http://svn.boost.org/trac/boost/changeset/64809
Log:
[GSoC2010][StringAlgo] Design fixes, refactoring etc.
Added:
sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/detail/string_search_ranges.hpp (contents, props changed)
sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/finder_generators.hpp (contents, props changed)
Removed:
sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/detail/last_finder_impl.hpp
sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/detail/nth_finder_impl.hpp
Properties modified:
sandbox/SOC/2010/stringalgos/boost/algorithm/string/ (props changed)
sandbox/SOC/2010/stringalgos/libs/algorithm/string/ (props changed)
Text files modified:
sandbox/SOC/2010/stringalgos/boost/algorithm/string/benchmark_finder.hpp | 10 +
sandbox/SOC/2010/stringalgos/boost/algorithm/string/config.hpp | 7 +
sandbox/SOC/2010/stringalgos/boost/algorithm/string/find.hpp | 24 ++-
sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder.hpp | 227 ------------------------------------
sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/default_search_algorithm.hpp | 7
sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/detail/finder_typedefs.hpp | 79 ++++++------
sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/detail/is_pointer_to.hpp | 2
sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/finder.hpp | 225 +++++++++++++++--------------------
sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/generated_finders.hpp | 251 +++++++++++++++++++++++++++++++++------
sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/simplified_finder.hpp | 124 +++++++------------
sandbox/SOC/2010/stringalgos/boost/algorithm/string/predicate.hpp | 24 ++
sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search.hpp | 2
sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/boyer_moore.hpp | 144 ++++++++++++----------
sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/detail/rabin_karp.hpp | 122 ++++++++++--------
sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/knuth_morris_pratt.hpp | 72 +++++++---
sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/naive_search.hpp | 46 ++++---
sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/rabin_karp.hpp | 47 +++++--
sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/suffix_array.hpp | 112 ++++++++++-------
sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/suffix_array2.hpp | 2
sandbox/SOC/2010/stringalgos/libs/algorithm/string/benchmark/string_search.cpp | 2
sandbox/SOC/2010/stringalgos/libs/algorithm/string/example/Jamfile | 1
sandbox/SOC/2010/stringalgos/libs/algorithm/string/example/finder_example.cpp | 85 +++++++------
sandbox/SOC/2010/stringalgos/libs/algorithm/string/test/find_test.cpp | 8
sandbox/SOC/2010/stringalgos/libs/algorithm/string/test/finder_test.cpp | 49 +++++++
24 files changed, 869 insertions(+), 803 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-14 20:20:26 EDT (Sat, 14 Aug 2010)
@@ -82,10 +82,14 @@
*/
template <class Range1T, class Range2T, class AlgorithmSequenceT,
class ComparatorT = boost::algorithm::is_equal>
- class benchmark_finder :
+ class benchmark_finder /*:
public boost::algorithm::detail::finder_typedefs<Range1T, Range2T,
- ComparatorT, std::allocator<std::size_t> >
+ 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:
//! See \ref simplified_finder_t::set_substring
@@ -287,4 +291,4 @@
namespace boost { using algorithm::benchmark_finder; }
-#endif
\ No newline at end of file
+#endif
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-14 20:20:26 EDT (Sat, 14 Aug 2010)
@@ -20,6 +20,13 @@
#define BOOST_STRING_TYPENAME BOOST_DEDUCED_TYPENAME
+//TODO maybe force inline exists for other compilers? like __inline__ for GCC/ICC?
+#ifdef BOOST_MSVC
+#define BOOST_STRING_FORCE_INLINE __forceinline
+#else
+#define BOOST_STRING_FORCE_INLINE inline
+#endif
+
// Metrowerks workaround
#if BOOST_WORKAROUND(__MWERKS__, <= 0x3003) // 8.x
#pragma parse_func_templ off
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-14 20:20:26 EDT (Sat, 14 Aug 2010)
@@ -19,6 +19,7 @@
#include <boost/range/iterator.hpp>
#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/default_search_algorithm.hpp>
#include <boost/algorithm/string/compare.hpp>
@@ -57,9 +58,10 @@
RangeT& Input,
FinderT& Finder)
{
-
- 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));
+
+ 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));
}
// find_first -----------------------------------------------//
@@ -86,8 +88,11 @@
const Range2T& Search,
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,Range1T,
+ ::boost::algorithm::first_finder_t<Range2T,
typename AlgorithmTagT::type,::boost::algorithm::is_equal>(&Search)
);
}
@@ -131,8 +136,9 @@
//boost::algorithm::simplified_finder_t<Range2T, Range1T, typename AlgorithmTagT::type,
// ::boost::algorithm::is_iequal> finder(&Search, &Input, ::boost::algorithm::is_iequal(Loc));
//return finder.find_first();
+
return ::boost::algorithm::find(Input,
- ::boost::algorithm::first_finder_t<Range2T,Range1T,
+ ::boost::algorithm::first_finder_t<Range2T,
typename AlgorithmTagT::type,::boost::algorithm::is_iequal>(&Search, ::boost::algorithm::is_iequal(Loc))
);
}
@@ -192,7 +198,7 @@
return prev;
*/
return ::boost::algorithm::find(Input,
- ::boost::algorithm::last_finder_t<Range2T,Range1T,
+ ::boost::algorithm::last_finder_t<Range2T,
typename AlgorithmTagT::type,::boost::algorithm::is_equal>(&Search)
);
//return ::boost::algorithm::find(Input, ::boost::algorithm::last_finder(Search));
@@ -235,7 +241,7 @@
const std::locale& Loc=std::locale())
{
return ::boost::algorithm::find(Input,
- ::boost::algorithm::last_finder_t<Range2T,Range1T,
+ ::boost::algorithm::last_finder_t<Range2T,
typename AlgorithmTagT::type,::boost::algorithm::is_iequal>(&Search, ::boost::algorithm::is_iequal(Loc)));
}
@@ -280,7 +286,7 @@
AlgorithmTagT const &)
{
return ::boost::algorithm::find(Input,
- ::boost::algorithm::nth_finder_t<Range2T, Range1T,
+ ::boost::algorithm::nth_finder_t<Range2T,
typename AlgorithmTagT::type, ::boost::algorithm::is_equal>(&Search, ::boost::algorithm::is_equal(), Nth)
);
}
@@ -327,7 +333,7 @@
const std::locale& Loc=std::locale())
{
return ::boost::algorithm::find(Input,
- ::boost::algorithm::nth_finder_t<Range2T, Range1T,
+ ::boost::algorithm::nth_finder_t<Range2T,
typename AlgorithmTagT::type, ::boost::algorithm::is_iequal>(&Search, ::boost::algorithm::is_iequal(Loc), Nth));
}
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-14 20:20:26 EDT (Sat, 14 Aug 2010)
@@ -49,6 +49,7 @@
#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
@@ -61,231 +62,5 @@
//TODO: test if get_internal_string() and get_internal_substring() are fine
-namespace boost { namespace algorithm {
-
-
-
-
-// Finder generators ------------------------------------------//
-
- //! "First" finder generator
- /*!
- Constructs a \ref first_finder_t. For backward compatibility, the finder is a
- functor which looks for the \b first occurrence of the string in a given input.
- The result is given as an \c iterator_range delimiting the match.
- \param Search The pattern to look for
- \param Comp A comparator used to match individual characters
- \tparam AlgorithmTagT A tag of the search algorithm that should be used for searching
- \deprecated
- */
- template<typename RangeT,typename PredicateT, typename AlgorithmTagT>
- inline boost::algorithm::first_finder_t<RangeT, RangeT, typename AlgorithmTagT::type,PredicateT>
- first_finder(
- const RangeT& Search, PredicateT const& Comp,
- AlgorithmTagT const&)
- {
- return boost::algorithm::first_finder_t<RangeT, RangeT, typename AlgorithmTagT::type,PredicateT>(&Search, Comp);
- }
-
- //! \overload
- template<typename RangeT,typename PredicateT>
- inline boost::algorithm::first_finder_t<RangeT, RangeT, boost::algorithm::default_finder_algorithm, PredicateT>
- first_finder(
- const RangeT& Search, PredicateT const& Comp)
- {
- return boost::algorithm::first_finder(Search,Comp, boost::algorithm::default_finder_algorithm_tag());
- }
-
- //! \overload
- template<typename RangeT>
- inline boost::algorithm::first_finder_t<RangeT, RangeT, boost::algorithm::default_finder_algorithm,
- boost::algorithm::is_equal>
- first_finder(
- const RangeT& Search)
- {
- return boost::algorithm::first_finder(Search,
- boost::algorithm::is_equal(), boost::algorithm::default_finder_algorithm_tag());
- }
-
- //! "Last" finder generator
- /*!
- Constructs a \ref last_finder_t. For backward compatibility, the finder is a
- functor which looks for the \b last occurrence of the string in a given input.
- The result is given as an \c iterator_range delimiting the match.
- \param Search The pattern to look for
- \param Comp A comparator used to match individual characters
- \tparam AlgorithmTagT A tag of the search algorithm that should be used for searching
- \deprecated
- */
- template<typename RangeT, typename PredicateT, typename AlgorithmTagT>
- inline boost::algorithm::last_finder_t<RangeT, RangeT, typename AlgorithmTagT::type,PredicateT>
- last_finder( const RangeT& Search, PredicateT const &Comp,
- AlgorithmTagT const&)
- {
- return boost::algorithm::last_finder_t<RangeT, RangeT, typename AlgorithmTagT::type,PredicateT>(&Search, Comp);
- }
-
- //!\overload
- template<typename RangeT, typename PredicateT>
- inline boost::algorithm::last_finder_t<RangeT, RangeT, boost::algorithm::default_finder_algorithm, PredicateT>
- last_finder( const RangeT& Search, PredicateT const &Comp)
- {
- return boost::algorithm::last_finder(Search, Comp,
- boost::algorithm::default_finder_algorithm_tag());
- }
-
- //!\overload
- template<typename RangeT>
- inline boost::algorithm::last_finder_t<RangeT, RangeT, boost::algorithm::default_finder_algorithm,
- boost::algorithm::is_equal>
- last_finder( const RangeT& Search)
- {
- return boost::algorithm::last_finder(Search,
- boost::algorithm::is_equal(), boost::algorithm::default_finder_algorithm_tag());
- }
-
- //! "Nth" finder generator
- /*!
- Constructs a \ref nth_finder_t. For backward compatibility, the finder is a
- functor which looks for the \b Nth occurrence of the string in a given input.
- The result is given as an \c iterator_range delimiting the match.
- \param Search The pattern to look for
- \param Comp A comparator used to match individual characters
- \tparam AlgorithmTagT A tag of the search algorithm that should be used for searching
- \deprecated
- */
- template<typename RangeT, typename PredicateT, typename AlgorithmTagT>
- inline boost::algorithm::nth_finder_t<RangeT, RangeT, typename AlgorithmTagT::type,PredicateT>
- nth_finder(const RangeT& Search, int Nth, PredicateT const &Comp, AlgorithmTagT const &)
- {
- return boost::algorithm::nth_finder_t<RangeT, RangeT, typename AlgorithmTagT::type, PredicateT>(&Search, Comp, Nth);
- }
-
- //!\overload
- template<typename RangeT, typename PredicateT>
- inline boost::algorithm::nth_finder_t<RangeT, RangeT, boost::algorithm::default_finder_algorithm,PredicateT>
- nth_finder(const RangeT& Search, int Nth, PredicateT const &Comp)
- {
- return boost::algorithm::nth_finder(Search, Nth, Comp,
- boost::algorithm::default_finder_algorithm_tag());
- }
-
- //!\overload
- template<typename RangeT>
- inline boost::algorithm::nth_finder_t<RangeT, RangeT, boost::algorithm::default_finder_algorithm,
- boost::algorithm::is_equal>
- nth_finder(const RangeT& Search, int Nth)
- {
- return boost::algorithm::nth_finder(Search, Nth, boost::algorithm::is_equal(),
- boost::algorithm::default_finder_algorithm_tag());
- }
-
- //! "Head" finder
- /*!
- Construct the \c head_finder. The finder returns a head of a given
- input. The head is a prefix of a string up to n elements in
- size. If an input has less then n elements, whole input is
- considered a head.
- The result is given as an \c iterator_range delimiting the match.
-
- \param N The size of the head
- \return An instance of the \c head_finder object
- \deprecated
- */
- inline detail::head_finderF
- head_finder( int N )
- {
- return detail::head_finderF(N);
- }
-
- //! "Tail" finder
- /*!
- Construct the \c tail_finder. The finder returns a tail of a given
- input. The tail is a suffix of a string up to n elements in
- size. If an input has less then n elements, whole input is
- considered a head.
- The result is given as an \c iterator_range delimiting the match.
-
- \param N The size of the head
- \return An instance of the \c tail_finder object
- */
- inline detail::tail_finderF
- tail_finder( int N )
- {
- return detail::tail_finderF(N);
- }
-
- //! "Token" finder
- /*!
- Construct the \c token_finder. The finder searches for a token
- specified by a predicate. It is similar to std::find_if
- algorithm, with an exception that it return a range of
- instead of a single iterator.
-
- If "compress token mode" is enabled, adjacent matching tokens are
- concatenated into one match. Thus the finder can be used to
- search for continuous segments of characters satisfying the
- given predicate.
-
- The result is given as an \c iterator_range delimiting the match.
-
- \param Pred An element selection predicate
- \param eCompress Compress flag
- \return An instance of the \c token_finder object
- */
- template< typename PredicateT >
- inline detail::token_finderF<PredicateT>
- token_finder(
- PredicateT Pred,
- token_compress_mode_type eCompress=token_compress_off )
- {
- return detail::token_finderF<PredicateT>( Pred, eCompress );
- }
-
- //! "Range" finder
- /*!
- Construct the \c range_finder. The finder does not perform
- any operation. It simply returns the given range for
- any input.
-
- \param Begin Beginning of the range
- \param End End of the range
- \param Range The range.
- \return An instance of the \c range_finger object
- */
- template< typename ForwardIteratorT >
- inline detail::range_finderF<ForwardIteratorT>
- range_finder(
- ForwardIteratorT Begin,
- ForwardIteratorT End )
- {
- return detail::range_finderF<ForwardIteratorT>( Begin, End );
- }
-
- //! "Range" finder
- /*!
- \overload
- */
- template< typename ForwardIteratorT >
- inline detail::range_finderF<ForwardIteratorT>
- range_finder( iterator_range<ForwardIteratorT> Range )
- {
- return detail::range_finderF<ForwardIteratorT>( Range );
- }
-
-} } // namespace algorithm, namespace boost
-
-namespace boost
-{
- // pull the names to the boost namespace
- using algorithm::first_finder;
- using algorithm::last_finder;
- using algorithm::nth_finder;
- using algorithm::head_finder;
- using algorithm::tail_finder;
- using algorithm::token_finder;
- using algorithm::range_finder;
-} // namespace boost
-
#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-14 20:20:26 EDT (Sat, 14 Aug 2010)
@@ -1,15 +1,16 @@
#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/knuth_morris_pratt.hpp>
+#include <boost/algorithm/string/string_search/naive_search.hpp>
namespace boost { namespace algorithm {
//! The default search algorithm used by find/replace functions.
- typedef boost::algorithm::knuth_morris_pratt default_finder_algorithm;
+ typedef boost::algorithm::naive_search default_finder_algorithm;
//! The tag of the default search algorithm used by find/replace functions.
//! Instances of this type can be passed to find/replace functions.
- struct default_finder_algorithm_tag { typedef boost::algorithm::knuth_morris_pratt type; };
+ struct default_finder_algorithm_tag { typedef boost::algorithm::naive_search type; };
} }
namespace boost
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-14 20:20:26 EDT (Sat, 14 Aug 2010)
@@ -8,50 +8,53 @@
#include <boost/iterator/iterator_traits.hpp>
+#define BOOST_ALGORITHM_DETAIL_COMMON_FINDER_TYPEDEFS(Range1T, Range2T) \
+ typedef Range1T substring_type; /*!< The type of the substring */ \
+ typedef Range2T string_type; /*!< The type of the string */ \
+ typedef typename boost::range_const_iterator<substring_type>::type \
+ substring_iterator_type; /*!< The type of the substring's iterator */ \
+ typedef typename boost::range_iterator<string_type>::type \
+ string_iterator_type; /*!< The type of the string's iterator */ \
+ typedef typename boost::iterator_value<substring_iterator_type>::type \
+ substring_char_type; /*!< The character type of the substring */ \
+ typedef typename boost::iterator_value<string_iterator_type>::type \
+ string_char_type; /*!< The character type of the string */ \
+ typedef typename boost::iterator_range<substring_iterator_type> \
+ substring_range_type; /*!< The range type of the substring (pattern) */ \
+ typedef typename boost::iterator_range<string_iterator_type> \
+ string_range_type; /*!< The range type of the text */ \
+ typedef typename boost::iterator_difference<string_iterator_type>::type \
+ string_difference_type /*!< A type capable of holding the difference between two iterators of the text */
+
+#define BOOST_ALGORITHM_DETAIL_UNCOMMON_FINDER_TYPEDEFS(Range1T, Range2T) \
+ typedef typename boost::range_category<substring_type>::type substring_iterator_category; \
+ typedef typename boost::range_category<string_type>::type string_iterator_category; \
+ typedef typename boost::reverse_iterator<substring_iterator_type> substring_reverse_iterator_type; \
+ typedef typename boost::reverse_iterator<string_iterator_type> string_reverse_iterator_type; \
+ typedef typename boost::iterator_range<substring_reverse_iterator_type> substring_reverse_range_type; \
+ typedef typename boost::iterator_range<string_reverse_iterator_type> string_reverse_range_type
+
+#define BOOST_ALGORITHM_DETAIL_FINDER_TYPEDEFS(Range1T, Range2T) \
+ BOOST_ALGORITHM_DETAIL_COMMON_FINDER_TYPEDEFS(Range1T, Range2T); \
+ protected: \
+ BOOST_ALGORITHM_DETAIL_UNCOMMON_FINDER_TYPEDEFS(Range1T, Range2T);
+
+
+#define BOOST_ALGORITHM_DETAIL_FINDER_TYPEDEFS2(ComparatorT, AllocatorT) \
+ typedef ComparatorT comparator_type; /*!< The type of the comparator */ \
+ typedef AllocatorT allocator_type /*!< The type of the allocator */
+
+
namespace boost { namespace algorithm { namespace detail {
template <class Range1T, class Range2T, class ComparatorT, class AllocatorT>
struct finder_typedefs
{
- //! The type of the substring
- typedef Range1T substring_type;
- //! The type of the string
- typedef Range2T string_type;
- //! The type of the comparator
- typedef ComparatorT comparator_type;
- //! The type of the allocator
- typedef AllocatorT allocator_type;
- //! The type of the substring's iterator
- typedef typename boost::range_const_iterator<substring_type>::type
- substring_iterator_type;
- //! The type of the string's iterator
- typedef typename boost::range_iterator<string_type>::type
- string_iterator_type;
- //! The character type of the substring
- typedef typename boost::iterator_value<substring_iterator_type>::type
- substring_char_type;
- //! The character type of the string
- typedef typename boost::iterator_value<string_iterator_type>::type
- string_char_type;
- //! The range type of the substring (pattern)
- typedef typename boost::iterator_range<substring_iterator_type>
- substring_range_type;
- //! The range type of the text
- typedef typename boost::iterator_range<string_iterator_type>
- string_range_type;
- //! A type capable of holding the difference between two iterators of the text
- typedef typename boost::iterator_difference<string_iterator_type>::type
- string_difference_type;
- protected:
- typedef typename boost::range_category<substring_type>::type substring_iterator_category;
- typedef typename boost::range_category<string_type>::type string_iterator_category;
-
- typedef typename boost::reverse_iterator<substring_iterator_type> substring_reverse_iterator_type;
- typedef typename boost::reverse_iterator<string_iterator_type> string_reverse_iterator_type;
- typedef typename boost::iterator_range<substring_reverse_iterator_type> substring_reverse_range_type;
- typedef typename boost::iterator_range<string_reverse_iterator_type> string_reverse_range_type;
+ BOOST_ALGORITHM_DETAIL_FINDER_TYPEDEFS(Range1T, Range2T);
+ BOOST_ALGORITHM_DETAIL_FINDER_TYPEDEFS2(ComparatorT, AllocatorT);
};
} } }
-#endif // BOOST_ALGORITHM_FINDER_TYPEDEFS_HPP
\ No newline at end of file
+
+#endif // 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-14 20:20:26 EDT (Sat, 14 Aug 2010)
@@ -13,4 +13,4 @@
} } }
-#endif // BOOST_ALGORITHM_IS_POINTER_TO_HPP
\ No newline at end of file
+#endif // BOOST_ALGORITHM_IS_POINTER_TO_HPP
Deleted: sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/detail/last_finder_impl.hpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/detail/last_finder_impl.hpp 2010-08-14 20:20:26 EDT (Sat, 14 Aug 2010)
+++ (empty file)
@@ -1,99 +0,0 @@
-#ifndef BOOST_ALGORITHM_DETAIL_LAST_FINDER_IMPL_HPP
-#define BOOST_ALGORITHM_DETAIL_LAST_FINDER_IMPL_HPP
-
-#include <boost/iterator/iterator_traits.hpp>
-#include <boost/iterator/reverse_iterator.hpp>
-
-#include <boost/mpl/and.hpp>
-#include <boost/mpl/or.hpp>
-#include <boost/mpl/not.hpp>
-#include <boost/type_traits/is_base_of.hpp>
-
-#include <boost/utility/enable_if.hpp>
-
-#include <memory>
-#include <iterator>
-
-#include <boost/range/category.hpp>
-
-#include <boost/algorithm/string/finder/simplified_finder.hpp>
-#include <boost/algorithm/string/finder/detail/finder_typedefs.hpp>
-
-
-namespace boost { namespace algorithm { namespace detail {
-
- template <class Range1T, class Range2T, class AlgorithmT,
- class ComparatorT, class Enable = void>
- class last_finder_impl_t;
-
- //Implementation of last_finder_t when both ranges are bidirectional
- template <class Range1T, class Range2T, class AlgorithmT, class ComparatorT>
- class last_finder_impl_t<Range1T, Range2T, AlgorithmT, ComparatorT,
- typename boost::enable_if<
- typename boost::mpl::and_<
- typename boost::is_base_of<std::bidirectional_iterator_tag, typename boost::range_category<Range1T>::type>,
- typename boost::is_base_of<std::bidirectional_iterator_tag, typename boost::range_category<Range2T>::type>
- >
- >::type>
- : public boost::algorithm::detail::finder_typedefs<Range1T, Range2T, ComparatorT, std::allocator<std::size_t> >
- {
- public:
- last_finder_impl_t (substring_range_type const &substr, ComparatorT comparator=ComparatorT())
- : finder(comparator)
- { finder.set_substring(substring_reverse_iterator_type(boost::end(substr)),
- substring_reverse_iterator_type(boost::begin(substr))
- ); }
- string_range_type operator()(string_iterator_type const &string_start, string_iterator_type const &string_end)
- {
- finder.set_string(string_reverse_iterator_type(string_end),
- string_reverse_iterator_type(string_start));
- string_reverse_range_type &ret = finder.find_first();
- //no match
- if (boost::begin(ret) == boost::end(finder.get_string_range()))
- return boost::make_iterator_range(string_end, string_end);
- return boost::make_iterator_range(boost::end(ret).base(), boost::begin(ret).base());
- }
- private:
- typedef typename boost::algorithm::simplified_finder_t<
- substring_reverse_range_type, string_reverse_range_type, AlgorithmT, ComparatorT> reverse_finder_type;
- reverse_finder_type finder;
- };
-
- //Implementation of last_finder_t when at least one range is not bidirectional
- template <class Range1T, class Range2T, class AlgorithmT, class ComparatorT>
- class last_finder_impl_t<Range1T, Range2T, AlgorithmT, ComparatorT,
- typename boost::enable_if<
- typename boost::mpl::or_<
- typename boost::mpl::not_<
- typename boost::is_base_of<std::bidirectional_iterator_tag, typename boost::range_category<Range1T>::type>
- >,
- typename boost::mpl::not_<
- typename boost::is_base_of<std::bidirectional_iterator_tag, typename boost::range_category<Range2T>::type>
- >
- >
- >::type>
- : public boost::algorithm::detail::finder_typedefs<Range1T, Range2T, ComparatorT, std::allocator<std::size_t> >
- {
- public:
- last_finder_impl_t (substring_range_type const &substr, ComparatorT comparator=ComparatorT())
- : finder(comparator)
- { finder.set_substring(boost::begin(substr), boost::end(substr)); }
- string_range_type operator()(string_iterator_type const &string_start, string_iterator_type const &string_end)
- {
- finder.set_string(string_start, string_end);
- string_iterator_type prev, crt = make_iterator_range(string_start, string_end);
- for (;;)
- {
- prev = crt;
- crt = finder.find_next();
- if (boost::begin(crt) == string_end) break;
- }
- return prev;
- }
- private:
- typedef boost::algorithm::simplified_finder_t<Range1T, Range2T, AlgorithmT, ComparatorT> internal_finder_type;
- internal_finder_type finder;
- };
-
-} } }
-#endif // BOOST_ALGORITHM_DETAIL_LAST_FINDER_IMPL_HPP
\ No newline at end of file
Deleted: sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/detail/nth_finder_impl.hpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/detail/nth_finder_impl.hpp 2010-08-14 20:20:26 EDT (Sat, 14 Aug 2010)
+++ (empty file)
@@ -1,136 +0,0 @@
-#ifndef BOOST_ALGORITHM_DETAIL_NTH_FINDER_IMPL_HPP
-#define BOOST_ALGORITHM_DETAIL_NTH_FINDER_IMPL_HPP
-
-#include <boost/iterator/iterator_traits.hpp>
-#include <boost/iterator/reverse_iterator.hpp>
-
-#include <boost/mpl/and.hpp>
-#include <boost/mpl/or.hpp>
-#include <boost/mpl/not.hpp>
-#include <boost/type_traits/is_base_of.hpp>
-
-#include <boost/utility/enable_if.hpp>
-
-#include <memory>
-#include <iterator>
-#include <stdexcept>
-
-#include <boost/range/category.hpp>
-
-#include <boost/algorithm/string/finder/simplified_finder.hpp>
-#include <boost/algorithm/string/finder/detail/finder_typedefs.hpp>
-
-namespace boost { namespace algorithm { namespace detail {
-
- template <class Range1T, class Range2T, class AlgorithmT,
- class ComparatorT, class Enable = void>
- class nth_finder_impl_t;
-
- //Implementation of last_finder_t when both ranges are bidirectional
- template <class Range1T, class Range2T, class AlgorithmT, class ComparatorT>
- class nth_finder_impl_t<Range1T, Range2T, AlgorithmT, ComparatorT,
- typename boost::enable_if<
- typename boost::mpl::and_<
- typename boost::is_base_of<std::bidirectional_iterator_tag, typename boost::range_category<Range1T>::type>,
- typename boost::is_base_of<std::bidirectional_iterator_tag, typename boost::range_category<Range2T>::type>
- >
- >::type>
- : public boost::algorithm::detail::finder_typedefs<Range1T, Range2T, ComparatorT, std::allocator<std::size_t> >
- {
- public:
- nth_finder_impl_t (substring_range_type const &substr, ComparatorT comparator=ComparatorT(), int n = 0)
- : n_(n), finder(comparator), reverse_finder(comparator)
- {
- reverse_finder.set_substring(substring_reverse_iterator_type(boost::end(substr)),
- substring_reverse_iterator_type(boost::begin(substr)));
- finder.set_substring(boost::begin(substr), boost::end(substr));
- }
- string_range_type operator()(string_iterator_type const &string_start, string_iterator_type const &string_end)
- {
- if (n_ >= 0)
- {
- finder.set_string(string_start, string_end);
- string_range_type ret;
- for (int n = 0; n <= n_; ++n)
- {
- ret = finder.find_next();
- if (boost::begin(ret) == string_end)
- return make_iterator_range(string_end, string_end);
- }
- return ret;
- }
- else
- {
- reverse_finder.set_string(
- string_reverse_iterator_type(string_end), string_reverse_iterator_type(string_start));
- string_reverse_range_type ret;
- int n_2 = -n_ - 1;
- for (int n = 0; n <= n_2; ++n)
- {
- ret = reverse_finder.find_next();
- if (boost::begin(ret) == boost::end(reverse_finder.get_string_range()))
- return boost::make_iterator_range(string_end, string_end);
- }
- return boost::make_iterator_range(boost::end(ret).base(), boost::begin(ret).base() );
- }
- }
- void set_n(int n)
- { n_ = n; }
- private:
- typedef typename boost::algorithm::simplified_finder_t<
- substring_reverse_range_type, string_reverse_range_type, AlgorithmT, ComparatorT> reverse_finder_type;
- typedef typename boost::algorithm::simplified_finder_t<
- substring_type, string_type, AlgorithmT, ComparatorT> finder_type;
- finder_type finder;
- reverse_finder_type reverse_finder;
- int n_;
- };
-
- //Implementation of nth_finder_t when at least one range is not bidirectional
- template <class Range1T, class Range2T, class AlgorithmT, class ComparatorT>
- class nth_finder_impl_t<Range1T, Range2T, AlgorithmT, ComparatorT,
- typename boost::enable_if<
- typename boost::mpl::or_<
- typename boost::mpl::not_<
- typename boost::is_base_of<std::bidirectional_iterator_tag, typename boost::range_category<Range1T>::type>
- >,
- typename boost::mpl::not_<
- typename boost::is_base_of<std::bidirectional_iterator_tag, typename boost::range_category<Range2T>::type>
- >
- >
- >::type>
- : public boost::algorithm::detail::finder_typedefs<Range1T, Range2T, ComparatorT, std::allocator<std::size_t> >
- {
- public:
- nth_finder_impl_t (substring_range_type const &substr, ComparatorT comparator=ComparatorT(), int n = 0)
- : finder(comparator)
- {
- assert (n > = 0); // we do not have bidirectional iterators
- finder.set_substring(boost::begin(substr), boost::end(substr));
- }
-
- string_range_type operator()(string_iterator_type const &string_start, string_iterator_type const &string_end)
- {
- finder.set_string(string_start, string_end);
- string_range_type ret;
- for (int n = 0; n <= n_; ++n)
- {
- ret = finder.find_next();
- if (boost::begin(ret) == string_end)
- return boost::make_iterator_range(string_end, string_end);
- }
- return ret;
- }
-
- void set_n(int n)
- { assert(n >= 0); n_ = n; }
- private:
- typedef typename boost::algorithm::simplified_finder_t<
- substring_type, string_type, AlgorithmT, ComparatorT> finder_type;
- finder_type finder;
- int n_;
- };
-
-} } }
-
-#endif // BOOST_ALGORITHM_DETAIL_NTH_FINDER_IMPL_HPP
\ No newline at end of file
Added: sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/detail/string_search_ranges.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/detail/string_search_ranges.hpp 2010-08-14 20:20:26 EDT (Sat, 14 Aug 2010)
@@ -0,0 +1,25 @@
+#ifndef BOOST_ALGORITHM_DETAIL_STRING_SEARCH_RANGES_HPP
+#define BOOST_ALGORITHM_DETAIL_STRING_SEARCH_RANGES_HPP
+
+#include <boost/algorithm/string/finder/detail/finder_typedefs.hpp>
+#include <boost/range/begin.hpp>
+
+namespace boost { namespace algorithm { namespace detail {
+
+ template <class Range1T, class Range2T>
+ class string_search_ranges
+ {
+ private:
+ BOOST_ALGORITHM_DETAIL_FINDER_TYPEDEFS(Range1T, Range2T);
+ public:
+ boost::iterator_range<substring_iterator_type> substr;
+ boost::iterator_range<string_iterator_type> str;
+ string_iterator_type offset;
+ string_search_ranges() { }
+ string_search_ranges (substring_range_type const &substr, string_range_type const &str)
+ : substr(substr), str(str), offset(boost::begin(str)) { }
+ };
+
+} } }
+
+#endif // 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-14 20:20:26 EDT (Sat, 14 Aug 2010)
@@ -18,8 +18,13 @@
#include <boost/call_traits.hpp>
+#include <boost/algorithm/string/finder/detail/finder_typedefs.hpp>
+
namespace boost { namespace algorithm {
+
+ //TODO: make optional copies of the text/pattern use the allocator too
+
//TODO: copyable finder type below?
//! A generic finder type
@@ -44,10 +49,12 @@
typename ComparatorT = ::boost::algorithm::is_equal,
class AllocatorT = std::allocator<std::size_t>
>
- class finder_t :
- public AlgorithmT::template algorithm<
+ class finder_t /*:*/
+ /*public AlgorithmT::template algorithm<
typename finder_t<Sequence1T, Sequence2T, AlgorithmT, ComparatorT, AllocatorT>,
- Sequence1T, Sequence2T, ComparatorT, AllocatorT>
+ Sequence1T, Sequence2T, ComparatorT, AllocatorT>*/
+ /*public AlgorithmT::template algorithm<
+ typename finder_t<Sequence1T, Sequence2T, AlgorithmT, ComparatorT, AllocatorT> >*/
{
//TODO:: Maybe write a String concept?
//TODO:: Currently, there's a SGI Sequence Concept implemented by Boost.ConceptCheck,
@@ -55,32 +62,16 @@
//! parameters sequences is wrong.
BOOST_CONCEPT_ASSERT((boost::Container<Sequence1T>));
BOOST_CONCEPT_ASSERT((boost::Container<Sequence2T>));
+ public:
+ 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<finder_t, Sequence1T,
+ Sequence2T, ComparatorT, AllocatorT> algorithm_type;*/
+ typedef typename AlgorithmT::template algorithm<substring_char_type, string_char_type,
+ comparator_type, allocator_type> algorithm_type;
public:
- //! The type of the pattern (substring)
- typedef typename algorithm_type::substring_type substring_type;
- //! The type of the text (string)
- typedef typename algorithm_type::string_type string_type;
- //! The type of the comparator
- typedef typename algorithm_type::comparator_type comparator_type;
- //! The type of the allocator
- typedef typename algorithm_type::allocator_type allocator_type;
- //! The type of the substring's iterator
- typedef typename algorithm_type::substring_iterator_type substring_iterator_type;
- //! The type of the text's iterator
- typedef typename algorithm_type::string_iterator_type string_iterator_type;
- //! The character type of the substring
- typedef typename algorithm_type::substring_char_type substring_char_type;
- //! The character type of the text
- typedef typename algorithm_type::string_char_type string_char_type;
- //! The range type of the substring (pattern)
- typedef typename algorithm_type::substring_range_type substring_range_type;
- //! The range type of the text
- typedef typename algorithm_type::string_range_type string_range_type;
- //! A type capable of holding the difference between two iterators of the text
- typedef typename algorithm_type::string_difference_type string_difference_type;
+
//! Constructs a finder given a pattern and a text
/*!
@@ -102,57 +93,45 @@
references, then a move is performed as opposed to a copy.
*/
explicit finder_t (const Sequence1T *const substring = 0, Sequence2T *const string = 0,
- ComparatorT comparator = ComparatorT(), AllocatorT allocator = AllocatorT())
- : comparator_(comparator), allocator_(allocator),
- substring_optional_copy_(), substring_range_(substring?*substring:substring_optional_copy_),
- string_optional_copy_(), string_range_(string?*string:string_optional_copy_),
- start_offset_(boost::begin(string_range_)),
- algorithm_type(),
+ ComparatorT const &comparator = ComparatorT(), AllocatorT const &allocator = AllocatorT())
+ : algorithm_(comparator, allocator), substring_optional_copy_(), string_optional_copy_(),
+ ranges_(substring?*substring:substring_optional_copy_, string?*string:string_optional_copy_),
substring_has_changed_(true), string_has_changed_(true)
{ }
//! \overload
template <class Range2T>
- finder_t (const Sequence1T *const substring, const Range2T &string,
- ComparatorT comparator = ComparatorT(), AllocatorT allocator = AllocatorT(),
+ 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)
- : comparator_(comparator), allocator_(allocator),
- substring_optional_copy_(), substring_range_(substring?*substring:substring_optional_copy_),
- string_optional_copy_(), string_range_(),
- start_offset_(),
- algorithm_type(),
- substring_has_changed_(true), string_has_changed_(true)
+ : algorithm_(comparator, allocator), substring_optional_copy_(), string_optional_copy_(), ranges_(),
+ substring_has_changed_(true)
{
set_string(string);
+ ranges_.substr = substring?*substring:substring_optional_copy_;
}
//! \overload
template <class Range1T>
explicit finder_t (const Range1T &substring, Sequence2T *const string = 0,
- ComparatorT comparator = ComparatorT(), AllocatorT allocator = AllocatorT(),
+ ComparatorT const &comparator = ComparatorT(), AllocatorT const &allocator = AllocatorT(),
typename boost::disable_if<typename ::boost::algorithm::detail::is_pointer_to<Range1T,Sequence1T> >::type* = 0)
- : comparator_(comparator), allocator_(allocator),
- substring_optional_copy_(), substring_range_(),
- string_optional_copy_(), string_range_(string?boost::as_literal(*string):string_optional_copy_),
- start_offset_(boost::begin(string_range_)),
- algorithm_type(),
- substring_has_changed_(true), string_has_changed_(true)
+ : algorithm_(comparator, allocator),
+ substring_optional_copy_(), string_optional_copy_(), ranges_(),
+ string_has_changed_(true)
{
set_substring(substring);
+ ranges_.str = string?boost::as_literal(*string):string_optional_copy_;
}
//! \overload
template <class Range1T, class Range2T>
- finder_t (const Range1T &substring, const Range2T &string,
+ 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)
- : comparator_(comparator), allocator_(allocator),
- substring_optional_copy_(), substring_range_(),
- string_optional_copy_(), string_range_(),
- start_offset_(),
- algorithm_type(),
- substring_has_changed_(true), string_has_changed_(true)
+ : algorithm_(comparator, allocator),
+ substring_optional_copy_(), string_optional_copy_(), ranges_()
{
set_substring(substring);
set_string(string);
@@ -164,12 +143,10 @@
explicit finder_t (
Sequence1T const &&substring,
Sequence2T *const string = 0,
- ComparatorT comparator = ComparatorT(), AllocatorT allocator = AllocatorT())
- : comparator_(comparator), allocator_(allocator),
+ ComparatorT const &comparator = ComparatorT(), AllocatorT const &allocator = AllocatorT())
+ : algorithm_(comparator, allocator),
substring_optional_copy_(std::move(substring)), string_optional_copy_(),
- substring_range_(substring_optional_copy_), string_range_(string?*string:string_optional_copy_),
- start_offset_(boost::begin(string_range_)),
- algorithm_type(),
+ ranges_(substring_optional_copy_, string?*string:string_optional_copy_),
substring_has_changed_(true), string_has_changed_(true)
{ }
@@ -177,39 +154,33 @@
template <class Range2T>
explicit finder_t (
Sequence1T const &&substring,
- const Range2T &string,
- ComparatorT comparator = ComparatorT(), AllocatorT allocator = AllocatorT(),
+ 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)
- : comparator_(comparator), allocator_(allocator),
- substring_optional_copy_(std::move(substring)), substring_range_(substring_optional_copy_),
- string_optional_copy_(), string_range_(),
- start_offset_(),
- algorithm_type(),
- substring_has_changed_(true), string_has_changed_(true)
- { set_string(string); }
+ : algorithm_(comparator, allocator),
+ substring_optional_copy_(std::move(substring)),
+ string_optional_copy_(), ranges_(),
+ substring_has_changed_(true)
+ { set_string(string); ranges_.substr = substring_optional_copy_; }
//! \overload
finder_t (
Sequence1T const &&substring,
Sequence2T &&string,
- ComparatorT comparator = ComparatorT(), AllocatorT allocator = AllocatorT())
- : comparator_(comparator), allocator_(allocator),
+ ComparatorT const &comparator = ComparatorT(), AllocatorT const &allocator = AllocatorT())
+ : algorithm_(comparator, allocator),
substring_optional_copy_(std::move(substring)), string_optional_copy_(std::move(string)),
- substring_range_(substring_optional_copy_), string_range_(string_optional_copy_),
- start_offset_(boost::begin(string_range_)),
- algorithm_type(),
+ ranges_(substring_optional_copy_, string_optional_copy_),
substring_has_changed_(true), string_has_changed_(true)
{ }
//! \overload
finder_t (const Sequence1T *const substring,
Sequence2T &&string,
- ComparatorT comparator = ComparatorT(), AllocatorT allocator = AllocatorT())
- : comparator_(comparator), allocator_(allocator),
+ ComparatorT const &comparator = ComparatorT(), AllocatorT const &allocator = AllocatorT())
+ : algorithm_(comparator, allocator),
substring_optional_copy_(), string_optional_copy_(std::move(string)),
- substring_range_(substring?*substring:substring_optional_copy_), string_range_(string_optional_copy_),
- start_offset_(boost::begin(string_range_)),
- algorithm_type(),
+ ranges_(substring?*substring:substring_optional_copy_, string_optional_copy_),
substring_has_changed_(true), string_has_changed_(true)
{ }
@@ -217,15 +188,12 @@
template <class Range1T>
finder_t (const Range1T &substring,
Sequence2T &&string,
- ComparatorT comparator = ComparatorT(), AllocatorT allocator = AllocatorT(),
+ ComparatorT const &comparator = ComparatorT(), AllocatorT const &allocator = AllocatorT(),
typename boost::disable_if<typename ::boost::algorithm::detail::is_pointer_to<Range1T,Sequence1T> >::type* = 0)
- : comparator_(comparator), allocator_(allocator),
- substring_optional_copy_(), substring_range_(),
- string_optional_copy_(std::move(string)), string_range_(string_optional_copy_),
- start_offset_(boost::begin(string_range_)),
- algorithm_type(),
- substring_has_changed_(true), string_has_changed_(true)
- { set_substring(substring); }
+ : algorithm_(comparator, allocator),
+ substring_optional_copy_(), string_optional_copy_(std::move(string)),
+ ranges_(), string_has_changed_(true)
+ { set_substring(substring); ranges_.str = string_optional_copy_; }
# endif
@@ -237,17 +205,18 @@
\ref use_internal_substring() (if the used pattern was the internal pattern)
or .set_substring(&your_pattern) otherwise
*/
- typename substring_range_type get_substring_range() const
- { return substring_range_; }
+ substring_range_type get_substring_range() const
+ { return ranges_.substr; }
//! Get an iterator range of the current text
/*!
\return Range of the current text
\see get_substring_range()
*/
- typename string_range_type get_string_range() const
- { return string_range_; }
+ string_range_type get_string_range() const
+ { return ranges_.str; }
+ /*
//! Gets a reference to an instance of the comparator in use
typename boost::call_traits<comparator_type>::const_reference get_comparator() const
{ return comparator_; }
@@ -262,6 +231,9 @@
//! \return A reference to the current allocator
typename boost::call_traits<allocator_type>::const_reference get_allocator() const
{ return allocator_; }
+ */
+
+ std::string get_algorithm_name() const { return algorithm_.get_algorithm_name(); }
//! Change the pattern (substring) to be searched.
/*!
@@ -280,7 +252,7 @@
substring_optional_copy_.clear();
substring_optional_copy_.insert(substring_optional_copy_.end(),
boost::begin(substring_range), boost::end(substring_range));
- substring_range_ = substring_optional_copy_;
+ ranges_.substr = substring_optional_copy_;
substring_has_changed_ = true;
}
@@ -289,9 +261,9 @@
{
substring_optional_copy_.clear();
if (substring)
- substring_range_ = *substring;
+ ranges_.substr = *substring;
else
- substring_range_ = substring_optional_copy_;
+ ranges_.substr = substring_optional_copy_;
substring_has_changed_ = true;
}
@@ -301,7 +273,7 @@
Sequence1T const &&substring)
{
substring_optional_copy_ = std::move(substring);
- substring_range_ = substring_optional_copy_;
+ ranges_.substr = substring_optional_copy_;
substring_has_changed_ = true;
}
# endif
@@ -321,7 +293,7 @@
string_optional_copy_.clear();
string_optional_copy_.insert(string_optional_copy_.end(),
boost::begin(string_range), boost::end(string_range));
- string_range_ = string_optional_copy_;
+ ranges_.str = string_optional_copy_;
string_has_changed_ = true;
}
@@ -330,19 +302,18 @@
{
string_optional_copy_.clear();
if (string)
- string_range_ = *string;
+ ranges_.str = *string;
else
- string_range_ = string_optional_copy_;
+ ranges_.str = string_optional_copy_;
string_has_changed_ = true;
}
# ifdef BOOST_HAS_RVALUE_REFS
//!overload
- void set_string (
- Sequence2T &&string)
+ void set_string (Sequence2T &&string)
{
string_optional_copy_ = std::move(string);
- string_range_ = string_optional_copy_;
+ ranges_.str = string_optional_copy_;
string_has_changed_ = true;
}
# endif
@@ -368,7 +339,7 @@
string_range_type operator()(string_iterator_type &string_start,
string_iterator_type &string_end)
{
- string_range_ = boost::make_iterator_range(string_start, string_end);
+ ranges_.str = boost::make_iterator_range(string_start, string_end);
string_has_changed_ = true;
return find_first();
}
@@ -385,7 +356,8 @@
*/
void use_internal_string()
{
- set_string();
+ ranges_.str = string_optional_copy_;
+ string_has_changed_ = true;
}
//! Forces the finder to use its internal pattern for searching
@@ -394,7 +366,8 @@
*/
void use_internal_substring()
{
- set_substring();
+ ranges_.substr = substring_optional_copy_;
+ substring_has_changed_ = true;
}
//! Gets a reference to its internal pattern sequence
@@ -478,21 +451,20 @@
string_range_type find_next()
{
apply_changes();
- if (start_offset_ == boost::end(string_range_))
+ if (ranges_.offset == boost::end(ranges_.str))
return boost::iterator_range<string_iterator_type>(
- start_offset_, start_offset_
+ ranges_.offset, ranges_.offset
);
- string_range_type ret =
- algorithm_type::find(start_offset_);
- if (boost::begin(ret) == boost::end(string_range_))
+ string_range_type ret = algorithm_.find(ranges_);
+ if (boost::begin(ret) == boost::end(ranges_.str))
{
- start_offset_ = boost::end(string_range_);
+ ranges_.offset = boost::end(ranges_.str);
return ret;
}
else
{
- start_offset_ = boost::begin(ret);
- ++start_offset_;
+ ranges_.offset = boost::begin(ret);
+ ++ranges_.offset;
return ret;
}
}
@@ -508,21 +480,21 @@
apply_changes();
//empty substring
- if (boost::begin(substring_range_) == boost::end(substring_range_))
+ if (boost::begin(ranges_.substr) == boost::end(ranges_.substr))
{
//empty string, empty substring
// TODO if this gets called more times, it always returns 0
// i.e. the pointer is not moved. what would be a good solution for that?
// maybe a special dummy value for the range?
- if (boost::begin(string_range_) == boost::end(string_range_))
+ if (boost::begin(ranges_.str) == boost::end(ranges_.str))
return static_cast<string_difference_type>(0);
//empty substring, offset at the end of the range
- if (start_offset_ == boost::end(string_range_))
+ if (ranges_.offset == boost::end(ranges_.str))
return static_cast<string_difference_type>(-1);
//empty substring, offset not at the end of range
- return std::distance(boost::begin(string_range_),start_offset_++);
+ return std::distance(boost::begin(ranges_.str),ranges_.offset++);
}
- else if (boost::begin(string_range_) == boost::end(string_range_))
+ else if (boost::begin(ranges_.str) == boost::end(ranges_.str))
{
//empty string, nonempty substring
return static_cast<string_difference_type>(-1);
@@ -530,15 +502,15 @@
//perform an actual search
string_range_type const &match = find_next();
- if (boost::begin(match) == boost::end(string_range_))
+ if (boost::begin(match) == boost::end(ranges_.str))
return static_cast<string_difference_type>(-1);
- return std::distance(boost::begin(string_range_), boost::begin(match));
+ return std::distance(boost::begin(ranges_.str), boost::begin(match));
}
//! Reset the internal offset to the beginning of the text.
void find_reset()
{
- start_offset_ = boost::begin(string_range_);
+ ranges_.offset = boost::begin(ranges_.str);
}
private:
@@ -547,23 +519,20 @@
if (substring_has_changed_ || string_has_changed_) {
find_reset();
if (substring_has_changed_) {
- on_substring_change();
+ algorithm_.on_substring_change(ranges_);
substring_has_changed_ = false;
}
if (string_has_changed_) {
- on_string_change();
+ algorithm_.on_string_change(ranges_);
string_has_changed_ = false;
}
}
}
+ algorithm_type algorithm_;
substring_type substring_optional_copy_;
string_type string_optional_copy_;
- comparator_type comparator_;
- allocator_type allocator_;
- substring_range_type substring_range_;
- string_range_type string_range_;
- string_iterator_type start_offset_;
+ boost::algorithm::detail::string_search_ranges<Sequence1T, Sequence2T> ranges_;
bool substring_has_changed_, string_has_changed_;
};
@@ -574,4 +543,4 @@
{
using algorithm::finder_t;
}
-#endif // BOOST_ALGORITHM_FINDER_T_HPP
\ No newline at end of file
+#endif // BOOST_ALGORITHM_FINDER_T_HPP
Added: sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/finder_generators.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder/finder_generators.hpp 2010-08-14 20:20:26 EDT (Sat, 14 Aug 2010)
@@ -0,0 +1,235 @@
+#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>
+
+namespace boost { namespace algorithm {
+
+ //! "First" finder generator
+ /*!
+ Constructs a \ref first_finder_t. For backward compatibility, the finder is a
+ functor which looks for the \b first occurrence of the string in a given input.
+ The result is given as an \c iterator_range delimiting the match.
+ \param Search The pattern to look for
+ \param Comp A comparator used to match individual characters
+ \tparam AlgorithmTagT A tag of the search algorithm that should be used for searching
+ \deprecated
+ */
+ template<typename RangeT,typename PredicateT, typename AlgorithmTagT>
+ inline boost::algorithm::first_finder_t<RangeT, 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);
+ }
+
+ //! \overload
+ template<typename RangeT,typename PredicateT>
+ inline boost::algorithm::first_finder_t<RangeT,
+ boost::algorithm::default_finder_algorithm, PredicateT>
+ first_finder(
+ const RangeT& Search, PredicateT const& Comp)
+ {
+ return boost::algorithm::first_finder(Search,Comp, boost::algorithm::default_finder_algorithm_tag());
+ }
+
+ //! \overload
+ template<typename RangeT>
+ inline boost::algorithm::first_finder_t<RangeT, boost::algorithm::default_finder_algorithm,
+ boost::algorithm::is_equal>
+ first_finder(
+ const RangeT& Search)
+ {
+ return boost::algorithm::first_finder(Search,
+ boost::algorithm::is_equal(), boost::algorithm::default_finder_algorithm_tag());
+ }
+
+ //! "Last" finder generator
+ /*!
+ Constructs a \ref last_finder_t. For backward compatibility, the finder is a
+ functor which looks for the \b last occurrence of the string in a given input.
+ The result is given as an \c iterator_range delimiting the match.
+ \param Search The pattern to look for
+ \param Comp A comparator used to match individual characters
+ \tparam AlgorithmTagT A tag of the search algorithm that should be used for searching
+ \deprecated
+ */
+ template<typename RangeT, typename PredicateT, typename AlgorithmTagT>
+ inline boost::algorithm::last_finder_t<RangeT, 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);
+ }
+
+ //!\overload
+ template<typename RangeT, typename PredicateT>
+ inline boost::algorithm::last_finder_t<RangeT, boost::algorithm::default_finder_algorithm,
+ PredicateT>
+ last_finder( const RangeT& Search, PredicateT const &Comp)
+ {
+ return boost::algorithm::last_finder(Search, Comp,
+ boost::algorithm::default_finder_algorithm_tag());
+ }
+
+ //!\overload
+ template<typename RangeT>
+ inline boost::algorithm::last_finder_t<RangeT,
+ boost::algorithm::default_finder_algorithm, boost::algorithm::is_equal>
+ last_finder( const RangeT& Search)
+ {
+ return boost::algorithm::last_finder(Search,
+ boost::algorithm::is_equal(), boost::algorithm::default_finder_algorithm_tag());
+ }
+
+ //! "Nth" finder generator
+ /*!
+ Constructs a \ref nth_finder_t. For backward compatibility, the finder is a
+ functor which looks for the \b Nth occurrence of the string in a given input.
+ The result is given as an \c iterator_range delimiting the match.
+ \param Search The pattern to look for
+ \param Comp A comparator used to match individual characters
+ \tparam AlgorithmTagT A tag of the search algorithm that should be used for searching
+ \deprecated
+ */
+ template<typename RangeT, typename PredicateT, typename AlgorithmTagT>
+ inline boost::algorithm::nth_finder_t<RangeT,
+ 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);
+ }
+
+ //!\overload
+ template<typename RangeT, typename PredicateT>
+ inline boost::algorithm::nth_finder_t<RangeT,
+ boost::algorithm::default_finder_algorithm, PredicateT>
+ nth_finder(const RangeT& Search, int Nth, PredicateT const &Comp)
+ {
+ return boost::algorithm::nth_finder(Search, Nth, Comp,
+ boost::algorithm::default_finder_algorithm_tag());
+ }
+
+ //!\overload
+ template<typename RangeT>
+ inline boost::algorithm::nth_finder_t<RangeT,
+ boost::algorithm::default_finder_algorithm, boost::algorithm::is_equal>
+ nth_finder(const RangeT& Search, int Nth)
+ {
+ return boost::algorithm::nth_finder(Search, Nth, boost::algorithm::is_equal(),
+ boost::algorithm::default_finder_algorithm_tag());
+ }
+
+ //! "Head" finder
+ /*!
+ Construct the \c head_finder. The finder returns a head of a given
+ input. The head is a prefix of a string up to n elements in
+ size. If an input has less then n elements, whole input is
+ considered a head.
+ The result is given as an \c iterator_range delimiting the match.
+
+ \param N The size of the head
+ \return An instance of the \c head_finder object
+ \deprecated
+ */
+ inline detail::head_finderF
+ head_finder( int N )
+ {
+ return detail::head_finderF(N);
+ }
+
+ //! "Tail" finder
+ /*!
+ Construct the \c tail_finder. The finder returns a tail of a given
+ input. The tail is a suffix of a string up to n elements in
+ size. If an input has less then n elements, whole input is
+ considered a head.
+ The result is given as an \c iterator_range delimiting the match.
+
+ \param N The size of the head
+ \return An instance of the \c tail_finder object
+ */
+ inline detail::tail_finderF
+ tail_finder( int N )
+ {
+ return detail::tail_finderF(N);
+ }
+
+ //! "Token" finder
+ /*!
+ Construct the \c token_finder. The finder searches for a token
+ specified by a predicate. It is similar to std::find_if
+ algorithm, with an exception that it return a range of
+ instead of a single iterator.
+
+ If "compress token mode" is enabled, adjacent matching tokens are
+ concatenated into one match. Thus the finder can be used to
+ search for continuous segments of characters satisfying the
+ given predicate.
+
+ The result is given as an \c iterator_range delimiting the match.
+
+ \param Pred An element selection predicate
+ \param eCompress Compress flag
+ \return An instance of the \c token_finder object
+ */
+ template< typename PredicateT >
+ inline detail::token_finderF<PredicateT>
+ token_finder(
+ PredicateT Pred,
+ token_compress_mode_type eCompress=token_compress_off )
+ {
+ return detail::token_finderF<PredicateT>( Pred, eCompress );
+ }
+
+ //! "Range" finder
+ /*!
+ Construct the \c range_finder. The finder does not perform
+ any operation. It simply returns the given range for
+ any input.
+
+ \param Begin Beginning of the range
+ \param End End of the range
+ \param Range The range.
+ \return An instance of the \c range_finger object
+ */
+ template< typename ForwardIteratorT >
+ inline detail::range_finderF<ForwardIteratorT>
+ range_finder(
+ ForwardIteratorT Begin,
+ ForwardIteratorT End )
+ {
+ return detail::range_finderF<ForwardIteratorT>( Begin, End );
+ }
+
+ //! "Range" finder
+ /*!
+ \overload
+ */
+ template< typename ForwardIteratorT >
+ inline detail::range_finderF<ForwardIteratorT>
+ range_finder( iterator_range<ForwardIteratorT> Range )
+ {
+ return detail::range_finderF<ForwardIteratorT>( Range );
+ }
+
+} } // namespace algorithm, namespace boost
+
+namespace boost
+{
+ // pull the names to the boost namespace
+ using algorithm::first_finder;
+ using algorithm::last_finder;
+ using algorithm::nth_finder;
+ using algorithm::head_finder;
+ using algorithm::tail_finder;
+ using algorithm::token_finder;
+ using algorithm::range_finder;
+} // namespace boost
+
+#endif // BOOST_ALGORITHM_FINDER_GENERATORS_HPP
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-14 20:20:26 EDT (Sat, 14 Aug 2010)
@@ -1,76 +1,251 @@
#ifndef BOOST_ALGORITHM_GENERATED_FINDERS_HPP
#define BOOST_ALGORITHM_GENERATED_FINDERS_HPP
-#include <boost/algorithm/string/finder/detail/last_finder_impl.hpp>
-#include <boost/algorithm/string/finder/detail/nth_finder_impl.hpp>
-#include <boost/algorithm/string/finder/simplified_finder.hpp>
+//#include <boost/algorithm/string/finder/detail/last_finder_impl.hpp>
+//#include <boost/algorithm/string/finder/detail/nth_finder_impl.hpp>
+#include <boost/algorithm/string/finder/detail/string_search_ranges.hpp>
#include <boost/algorithm/string/finder/detail/finder_typedefs.hpp>
#include <boost/range/begin.hpp>
#include <boost/range/end.hpp>
#include <boost/range/as_literal.hpp>
+#include <boost/range/value_type.hpp>
+#include <boost/range/iterator_range.hpp>
+
+#include <boost/iterator/iterator_traits.hpp>
#include <memory>
namespace boost { namespace algorithm {
- template <class Range1T, class Range2T, class AlgorithmT, class ComparatorT>
+ template <class Range1T, class AlgorithmT, class ComparatorT>
class first_finder_t
- : public boost::algorithm::detail::finder_typedefs<Range1T, Range2T, ComparatorT, std::allocator<std::size_t> >
{
public:
- first_finder_t (Range1T const *const substr, ComparatorT comparator=ComparatorT())
- : finder(comparator) { finder.set_substring(substr); }
- string_range_type operator()(string_iterator_type const &string_start, string_iterator_type const &string_end)
+ first_finder_t (Range1T const *const substr, ComparatorT const &comparator=ComparatorT())
+ : substring_range_(boost::as_literal(*substr)), algorithm_(comparator,std::allocator<std::size_t>()),
+ first_call_(true) { }
+
+ template <class Iterator2T>
+ typename boost::iterator_range<Iterator2T>
+ operator()(Iterator2T const &string_start, Iterator2T const &string_end)
{
- finder.set_string(string_start, string_end);
- return finder.find_first();
+ typedef 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);
+ ranges.substr = substring_range_;
+ ranges.offset = string_start;
+ if (first_call_) { algorithm_.on_substring_change(ranges); first_call_ = false; }
+ algorithm_.on_string_change(ranges);
+ return algorithm_.find(ranges);
}
private:
- typedef boost::algorithm::simplified_finder_t<Range1T, Range2T, AlgorithmT, ComparatorT> internal_finder_type;
- internal_finder_type finder;
+ 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,
+ ComparatorT, std::allocator<std::size_t> > algorithm_type;
+
+ typename boost::iterator_range<substring_iterator_type> substring_range_;
+ algorithm_type algorithm_;
+ bool first_call_;
};
- template <class Range1T, class Range2T, class AlgorithmT, class ComparatorT>
+ template <class Range1T, class AlgorithmT, class ComparatorT>
class last_finder_t
- : public boost::algorithm::detail::last_finder_impl_t<Range1T, Range2T, AlgorithmT, ComparatorT>
{
- private:
- typedef boost::algorithm::detail::last_finder_impl_t<Range1T, Range2T, AlgorithmT, ComparatorT> impl_type;
public:
- last_finder_t (Range1T const *const substr, ComparatorT comparator=ComparatorT())
- : impl_type(boost::as_literal(*substr), comparator) { }
- };
+ last_finder_t (Range1T const *const substr, ComparatorT const &comparator=ComparatorT())
+ : substring_range_(boost::as_literal(*substr)), algorithm_(comparator,std::allocator<std::size_t>()),
+ first_call_bidi_(true), first_call_forw_(true) { }
+
+ template <class Iterator2T>
+ typename boost::iterator_range<Iterator2T>
+ operator()(Iterator2T const &string_start, Iterator2T const &string_end)
+ {
+ return find(string_start, string_end,
+ typename boost::range_category<Range1T>::type(),
+ 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,
+ std::bidirectional_iterator_tag, std::bidirectional_iterator_tag)
+ {
+ typedef 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,
+ 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_start)
+ );
+ 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 = algorithm_.find(ranges);
+
+ //no match
+ if (boost::begin(ret) == string_reverse_iterator_type(string_start))
+ 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
+ template <class Iterator2T>
+ typename boost::iterator_range<Iterator2T>
+ find (Iterator2T const &string_start, Iterator2T const &string_end,
+ std::forward_iterator_tag, std::forward_iterator_tag)
+ {
+ typedef typename boost::iterator_range<Iterator2T> Range2T;
- template <class Range1T, class Range2T, class AlgorithmT, class ComparatorT>
+ typename boost::algorithm::detail::string_search_ranges<Range1T, Range2T> ranges;
+ ranges.str = boost::make_iterator_range(string_start, string_end);
+ ranges.substr = substring_range_;
+ ranges.offset = string_start;
+
+ 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 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,
+ ComparatorT, std::allocator<std::size_t> > algorithm_type;
+
+ 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>
class nth_finder_t
- : public boost::algorithm::detail::nth_finder_impl_t<Range1T, Range2T, AlgorithmT, ComparatorT>
{
- private:
- typedef boost::algorithm::detail::nth_finder_impl_t<Range1T, Range2T, AlgorithmT, ComparatorT> impl_type;
public:
- nth_finder_t (Range1T const *const substr, ComparatorT comparator=ComparatorT(), int n = 0)
- : impl_type(boost::as_literal(*substr), comparator, n)
- // : finder(comparator), n_(n) { finder.set_substring(substr); }
+ 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),
+ first_call_forw_(true), first_call_bidi_(true) { }
+
+ template <class Iterator2T>
+ typename boost::iterator_range<Iterator2T>
+ operator()(Iterator2T const &string_start, 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);
}
- /*void set_n(int n) { n_ = n; }
- string_range_type operator()(string_iterator_type const &string_start, string_iterator_type const &string_end)
+ private:
+ //find nth, for n>=0
+ template <class Iterator2T>
+ typename boost::iterator_range<Iterator2T>
+ find(Iterator2T const &string_start, Iterator2T const &string_end)
{
- //IMPORTANT TODO: THIS ONLY TREATS THE CASE OF N>=0, MAKE IT SO IT WORKS WITH N<=0 too
- string_range_type ret;
- finder.set_string(string_start, string_end);
+ typedef 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;
+
+ 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 = finder.find_next();
- if (boost::begin(ret) == boost::end(finder.get_string_range())) return ret;
+ 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;
}
- private:
- typedef boost::algorithm::simplified_finder_t<Range1T, Range2T, AlgorithmT, ComparatorT> internal_finder_type;
- int n_; // TODO: better type?
- internal_finder_type finder;*/
+
+ //find nth, for n < 0
+ template <class Iterator2T>
+ typename boost::iterator_range<Iterator2T>
+ find_backwards(Iterator2T const &string_start, Iterator2T const &string_end,
+ std::bidirectional_iterator_tag, std::bidirectional_iterator_tag)
+ {
+ typedef 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_start)
+ );
+ 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_start))
+ 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,
+ ComparatorT, std::allocator<std::size_t> > algorithm_type;
+
+ typename boost::iterator_range<substring_iterator_type> substring_range_;
+ algorithm_type algorithm_;
+ bool first_call_forw_, first_call_bidi_;
+ int n_;
};
} }
@@ -81,4 +256,4 @@
using algorithm::nth_finder_t;
}
-#endif // BOOST_ALGORITHM_GENERATED_FINDERS_HPP
\ No newline at end of file
+#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-14 20:20:26 EDT (Sat, 14 Aug 2010)
@@ -3,6 +3,7 @@
#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/range/as_literal.hpp>
#include <boost/range/iterator_range.hpp>
@@ -34,49 +35,26 @@
class ComparatorT = ::boost::algorithm::is_equal,
class AllocatorT = std::allocator<std::size_t>
>
- class simplified_finder_t :
- public AlgorithmT::template algorithm<
- simplified_finder_t<Range1T, Range2T, AlgorithmT, ComparatorT, AllocatorT>,
- Range1T, Range2T, ComparatorT,AllocatorT>
+ class simplified_finder_t
{
// TODO Add concept assertions here.
+ public:
+ BOOST_ALGORITHM_DETAIL_COMMON_FINDER_TYPEDEFS(Range1T, Range2T);
+ BOOST_ALGORITHM_DETAIL_FINDER_TYPEDEFS2(ComparatorT, AllocatorT);
private:
- typedef typename AlgorithmT::template algorithm<simplified_finder_t, Range1T,
- Range2T, ComparatorT, AllocatorT> algorithm_type;
+ typedef typename AlgorithmT::template algorithm<substring_char_type, string_char_type,
+ comparator_type, allocator_type> algorithm_type;
public:
- //! The type of the pattern (substring)
- typedef typename algorithm_type::substring_type substring_type;
- //! The type of the text (string)
- typedef typename algorithm_type::string_type string_type;
- //! The type of the comparator
- typedef typename algorithm_type::comparator_type comparator_type;
- //! The type of the allocator
- typedef typename algorithm_type::allocator_type allocator_type;
- //! The type of the substring's iterator
- typedef typename algorithm_type::substring_iterator_type substring_iterator_type;
- //! The type of the text's iterator
- typedef typename algorithm_type::string_iterator_type string_iterator_type;
- //! The character type of the substring
- typedef typename algorithm_type::substring_char_type substring_char_type;
- //! The character type of the text
- typedef typename algorithm_type::string_char_type string_char_type;
- //! The range type of the substring (pattern)
- typedef typename algorithm_type::substring_range_type substring_range_type;
- //! The range type of the text
- typedef typename algorithm_type::string_range_type string_range_type;
- //! A type capable of holding the difference between two iterators of the text
- typedef typename algorithm_type::string_difference_type string_difference_type;
-
//! Constructs a finder.
/*!
\param comparator ComparatorT instance used to compare individual characters
\param allocator AllocatorT instance used to allocate memory
for storing precomputed data if necessary
*/
- explicit simplified_finder_t(ComparatorT comparator = ComparatorT(), AllocatorT allocator = AllocatorT())
- : substring_range_(), string_range_(), substring_has_changed_(false),
- string_has_changed_(false), comparator_(comparator), allocator_(allocator),
- start_offset_()
+ explicit simplified_finder_t(ComparatorT const &comparator = ComparatorT(),
+ AllocatorT const &allocator = AllocatorT())
+ : ranges_(), substring_has_changed_(false), string_has_changed_(false),
+ algorithm_(comparator, allocator)
{ }
/*!
Constructs a finder given a pattern and a text
@@ -95,32 +73,27 @@
finder.set_substring(&substr); // re-set the substring so the finder now uses the new, valid range
</code> </example>
*/
- simplified_finder_t(Range1T const *const substr, Range2T *str,
+ simplified_finder_t(Range1T const *const substr, Range2T *const str,
ComparatorT comparator = ComparatorT(), AllocatorT allocator = AllocatorT())
- : substring_range_(boost::as_literal(*substr)),
- string_range_(boost::as_literal(*str)),
- comparator_(comparator), allocator_(allocator),
- substring_has_changed_(true), string_has_changed_(true),
- algorithm_type()
+ : ranges_(boost::as_literal(*substr), boost::as_literal(*str)),
+ algorithm_(comparator, allocator),
+ substring_has_changed_(true), string_has_changed_(true)
{ }
simplified_finder_t (const simplified_finder_t &other)
- : substring_range_(other.substring_range_), string_range_(other.string_range_),
- substring_has_changed_(other.substring_has_changed_), string_has_changed_(other.string_has_changed_),
- comparator_(other.comparator_), allocator_(other.allocator_), start_offset_(other.start_offset_),
- algorithm_type(other)
+ : ranges_(other.ranges_), algorithm_(other.algorithm_),
+ substring_has_changed_(other.substring_has_changed_),
+ string_has_changed_(other.string_has_changed_)
{
}
+
simplified_finder_t &operator=(const simplified_finder_t &rhs)
{
- substring_range_ = rhs.substring_range_;
- string_range_ = rhs.string_range_;
+ ranges_ = rhs.ranges_;
+ algorithm_ = rhs.algorithm_;
substring_has_changed_ = rhs.substring_has_changed_;
string_has_changed_ = rhs.string_has_changed_;
- comparator_ = rhs.comparator_;
- allocator_ = rhs.allocator_;
- start_offset_ = rhs.start_offset_;
return *this;
}
@@ -129,11 +102,11 @@
\param substr A pointer to a range (or a character array) representing the sought string
*/
void set_substring (substring_type const *const substr)
- { substring_range_ = boost::as_literal(*substr); substring_has_changed_ = true; }
+ { ranges_.substr = boost::as_literal(*substr); substring_has_changed_ = true; }
void set_substring (substring_iterator_type const &substring_begin, substring_iterator_type const &substring_end)
{
- substring_range_ = boost::make_iterator_range(substring_begin, substring_end);
+ ranges_.substr = boost::make_iterator_range(substring_begin, substring_end);
substring_has_changed_ = true;
}
@@ -143,17 +116,17 @@
in which to search
*/
void set_string (string_type *const str)
- { string_range_ = boost::as_literal(*str); string_has_changed_ = true; }
+ { ranges_.str = boost::as_literal(*str); string_has_changed_ = true; }
void set_string (string_iterator_type const &string_begin, string_iterator_type const &string_end)
{
- string_range_ = boost::make_iterator_range(string_begin, string_end);
+ ranges_.str = boost::make_iterator_range(string_begin, string_end);
string_has_changed_ = true;
}
//! Reset the internal offset to the beginning of the text.
void find_reset ()
- { start_offset_ = boost::begin(string_range_); }
+ { ranges_.offset = boost::begin(ranges_.str); }
//! Finds the first occurrence of the pattern in the text (substring in the string)
/*!
@@ -186,8 +159,8 @@
return finder.find_first();
</code>
*/
- string_range_type operator()(string_iterator_type &string_start,
- string_iterator_type &string_end)
+ string_range_type operator()(string_iterator_type const &string_start,
+ string_iterator_type const &string_end)
{
set_string(string_start, string_end);
return find_first();
@@ -201,19 +174,19 @@
string_range_type find_next()
{
apply_changes();
- if (start_offset_ == boost::end(string_range_))
- return string_range_type(start_offset_, start_offset_);
+ if (ranges_.offset == boost::end(ranges_.str))
+ return string_range_type(ranges_.offset, ranges_.offset);
string_range_type ret =
- algorithm_type::find(start_offset_);
- if (boost::begin(ret) == boost::end(string_range_))
+ algorithm_.find(ranges_);
+ if (boost::begin(ret) == boost::end(ranges_.str))
{
- start_offset_ = boost::end(string_range_);
+ ranges_.offset = boost::end(ranges_.str);
return ret;
}
else
{
- start_offset_ = boost::begin(ret);
- ++start_offset_;
+ ranges_.offset = boost::begin(ret);
+ ++ranges_.offset;
return ret;
}
}
@@ -224,7 +197,7 @@
\warning If you modify the contents in this range, you must manually call
\ref use_internal_substring(), so that the finder can perform any required precomputation on the pattern
*/
- substring_range_type get_substring_range() const { return substring_range_; }
+ substring_range_type get_substring_range() const { return ranges_.substr; }
//! Get an iterator range of the current text
/*!
@@ -232,8 +205,10 @@
\warning If you modify the contents in this range, you must manually call
\ref use_internal_string(), so that the finder can perform any required precomputation on the text
*/
- string_range_type get_string_range() const { return string_range_; }
-
+ 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
{ return comparator_; }
@@ -247,6 +222,8 @@
//! \return A reference to the current allocator
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:
inline void apply_changes()
@@ -254,26 +231,19 @@
if (substring_has_changed_ || string_has_changed_) {
find_reset();
if (substring_has_changed_) {
- on_substring_change();
+ algorithm_.on_substring_change(ranges_);
substring_has_changed_ = false;
}
if (string_has_changed_) {
- on_string_change();
+ algorithm_.on_string_change(ranges_);
string_has_changed_ = false;
}
}
}
-
- protected:
- substring_range_type substring_range_;
- string_range_type string_range_;
+ boost::algorithm::detail::string_search_ranges<substring_type, string_type> ranges_;
+ algorithm_type algorithm_;
bool substring_has_changed_, string_has_changed_;
-
- comparator_type comparator_;
- allocator_type allocator_;
-
- string_iterator_type start_offset_;
};
} }
@@ -283,4 +253,4 @@
using algorithm::simplified_finder_t;
}
-#endif // BOOST_ALGORITHM_SIMPLIFIED_FINDER_HPP
\ No newline at end of file
+#endif // BOOST_ALGORITHM_SIMPLIFIED_FINDER_HPP
Modified: sandbox/SOC/2010/stringalgos/boost/algorithm/string/predicate.hpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/boost/algorithm/string/predicate.hpp (original)
+++ sandbox/SOC/2010/stringalgos/boost/algorithm/string/predicate.hpp 2010-08-14 20:20:26 EDT (Sat, 14 Aug 2010)
@@ -20,7 +20,8 @@
#include <boost/range/iterator_range.hpp>
#include <boost/algorithm/string/compare.hpp>
-#include <boost/algorithm/string/find.hpp>
+#include <boost/algorithm/string/finder/default_search_algorithm.hpp>
+#include <boost/algorithm/string/finder/simplified_finder.hpp>
#include <boost/algorithm/string/detail/predicate.hpp>
/*! \file boost/algorithm/string/predicate.hpp
@@ -215,18 +216,29 @@
const Range2T& Test,
PredicateT Comp)
{
- iterator_range<BOOST_STRING_TYPENAME range_const_iterator<Range1T>::type> lit_input(::boost::as_literal(Input));
- iterator_range<BOOST_STRING_TYPENAME range_const_iterator<Range2T>::type> lit_test(::boost::as_literal(Test));
+ /*iterator_range<BOOST_STRING_TYPENAME range_const_iterator<Range1T>::type> lit_input(::boost::as_literal(Input));
+ iterator_range<BOOST_STRING_TYPENAME range_const_iterator<Range2T>::type> lit_test(::boost::as_literal(Test));
if (::boost::empty(lit_test))
{
// Empty range is contained always
return true;
- }
+ }*/
+ //
+ /*
// Use the temporary variable to make VACPP happy
- bool bResult=(::boost::algorithm::first_finder(lit_test,Comp)(::boost::begin(lit_input), ::boost::end(lit_input)));
- return bResult;
+ //bool bResult=(::boost::algorithm::first_finder(lit_test,Comp)(::boost::begin(lit_input), ::boost::end(lit_input)));*/
+
+ boost::algorithm::simplified_finder_t<Range2T, const Range1T,
+ boost::default_finder_algorithm, PredicateT> finder(&Test, &Input, Comp);
+
+ if (boost::empty(finder.get_substring_range()))
+ return true;
+
+ return boost::begin(finder.find_first()) != boost::end(finder.get_string_range());
+ //bool bResult
+ //return bResult;
}
//! 'Contains' predicate
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-14 20:20:26 EDT (Sat, 14 Aug 2010)
@@ -9,4 +9,4 @@
#include <boost/algorithm/string/string_search/boyer_moore.hpp>
#include <boost/algorithm/string/string_search/suffix_array.hpp>
-#endif
\ No newline at end of file
+#endif
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-14 20:20:26 EDT (Sat, 14 Aug 2010)
@@ -1,28 +1,35 @@
#ifndef BOOST_ALGORITHM_BOYER_MOORE_HPP
#define BOOST_ALGORITHM_BOYER_MOORE_HPP
-#include <iterator>
-#include <memory>
-#include <utility>
-#include <vector>
#include <boost/range/begin.hpp>
#include <boost/range/end.hpp>
#include <boost/range/adaptor/reversed.hpp>
#include <boost/range/algorithm/for_each.hpp>
#include <boost/range/distance.hpp>
#include <boost/range/category.hpp>
+
#include <boost/call_traits.hpp>
+
#include <boost/type_traits/is_same.hpp>
+
#include <boost/static_assert.hpp>
+
#include <map>
#include <string>
+#include <locale>
+#include <iterator>
+#include <memory>
+#include <utility>
+#include <vector>
#include <boost/algorithm/string/finder/detail/finder_typedefs.hpp>
+#include <boost/algorithm/string/finder/detail/string_search_ranges.hpp>
#include <boost/unordered_map.hpp>
#include <boost/functional/hash.hpp>
+
#include <boost/utility/enable_if.hpp>
-#include <locale>
+
/*!
\file
@@ -39,33 +46,59 @@
struct boyer_moore
{
- template <class Finder, class RandomAccessRange1T,class RandomAccessRange2T,
- class ComparatorT,class AllocatorT>
+ template <class Range1CharT, class Range2CharT, class ComparatorT, class AllocatorT>
class algorithm
- : public boost::algorithm::detail::finder_typedefs<
- RandomAccessRange1T,RandomAccessRange2T,ComparatorT,AllocatorT>
{
+ private:
+ typedef Range1CharT substring_char_type;
+ typedef Range2CharT string_char_type;
+ typedef ComparatorT comparator_type;
+ typedef AllocatorT allocator_type;
public:
std::string get_algorithm_name () const { return "Boyer-Moore"; }
- protected:
- algorithm () {
+ algorithm (comparator_type const &comp, allocator_type const &alloc)
+ : comp_(comp), alloc_(alloc), table1(alloc_), table2(alloc_)
+ {
BOOST_STATIC_ASSERT((boost::is_same<substring_char_type,string_char_type>::value));
}
- string_range_type find(string_iterator_type start)
+ 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)
{
- return find(start, string_iterator_category());
+
+ return find(ranges, typename boost::range_category<Range2T>::type());
}
//Compute the two tables
- void on_substring_change()
+ template <class Range1T, class Range2T>
+ inline void on_substring_change(
+ typename boost::algorithm::detail::string_search_ranges<Range1T, Range2T> const &ranges)
{
- on_substring_change(substring_iterator_category());
+ on_substring_change(ranges.substr, typename boost::range_category<Range1T>::type());
}
+
//No precomputation to be done on the string
- inline void on_string_change()
- { }
+ template <class T>
+ inline void on_string_change(T const&) { }
private:
+ 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
+ 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
+ > table2_type;
+ table2_type table2;
+
+ std::size_t substr_size_;
+
struct compute_first_table_functor
{
//Case 1: ComparatorT=boost::algorithm::is_equal
@@ -75,7 +108,7 @@
}
compute_first_table_functor (algorithm &alg) : idx_(0), alg_(alg)
{ alg_.table1.clear(); }
- private:
+
template <class ComparatorTT>
void compute_first_table(typename boost::call_traits<substring_char_type>::param_type c,
typename boost::enable_if<
@@ -106,25 +139,10 @@
algorithm &alg_;
};
-#if 0
- struct compute_second_table_functor {
- void operator()(typename boost::call_traits<substring_char_type>::param_type c)
- {
-
- }
- compute_second_table_functor (algorithm &alg) : idx_(0), alg_(alg)
- { /*alg_.table2.clear();*/ }
- private:
- std::size_t idx_;
- algorithm &alg_;
- };
-#endif
-
//precomputation on pattern=bidirectional range
- void on_substring_change(std::bidirectional_iterator_tag)
+ template <class RangeT>
+ void on_substring_change(RangeT const &substr, std::bidirectional_iterator_tag)
{
- substring_range_type const &substr = static_cast<Finder*>(this)->get_substring_range();
- comparator_type const &comp = static_cast<Finder*>(this)->get_comparator();
substr_size_ = boost::distance(substr);
@@ -150,14 +168,14 @@
if (substr_size_ < 2) return;
- substring_iterator_type const &pattern = boost::begin(substr);
+ typename boost::range_iterator<RangeT>::type const &pattern = boost::begin(substr);
//todo find a better solution for this
for (unsigned int i = substr_size_-1;i--;)
{
//pattern[i] != pattern[m-1]
- if (!comp(*(pattern+i),*(pattern+(substr_size_-1))))
+ if (!comp_(*(pattern+i),*(pattern+(substr_size_-1))))
{
table2[substr_size_-1] = substr_size_ - 1 - i;
break;
@@ -175,12 +193,12 @@
{
//Invariant: P[i+1..m-1] = P[j+1..m-1]
//try to align with pattern indexed by j (by sliding the pattern indexed by i)
- while (i != substr_size_ - 1 && !comp(*(pattern+i),*(pattern+j)))
+ while (i != substr_size_ - 1 && !comp_(*(pattern+i),*(pattern+j)))
i = substr_size_ - 1 - failure_func[i + 1];
//Invariant: Either i=m-1 or P[i..m-1] = P[j..m-1]
while (i == substr_size_-1 && j > 0 &&
- !comp(*(pattern+(substr_size_-1)),*(pattern+j)))
+ !comp_(*(pattern+(substr_size_-1)),*(pattern+j)))
{
//couldn't align the given j with any i
failure_func[j] = 0;
@@ -188,7 +206,7 @@
}
//Invariant: either (j==0 and i=m-1) or P[i..m-1] = P[j..m-1]
if (j == 0 && i == substr_size_-1 &&
- !comp(*(pattern+0),*(pattern+(substr_size_-1))))
+ !comp_(*(pattern+0),*(pattern+(substr_size_-1))))
{
failure_func[0] = 0;
}
@@ -224,7 +242,7 @@
//a = m-1-x <=> x = m-1-a
//j = x+1-k <=> k = m-a-j
unsigned int a = failure_func[j];
- while (a > 0 && !comp(*(pattern+(substr_size_-1-a)), *(pattern+(j-1))))
+ while (a > 0 && !comp_(*(pattern+(substr_size_-1-a)), *(pattern+(j-1))))
//while (a > 0 && !compare_range_nth(comp, substr, substr_size_-1-a, substr, j-1))
{
assert(substr_size_-1-a >= substr_size_-a-j); // x >= k
@@ -262,11 +280,20 @@
}
//finding in text=random access range
- string_range_type find(string_iterator_type start, std::random_access_iterator_tag)
+ 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,
+ std::random_access_iterator_tag)
{
- string_range_type const &str = static_cast<Finder*>(this)->get_string_range();
- substring_range_type const &substr = static_cast<Finder*>(this)->get_substring_range();
- comparator_type const &comp = static_cast<Finder*>(this)->get_comparator();
+ BOOST_ALGORITHM_DETAIL_COMMON_FINDER_TYPEDEFS(Range1T, Range2T);
+
+ string_range_type const &str = ranges.str;
+ substring_range_type const &substr = ranges.substr;
+ string_iterator_type start = ranges.offset;
+
+ //string_range_type const &str = static_cast<Finder*>(this)->get_string_range();
+ //substring_range_type const &substr = static_cast<Finder*>(this)->get_substring_range();
+ //comparator_type const &comp = static_cast<Finder*>(this)->get_comparator();
std::size_t str_idx, substr_idx, str_size;
@@ -279,8 +306,7 @@
while (str_idx < str_size)
{
- if (comp(*(start+str_idx), *(boost::begin(substr)+substr_idx)))
- //if (compare_range_nth(comp, start[str_idx], boost::begin(substr)[substr_idx]))
+ if (comp_(*(start+str_idx), *(boost::begin(substr)+substr_idx)))
{
if (substr_idx == 0)
{
@@ -290,7 +316,7 @@
}
else
{
- table1_type::const_iterator iter = table1_find<comparator_type>(start[str_idx]);
+ 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())
{
@@ -318,22 +344,10 @@
return string_range_type(boost::end(str), boost::end(str));
}
- //TODO Maybe optimize for sizeof(substring_char_type)==1?
- typedef typename boost::unordered_map<substring_char_type, std::size_t,
- boost::hash<substring_char_type>, ComparatorT,
- typename AllocatorT::template
- rebind<substring_char_type>::other
- > table1_type;
- table1_type table1;
- typedef typename std::vector<std::size_t,
- typename AllocatorT::template rebind<std::size_t>::other
- > table2_type;
- table2_type table2;
-
//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::enable_if<
typename boost::is_same<ComparatorTT, boost::algorithm::is_equal> >::type* = 0)
{
return table1.find(chr);
@@ -343,14 +357,10 @@
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)
+ typename boost::is_same<ComparatorTT, boost::algorithm::is_iequal> >::type* = 0)
{
return table1.find(std::tolower(chr, std::locale()));
}
-
- //std::vector<std::pair<substring_char_type, std::size_t> > table1;
-
- std::size_t substr_size_;
};
};
@@ -365,4 +375,4 @@
using boost::algorithm::boyer_moore_tag;
}
-#endif
\ No newline at end of file
+#endif
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-14 20:20:26 EDT (Sat, 14 Aug 2010)
@@ -2,19 +2,28 @@
#define BOOST_ALGORITHM_RABIN_KARP_DETAIL_HPP
#include <boost/utility/enable_if.hpp>
+
#include <boost/type_traits/is_base_of.hpp>
#include <boost/type_traits/make_unsigned.hpp>
+
#include <boost/mpl/void.hpp>
#include <boost/mpl/and.hpp>
#include <boost/mpl/not.hpp>
+
#include <boost/range/iterator.hpp>
#include <boost/range/category.hpp>
-#include <boost/call_traits.hpp>
-#include <iterator>
#include <boost/range/begin.hpp>
#include <boost/range/end.hpp>
+
+#include <boost/call_traits.hpp>
+
+#include <iterator>
#include <cassert>
#include <limits>
+#include <memory>
+
+#include <boost/algorithm/string/config.hpp>
+#include <boost/algorithm/string/compare.hpp>
//todo add proper overflow assertions here. also try to find if these aren't already in boost
#define BOOST_ALGORITHM_DETAIL_ASSERTED_ADD(a, b, T) \
@@ -47,67 +56,58 @@
return ret;
}
- template <class Finder, class Range1T,class Range2T, class HashType,
+ template <class Range1CharT, class Range2CharT, class HashType,
HashType FirstBase, HashType FirstModulo,
- HashType SecondBase, HashType SecondModulo, class Enable = void>
+ HashType SecondBase, HashType SecondModulo, class StringIteratorCategory, class Enable = void>
class rabin_karp_algorithm;
// Implementation of Rabin Karp for text supporting Input Iterators
- template <class Finder, class Range1T,class Range2T, class HashType,
+ template <class Range1CharT, class Range2CharT, class HashType,
HashType FirstBase, HashType FirstModulo,
- HashType SecondBase, HashType SecondModulo>
- class rabin_karp_algorithm<Finder,
- Range1T, Range2T, HashType,
- FirstBase, FirstModulo, SecondBase, SecondModulo,
+ 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,
- typename boost::range_category<Range2T>::type>,
- typename boost::mpl::not_<typename boost::is_base_of<std::forward_iterator_tag,
- typename boost::range_category<Range2T>::type> >
- >
+ 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> >
+ >
>::type
>
;
// Implementation of Rabin Karp for text supporting Forward Iterators
- template <class Finder, class Range1T,class ForwardRange2T, class HashType,
+ template <class Range1CharT, class Range2CharT, class HashType,
HashType FirstBase, HashType FirstModulo,
- HashType SecondBase, HashType SecondModulo>
- class rabin_karp_algorithm<Finder,
- Range1T, ForwardRange2T, HashType,
- FirstBase, FirstModulo, SecondBase, SecondModulo,
+ 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,
- typename boost::range_category<ForwardRange2T>::type>,
- typename boost::mpl::not_<typename boost::is_base_of<std::random_access_iterator_tag,
- typename boost::range_category<ForwardRange2T>::type> >
- >
+ 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> >
+ >
>::type
>
;
//Implementation of Rabin Karp for text supporting Random Access Iterators
- template <class Finder, class Range1T,class RandomAccessRange2T, class HashType,
+ template <class Range1CharT, class Range2CharT, class HashType,
HashType FirstBase, HashType FirstModulo,
- HashType SecondBase, HashType SecondModulo>
- class rabin_karp_algorithm<
- Finder, Range1T, RandomAccessRange2T, HashType,
- FirstBase, FirstModulo, SecondBase, SecondModulo,
+ 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<
std::random_access_iterator_tag,
- typename boost::range_category<RandomAccessRange2T>::type
+ StringIteratorCategory
>
>::type
>
- //todo this generates possibly invalid allocator_type typedefs, although this is internally not relevant
- // because rabin_karp doesn't need an allocator. however, this may be nasty externally
- // possibly fix, although it's minor.
- : public boost::algorithm::detail::finder_typedefs<
- Range1T,RandomAccessRange2T,boost::algorithm::is_equal,std::allocator<std::size_t> >
{
+ private:
+ typedef Range1CharT substring_char_type;
+ typedef Range2CharT string_char_type;
protected:
rabin_karp_algorithm() :
@@ -119,12 +119,18 @@
//\todo this the right name? the right way to do it?
template <class T>
- inline HashType integer_promotion(T i)
- { return static_cast<HashType>(static_cast<boost::make_unsigned<T>::type>(i)); }
+ BOOST_STRING_FORCE_INLINE HashType integer_promotion(T i)
+ { return static_cast<HashType>(static_cast<typename boost::make_unsigned<T>::type>(i)); }
- void on_substring_change()
+ public:
+
+ template <class Range1T, class Range2T>
+ inline void on_substring_change(
+ typename boost::algorithm::detail::string_search_ranges<Range1T, Range2T> const &ranges)
{
- substring_range_type const &substr = static_cast<Finder*>(this)->get_substring_range();
+ BOOST_ALGORITHM_DETAIL_COMMON_FINDER_TYPEDEFS(Range1T, Range2T);
+
+ substring_range_type const &substr = ranges.substr;
HashType first = static_cast<HashType>(0), second = static_cast<HashType>(0);
@@ -149,12 +155,16 @@
second_substring_hash_ = second;
if (substring_size_ != old_substring_size)
- on_string_change();
+ on_string_change(ranges);
}
- void on_string_change()
+ template <class Range1T, class Range2T>
+ inline void on_string_change(
+ typename boost::algorithm::detail::string_search_ranges<Range1T, Range2T> const &ranges)
{
- string_range_type const &str = static_cast<Finder*>(this)->get_string_range();
+ BOOST_ALGORITHM_DETAIL_COMMON_FINDER_TYPEDEFS(Range1T, Range2T);
+
+ string_range_type const &str = ranges.str;
HashType first = static_cast<HashType>(0), second = static_cast<HashType>(0);
std::size_t computed = 0;
@@ -177,9 +187,15 @@
second_string_hash_current_ = second;
}
- string_range_type find(string_iterator_type start)
+ 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)
{
- string_range_type const &str = static_cast<Finder*>(this)->get_string_range();
+ BOOST_ALGORITHM_DETAIL_COMMON_FINDER_TYPEDEFS(Range1T, Range2T);
+
+ string_range_type const &str = ranges.str;
+ substring_range_type const &substr = ranges.substr;
+ string_iterator_type start = ranges.offset;
//substring bigger than string
if (string_size_ < substring_size_)
@@ -200,7 +216,7 @@
}
//roll the hash until we reach the current offset
while (offset > string_computed_upto_ - substring_size_)
- roll_string_hash();
+ roll_string_hash(str);
//a match found right at the current offset.
if (equal())
@@ -208,7 +224,7 @@
//rolling the hash until we find a match
while (string_computed_upto_ != string_size_)
{
- roll_string_hash();
+ roll_string_hash(str);
//match found
if (equal())
return boost::iterator_range<string_iterator_type>(
@@ -242,16 +258,16 @@
//todo compatible force inline? __attribute__((force_inline)) in GCC
//inline void roll_string_hash()
- __forceinline void roll_string_hash()
+ template <class StrT>
+ BOOST_STRING_FORCE_INLINE void roll_string_hash(StrT const &str)
{
- string_range_type const &str = static_cast<Finder*>(this)->get_string_range();
HashType remove = static_cast<HashType>(
- static_cast<boost::make_unsigned<string_char_type>::type>(
+ static_cast<typename boost::make_unsigned<string_char_type>::type>(
boost::begin(str)[string_computed_upto_-substring_size_]
));
HashType add = static_cast<HashType>(
- static_cast<boost::make_unsigned<string_char_type>::type>(
+ static_cast<typename boost::make_unsigned<string_char_type>::type>(
boost::begin(str)[string_computed_upto_]
));
@@ -293,4 +309,4 @@
};
} } }
-#endif
\ No newline at end of file
+#endif
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-14 20:20:26 EDT (Sat, 14 Aug 2010)
@@ -8,8 +8,10 @@
#include <boost/range/iterator_range.hpp>
#include <boost/range/begin.hpp>
#include <boost/range/end.hpp>
+#include <boost/range/category.hpp>
#include <boost/algorithm/string/finder/detail/finder_typedefs.hpp>
+#include <boost/algorithm/string/finder/detail/string_search_ranges.hpp>
/*!
\file
@@ -21,38 +23,61 @@
struct knuth_morris_pratt
{
- template <class Finder,class RandomAccessRange1T,
- class RandomAccessRange2T,class ComparatorT,class AllocatorT>
+ template <class Range1CharT, class Range2CharT, class ComparatorT, class AllocatorT>
class algorithm
- : public boost::algorithm::detail::finder_typedefs<
- RandomAccessRange1T,RandomAccessRange2T,ComparatorT,AllocatorT>
+ /*: 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;
+ typedef ComparatorT comparator_type;
+ typedef AllocatorT allocator_type;
public:
std::string get_algorithm_name () const { return "Knuth-Morris-Pratt"; }
- protected:
- string_range_type find(string_iterator_type start)
+
+ algorithm (comparator_type const &comp, allocator_type const &alloc)
+ : comp_(comp), alloc_(alloc), failure_func(alloc_)
{
- return find(start, string_iterator_category());
}
- void on_substring_change()
+
+ 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)
{
- on_substring_change(substring_iterator_category());
+ return find(ranges, typename boost::range_category<Range2T>::type());
}
- void on_string_change()
+ template <class Range1T, class Range2T>
+ inline void on_substring_change(
+ typename boost::algorithm::detail::string_search_ranges<Range1T, Range2T> const &ranges)
{
+ on_substring_change(ranges.substr, typename boost::range_category<Range1T>::type());
}
+
+ //No precomputation to be done on the string
+ template <class T>
+ inline void on_string_change(T const&) { }
private:
+ comparator_type comp_;
+ allocator_type alloc_;
std::vector<std::size_t,
- typename AllocatorT::template rebind<std::size_t>::other > failure_func;
+ typename allocator_type::template rebind<std::size_t>::other > failure_func;
- string_range_type find(string_iterator_type start, std::random_access_iterator_tag)
+ 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,
+ std::random_access_iterator_tag)
{
- string_range_type const &str = static_cast<Finder*>(this)->get_string_range();
- substring_range_type const &substr = static_cast<Finder*>(this)->get_substring_range();
- comparator_type const &comp = static_cast<Finder*>(this)->get_comparator();
+ BOOST_ALGORITHM_DETAIL_COMMON_FINDER_TYPEDEFS(Range1T, Range2T);
+
+ string_range_type const &str = ranges.str;
+ 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,
@@ -79,13 +104,13 @@
//Slide the pattern to the right until we manage to find a match for the current char
while (substr_idx > 0 &&
- !comp(*(boost::begin(str)+str_idx),*(boost::begin(substr)+substr_idx)))
+ !comp_(*(boost::begin(str)+str_idx),*(boost::begin(substr)+substr_idx)))
substr_idx = failure_func[substr_idx-1];
// Invariant: Either substr_idx==0 or string[str_idx]==substr[substr_idx]
while (substr_idx == 0 && str_idx < compare_against
- && !comp(*(boost::begin(str)+str_idx),*(boost::begin(substr)+0)))
+ && !comp_(*(boost::begin(str)+str_idx),*(boost::begin(substr)+0)))
++str_idx;
//Invariant: string[str_idx]==substr[substr_idx] or (str_idx=0 and str_idx >= str_size)
@@ -101,10 +126,11 @@
boost::end(str), boost::end(str));
}
- void on_substring_change(std::random_access_iterator_tag)
+ template <class RangeT>
+ void on_substring_change(RangeT const &substr, std::random_access_iterator_tag)
{
- substring_range_type const &substr = static_cast<Finder*>(this)->get_substring_range();
- comparator_type const &comp = static_cast<Finder*>(this)->get_comparator();
+ //substring_range_type const &substr = static_cast<Finder*>(this)->get_substring_range();
+ //comparator_type const &comp = static_cast<Finder*>(this)->get_comparator();
//failure_func[i] = the size of the largest border (prefix that's also a suffix)
// of P[0..i], that's different from itself.
@@ -120,10 +146,10 @@
//std::size_t capacity = failure_func.capacity();
while (j < substr_size)
{
- while (i > 0 && !comp(*(boost::begin(substr)+i), *(boost::begin(substr)+j)))
+ while (i > 0 && !comp_(*(boost::begin(substr)+i), *(boost::begin(substr)+j)))
i = failure_func[i-1];
while (i == 0 && j < substr_size &&
- !comp(*(boost::begin(substr)+0),*(boost::begin(substr)+j)))
+ !comp_(*(boost::begin(substr)+0),*(boost::begin(substr)+j)))
{
//Invariant: i == 0 and substr[0] != substr[j], which means failure_func[j]=0
failure_func.push_back(0);
@@ -150,4 +176,4 @@
}
-#endif
\ No newline at end of file
+#endif
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-14 20:20:26 EDT (Sat, 14 Aug 2010)
@@ -9,6 +9,7 @@
#include <string>
#include <boost/algorithm/string/finder/detail/finder_typedefs.hpp>
+#include <boost/algorithm/string/finder/detail/string_search_ranges.hpp>
/*!
\file
@@ -22,28 +23,30 @@
struct naive_search
{
- template <class Finder, class ForwardRange1T, class ForwardRange2T, class ComparatorT, class AllocatorT>
- struct algorithm
- : public boost::algorithm::detail::finder_typedefs<
- ForwardRange1T,ForwardRange2T,ComparatorT,AllocatorT>
+ 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;
+ typedef Range2CharT string_char_type;
+ typedef ComparatorT comparator_type;
+ typedef AllocatorT allocator_type;
public:
std::string get_algorithm_name () const { return "Naive search"; }
- protected:
- algorithm () { }
+ algorithm (comparator_type const &comp, allocator_type const &alloc)
+ : comp_(comp), alloc_(alloc) { }
-
- string_range_type find(string_iterator_type start)
+ 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)
{
- /*typedef typename Finder::string_iterator_type string_iterator_type;
- typedef typename Finder::substring_iterator_type substring_iterator_type;
- typedef typename Finder::substring_range_type substring_range_type;
- typedef typename Finder::string_range_type string_range_type;
- typedef typename Finder::comparator_type comparator_type;*/
- string_range_type const &str = static_cast<Finder*>(this)->get_string_range();
- substring_range_type const &substr = static_cast<Finder*>(this)->get_substring_range();
- comparator_type const &comparator = static_cast<Finder*>(this)->get_comparator();
+ BOOST_ALGORITHM_DETAIL_COMMON_FINDER_TYPEDEFS(Range1T, Range2T);
+ string_range_type const &str = ranges.str;
+ substring_range_type const &substr = ranges.substr;
+ string_iterator_type start = ranges.offset;
for (;
start != boost::end(str); ++start)
@@ -54,7 +57,7 @@
substr_iter != boost::end(substr) && str_iter != boost::end(str);
++substr_iter, ++str_iter)
{
- if (!comparator(*str_iter, *substr_iter)) break;
+ if (!comp_(*str_iter, *substr_iter)) break;
}
if (substr_iter == boost::end(substr))
return boost::iterator_range<string_iterator_type>(start, str_iter);
@@ -65,13 +68,16 @@
//! 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
- inline void on_substring_change()
+ template <class T> inline void on_substring_change(T const&)
{
}
//No precomputation to be done on the string
- inline void on_string_change()
+ template <class T> inline void on_string_change(T const&)
{
}
+ private:
+ comparator_type comp_;
+ allocator_type alloc_;
};
};
@@ -85,4 +91,4 @@
using boost::algorithm::naive_search;
}
-#endif
\ No newline at end of file
+#endif
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-14 20:20:26 EDT (Sat, 14 Aug 2010)
@@ -2,21 +2,31 @@
#define BOOST_ALGORITHM_RABIN_KARP_HPP
#include <boost/cstdint.hpp>
-#include <boost/range/iterator_range.hpp>
-#include <boost/algorithm/string/compare.hpp>
+
#include <boost/call_traits.hpp>
+
#include <boost/tuple/tuple.hpp>
+
#include <boost/mpl/void.hpp>
-#include <cstdlib>
+
#include <boost/static_assert.hpp>
+
#include <boost/range/begin.hpp>
#include <boost/range/end.hpp>
-#include <string>
+#include <boost/range/iterator_range.hpp>
+
#include <boost/lexical_cast.hpp>
+
+#include <boost/algorithm/string/compare.hpp>
#include <boost/algorithm/string/string_search/detail/rabin_karp.hpp>
#include <boost/algorithm/string/finder/detail/finder_typedefs.hpp>
+#include <boost/algorithm/string/finder/detail/string_search_ranges.hpp>
+
#include <cassert>
#include <limits>
+#include <string>
+#include <cstdlib>
+
#include <boost/type_traits/is_same.hpp>
/*!
@@ -40,27 +50,33 @@
template <
class HashType,
HashType FirstBase, HashType FirstModulo,
- HashType SecondBase, HashType SecondModulo>
+ HashType SecondBase, HashType SecondModulo,
+ class StringIteratorCategory = std::random_access_iterator_tag>
struct rabin_karp_algorithm
{
- template <class Finder, class Range1T, class Range2T, class ComparatorT, class AllocatorT>
+ template <class Range1CharT, class Range2CharT, class ComparatorT, class AllocatorT>
class algorithm;
- template <class Finder, class Range1T, class Range2T, class AllocatorT>
- class algorithm<Finder, Range1T, Range2T, boost::algorithm::is_equal, AllocatorT>
- : public ::boost::algorithm::detail::rabin_karp_algorithm<Finder,
- Range1T, Range2T, HashType, FirstBase, FirstModulo, SecondBase, SecondModulo>
+ template <class Range1CharT, class Range2CharT, class AllocatorT>
+ class algorithm<Range1CharT, Range2CharT, boost::algorithm::is_equal, AllocatorT>
+ : public ::boost::algorithm::detail::rabin_karp_algorithm<
+ Range1CharT, Range2CharT, HashType, FirstBase, FirstModulo, SecondBase, SecondModulo, StringIteratorCategory>
{
+ private:
+ typedef Range1CharT substring_char_type;
+ typedef Range2CharT string_char_type;
+ typedef boost::algorithm::is_equal comparator_type;
+ typedef AllocatorT allocator_type;
public:
std::string get_algorithm_name () const
{ return "Rabin-Karp (" + boost::lexical_cast<std::string>(sizeof(HashType)) + ")"; }
- protected:
- //construct the algorithm given iterator ranges for the substring and the string
- algorithm () {
+ algorithm (comparator_type const &comp, allocator_type const &alloc)
+ : comp_(comp), alloc_(alloc)
+ {
//todo add more assertions here
BOOST_STATIC_ASSERT((
- sizeof(boost::range_value<Range1T>::type)*2 <= sizeof(HashType)
+ sizeof(substring_char_type)*2 <= sizeof(HashType)
));
BOOST_STATIC_ASSERT(( boost::is_same<substring_char_type,string_char_type>::value ));
assert_overflow(FirstBase, FirstModulo);
@@ -82,6 +98,7 @@
BOOST_ALGORITHM_DETAIL_ASSERTED_MULTIPLY(M-1, B, HashType), char_range_size, HashType),
BOOST_ALGORITHM_DETAIL_ASSERTED_MULTIPLY(M-1,char_range_size, HashType), HashType );*/
}
+ comparator_type comp_; allocator_type alloc_;
};
};
@@ -108,4 +125,4 @@
using boost::algorithm::rabin_karp64_tag;
}
-#endif
\ No newline at end of file
+#endif
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-14 20:20:26 EDT (Sat, 14 Aug 2010)
@@ -10,8 +10,11 @@
#include <boost/range/end.hpp>
#include <boost/range/iterator_range.hpp>
#include <boost/range/algorithm/sort.hpp>
+#include <boost/range/category.hpp>
+#include <boost/algorithm/string/compare.hpp>
#include <boost/algorithm/string/finder/detail/finder_typedefs.hpp>
+#include <boost/algorithm/string/finder/detail/string_search_ranges.hpp>
/*!
\file
@@ -27,44 +30,55 @@
//! \TODO this currently only works for boost::algorithm::is_equal as comparator because we don't yet have a template
//! parameter for LessThanComparator. Maybe we should pass two comparators, give it some thought.
- template <class Finder,class RandomAccessRange1T,
- class RandomAccessRange2T,class ComparatorT,class AllocatorT>
+ template <class Range1CharT, class Range2CharT, class ComparatorT, class AllocatorT>
class algorithm;
- template <class Finder, class RandomAccessRange1T,
- class RandomAccessRange2T, class AllocatorT>
- class algorithm<Finder,RandomAccessRange1T,RandomAccessRange2T,
- boost::algorithm::is_equal,AllocatorT>
- : public boost::algorithm::detail::finder_typedefs<
- RandomAccessRange1T,RandomAccessRange2T,boost::algorithm::is_equal,AllocatorT>
+ 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;
+ typedef Range2CharT string_char_type;
+ typedef boost::algorithm::is_equal comparator_type;
+ typedef AllocatorT allocator_type;
public:
std::string get_algorithm_name () const { return "Suffix array"; }
- protected:
- algorithm () : found_matches_(false), pos_(), matches_() { }
-
- void on_substring_change()
- { on_substring_change(substring_iterator_category()); }
+
+ algorithm (comparator_type const &comp, allocator_type const &alloc)
+ : comp_(comp), alloc_(alloc), found_matches_(false), pos_(alloc_), matches_(alloc_) { }
- void on_string_change()
- { on_string_change(string_iterator_category()); }
- string_range_type find (string_iterator_type start)
- {
- substring_range_type const &substr = static_cast<Finder*>(this)->get_substring_range();
- string_range_type const &str = static_cast<Finder*>(this)->get_string_range();
- comparator_type const &comp = static_cast<Finder*>(this)->get_comparator();
+ // 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()); }
+
+ 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()); }
+
+ 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)
+ {
+ BOOST_ALGORITHM_DETAIL_COMMON_FINDER_TYPEDEFS(Range1T, Range2T);
+
+ string_range_type const &str = ranges.str;
+ substring_range_type const &substr = ranges.substr;
+ string_iterator_type start = ranges.offset;
std::size_t start_offset = start - boost::begin(str),
substr_size = boost::end(substr) - boost::begin(substr),
str_size = boost::end(str) - boost::begin(str);
if (found_matches_)
- return find_first_match(start_offset);
+ return find_first_match(str, substr, start_offset);
if (boost::begin(str) == boost::end(str)) return string_range_type(boost::end(str), boost::end(str));
std::size_t suffix_left, suffix_right;
- std::size_t firstsuffix_end = pos_[0] + substr_size, lastsuffix_end = pos_.back()+substr_size;
+ std::size_t /*firstsuffix_end = pos_[0] + substr_size, */lastsuffix_end = pos_.back()+substr_size;
//the end position of the smallest lexicographic suffix
//if (firstsuffix_end > str.size()) firstsuffix_end = str.size();
//the end position of the biggest lexicographic suffix
@@ -131,23 +145,24 @@
for (std::size_t k = suffix_left; k < suffix_right; ++k)
matches_.push_back(pos_[k]);
boost::sort(matches_);
- return find_first_match(start_offset);
+ return find_first_match(str, substr, start_offset);
}
}
private:
- inline string_range_type find_first_match (std::size_t start_offset)
+ template <class StrT, class SubstrT>
+ inline StrT find_first_match (StrT const &str, SubstrT const &substr, std::size_t start_offset)
{
- string_range_type const &str = static_cast<Finder*>(this)->get_string_range();
- substring_range_type const &substr = static_cast<Finder*>(this)->get_substring_range();
+ //string_range_type const &str = static_cast<Finder*>(this)->get_string_range();
+ //substring_range_type const &substr = static_cast<Finder*>(this)->get_substring_range();
- std::vector<std::size_t, AllocatorT>::const_iterator first_match =
+ 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 string_range_type(
+ return StrT(
boost::end(str), boost::end(str));
std::size_t substr_size = boost::end(substr) - boost::begin(substr);
assert(*first_match + substr_size <= static_cast<std::size_t>(str.size()) );
- return string_range_type(
+ return StrT(
boost::begin(str) + (*first_match),
boost::begin(str) + (*first_match) + substr_size
);
@@ -157,22 +172,27 @@
found_matches_ = false;
}
- void on_string_change(std::random_access_iterator_tag)
+ template <class Range1T, class Range2T>
+ void on_string_change(typename boost::algorithm::detail::string_search_ranges<Range1T, Range2T> const &ranges,
+ std::random_access_iterator_tag)
{
- string_range_type const &str = static_cast<Finder*>(this)->get_string_range();
+ BOOST_ALGORITHM_DETAIL_COMMON_FINDER_TYPEDEFS(Range1T, Range2T);
+
+ string_range_type const &str = ranges.str;
// compute the suffix array
std::size_t str_size = boost::end(str) - boost::begin(str);
pos_.clear();
pos_.reserve(str_size);
std::generate_n(std::back_inserter(pos_), str_size, increasing_generator());
- std::sort(pos_.begin(), pos_.end(), suffix_array_sort_comparator(str));
+ std::sort(pos_.begin(), pos_.end(), suffix_array_sort_comparator<string_range_type>(str));
found_matches_ = false;
}
- inline bool suffix_less(substring_range_type const &substr,
- string_range_type const &str, std::size_t suffix)
+ template <class SubstrT, class StrT>
+ inline bool suffix_less(SubstrT const &substr,
+ StrT const &str, std::size_t suffix)
{
std::size_t start_offset = pos_[suffix],
end_offset = start_offset + (boost::end(substr) - boost::begin(substr)),
@@ -183,8 +203,9 @@
boost::begin(str) + start_offset, boost::begin(str) + end_offset);
}
- inline bool suffix_equal(substring_range_type const &substr,
- string_range_type const &str, std::size_t suffix)
+ template <class SubstrT, class StrT>
+ inline bool suffix_equal(SubstrT const &substr,
+ StrT const &str, std::size_t suffix)
{
std::size_t start_offset = pos_[suffix],
end_offset = start_offset + (boost::end(substr) - boost::begin(substr)),
@@ -194,11 +215,6 @@
return std::equal(substr.begin(), substr.end(), boost::begin(str)+start_offset);
}
- std::vector<std::size_t, typename AllocatorT::template rebind<std::size_t>::other> pos_;
- bool found_matches_;
- std::vector<std::size_t, typename AllocatorT::template rebind<std::size_t>::other> matches_;
-
-
struct increasing_generator
{
increasing_generator () : idx_(0) { }
@@ -206,16 +222,24 @@
std::size_t idx_;
};
+ template <class Range2T>
struct suffix_array_sort_comparator
{
- suffix_array_sort_comparator (string_range_type const &str) : str_(str) { }
+ suffix_array_sort_comparator (Range2T const &str) : str_(str) { }
bool operator()(std::size_t lhs, std::size_t rhs)
{
return std::lexicographical_compare(str_.begin()+lhs, str_.end(), str_.begin()+rhs, str_.end());
}
- string_range_type const &str_;
+ Range2T const &str_;
};
+ 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_;
+
+
};
};
//! Instances of this type can be passed to find functions to require them to
@@ -229,4 +253,4 @@
using boost::algorithm::suffix_array_search_tag;
}
-#endif
\ No newline at end of file
+#endif
Modified: sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/suffix_array2.hpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/suffix_array2.hpp (original)
+++ sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/suffix_array2.hpp 2010-08-14 20:20:26 EDT (Sat, 14 Aug 2010)
@@ -216,4 +216,4 @@
boost::algorithm::suffix_array_search> wsuffix_array_finder;
}
-#endif
\ No newline at end of file
+#endif
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-14 20:20:26 EDT (Sat, 14 Aug 2010)
@@ -350,7 +350,7 @@
std::cout << "Test " << test << " (" << fn << "):" << std::endl;
- std::ifstream bf(fn, std::ios::binary);
+ std::ifstream bf(fn.c_str(), std::ios::binary);
if (!bf) { std::cerr << "Error opening " << fn << std::endl; return -1; }
const unsigned int MAX_STR_SIZE = 10*1024*1024;//10;//1000000;
Modified: sandbox/SOC/2010/stringalgos/libs/algorithm/string/example/Jamfile
==============================================================================
--- sandbox/SOC/2010/stringalgos/libs/algorithm/string/example/Jamfile (original)
+++ sandbox/SOC/2010/stringalgos/libs/algorithm/string/example/Jamfile 2010-08-14 20:20:26 EDT (Sat, 14 Aug 2010)
@@ -11,6 +11,7 @@
exe conv_example : conv_example.cpp ;
exe predicate_example : predicate_example.cpp ;
exe find_example : find_example.cpp ;
+exe finder_example : finder_example.cpp ;
exe replace_example : replace_example.cpp ;
exe rle_example : rle_example.cpp ;
exe trim_example : trim_example.cpp ;
Modified: sandbox/SOC/2010/stringalgos/libs/algorithm/string/example/finder_example.cpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/libs/algorithm/string/example/finder_example.cpp (original)
+++ sandbox/SOC/2010/stringalgos/libs/algorithm/string/example/finder_example.cpp 2010-08-14 20:20:26 EDT (Sat, 14 Aug 2010)
@@ -14,66 +14,68 @@
//Example 1: KMP
- //typedef boost::finder_t<std::wstring, std::wstring, boost::knuth_morris_pratt> finder;
+ //typedef boost::finder_t<std::string, std::string, boost::knuth_morris_pratt> finder;
//OR
- typedef boost::wknuth_morris_pratt_finder finder;
+ typedef boost::knuth_morris_pratt_finder finder;
finder f;
- f.set_string(L"The world is mine"); // set the string to search for: "The world is mine"
- f.set_substring(L"mine"); // set the pattern to search for: "mine"
- std::wstring::difference_type match = f.find_first_index(); // searches pattern "mine" in text
+ f.set_string("The world is mine"); // set the string to search for: "The world is mine"
+ f.set_substring("mine"); // set the pattern to search for: "mine"
+ std::string::difference_type match = f.find_first_index(); // searches pattern "mine" in text
// "The world is mine"
// returns an index
if (match != static_cast<std::string::difference_type>(-1))
- std::wcout << L"Found a match at position " << match << std::endl;
+ std::cout << "Found a match at position " << match << std::endl;
- f.set_substring(L"world"); // Note: the string stays the same, only the substring was changed
+ f.set_substring("world"); // Note: the string stays the same, only the substring was changed
match = f.find_first_index(); // searches pattern "world" in text "The world is mine"
if (match != static_cast<std::string::difference_type>(-1))
- std::wcout << L"Found a match at position " << match << std::endl;
+ std::cout << "Found a match at position " << match << std::endl;
// Turn "Hello world" into "Hello WORLD"
- std::wstring mystr(L"Hello world");
+ std::string mystr("Hello world");
f.set_string(mystr);
match = f.find_first_index(); // searches pattern "world" in text "Hello world"
- boost::to_upper( boost::make_iterator_range(mystr.begin()+match,mystr.begin()+match+5) );
- std::wcout << mystr << std::endl;
+ finder::string_range_type match2(mystr.begin()+match, mystr.begin()+match+5);
+ boost::to_upper(match2);
+ std::cout << mystr << std::endl;
// Turn "Hello WORLD" into "HELLO WORLD"
f.set_string(&mystr);
- f.set_substring(L"Hello");
- finder::string_range_type match2 = f.find_first(); // because we've passed the string as a
- // pointer, no internal copy of the text
- // was made, and we can use find_first()
- // to get a range of the match
+ f.set_substring("Hello");
+ match2 = f.find_first(); // because we've passed the string as a
+ // pointer, no internal copy of the text
+ // was made, and we can use find_first()
+ // to get a range of the match
boost::to_upper(match2);
- std::wcout << mystr << std::endl;
+ std::cout << mystr << std::endl;
// Example 2: Searching with suffix arrays
- typedef boost::finder_t<std::vector<wchar_t>, std::wstring, boost::suffix_array_search,
+ typedef boost::finder_t<std::vector<char>, std::string, boost::suffix_array_search,
boost::is_equal> finder2;
- //the pattern's type is a vector of wchar_t-s, whereas the text's type is a wstring
+ //the pattern's type is a vector of char-s, whereas the text's type is a string
finder2 f2;
f2.set_string(
- L"Lorem ipsum dolor sit amet, consectetur adipiscing elit. Integer interdum elit ac orci "
- L"fermentum in pretium lectus facilisis. Vestibulum rutrum convallis justo nec fringilla. "
- L"Sed magna justo, sollicitudin sed viverra in, lacinia quis metus. Integer volutpat, nisl "
- L"rhoncus condimentum accumsan, est mi fermentum lacus, sed imperdiet sem erat a risus. "
+ "Lorem ipsum dolor sit amet, consectetur adipiscing elit. Integer interdum elit ac orci "
+ "fermentum in pretium lectus facilisis. Vestibulum rutrum convallis justo nec fringilla. "
+ "Sed magna justo, sollicitudin sed viverra in, lacinia quis metus. Integer volutpat, nisl "
+ "rhoncus condimentum accumsan, est mi fermentum lacus, sed imperdiet sem erat a risus. "
); // Note: this works by making an internal copy (or move if the compiler supports it) of
// the given text
- f2.set_substring(L"consectetur");
+ f2.set_substring("consectetur");
- boost::to_upper(f2.find_first()); // finds consectetur in the internal copy
- // then makes it uppercase
+ match2 = f2.find_first();
+ boost::to_upper(match2); // finds consectetur in the internal copy
+ // then makes it uppercase
- // Changes have occured in the internal copy of the string from the outside, the finder
+ // Changes have occurred in the internal copy of the string from the outside, the finder
// has no way of knowing. Call use_internal_string() in order for the finder to
// obtain a new range from its internal string
f2.use_internal_string();
- //turns all occurences of letter e into uppercase
- f2.set_substring(L"e");
+ //turns all occurrences of letter e into uppercase
+ f2.set_substring("e");
for (finder2::string_range_type range = f2.find_first();
boost::begin(range) != boost::end(range); range = f2.find_next())
{
@@ -82,26 +84,27 @@
//display the internal copy of the text, after updating the internal range
f2.use_internal_string();
- boost::copy(f2.get_string_range(), std::ostream_iterator<wchar_t,wchar_t>(std::wcout));
- std::wcout << std::endl;
+ boost::copy(f2.get_string_range(), std::ostream_iterator<char,char>(std::cout));
+ std::cout << std::endl;
// Example 3: Using finder_t with boyer_moore
- boost::wboyer_moore_finder f3;
+ boost::boyer_moore_finder f3;
- std::wstring apple(L"apple");
+ std::string apple("apple");
f3.set_substring(&apple); // you need to guarantee on the lifetime of apple to do this
- std::wstring coolsaying(
- L"If you have an apple and I have an apple and we exchange these apples then you "
- L"and I will still each have one apple. But if you have an idea and I have an "
- L"idea and we exchange these ideas, then each of us will have two ideas."
+ std::string coolsaying(
+ "If you have an apple and I have an apple and we exchange these apples then you "
+ "and I will still each have one apple. But if you have an idea and I have an "
+ "idea and we exchange these ideas, then each of us will have two ideas."
);
f3.set_string(&coolsaying); // you need to guarantee on the lifetime of coolsaying to do this
- boost::to_upper(f3.find_first()); // turn the first occurence of apple uppercase
- // modifications occur directly in coolsaying, since no copy
- // was made
- std::wcout << coolsaying << std::endl;
+ match2 = f3.find_first();
+ boost::to_upper(match2); // turn the first occurence of apple uppercase
+ // modifications occur directly in coolsaying, since no copy
+ // was made
+ std::cout << coolsaying << std::endl;
std::cin.get();
Modified: sandbox/SOC/2010/stringalgos/libs/algorithm/string/test/find_test.cpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/libs/algorithm/string/test/find_test.cpp (original)
+++ sandbox/SOC/2010/stringalgos/libs/algorithm/string/test/find_test.cpp 2010-08-14 20:20:26 EDT (Sat, 14 Aug 2010)
@@ -210,13 +210,13 @@
nc_vresult=find_first( vec1, string("abc") );
BOOST_CHECK(
- ( (nc_result.begin()-str1.begin()) == 3) &&
- ( (nc_result.end()-str1.begin()) == 6) );
+ ( (nc_vresult.begin()-vec1.begin()) == 3) &&
+ ( (nc_vresult.end()-vec1.begin()) == 6) );
cv_vresult=find_first( const_cast<const vector<int>&>(vec1), str2 );
BOOST_CHECK(
- ( (cv_result.begin()-str1.begin()) == 3) &&
- ( (cv_result.end()-str1.begin()) == 6) );
+ ( (cv_vresult.begin()-vec1.begin()) == 3) &&
+ ( (cv_vresult.end()-vec1.begin()) == 6) );
// overflow test
BOOST_CHECKPOINT( "overflow" );
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-14 20:20:26 EDT (Sat, 14 Aug 2010)
@@ -595,6 +595,7 @@
string str1("123abcxXxabcXxXabc321");
string str2("abc");
string str3("");
+ std::string str4("abc-AbC-bAc-ABC-abC-ACC-ACB-AbC-XYZ"); //[0,3) [4,7) [12,15) [16,19) [28,31)
const char* pch1="123abcxxxabcXXXabc321";
vector<int> vec1( str1.begin(), str1.end() );
@@ -687,6 +688,50 @@
( (cv_result.begin()-str1.begin()) == 12) &&
( (cv_result.end()-str1.begin()) == 15) );
+
+ nc_result = ifind_nth(str4, "abc", -1);
+ BOOST_CHECK_EQUAL(nc_result.begin() - str4.begin(), 28);
+ BOOST_CHECK_EQUAL(nc_result.end() - str4.begin(), 31);
+
+ nc_result = ifind_nth(str4, "abc", -2);
+ BOOST_CHECK_EQUAL(nc_result.begin() - str4.begin(), 16);
+ BOOST_CHECK_EQUAL(nc_result.end() - str4.begin(), 19);
+
+ nc_result = ifind_nth(str4, "abc", -3);
+ BOOST_CHECK_EQUAL(nc_result.begin() - str4.begin(), 12);
+ BOOST_CHECK_EQUAL(nc_result.end() - str4.begin(), 15);
+
+ nc_result = ifind_nth(str4, "abc", -4);
+ BOOST_CHECK_EQUAL(nc_result.begin() - str4.begin(), 4);
+ BOOST_CHECK_EQUAL(nc_result.end() - str4.begin(), 7);
+
+ nc_result = ifind_nth(str4, "abc", -5);
+ BOOST_CHECK_EQUAL(nc_result.begin() - str4.begin(), 0);
+ BOOST_CHECK_EQUAL(nc_result.end() - str4.begin(), 3);
+
+ nc_result = ifind_nth(str4, "abc", -6);
+ BOOST_CHECK(nc_result.begin() == nc_result.end());
+ BOOST_CHECK(nc_result.end() == str4.end());
+
+ nc_result = ifind_nth(str4, "abc", -12345);
+ BOOST_CHECK(nc_result.begin() == nc_result.end());
+ BOOST_CHECK(nc_result.end() == str4.end());
+
+ nc_result = ifind_last(str4, "abc");
+ BOOST_CHECK_EQUAL(nc_result.begin() - str4.begin(), 28);
+ BOOST_CHECK_EQUAL(nc_result.end() - str4.begin(), 31);
+
+ std::list<char> l4(str4.begin(), str4.end());
+ using std::distance;
+ boost::iterator_range<std::list<char>::iterator> nc_lresult = ifind_last(l4, "abc", boost::algorithm::naive_search_tag());
+ BOOST_CHECK_EQUAL(distance(l4.begin(),nc_lresult.begin()), 28);
+ BOOST_CHECK_EQUAL(distance(l4.begin(),nc_lresult.end()), 31);
+
+ nc_result = ifind_last(str4, "abo");
+ BOOST_CHECK(nc_result.begin() == nc_result.end());
+ BOOST_CHECK(nc_result.end() == str4.end());
+
+
ch_result=find_nth( pch1, "abc", 1 );
BOOST_CHECK(( (ch_result.begin() - pch1 ) == 9) && ( (ch_result.end() - pch1 ) == 12 ) );
@@ -767,18 +812,14 @@
( (nc_result.begin()-str1.begin()) == 3) &&
( (nc_result.end()-str1.begin()) == 6) );
- //TODO: this one cannot work, what should we do about it?
- /*
cv_result=find(const_cast<const string&>(str1), first_finder(str2) );
BOOST_CHECK(
( (cv_result.begin()-str1.begin()) == 3) &&
( (cv_result.end()-str1.begin()) == 6) );
- */
// multi-type comparison test
BOOST_CHECKPOINT( "multi-type" );
- //!\todo fix this in find_test.cpp. find why teh fuck did these tests use to pass.
nc_vresult=find_first( vec1, string("abc") );
BOOST_CHECK(nc_vresult.begin()-vec1.begin() == 3);
BOOST_CHECK(nc_vresult.end()-vec1.begin() == 6);