Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
|
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