NVBIO
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Classes | Namespaces | Macros | Functions
divsufsortxx.h File Reference
#include <algorithm>
#include <stack>

Go to the source code of this file.

Classes

struct  divsufsortxx::helper::stackinfo3< a_type, b_type, c_type >
 
struct  divsufsortxx::helper::stackinfo4< a_type, b_type, c_type, d_type >
 
class  divsufsortxx::substring::substring_wrapper< StringIterator_type, PAIterator_type >
 

Namespaces

 divsufsortxx
 
 divsufsortxx::helper
 
 divsufsortxx::substring
 
 divsufsortxx::doubling
 
 divsufsortxx::tandemrepeat
 
 divsufsortxx::core
 

Macros

#define STACK_POP3(_a, _b, _c)
 
#define STACK_POP4(_a, _b, _c, _d)
 
#define STACK_PUSH3(_a, _b, _c)   stack.push(stackinfo_type((_a), (_b), (_c)))
 
#define STACK_PUSH4(_a, _b, _c, _d)   stack.push(stackinfo_type((_a), (_b), (_c), (_d)))
 
#define GETIDX(a)   ((0 <= (a)) ? (a) : (~(a)))
 
#define MERGE_CHECK(a)
 
#define UPDATE_BUDGET(n)
 
#define BUCKET_A(c0)   bucket_A[(c0)]
 
#define BUCKET_B(c0, c1)   (bucket_B[((alphabetsize_type)(c1)) * alphabetsize + (alphabetsize_type)(c0)])
 
#define BUCKET_BSTAR(c0, c1)   (bucket_B[((alphabetsize_type)(c0)) * alphabetsize + (alphabetsize_type)(c1)])
 

Functions

template<typename ISAIterator_type , typename SAIterator_type >
void divsufsortxx::helper::insertionsort (const ISAIterator_type ISAd, SAIterator_type first, SAIterator_type last)
 
template<typename StringIterator_type , typename SAIterator_type , typename pos_type >
void divsufsortxx::helper::fixdown (const StringIterator_type Td, SAIterator_type SA, pos_type i, pos_type size)
 
template<typename StringIterator_type , typename SAIterator_type >
void divsufsortxx::helper::heapsort (const StringIterator_type Td, SAIterator_type SA, typename std::iterator_traits< SAIterator_type >::value_type size)
 
template<typename numeric_type >
int divsufsortxx::helper::lg (numeric_type n)
 
template<typename Iterator1_type , typename Iterator2_type >
void divsufsortxx::helper::vecswap (Iterator1_type first1, Iterator1_type last1, Iterator2_type first2)
 
template<typename StringIterator_type , typename SAIterator_type >
SAIterator_type divsufsortxx::helper::median3 (const StringIterator_type Td, SAIterator_type v1, SAIterator_type v2, SAIterator_type v3)
 
template<typename StringIterator_type , typename SAIterator_type >
SAIterator_type divsufsortxx::helper::median5 (const StringIterator_type Td, SAIterator_type v1, SAIterator_type v2, SAIterator_type v3, SAIterator_type v4, SAIterator_type v5)
 
template<typename StringIterator_type , typename SAIterator_type >
SAIterator_type divsufsortxx::helper::pivot (const StringIterator_type Td, SAIterator_type first, SAIterator_type last)
 
template<typename StringIterator_type , typename SAIterator_type >
bool divsufsortxx::helper::partition (const StringIterator_type Td, SAIterator_type first1, SAIterator_type first2, SAIterator_type last, SAIterator_type &mfirst, SAIterator_type &mlast, const typename std::iterator_traits< StringIterator_type >::value_type &v)
 
template<typename StringIterator_type , typename SAIterator_type >
int divsufsortxx::substring::compare (StringIterator_type T, const SAIterator_type p1, const SAIterator_type p2, typename std::iterator_traits< SAIterator_type >::value_type depth)
 
template<typename StringIterator_type , typename SAIterator_type >
int divsufsortxx::substring::compare_last (StringIterator_type T, const SAIterator_type p1, const SAIterator_type p2, typename std::iterator_traits< SAIterator_type >::value_type depth, typename std::iterator_traits< SAIterator_type >::value_type size)
 
template<typename StringIterator_type , typename SAIterator_type >
void divsufsortxx::substring::insertionsort (StringIterator_type T, const SAIterator_type PA, SAIterator_type first, SAIterator_type last, typename std::iterator_traits< SAIterator_type >::value_type depth)
 
template<typename SAIterator_type >
SAIterator_type divsufsortxx::substring::partition (const SAIterator_type PA, SAIterator_type first, SAIterator_type last, typename std::iterator_traits< SAIterator_type >::value_type depth)
 
template<typename stack_type , typename StringIterator_type , typename SAIterator_type >
void divsufsortxx::substring::mintrosort (stack_type &stack, const StringIterator_type T, const SAIterator_type PA, SAIterator_type first, SAIterator_type last, typename std::iterator_traits< SAIterator_type >::value_type depth)
 
template<typename StringIterator_type , typename SAIterator_type , typename BufIterator_type >
void divsufsortxx::substring::merge_forward (const StringIterator_type T, const SAIterator_type PA, BufIterator_type buf, SAIterator_type first, SAIterator_type middle, SAIterator_type last, typename std::iterator_traits< SAIterator_type >::value_type depth)
 
template<typename StringIterator_type , typename SAIterator_type , typename BufIterator_type >
void divsufsortxx::substring::merge_backward (const StringIterator_type T, const SAIterator_type PA, BufIterator_type buf, SAIterator_type first, SAIterator_type middle, SAIterator_type last, typename std::iterator_traits< SAIterator_type >::value_type depth)
 
template<typename stack_type , typename StringIterator_type , typename SAIterator_type , typename BufIterator_type >
void divsufsortxx::substring::merge (stack_type &stack, const StringIterator_type T, const SAIterator_type PA, SAIterator_type first, SAIterator_type middle, SAIterator_type last, BufIterator_type buf, typename std::iterator_traits< SAIterator_type >::value_type bufsize, typename std::iterator_traits< SAIterator_type >::value_type depth)
 
template<typename StringIterator_type , typename SAIterator_type , typename BufIterator_type >
void divsufsortxx::substring::sort (const StringIterator_type T, const SAIterator_type PA, SAIterator_type first, SAIterator_type last, BufIterator_type buf, typename std::iterator_traits< SAIterator_type >::value_type bufsize, typename std::iterator_traits< SAIterator_type >::value_type depth, typename std::iterator_traits< SAIterator_type >::value_type size, bool lastsuffix, int blocksize=1024)
 
template<typename ISAIterator_type , typename SAIterator_type >
void divsufsortxx::doubling::updategroup (ISAIterator_type ISA, const SAIterator_type SA, SAIterator_type first, SAIterator_type last)
 
template<typename stack_type , typename ISAIterator_type , typename SAIterator_type >
void divsufsortxx::doubling::introsort (stack_type &stack, ISAIterator_type ISA, const ISAIterator_type ISAd, const SAIterator_type SA, SAIterator_type first, SAIterator_type last)
 
template<typename ISAIterator_type , typename SAIterator_type >
void divsufsortxx::doubling::sort (ISAIterator_type ISA, SAIterator_type first, SAIterator_type last)
 
template<typename stack_type , typename ISAIterator_type , typename SAIterator_type , typename pos_type >
void divsufsortxx::tandemrepeat::introsort (stack_type &stack, ISAIterator_type ISA, ISAIterator_type ISAd, const SAIterator_type SA, SAIterator_type first, SAIterator_type last, pos_type &budget, int &chance, pos_type size)
 
template<typename ISAIterator_type , typename SAIterator_type >
bool divsufsortxx::tandemrepeat::sort (ISAIterator_type ISA, SAIterator_type first, SAIterator_type last)
 
template<typename StringIterator_type , typename SAIterator_type , typename pos_type , typename alphabetsize_type >
pos_type divsufsortxx::core::sort_typeBstar (const StringIterator_type T, SAIterator_type SA, pos_type *bucket_A, pos_type *bucket_B, pos_type n, pos_type SAsize, alphabetsize_type alphabetsize)
 
template<typename StringIterator_type , typename SAIterator_type , typename pos_type , typename alphabetsize_type >
void divsufsortxx::core::constructSA_from_typeBstar (const StringIterator_type T, SAIterator_type SA, pos_type *bucket_A, pos_type *bucket_B, pos_type n, pos_type m, alphabetsize_type alphabetsize)
 
template<typename StringIterator_type , typename SAIterator_type , typename pos_type , typename alphabetsize_type >
SAIterator_type divsufsortxx::core::constructBWT_from_typeBstar (const StringIterator_type T, SAIterator_type SA, pos_type *bucket_A, pos_type *bucket_B, pos_type n, pos_type m, alphabetsize_type alphabetsize)
 
template<typename StringIterator_type , typename SAIterator_type , typename alphabetsize_type >
int divsufsortxx::constructSA (const StringIterator_type T, const StringIterator_type T_last, SAIterator_type SA, SAIterator_type SA_last, alphabetsize_type alphabetsize=256)
 
template<typename StringIterator_type , typename SAIterator_type , typename alphabetsize_type >
int divsufsortxx::constructSA (const StringIterator_type T, SAIterator_type SA, typename std::iterator_traits< SAIterator_type >::value_type n, alphabetsize_type alphabetsize=256)
 
template<typename StringIterator1_type , typename StringIterator2_type , typename SAIterator_type , typename alphabetsize_type >
std::iterator_traits
< SAIterator_type >
::value_type 
divsufsortxx::constructBWT (const StringIterator1_type T, const StringIterator1_type T_last, StringIterator2_type U, StringIterator2_type U_last, SAIterator_type SA, SAIterator_type SA_last, alphabetsize_type alphabetsize=256)
 
template<typename pos_type , typename StringIterator1_type , typename StringIterator2_type , typename alphabetsize_type >
pos_type divsufsortxx::constructBWT (const StringIterator1_type T, const StringIterator1_type T_last, StringIterator2_type U, StringIterator2_type U_last, alphabetsize_type alphabetsize=256)
 
template<typename pos_type , typename StringIterator_type , typename alphabetsize_type >
pos_type divsufsortxx::constructBWT (StringIterator_type T, StringIterator_type T_last, alphabetsize_type alphabetsize=256)
 
template<typename StringIterator1_type , typename StringIterator2_type , typename SAIterator_type , typename alphabetsize_type >
std::iterator_traits
< SAIterator_type >
::value_type 
divsufsortxx::constructBWT (const StringIterator1_type T, StringIterator2_type U, SAIterator_type SA, typename std::iterator_traits< SAIterator_type >::value_type n, alphabetsize_type alphabetsize=256)
 
template<typename pos_type , typename StringIterator1_type , typename StringIterator2_type , typename alphabetsize_type >
pos_type divsufsortxx::constructBWT (const StringIterator1_type T, StringIterator2_type U, pos_type n, alphabetsize_type alphabetsize=256)
 
template<typename pos_type , typename StringIterator_type , typename alphabetsize_type >
pos_type divsufsortxx::constructBWT (StringIterator_type T, pos_type n, alphabetsize_type alphabetsize=256)
 

Macro Definition Documentation

#define BUCKET_A (   c0)    bucket_A[(c0)]

Definition at line 1107 of file divsufsortxx.h.

#define BUCKET_B (   c0,
  c1 
)    (bucket_B[((alphabetsize_type)(c1)) * alphabetsize + (alphabetsize_type)(c0)])

Definition at line 1108 of file divsufsortxx.h.

#define BUCKET_BSTAR (   c0,
  c1 
)    (bucket_B[((alphabetsize_type)(c0)) * alphabetsize + (alphabetsize_type)(c1)])

Definition at line 1109 of file divsufsortxx.h.

#define GETIDX (   a)    ((0 <= (a)) ? (a) : (~(a)))
#define MERGE_CHECK (   a)
Value:
{\
if((0 <= *(a)) &&\
(compare(T, PA + GETIDX(*((a) - 1)), PA + *(a), depth) == 0)) {\
*(a) = ~*(a);\
}\
}
#define STACK_POP3 (   _a,
  _b,
  _c 
)
Value:
{\
if(stack.empty()) { return; }\
stackinfo_type tempinfo = stack.top();\
(_a) = tempinfo.m_a, (_b) = tempinfo.m_b, (_c) = tempinfo.m_c;\
stack.pop();\
}

Definition at line 277 of file divsufsortxx.h.

#define STACK_POP4 (   _a,
  _b,
  _c,
  _d 
)
Value:
{\
if(stack.empty()) { return; }\
stackinfo_type tempinfo = stack.top();\
(_a) = tempinfo.m_a, (_b) = tempinfo.m_b, (_c) = tempinfo.m_c, (_d) = tempinfo.m_d;\
stack.pop();\
}

Definition at line 284 of file divsufsortxx.h.

#define STACK_PUSH3 (   _a,
  _b,
  _c 
)    stack.push(stackinfo_type((_a), (_b), (_c)))

Definition at line 291 of file divsufsortxx.h.

#define STACK_PUSH4 (   _a,
  _b,
  _c,
  _d 
)    stack.push(stackinfo_type((_a), (_b), (_c), (_d)))

Definition at line 293 of file divsufsortxx.h.

#define UPDATE_BUDGET (   n)
Value:
{\
budget -= (n);\
if(budget <= 0) {\
budget += size;\
if(--chance == 0) { break; }\
}\
}