Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
src/strings/suffix_array_naive/sort_helper.h
Go to the documentation of this file.
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
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines