Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
src/strings/suffix_array_lcp_naive/lcp_naive.h
Go to the documentation of this file.
00001 #ifndef H_STRINGS_SUFFIX_ARRAY_LCP_NAIVE
00002 #define H_STRINGS_SUFFIX_ARRAY_LCP_NAIVE
00003 #include "utils/preconditions/preconditions.h"
00004 namespace strings {
00005 namespace suffix_array {
00006 
00015 class LCPNaive {
00016 private:
00017   template<typename _Iterator>
00018   static inline int lcp(_Iterator pos1, _Iterator pos2, _Iterator last)
00019   {
00020     int i = 0;
00021     while (pos1 != last && pos2 != last && *pos1 == *pos2) {
00022       ++i;
00023       ++pos1;
00024       ++pos2;
00025     }
00026     return i;
00027   }
00028 
00029 public:
00037   template<typename _Iterator, typename _SAIterator>
00038   static void getHeightArray(_Iterator seq_first, _Iterator seq_last,
00039       _SAIterator sa_first, _SAIterator sa_last, 
00040       std::vector<int> * out)
00041   {
00042     Preconditions::checkNotNull(out);
00043 
00044     Preconditions::check(seq_last - seq_first == sa_last - sa_first);
00045 
00046     unsigned int n = sa_last - sa_first;
00047 
00048     out->clear();
00049     out->resize(n);
00050 
00051     const int undefined = 0;
00052     (*out)[0] = undefined;
00053 
00054     for (unsigned int i = 1; i < n; i++) {
00055       _Iterator pos1 = seq_first + *(sa_first + (i - 1));
00056       _Iterator pos2 = seq_first + *(sa_first + i);
00057       (*out)[i] = lcp(pos1, pos2, seq_last);
00058     }
00059   }
00060 };
00061 
00062 } // namespace suffix_array
00063 } // namespace strings
00064 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines