Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
src/strings/suffix_array_binsearch/binsearch.h
Go to the documentation of this file.
00001 #ifndef H_STRINGS_SUFFIX_ARRAY_BINSEARCH_BINSEARCH
00002 #define H_STRINGS_SUFFIX_ARRAY_BINSEARCH_BINSEARCH
00003 
00008 #include "utils/preconditions/preconditions.h"
00009 #include <vector>
00010 #include <iterator>
00011 #include <algorithm>
00012 #include "strings/suffix_array_naive/sort_helper.h"
00013 #include "strings/search_callback/search_callback.h"
00014 #include "utils/macros/unused.h"
00015 #include <stdio.h>
00016 
00017 namespace strings {
00018 namespace suffix_array {
00019 
00024 template <typename _Iterator>
00025 class SearchHelper {
00026  public:
00031   SearchHelper(const _Iterator& first, const _Iterator& last_) {
00032     base = first;
00033     last = last_;
00034   }
00035 
00041   template <typename _PatternIterator>
00042   int compare(const std::pair<_PatternIterator, _PatternIterator>& pattern, const int& a) {
00043     // FIXME(ppershing): type
00044     const int l = last - base;
00045     Preconditions::checkRange(a, l);
00046     _PatternIterator itp = pattern.first;
00047     _Iterator ita = base + a;
00048 
00049     while ((ita != last) && (itp != pattern.second) && (*ita == *itp)) {
00050       ++ita;
00051       ++itp;
00052     }
00053     bool seq_last = (ita == last);
00054     bool pat_last = (itp == pattern.second);
00055     if (UNLIKELY(seq_last || pat_last)) {
00056       if (pat_last) return 0;
00057       return 1;
00058     }
00059 
00060     if (*itp < *ita) {
00061       return -1;
00062     } else {
00063       return 1;
00064     }
00065   }
00073   template <typename _PatternIterator>
00074   bool operator()(const std::pair<_PatternIterator, _PatternIterator>& pattern, const int& a) {
00075     return compare(pattern, a) < 0;
00076   }
00077 
00078   template <typename _PatternIterator>
00079   bool operator()(const int& a, const std::pair<_PatternIterator, _PatternIterator>& pattern) {
00080     return compare(pattern, a) > 0;
00081   }
00082 
00083   private:
00084    _Iterator base;
00085    _Iterator last;
00086 };
00087 
00088 
00096 class Binsearch {
00097  public:
00112   template <typename _Iterator, typename _PatternIterator>
00113   static void searchSuffixArray(
00114       _Iterator first,
00115       _Iterator last, 
00116       const std::vector<int>& array,
00117       _PatternIterator pattern_first,
00118       _PatternIterator pattern_last,
00119       strings::search_callback::SearchCallback<_Iterator>* callback 
00120       ) {
00121     typedef typename std::iterator_traits<_Iterator>::difference_type DifferenceType;
00122     DifferenceType length = last - first;
00123     // TODO(ppershing): fix unsigned comparison
00124     Preconditions::check(length == (DifferenceType) array.size());
00125 
00126     SearchHelper<_Iterator> helper(first, last);
00127 
00128     typedef std::vector<int>::const_iterator SAIterator;
00129     SAIterator match_first = std::lower_bound(
00130               array.begin(), array.end(),
00131               std::make_pair(pattern_first, pattern_last),
00132               helper);
00133     SAIterator match_last = std::upper_bound(
00134               array.begin(), array.end(),
00135               std::make_pair(pattern_first, pattern_last),
00136               helper);
00137     while (match_first != match_last) {
00138       int suffix = *match_first;
00139       callback->foundMatch(first + suffix);
00140       ++match_first;
00141     }
00142   }
00143 };
00144 
00145 } // namespace suffix_array
00146 } // namespace strings
00147 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines