0
|
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 <stdint.h>
|
|
33
|
|
34 #define KEY(V, I, p, h) ( V[ I[p] + h ] )
|
|
35 #define INSERT_SORT_NUM_ITEM 16
|
|
36
|
|
37 typedef int64_t qsint_t;
|
|
38 #define QSINT_MAX INT64_MAX
|
|
39
|
|
40 void QSufSortSuffixSort(qsint_t* __restrict V, qsint_t* __restrict I, const qsint_t numChar, const qsint_t largestInputSymbol,
|
|
41 const qsint_t smallestInputSymbol, const int skipTransform);
|
|
42 void QSufSortGenerateSaFromInverse(const qsint_t *V, qsint_t* __restrict I, const qsint_t numChar);
|
|
43
|
|
44
|
|
45 #endif
|