Subject: [Boost-commit] svn:boost r64056 - in sandbox/SOC/2010/stringalgos: boost/algorithm/string boost/algorithm/string/string_search libs/algorithm/string/example
From: mstefanro_at_[hidden]
Date: 2010-07-15 14:13:01
Author: mstefanro
Date: 2010-07-15 14:13:00 EDT (Thu, 15 Jul 2010)
New Revision: 64056
URL: http://svn.boost.org/trac/boost/changeset/64056
Log:
[GSoC2010][StringAlgo] Fixed the example, added some typedefs.
Text files modified:
sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder.hpp | 31 +++++++++++++++++++++----------
sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/boyer_moore.hpp | 11 ++++++++++-
sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/knuth_morris_pratt.hpp | 11 ++++++++++-
sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/naive_search.hpp | 11 ++++++++++-
sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/rabin_karp.hpp | 23 ++++++++++++++++++++---
sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/suffix_array.hpp | 9 ++++++++-
sandbox/SOC/2010/stringalgos/libs/algorithm/string/example/finder_example.cpp | 36 ++++++++++++++++++++++++++++++++----
7 files changed, 111 insertions(+), 21 deletions(-)
Modified: sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder.hpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder.hpp (original)
+++ sandbox/SOC/2010/stringalgos/boost/algorithm/string/finder.hpp 2010-07-15 14:13:00 EDT (Thu, 15 Jul 2010)
@@ -68,25 +68,26 @@
private AlgorithmT::algorithm<
simplified_finder_t<Range1T, Range2T, AlgorithmT, ComparatorT, AllocatorT, AdditionalBehaviorT>,
typename boost::range_const_iterator<Range1T>::type,
- typename boost::range_const_iterator<Range2T>::type,
+ typename boost::range_iterator<Range2T>::type,
ComparatorT,AllocatorT>
{
//! \todo Add concept assertions here.
public:
- simplified_finder_t(Range1T const &substr, Range2T const &str,
+ simplified_finder_t(Range1T const *const substr, Range2T *str,
ComparatorT comparator = ComparatorT(), AllocatorT allocator = AllocatorT())
- : substring_range_(substr), string_range_(str),
+ : 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()
{ }
- void set_substring (Range1T const &substr)
- { substring_range_ = substr; substring_has_changed_ = true; }
+ void set_substring (Range1T const *substr)
+ { substring_range_ = boost::as_literal(*substr); substring_has_changed_ = true; }
- void set_string (Range2T const &str)
- { string_range_ = str; string_has_changed_ = true; }
+ void set_string (Range2T *str)
+ { string_range_ = boost::as_literal(*str); string_has_changed_ = true; }
void find_reset ()
{ start_offset_ = boost::begin(string_range_); }
@@ -97,6 +98,12 @@
return find_next();
}
+ void refresh()
+ {
+ string_has_changed_ = true;
+ find_reset();
+ }
+
string_range_type find_next()
{
apply_changes();
@@ -169,9 +176,8 @@
template <class,class,class,class,class,class> class AdditionalBehavior =
boost::algorithm::finder_no_additional_behavior
>
- class finder_t : private Algorithm::algorithm</*typename boost::range_const_iterator<Sequence1T>::type,
- typename boost::range_const_iterator<Sequence2T>::type,
- Comparator,Allocator*/
+ class finder_t :
+ private Algorithm::algorithm<
typename finder_t<Sequence1T, Sequence2T, Algorithm, Comparator, Allocator, AdditionalBehavior>,
typename boost::range_const_iterator<Sequence1T>::type,
typename boost::range_iterator<Sequence2T>::type,
@@ -500,6 +506,11 @@
\note This is semantically equivalent to \c find_reset(); match=find_next();
*/
+ void refresh()
+ {
+ string_has_changed_ = true;
+ find_reset();
+ }
//!\todo Must return a range of const iterators, otherwise one could modify
//! the range's contents, range which may actually
Modified: sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/boyer_moore.hpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/boyer_moore.hpp (original)
+++ sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/boyer_moore.hpp 2010-07-15 14:13:00 EDT (Thu, 15 Jul 2010)
@@ -14,6 +14,8 @@
#include <boost/type_traits/is_same.hpp>
#include <boost/static_assert.hpp>
#include <map>
+#include <string>
+#include <boost/algorithm/string/finder.hpp>
namespace boost { namespace algorithm {
struct boyer_moore
@@ -165,6 +167,13 @@
};
} }
-namespace boost { using boost::algorithm::boyer_moore; }
+namespace boost
+{
+ using boost::algorithm::boyer_moore;
+ typedef boost::algorithm::finder_t<std::string, std::string,
+ boost::algorithm::boyer_moore> boyer_moore_finder;
+ typedef boost::algorithm::finder_t<std::wstring, std::wstring,
+ boost::algorithm::boyer_moore> wboyer_moore_finder;
+}
#endif
\ No newline at end of file
Modified: sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/knuth_morris_pratt.hpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/knuth_morris_pratt.hpp (original)
+++ sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/knuth_morris_pratt.hpp 2010-07-15 14:13:00 EDT (Thu, 15 Jul 2010)
@@ -5,6 +5,8 @@
#include <boost/range/iterator_range.hpp>
#include <boost/range/begin.hpp>
#include <boost/range/end.hpp>
+#include <boost/algorithm/string/finder.hpp>
+#include <string>
#include <vector>
#include <allocators>
@@ -111,6 +113,13 @@
};
} }
-namespace boost { using boost::algorithm::knuth_morris_pratt; }
+namespace boost
+{
+ using boost::algorithm::knuth_morris_pratt;
+ typedef boost::algorithm::finder_t<std::string, std::string,
+ boost::algorithm::knuth_morris_pratt> knuth_morris_pratt_finder;
+ typedef boost::algorithm::finder_t<std::wstring, std::wstring,
+ boost::algorithm::knuth_morris_pratt> wknuth_morris_pratt_finder;
+}
#endif
\ No newline at end of file
Modified: sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/naive_search.hpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/naive_search.hpp (original)
+++ sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/naive_search.hpp 2010-07-15 14:13:00 EDT (Thu, 15 Jul 2010)
@@ -6,6 +6,8 @@
#include <boost/mpl/void.hpp>
#include <boost/range/begin.hpp>
#include <boost/range/end.hpp>
+#include <string>
+#include <boost/algorithm/string/finder.hpp>
namespace boost { namespace algorithm {
//! \todo Copyable
@@ -64,6 +66,13 @@
} }
-namespace boost { using boost::algorithm::naive_search; }
+namespace boost
+{
+ using boost::algorithm::naive_search;
+ typedef boost::algorithm::finder_t<std::string, std::string,
+ boost::algorithm::naive_search> naive_search_finder;
+ typedef boost::algorithm::finder_t<std::wstring, std::wstring,
+ boost::algorithm::naive_search> wnaive_search_finder;
+}
#endif
\ No newline at end of file
Modified: sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/rabin_karp.hpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/rabin_karp.hpp (original)
+++ sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/rabin_karp.hpp 2010-07-15 14:13:00 EDT (Thu, 15 Jul 2010)
@@ -11,14 +11,17 @@
#include <boost/static_assert.hpp>
#include <boost/range/begin.hpp>
#include <boost/range/end.hpp>
+#include <string>
+#include <boost/algorithm/string/finder.hpp>
#include <boost/algorithm/string/string_search/detail/rabin_karp.hpp>
namespace boost { namespace algorithm {
- //! \todo Find this in boost?
- //struct void_type {};
+ //!\todo document the fact that it's approximate, how to make it deterministic
+ // the limited comparators
+ //!\todo Make it work with case insensitive. Find a way to allow providing locales.
//Note: this only works with comparator ==
//! \todo Implement a version that works with Input iterators?
@@ -60,6 +63,20 @@
} } // namespace algorithm, namespace boost
-namespace boost { using boost::algorithm::rabin_karp32; using boost::algorithm::rabin_karp64; }
+namespace boost
+{
+ using boost::algorithm::rabin_karp32;
+ using boost::algorithm::rabin_karp64;
+
+ typedef boost::algorithm::finder_t<std::string, std::string,
+ boost::algorithm::rabin_karp32> rabin_karp32_finder;
+ typedef boost::algorithm::finder_t<std::wstring, std::wstring,
+ boost::algorithm::rabin_karp32> wrabin_karp32_finder;
+
+ typedef boost::algorithm::finder_t<std::string, std::string,
+ boost::algorithm::rabin_karp64> rabin_karp64_finder;
+ typedef boost::algorithm::finder_t<std::wstring, std::wstring,
+ boost::algorithm::rabin_karp64> wrabin_karp64_finder;
+}
#endif
\ No newline at end of file
Modified: sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/suffix_array.hpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/suffix_array.hpp (original)
+++ sandbox/SOC/2010/stringalgos/boost/algorithm/string/string_search/suffix_array.hpp 2010-07-15 14:13:00 EDT (Thu, 15 Jul 2010)
@@ -211,6 +211,13 @@
};
} }
-namespace boost { using boost::algorithm::suffix_array_search; }
+namespace boost
+{
+ using boost::algorithm::suffix_array_search;
+ typedef boost::algorithm::finder_t<std::string, std::string,
+ boost::algorithm::suffix_array_search> suffix_array_finder;
+ typedef boost::algorithm::finder_t<std::wstring, std::wstring,
+ boost::algorithm::suffix_array_search> wsuffix_array_finder;
+}
#endif
\ No newline at end of file
Modified: sandbox/SOC/2010/stringalgos/libs/algorithm/string/example/finder_example.cpp
==============================================================================
--- sandbox/SOC/2010/stringalgos/libs/algorithm/string/example/finder_example.cpp (original)
+++ sandbox/SOC/2010/stringalgos/libs/algorithm/string/example/finder_example.cpp 2010-07-15 14:13:00 EDT (Thu, 15 Jul 2010)
@@ -13,13 +13,16 @@
//Example 1: KMP
- typedef boost::finder_t<std::wstring, std::wstring, boost::knuth_morris_pratt> finder;
+ //typedef boost::finder_t<std::wstring, std::wstring, boost::knuth_morris_pratt> finder;
+ //OR
+ typedef boost::wknuth_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
- // "The world is mine"
+ // "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;
@@ -62,6 +65,12 @@
boost::to_upper(f2.find_first()); // 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
+ // has no way of knowing. Call refresh() in order for the finder to perform any computation
+ // required on the modified string
+ f2.refresh();
+
//turns all occurences of letter e into uppercase
f2.set_substring(L"e");
for (finder2::string_range_type range = f2.find_first();
@@ -73,7 +82,26 @@
//display the internal copy of the text
boost::copy(f2.get_string_range(), std::ostream_iterator<wchar_t,wchar_t>(std::wcout));
std::wcout << std::endl;
-
+
+// Example 3: Using finder_t with boyer_moore
+ boost::wboyer_moore_finder f3;
+
+ std::wstring apple(L"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."
+ );
+ 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;
+
+
std::cin.get();
- return 0;
+ return 0;
}