BGI/soap_src/soap_builder/QSufSort.h

   1 /* QSufSort.h
   2
   3    Header file for QSufSort.c
   4
   5    This file contains an implementation of the algorithm presented in "Faster
   6    Suffix Sorting" by N. Jesper Larsson (jesper@cs.lth.se) and Kunihiko
   7    Sadakane (sada@is.s.u-tokyo.ac.jp).
   8
   9    This software may be used freely for any purpose. However, when distributed,
  10    the original source must be clearly stated, and, when the source code is
  11    distributed, the copyright notice must be retained and any alterations in
  12    the code must be clearly marked. No warranty is given regarding the quality
  13    of this software.
  14
  15    Modified by Wong Chi-Kwong, 2004
  16
  17    Changes summary:     - Used long variable and function names
  18                                         - Removed global variables
  19                                         - Replace pointer references with array references
  20                                         - Used insertion sort in place of selection sort and increased insertion sort threshold
  21                                         - Reconstructing suffix array from inverse becomes an option
  22                                         - Add handling where end-of-text symbol is not necessary < all characters
  23                                         - Removed codes for supporting alphabet size > number of characters
  24
  25   No warrenty is given regarding the quality of the modifications.
  26
  27 */
  28
  29 #ifndef __QSUFSORT_H__
  30 #define __QSUFSORT_H__
  31
  32 #include "TypeNLimit.h"
  33
  34 #define KEY(V, I, p, h)                                 ( V[ I[p] + h ] )
  35 #define INSERT_SORT_NUM_ITEM    16
  36
  37 void QSufSortSuffixSort(int* __restrict V, int* __restrict I, const int numChar, const int largestInputSymbol,
  38                                                 const int smallestInputSymbol, const int skipTransform);
  39 void QSufSortGenerateSaFromInverse(const int *V, int* __restrict I, const int numChar);
  40
  41
  42 #endif