1 ///////////////////////////////////////////////////////////////////////////////
2 /// \file boyer_moore.hpp
3 /// Contains the boyer-moore implementation. Note: this is *not* a general-
4 /// purpose boyer-moore implementation. It truncates the search string at
5 /// 256 characters, but it is sufficient for the needs of xpressive.
7 // Copyright 2008 Eric Niebler. Distributed under the Boost
8 // Software License, Version 1.0. (See accompanying file
9 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
11 #ifndef BOOST_XPRESSIVE_DETAIL_BOYER_MOORE_HPP_EAN_10_04_2005
12 #define BOOST_XPRESSIVE_DETAIL_BOYER_MOORE_HPP_EAN_10_04_2005
14 // MS compatible compilers support #pragma once
17 # pragma warning(push)
18 # pragma warning(disable : 4100) // unreferenced formal parameter
21 #include <climits> // for UCHAR_MAX
22 #include <cstddef> // for std::ptrdiff_t
23 #include <utility> // for std::max
25 #include <boost/mpl/bool.hpp>
26 #include <boost/noncopyable.hpp>
27 #include <boost/iterator/iterator_traits.hpp>
28 #include <boost/type_traits/is_convertible.hpp>
29 #include <boost/xpressive/detail/detail_fwd.hpp>
31 namespace boost { namespace xpressive { namespace detail
34 ///////////////////////////////////////////////////////////////////////////////
37 template<typename BidiIter, typename Traits>
41 typedef typename iterator_value<BidiIter>::type char_type;
42 typedef Traits traits_type;
43 typedef has_fold_case<Traits> case_fold;
44 typedef typename Traits::string_type string_type;
46 // initialize the Boyer-Moore search data structure, using the
47 // search sub-sequence to prime the pump.
48 boyer_moore(char_type const *begin, char_type const *end, Traits const &tr, bool icase)
54 ? (case_fold() ? &boyer_moore::find_nocase_fold_ : &boyer_moore::find_nocase_)
58 std::ptrdiff_t const uchar_max = UCHAR_MAX;
59 std::ptrdiff_t diff = std::distance(begin, end);
60 this->length_ = static_cast<unsigned char>((std::min)(diff, uchar_max));
61 std::fill_n(static_cast<unsigned char *>(this->offsets_), uchar_max + 1, this->length_);
64 icase ? this->init_(tr, case_fold()) : this->init_(tr, mpl::false_());
67 BidiIter find(BidiIter begin, BidiIter end, Traits const &tr) const
69 return (this->*this->find_fun_)(begin, end, tr);
74 void init_(Traits const &tr, mpl::false_)
76 for(unsigned char offset = this->length_; offset; --offset, ++this->last_)
78 this->offsets_[tr.hash(*this->last_)] = offset;
82 void init_(Traits const &tr, mpl::true_)
84 this->fold_.reserve(this->length_ + 1);
85 for(unsigned char offset = this->length_; offset; --offset, ++this->last_)
87 this->fold_.push_back(tr.fold_case(*this->last_));
88 for(typename string_type::const_iterator beg = this->fold_.back().begin(), end = this->fold_.back().end();
91 this->offsets_[tr.hash(*beg)] = offset;
94 this->fold_.push_back(tr.fold_case(*this->last_));
97 // case-sensitive Boyer-Moore search
98 BidiIter find_(BidiIter begin, BidiIter end, Traits const &tr) const
100 typedef typename boost::iterator_difference<BidiIter>::type diff_type;
101 diff_type const endpos = std::distance(begin, end);
102 diff_type offset = static_cast<diff_type>(this->length_);
104 for(diff_type curpos = offset; curpos < endpos; curpos += offset)
106 std::advance(begin, offset);
108 char_type const *pat_tmp = this->last_;
109 BidiIter str_tmp = begin;
111 for(; tr.translate(*str_tmp) == *pat_tmp; --pat_tmp, --str_tmp)
113 if(pat_tmp == this->begin_)
119 offset = this->offsets_[tr.hash(tr.translate(*begin))];
125 // case-insensitive Boyer-Moore search
126 BidiIter find_nocase_(BidiIter begin, BidiIter end, Traits const &tr) const
128 typedef typename boost::iterator_difference<BidiIter>::type diff_type;
129 diff_type const endpos = std::distance(begin, end);
130 diff_type offset = static_cast<diff_type>(this->length_);
132 for(diff_type curpos = offset; curpos < endpos; curpos += offset)
134 std::advance(begin, offset);
136 char_type const *pat_tmp = this->last_;
137 BidiIter str_tmp = begin;
139 for(; tr.translate_nocase(*str_tmp) == *pat_tmp; --pat_tmp, --str_tmp)
141 if(pat_tmp == this->begin_)
147 offset = this->offsets_[tr.hash(tr.translate_nocase(*begin))];
153 // case-insensitive Boyer-Moore search with case-folding
154 BidiIter find_nocase_fold_(BidiIter begin, BidiIter end, Traits const &tr) const
156 typedef typename boost::iterator_difference<BidiIter>::type diff_type;
157 diff_type const endpos = std::distance(begin, end);
158 diff_type offset = static_cast<diff_type>(this->length_);
160 for(diff_type curpos = offset; curpos < endpos; curpos += offset)
162 std::advance(begin, offset);
164 string_type const *pat_tmp = &this->fold_.back();
165 BidiIter str_tmp = begin;
167 for(; pat_tmp->end() != std::find(pat_tmp->begin(), pat_tmp->end(), *str_tmp);
168 --pat_tmp, --str_tmp)
170 if(pat_tmp == &this->fold_.front())
176 offset = this->offsets_[tr.hash(*begin)];
184 char_type const *begin_;
185 char_type const *last_;
186 std::vector<string_type> fold_;
187 BidiIter (boyer_moore::*const find_fun_)(BidiIter, BidiIter, Traits const &) const;
188 unsigned char length_;
189 unsigned char offsets_[UCHAR_MAX + 1];
192 }}} // namespace boost::xpressive::detail
194 #if defined(_MSC_VER)
195 # pragma warning(pop)