Statistics
| Revision:

## root / tmp / org.txm.statsengine.r.core.win32 / res / win32 / library / BH / include / boost / algorithm / searching / boyer_moore.hpp @ 2486

 1 /*   Copyright (c) Marshall Clow 2010-2012.     Distributed under the Boost Software License, Version 1.0. (See accompanying   file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)     For more information, see http://www.boost.org  */  #ifndef BOOST_ALGORITHM_BOYER_MOORE_SEARCH_HPP  #define BOOST_ALGORITHM_BOYER_MOORE_SEARCH_HPP  #include // for std::iterator_traits  #include  #include  #include  #include  #include  #include  #include  #include  namespace boost { namespace algorithm {  /*   A templated version of the boyer-moore searching algorithm.    References:   http://www.cs.utexas.edu/users/moore/best-ideas/string-searching/   http://www.cs.utexas.edu/~moore/publications/fstrpos.pdf    Explanations:   http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm   http://www.movsd.com/bm.htm   http://www.cs.ucdavis.edu/~gusfield/cs224f09/bnotes.pdf    The Boyer-Moore search algorithm uses two tables, a "bad character" table  to tell how far to skip ahead when it hits a character that is not in the pattern,  and a "good character" table to tell how far to skip ahead when it hits a  mismatch on a character that _is_ in the pattern.    Requirements:   * Random access iterators   * The two iterator types (patIter and corpusIter) must   "point to" the same underlying type and be comparable.   * Additional requirements may be imposed but the skip table, such as:   ** Numeric type (array-based skip table)   ** Hashable type (map-based skip table)  */   template >   class boyer_moore {   typedef typename std::iterator_traits::difference_type difference_type;   public:   boyer_moore ( patIter first, patIter last )   : pat_first ( first ), pat_last ( last ),   k_pattern_length ( std::distance ( pat_first, pat_last )),   skip_ ( k_pattern_length, -1 ),   suffix_ ( k_pattern_length + 1 )   {   this->build_skip_table ( first, last );   this->build_suffix_table ( first, last );   }     ~boyer_moore () {}     /// \fn operator ( corpusIter corpus_first, corpusIter corpus_last )   /// \brief Searches the corpus for the pattern that was passed into the constructor   ///   /// \param corpus_first The start of the data to search (Random Access Iterator)   /// \param corpus_last One past the end of the data to search   ///   template   corpusIter operator () ( corpusIter corpus_first, corpusIter corpus_last ) const {   BOOST_STATIC_ASSERT (( boost::is_same<   typename std::iterator_traits::value_type,   typename std::iterator_traits::value_type>::value ));   if ( corpus_first == corpus_last ) return corpus_last; // if nothing to search, we didn't find it!   if ( pat_first == pat_last ) return corpus_first; // empty pattern matches at start   const difference_type k_corpus_length = std::distance ( corpus_first, corpus_last );   // If the pattern is larger than the corpus, we can't find it!   if ( k_corpus_length < k_pattern_length )   return corpus_last;   // Do the search   return this->do_search ( corpus_first, corpus_last );   }     template   typename boost::range_iterator::type operator () ( Range &r ) const {   return (*this) (boost::begin(r), boost::end(r));   }   private:  /// \cond DOXYGEN_HIDE   patIter pat_first, pat_last;   const difference_type k_pattern_length;   typename traits::skip_table_t skip_;   std::vector suffix_;   /// \fn operator ( corpusIter corpus_first, corpusIter corpus_last, Pred p )   /// \brief Searches the corpus for the pattern that was passed into the constructor   ///   /// \param corpus_first The start of the data to search (Random Access Iterator)   /// \param corpus_last One past the end of the data to search   /// \param p A predicate used for the search comparisons.   ///   template   corpusIter do_search ( corpusIter corpus_first, corpusIter corpus_last ) const {   /* ---- Do the matching ---- */   corpusIter curPos = corpus_first;   const corpusIter lastPos = corpus_last - k_pattern_length;   difference_type j, k, m;   while ( curPos <= lastPos ) {   /* while ( std::distance ( curPos, corpus_last ) >= k_pattern_length ) { */   // Do we match right where we are?   j = k_pattern_length;   while ( pat_first [j-1] == curPos [j-1] ) {   j--;   // We matched - we're done!   if ( j == 0 )   return curPos;   }     // Since we didn't match, figure out how far to skip forward   k = skip_ [ curPos [ j - 1 ]];   m = j - k - 1;   if ( k < j && m > suffix_ [ j ] )   curPos += m;   else   curPos += suffix_ [ j ];   }     return corpus_last; // We didn't find anything   }   void build_skip_table ( patIter first, patIter last ) {   for ( std::size_t i = 0; first != last; ++first, ++i )   skip_.insert ( *first, i );   }     template   void compute_bm_prefix ( Iter pat_first, Iter pat_last, Container &prefix ) {   const std::size_t count = std::distance ( pat_first, pat_last );   BOOST_ASSERT ( count > 0 );   BOOST_ASSERT ( prefix.size () == count );     prefix[0] = 0;   std::size_t k = 0;   for ( std::size_t i = 1; i < count; ++i ) {   BOOST_ASSERT ( k < count );   while ( k > 0 && ( pat_first[k] != pat_first[i] )) {   BOOST_ASSERT ( k < count );   k = prefix [ k - 1 ];   }     if ( pat_first[k] == pat_first[i] )   k++;   prefix [ i ] = k;   }   }   void build_suffix_table ( patIter pat_first, patIter pat_last ) {   const std::size_t count = (std::size_t) std::distance ( pat_first, pat_last );     if ( count > 0 ) { // empty pattern   std::vector::value_type> reversed(count);   (void) std::reverse_copy ( pat_first, pat_last, reversed.begin ());     std::vector prefix (count);   compute_bm_prefix ( pat_first, pat_last, prefix );     std::vector prefix_reversed (count);   compute_bm_prefix ( reversed.begin (), reversed.end (), prefix_reversed );     for ( std::size_t i = 0; i <= count; i++ )   suffix_[i] = count - prefix [count-1];     for ( std::size_t i = 0; i < count; i++ ) {   const std::size_t j = count - prefix_reversed[i];   const difference_type k = i - prefix_reversed[i] + 1;     if (suffix_[j] > k)   suffix_[j] = k;   }   }   }  /// \endcond   };  /* Two ranges as inputs gives us four possibilities; with 2,3,3,4 parameters   Use a bit of TMP to disambiguate the 3-argument templates */  /// \fn boyer_moore_search ( corpusIter corpus_first, corpusIter corpus_last,  /// patIter pat_first, patIter pat_last )  /// \brief Searches the corpus for the pattern.  ///  /// \param corpus_first The start of the data to search (Random Access Iterator)  /// \param corpus_last One past the end of the data to search  /// \param pat_first The start of the pattern to search for (Random Access Iterator)  /// \param pat_last One past the end of the data to search for  ///   template   corpusIter boyer_moore_search (   corpusIter corpus_first, corpusIter corpus_last,   patIter pat_first, patIter pat_last )   {   boyer_moore bm ( pat_first, pat_last );   return bm ( corpus_first, corpus_last );   }   template   corpusIter boyer_moore_search (   corpusIter corpus_first, corpusIter corpus_last, const PatternRange &pattern )   {   typedef typename boost::range_iterator::type pattern_iterator;   boyer_moore bm ( boost::begin(pattern), boost::end (pattern));   return bm ( corpus_first, corpus_last );   }     template   typename boost::lazy_disable_if_c<   boost::is_same::value, typename boost::range_iterator >   ::type   boyer_moore_search ( CorpusRange &corpus, patIter pat_first, patIter pat_last )   {   boyer_moore bm ( pat_first, pat_last );   return bm (boost::begin (corpus), boost::end (corpus));   }     template   typename boost::range_iterator::type   boyer_moore_search ( CorpusRange &corpus, const PatternRange &pattern )   {   typedef typename boost::range_iterator::type pattern_iterator;   boyer_moore bm ( boost::begin(pattern), boost::end (pattern));   return bm (boost::begin (corpus), boost::end (corpus));   }   // Creator functions -- take a pattern range, return an object   template   boost::algorithm::boyer_moore::type>   make_boyer_moore ( const Range &r ) {   return boost::algorithm::boyer_moore   ::type> (boost::begin(r), boost::end(r));   }     template   boost::algorithm::boyer_moore::type>   make_boyer_moore ( Range &r ) {   return boost::algorithm::boyer_moore   ::type> (boost::begin(r), boost::end(r));   }  }}  #endif // BOOST_ALGORITHM_BOYER_MOORE_SEARCH_HPP