diff options
Diffstat (limited to 'src/third_party/boost-1.56.0/boost/algorithm/searching/boyer_moore.hpp')
| -rw-r--r-- | src/third_party/boost-1.56.0/boost/algorithm/searching/boyer_moore.hpp | 268 |
1 files changed, 0 insertions, 268 deletions
diff --git a/src/third_party/boost-1.56.0/boost/algorithm/searching/boyer_moore.hpp b/src/third_party/boost-1.56.0/boost/algorithm/searching/boyer_moore.hpp deleted file mode 100644 index c5fe9fa255f..00000000000 --- a/src/third_party/boost-1.56.0/boost/algorithm/searching/boyer_moore.hpp +++ /dev/null @@ -1,268 +0,0 @@ -/* - 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 <iterator> // for std::iterator_traits - -#include <boost/assert.hpp> -#include <boost/static_assert.hpp> - -#include <boost/range/begin.hpp> -#include <boost/range/end.hpp> - -#include <boost/utility/enable_if.hpp> -#include <boost/type_traits/is_same.hpp> - -#include <boost/algorithm/searching/detail/bm_traits.hpp> -#include <boost/algorithm/searching/detail/debugging.hpp> - -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 <typename patIter, typename traits = detail::BM_traits<patIter> > - class boyer_moore { - typedef typename std::iterator_traits<patIter>::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 <typename corpusIter> - corpusIter operator () ( corpusIter corpus_first, corpusIter corpus_last ) const { - BOOST_STATIC_ASSERT (( boost::is_same< - typename std::iterator_traits<patIter>::value_type, - typename std::iterator_traits<corpusIter>::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 Range> - typename boost::range_iterator<Range>::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 <difference_type> 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 <typename corpusIter> - 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<typename Iter, typename Container> - 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<typename std::iterator_traits<patIter>::value_type> reversed(count); - (void) std::reverse_copy ( pat_first, pat_last, reversed.begin ()); - - std::vector<difference_type> prefix (count); - compute_bm_prefix ( pat_first, pat_last, prefix ); - - std::vector<difference_type> 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 <typename patIter, typename corpusIter> - corpusIter boyer_moore_search ( - corpusIter corpus_first, corpusIter corpus_last, - patIter pat_first, patIter pat_last ) - { - boyer_moore<patIter> bm ( pat_first, pat_last ); - return bm ( corpus_first, corpus_last ); - } - - template <typename PatternRange, typename corpusIter> - corpusIter boyer_moore_search ( - corpusIter corpus_first, corpusIter corpus_last, const PatternRange &pattern ) - { - typedef typename boost::range_iterator<const PatternRange>::type pattern_iterator; - boyer_moore<pattern_iterator> bm ( boost::begin(pattern), boost::end (pattern)); - return bm ( corpus_first, corpus_last ); - } - - template <typename patIter, typename CorpusRange> - typename boost::lazy_disable_if_c< - boost::is_same<CorpusRange, patIter>::value, typename boost::range_iterator<CorpusRange> > - ::type - boyer_moore_search ( CorpusRange &corpus, patIter pat_first, patIter pat_last ) - { - boyer_moore<patIter> bm ( pat_first, pat_last ); - return bm (boost::begin (corpus), boost::end (corpus)); - } - - template <typename PatternRange, typename CorpusRange> - typename boost::range_iterator<CorpusRange>::type - boyer_moore_search ( CorpusRange &corpus, const PatternRange &pattern ) - { - typedef typename boost::range_iterator<const PatternRange>::type pattern_iterator; - boyer_moore<pattern_iterator> 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 <typename Range> - boost::algorithm::boyer_moore<typename boost::range_iterator<const Range>::type> - make_boyer_moore ( const Range &r ) { - return boost::algorithm::boyer_moore - <typename boost::range_iterator<const Range>::type> (boost::begin(r), boost::end(r)); - } - - template <typename Range> - boost::algorithm::boyer_moore<typename boost::range_iterator<Range>::type> - make_boyer_moore ( Range &r ) { - return boost::algorithm::boyer_moore - <typename boost::range_iterator<Range>::type> (boost::begin(r), boost::end(r)); - } - -}} - -#endif // BOOST_ALGORITHM_BOYER_MOORE_SEARCH_HPP |