ceph/src/boost/libs/algorithm/include/boost/algorithm/searching/boyer_moore_horspool.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_HORSPOOOL_SEARCH_HPP
  11 #define BOOST_ALGORITHM_BOYER_MOORE_HORSPOOOL_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 // #define  BOOST_ALGORITHM_BOYER_MOORE_HORSPOOL_DEBUG_HPP
  28
  29 namespace boost { namespace algorithm {
  30
  31 /*
  32     A templated version of the boyer-moore-horspool searching algorithm.
  33
  34     Requirements:
  35         * Random access iterators
  36         * The two iterator types (patIter and corpusIter) must
  37             "point to" the same underlying type.
  38         * Additional requirements may be imposed buy the skip table, such as:
  39         ** Numeric type (array-based skip table)
  40         ** Hashable type (map-based skip table)
  41
  42 http://www-igm.univ-mlv.fr/%7Elecroq/string/node18.html
  43
  44 */
  45
  46     template <typename patIter, typename traits = detail::BM_traits<patIter> >
  47     class boyer_moore_horspool {
  48         typedef typename std::iterator_traits<patIter>::difference_type difference_type;
  49     public:
  50         boyer_moore_horspool ( patIter first, patIter last )
  51                 : pat_first ( first ), pat_last ( last ),
  52                   k_pattern_length ( std::distance ( pat_first, pat_last )),
  53                   skip_ ( k_pattern_length, k_pattern_length ) {
  54
  55         //  Build the skip table
  56             std::size_t i = 0;
  57             if ( first != last )    // empty pattern?
  58                 for ( patIter iter = first; iter != last-1; ++iter, ++i )
  59                     skip_.insert ( *iter, k_pattern_length - 1 - i );
  60 #ifdef BOOST_ALGORITHM_BOYER_MOORE_HORSPOOL_DEBUG_HPP
  61             skip_.PrintSkipTable ();
  62 #endif
  63             }
  64
  65         ~boyer_moore_horspool () {}
  66
  67         /// \fn operator ( corpusIter corpus_first, corpusIter corpus_last)
  68         /// \brief Searches the corpus for the pattern that was passed into the constructor
  69         ///
  70         /// \param corpus_first The start of the data to search (Random Access Iterator)
  71         /// \param corpus_last  One past the end of the data to search
  72         ///
  73         template <typename corpusIter>
  74         std::pair<corpusIter, corpusIter>
  75         operator () ( corpusIter corpus_first, corpusIter corpus_last ) const {
  76             BOOST_STATIC_ASSERT (( boost::is_same<
  77                 typename std::iterator_traits<patIter>::value_type,
  78                 typename std::iterator_traits<corpusIter>::value_type>::value ));
  79
  80             if ( corpus_first == corpus_last ) return std::make_pair(corpus_last, corpus_last);   // if nothing to search, we didn't find it!
  81             if (    pat_first ==    pat_last ) return std::make_pair(corpus_first, corpus_first); // empty pattern matches at start
  82
  83             const difference_type k_corpus_length  = std::distance ( corpus_first, corpus_last );
  84         //  If the pattern is larger than the corpus, we can't find it!
  85             if ( k_corpus_length < k_pattern_length )
  86                 return std::make_pair(corpus_last, corpus_last);
  87
  88         //  Do the search
  89             return this->do_search ( corpus_first, corpus_last );
  90             }
  91
  92         template <typename Range>
  93         std::pair<typename boost::range_iterator<Range>::type, typename boost::range_iterator<Range>::type>
  94         operator () ( Range &r ) const {
  95             return (*this) (boost::begin(r), boost::end(r));
  96             }
  97
  98     private:
  99 /// \cond DOXYGEN_HIDE
 100         patIter pat_first, pat_last;
 101         const difference_type k_pattern_length;
 102         typename traits::skip_table_t skip_;
 103
 104         /// \fn do_search ( corpusIter corpus_first, corpusIter corpus_last )
 105         /// \brief Searches the corpus for the pattern that was passed into the constructor
 106         ///
 107         /// \param corpus_first The start of the data to search (Random Access Iterator)
 108         /// \param corpus_last  One past the end of the data to search
 109         /// \param k_corpus_length The length of the corpus to search
 110         ///
 111         template <typename corpusIter>
 112         std::pair<corpusIter, corpusIter>
 113         do_search ( corpusIter corpus_first, corpusIter corpus_last ) const {
 114             corpusIter curPos = corpus_first;
 115             const corpusIter lastPos = corpus_last - k_pattern_length;
 116             while ( curPos <= lastPos ) {
 117             //  Do we match right where we are?
 118                 std::size_t j = k_pattern_length - 1;
 119                 while ( pat_first [j] == curPos [j] ) {
 120                 //  We matched - we're done!
 121                     if ( j == 0 )
 122                         return std::make_pair(curPos, curPos + k_pattern_length);
 123                     j--;
 124                     }
 125
 126                 curPos += skip_ [ curPos [ k_pattern_length - 1 ]];
 127                 }
 128
 129             return std::make_pair(corpus_last, corpus_last);
 130             }
 131 // \endcond
 132         };
 133
 134 /*  Two ranges as inputs gives us four possibilities; with 2,3,3,4 parameters
 135     Use a bit of TMP to disambiguate the 3-argument templates */
 136
 137 /// \fn boyer_moore_horspool_search ( corpusIter corpus_first, corpusIter corpus_last,
 138 ///       patIter pat_first, patIter pat_last )
 139 /// \brief Searches the corpus for the pattern.
 140 ///
 141 /// \param corpus_first The start of the data to search (Random Access Iterator)
 142 /// \param corpus_last  One past the end of the data to search
 143 /// \param pat_first    The start of the pattern to search for (Random Access Iterator)
 144 /// \param pat_last     One past the end of the data to search for
 145 ///
 146     template <typename patIter, typename corpusIter>
 147     std::pair<corpusIter, corpusIter> boyer_moore_horspool_search (
 148                   corpusIter corpus_first, corpusIter corpus_last,
 149                   patIter pat_first, patIter pat_last )
 150     {
 151         boyer_moore_horspool<patIter> bmh ( pat_first, pat_last );
 152         return bmh ( corpus_first, corpus_last );
 153     }
 154
 155     template <typename PatternRange, typename corpusIter>
 156     std::pair<corpusIter, corpusIter> boyer_moore_horspool_search (
 157         corpusIter corpus_first, corpusIter corpus_last, const PatternRange &pattern )
 158     {
 159         typedef typename boost::range_iterator<const PatternRange>::type pattern_iterator;
 160         boyer_moore_horspool<pattern_iterator> bmh ( boost::begin(pattern), boost::end (pattern));
 161         return bmh ( corpus_first, corpus_last );
 162     }
 163
 164     template <typename patIter, typename CorpusRange>
 165     typename boost::disable_if_c<
 166         boost::is_same<CorpusRange, patIter>::value,
 167         std::pair<typename boost::range_iterator<CorpusRange>::type, typename boost::range_iterator<CorpusRange>::type> >
 168     ::type
 169     boyer_moore_horspool_search ( CorpusRange &corpus, patIter pat_first, patIter pat_last )
 170     {
 171         boyer_moore_horspool<patIter> bmh ( pat_first, pat_last );
 172         return bm (boost::begin (corpus), boost::end (corpus));
 173     }
 174
 175     template <typename PatternRange, typename CorpusRange>
 176     std::pair<typename boost::range_iterator<CorpusRange>::type, typename boost::range_iterator<CorpusRange>::type>
 177     boyer_moore_horspool_search ( CorpusRange &corpus, const PatternRange &pattern )
 178     {
 179         typedef typename boost::range_iterator<const PatternRange>::type pattern_iterator;
 180         boyer_moore_horspool<pattern_iterator> bmh ( boost::begin(pattern), boost::end (pattern));
 181         return bmh (boost::begin (corpus), boost::end (corpus));
 182     }
 183
 184
 185     //  Creator functions -- take a pattern range, return an object
 186     template <typename Range>
 187     boost::algorithm::boyer_moore_horspool<typename boost::range_iterator<const Range>::type>
 188     make_boyer_moore_horspool ( const Range &r ) {
 189         return boost::algorithm::boyer_moore_horspool
 190             <typename boost::range_iterator<const Range>::type> (boost::begin(r), boost::end(r));
 191         }
 192
 193     template <typename Range>
 194     boost::algorithm::boyer_moore_horspool<typename boost::range_iterator<Range>::type>
 195     make_boyer_moore_horspool ( Range &r ) {
 196         return boost::algorithm::boyer_moore_horspool
 197             <typename boost::range_iterator<Range>::type> (boost::begin(r), boost::end(r));
 198         }
 199
 200 }}
 201
 202 #endif  //  BOOST_ALGORITHM_BOYER_MOORE_HORSPOOOL_SEARCH_HPP