ceph/src/boost/libs/algorithm/include/boost/algorithm/searching/boyer_moore.hpp

   1 /*
   2    Copyright (c) Marshall Clow 2010-2012.
   3
   4    Distributed under the Boost Software License, Version 1.0. (See accompanying
   5    file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   6
   7     For more information, see http://www.boost.org
   8 */
   9
  10 #ifndef BOOST_ALGORITHM_BOYER_MOORE_SEARCH_HPP
  11 #define BOOST_ALGORITHM_BOYER_MOORE_SEARCH_HPP
  12
  13 #include <iterator>     // for std::iterator_traits
  14
  15 #include <boost/assert.hpp>
  16 #include <boost/static_assert.hpp>
  17
  18 #include <boost/range/begin.hpp>
  19 #include <boost/range/end.hpp>
  20
  21 #include <boost/utility/enable_if.hpp>
  22 #include <boost/type_traits/is_same.hpp>
  23
  24 #include <boost/algorithm/searching/detail/bm_traits.hpp>
  25 #include <boost/algorithm/searching/detail/debugging.hpp>
  26
  27 namespace boost { namespace algorithm {
  28
  29 /*
  30     A templated version of the boyer-moore searching algorithm.
  31
  32 References:
  33     http://www.cs.utexas.edu/users/moore/best-ideas/string-searching/
  34     http://www.cs.utexas.edu/~moore/publications/fstrpos.pdf
  35
  36 Explanations:
  37     http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm
  38     http://www.movsd.com/bm.htm
  39     http://www.cs.ucdavis.edu/~gusfield/cs224f09/bnotes.pdf
  40
  41 The Boyer-Moore search algorithm uses two tables, a "bad character" table
  42 to tell how far to skip ahead when it hits a character that is not in the pattern,
  43 and a "good character" table to tell how far to skip ahead when it hits a
  44 mismatch on a character that _is_ in the pattern.
  45
  46 Requirements:
  47         * Random access iterators
  48         * The two iterator types (patIter and corpusIter) must
  49             "point to" the same underlying type and be comparable.
  50         * Additional requirements may be imposed but the skip table, such as:
  51         ** Numeric type (array-based skip table)
  52         ** Hashable type (map-based skip table)
  53 */
  54
  55     template <typename patIter, typename traits = detail::BM_traits<patIter> >
  56     class boyer_moore {
  57         typedef typename std::iterator_traits<patIter>::difference_type difference_type;
  58     public:
  59         boyer_moore ( patIter first, patIter last )
  60                 : pat_first ( first ), pat_last ( last ),
  61                   k_pattern_length ( std::distance ( pat_first, pat_last )),
  62                   skip_ ( k_pattern_length, -1 ),
  63                   suffix_ ( k_pattern_length + 1 )
  64             {
  65             this->build_skip_table   ( first, last );
  66             this->build_suffix_table ( first, last );
  67             }
  68
  69         ~boyer_moore () {}
  70
  71         /// \fn operator ( corpusIter corpus_first, corpusIter corpus_last )
  72         /// \brief Searches the corpus for the pattern that was passed into the constructor
  73         ///
  74         /// \param corpus_first The start of the data to search (Random Access Iterator)
  75         /// \param corpus_last  One past the end of the data to search
  76         ///
  77         template <typename corpusIter>
  78         std::pair<corpusIter, corpusIter>
  79         operator () ( corpusIter corpus_first, corpusIter corpus_last ) const {
  80             BOOST_STATIC_ASSERT (( boost::is_same<
  81                                     typename std::iterator_traits<patIter>::value_type,
  82                                     typename std::iterator_traits<corpusIter>::value_type>::value ));
  83
  84             if ( corpus_first == corpus_last ) return std::make_pair(corpus_last, corpus_last);   // if nothing to search, we didn't find it!
  85             if (    pat_first ==    pat_last ) return std::make_pair(corpus_first, corpus_first); // empty pattern matches at start
  86
  87             const difference_type k_corpus_length  = std::distance ( corpus_first, corpus_last );
  88         //  If the pattern is larger than the corpus, we can't find it!
  89             if ( k_corpus_length < k_pattern_length )
  90                 return std::make_pair(corpus_last, corpus_last);
  91
  92         //  Do the search
  93             return this->do_search ( corpus_first, corpus_last );
  94             }
  95
  96         template <typename Range>
  97         std::pair<typename boost::range_iterator<Range>::type, typename boost::range_iterator<Range>::type>
  98         operator () ( Range &r ) const {
  99             return (*this) (boost::begin(r), boost::end(r));
 100             }
 101
 102     private:
 103 /// \cond DOXYGEN_HIDE
 104         patIter pat_first, pat_last;
 105         const difference_type k_pattern_length;
 106         typename traits::skip_table_t skip_;
 107         std::vector <difference_type> suffix_;
 108
 109         /// \fn operator ( corpusIter corpus_first, corpusIter corpus_last, Pred p )
 110         /// \brief Searches the corpus for the pattern that was passed into the constructor
 111         ///
 112         /// \param corpus_first The start of the data to search (Random Access Iterator)
 113         /// \param corpus_last  One past the end of the data to search
 114         /// \param p            A predicate used for the search comparisons.
 115         ///
 116         template <typename corpusIter>
 117         std::pair<corpusIter, corpusIter>
 118         do_search ( corpusIter corpus_first, corpusIter corpus_last ) const {
 119         /*  ---- Do the matching ---- */
 120             corpusIter curPos = corpus_first;
 121             const corpusIter lastPos = corpus_last - k_pattern_length;
 122             difference_type j, k, m;
 123
 124             while ( curPos <= lastPos ) {
 125         /*  while ( std::distance ( curPos, corpus_last ) >= k_pattern_length ) { */
 126             //  Do we match right where we are?
 127                 j = k_pattern_length;
 128                 while ( pat_first [j-1] == curPos [j-1] ) {
 129                     j--;
 130                 //  We matched - we're done!
 131                     if ( j == 0 )
 132                         return std::make_pair(curPos, curPos + k_pattern_length);
 133                     }
 134
 135             //  Since we didn't match, figure out how far to skip forward
 136                 k = skip_ [ curPos [ j - 1 ]];
 137                 m = j - k - 1;
 138                 if ( k < j && m > suffix_ [ j ] )
 139                     curPos += m;
 140                 else
 141                     curPos += suffix_ [ j ];
 142                 }
 143
 144             return std::make_pair(corpus_last, corpus_last);     // We didn't find anything
 145             }
 146
 147
 148         void build_skip_table ( patIter first, patIter last ) {
 149             for ( std::size_t i = 0; first != last; ++first, ++i )
 150                 skip_.insert ( *first, i );
 151             }
 152
 153
 154         template<typename Iter, typename Container>
 155         void compute_bm_prefix ( Iter pat_first, Iter pat_last, Container &prefix ) {
 156             const std::size_t count = std::distance ( pat_first, pat_last );
 157             BOOST_ASSERT ( count > 0 );
 158             BOOST_ASSERT ( prefix.size () == count );
 159
 160             prefix[0] = 0;
 161             std::size_t k = 0;
 162             for ( std::size_t i = 1; i < count; ++i ) {
 163                 BOOST_ASSERT ( k < count );
 164                 while ( k > 0 && ( pat_first[k] != pat_first[i] )) {
 165                     BOOST_ASSERT ( k < count );
 166                     k = prefix [ k - 1 ];
 167                     }
 168
 169                 if ( pat_first[k] == pat_first[i] )
 170                     k++;
 171                 prefix [ i ] = k;
 172                 }
 173             }
 174
 175         void build_suffix_table ( patIter pat_first, patIter pat_last ) {
 176             const std::size_t count = (std::size_t) std::distance ( pat_first, pat_last );
 177
 178             if ( count > 0 ) {  // empty pattern
 179                 std::vector<typename std::iterator_traits<patIter>::value_type> reversed(count);
 180                 (void) std::reverse_copy ( pat_first, pat_last, reversed.begin ());
 181
 182                 std::vector<difference_type> prefix (count);
 183                 compute_bm_prefix ( pat_first, pat_last, prefix );
 184
 185                 std::vector<difference_type> prefix_reversed (count);
 186                 compute_bm_prefix ( reversed.begin (), reversed.end (), prefix_reversed );
 187
 188                 for ( std::size_t i = 0; i <= count; i++ )
 189                     suffix_[i] = count - prefix [count-1];
 190
 191                 for ( std::size_t i = 0; i < count; i++ ) {
 192                     const std::size_t     j = count - prefix_reversed[i];
 193                     const difference_type k = i -     prefix_reversed[i] + 1;
 194
 195                     if (suffix_[j] > k)
 196                         suffix_[j] = k;
 197                     }
 198                 }
 199             }
 200 /// \endcond
 201         };
 202
 203
 204 /*  Two ranges as inputs gives us four possibilities; with 2,3,3,4 parameters
 205     Use a bit of TMP to disambiguate the 3-argument templates */
 206
 207 /// \fn boyer_moore_search ( corpusIter corpus_first, corpusIter corpus_last,
 208 ///       patIter pat_first, patIter pat_last )
 209 /// \brief Searches the corpus for the pattern.
 210 ///
 211 /// \param corpus_first The start of the data to search (Random Access Iterator)
 212 /// \param corpus_last  One past the end of the data to search
 213 /// \param pat_first    The start of the pattern to search for (Random Access Iterator)
 214 /// \param pat_last     One past the end of the data to search for
 215 ///
 216     template <typename patIter, typename corpusIter>
 217     std::pair<corpusIter, corpusIter> boyer_moore_search (
 218                   corpusIter corpus_first, corpusIter corpus_last,
 219                   patIter pat_first, patIter pat_last )
 220     {
 221         boyer_moore<patIter> bm ( pat_first, pat_last );
 222         return bm ( corpus_first, corpus_last );
 223     }
 224
 225     template <typename PatternRange, typename corpusIter>
 226     std::pair<corpusIter, corpusIter> boyer_moore_search (
 227         corpusIter corpus_first, corpusIter corpus_last, const PatternRange &pattern )
 228     {
 229         typedef typename boost::range_iterator<const PatternRange>::type pattern_iterator;
 230         boyer_moore<pattern_iterator> bm ( boost::begin(pattern), boost::end (pattern));
 231         return bm ( corpus_first, corpus_last );
 232     }
 233
 234     template <typename patIter, typename CorpusRange>
 235     typename boost::disable_if_c<
 236         boost::is_same<CorpusRange, patIter>::value,
 237         std::pair<typename boost::range_iterator<CorpusRange>::type, typename boost::range_iterator<CorpusRange>::type> >
 238     ::type
 239     boyer_moore_search ( CorpusRange &corpus, patIter pat_first, patIter pat_last )
 240     {
 241         boyer_moore<patIter> bm ( pat_first, pat_last );
 242         return bm (boost::begin (corpus), boost::end (corpus));
 243     }
 244
 245     template <typename PatternRange, typename CorpusRange>
 246     std::pair<typename boost::range_iterator<CorpusRange>::type, typename boost::range_iterator<CorpusRange>::type>
 247     boyer_moore_search ( CorpusRange &corpus, const PatternRange &pattern )
 248     {
 249         typedef typename boost::range_iterator<const PatternRange>::type pattern_iterator;
 250         boyer_moore<pattern_iterator> bm ( boost::begin(pattern), boost::end (pattern));
 251         return bm (boost::begin (corpus), boost::end (corpus));
 252     }
 253
 254
 255     //  Creator functions -- take a pattern range, return an object
 256     template <typename Range>
 257     boost::algorithm::boyer_moore<typename boost::range_iterator<const Range>::type>
 258     make_boyer_moore ( const Range &r ) {
 259         return boost::algorithm::boyer_moore
 260             <typename boost::range_iterator<const Range>::type> (boost::begin(r), boost::end(r));
 261         }
 262
 263     template <typename Range>
 264     boost::algorithm::boyer_moore<typename boost::range_iterator<Range>::type>
 265     make_boyer_moore ( Range &r ) {
 266         return boost::algorithm::boyer_moore
 267             <typename boost::range_iterator<Range>::type> (boost::begin(r), boost::end(r));
 268         }
 269
 270 }}
 271
 272 #endif  //  BOOST_ALGORITHM_BOYER_MOORE_SEARCH_HPP