Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
|
00001 #ifndef H_STRINGS_SUFFIX_ARRAY_NAIVE_SORT_HELPER 00002 #define H_STRINGS_SUFFIX_ARRAY_NAIVE_SORT_HELPER 00003 00004 #include <iterator> 00005 #include "utils/preconditions/preconditions.h" 00006 #include "utils/branch_predict/branch_predict.h" 00007 00008 namespace strings { 00009 namespace suffix_array { 00010 00015 template <typename _Iterator> 00016 class SortHelper { 00017 public: 00022 SortHelper(const _Iterator first, const _Iterator last_) { 00023 base = first; 00024 last = last_; 00025 } 00026 00034 bool operator()(const int& a, const int& b) { 00035 int l = last - base; 00036 Preconditions::checkRange(a, l); 00037 Preconditions::checkRange(b, l); 00038 if (a == b) return false; 00039 _Iterator ita = base + a; 00040 _Iterator itb = base + b; 00041 00042 while ((ita != last) && (itb != last) && (*ita == *itb)) { 00043 ++ita; 00044 ++itb; 00045 } 00046 if (UNLIKELY(ita == last)) return true; // suffix a is shorter 00047 if (UNLIKELY(itb == last)) return false; // suffix b is shorter 00048 return *ita < *itb; 00049 } 00050 00051 private: 00052 _Iterator base; 00053 _Iterator last; 00054 }; 00055 00056 } // namespace suffix_array 00057 } // namespace strings 00058 00059 #endif