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