1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
|
#ifndef ALGORITHMS_SORTING_LIGHTWEIGHT_SUFFIX_ARRAY_H_
#define ALGORITHMS_SORTING_LIGHTWEIGHT_SUFFIX_ARRAY_H_
#include <algorithm>
#include "qsufsort.hpp"
#include "MultikeyQuicksort.hpp"
#include "DifferenceCovers.hpp"
#include "../../../pbdata/Types.h"
/*
* a - b potentially may not fit into a signed type. Use some logic
* to get around that.
*/
UInt DiffMod(UInt a, UInt b, UInt d);
void BuildDiffCoverReverseLookup(UInt diffCover[], UInt diffCoverLength,
UInt reverseDiffCover[] // of size diffCoverSize
);
UInt DiffCoverFindH(UInt diffCover[], UInt diffCoverLength, UInt diffCoverSize, UInt textSize);
class DiffCoverMu {
public:
UInt *diffCoverReverseLookup;
UInt diffCoverLength;
UInt diffCoverSize;
UInt textSize;
UInt h;
UInt *diffCover;
UInt compute(UInt i, UInt j);
UInt operator()(const UInt k);
DiffCoverMu();
~DiffCoverMu();
void Initialize(UInt diffCoverP[], UInt diffCoverLengthP, UInt diffCoverSizeP, UInt textSizeP);
};
void BuildDiffCoverLookup(UInt diffCover[], UInt diffCoverLength, UInt v, UInt diffCoverLookup[]);
class DiffCoverDelta {
public:
UInt *diffCoverLookup;
UInt diffCoverSize;
void Initialize(UInt diffCoverP[], UInt diffCoverLengthP, UInt diffCoverSizeP);
UInt operator()(UInt i, UInt j);
~DiffCoverDelta();
};
UInt NCompareSuffices(unsigned char text[], UInt a, UInt b, UInt n);
UInt ComputeDSetSize(UInt diffCover, UInt diffCoverLength, UInt diffCoverSize, UInt textSize);
void ComputeSufVNaming(UInt diffCover[], UInt diffCoverLength, UInt diffCoverN, UInt textSize, UInt lexNaming[],
DiffCoverMu &mu,
UInt sufVNaming[]);
UInt IndexToDiffCoverIndex(UInt index, UInt diffCoverlookup[], UInt diffCoverSize, UInt diffCoverLength );
void DiffCoverComputeLOrder(UInt sufVNaming[], UInt sufVNamingLength, UInt maxVNaming, UInt textLength, DiffCoverMu &mu, UInt lOrder[]);
/*
* Build the lex naming of the v-ordered suffices.
*
* Input: textVOrder - the v-ordering of a subset of the text.
* textSize - the size of the v-order set.
* diffCoverLength - length of diffCover
* diffCoverSize - the size of the diff cover.
* Output: lexNaming: the lex-naming of the v-order suffices. The
* names are implemented as unsigned integers.
* Returns: the largest value of the lex-ordering.
*/
UInt DiffCoverBuildLexNaming( unsigned char text[], UInt textSize,
UInt textVOrder[],
UInt dSetSize, UInt diffCoverLength, UInt diffCoverSize,
UInt diffCoverLookup[],
UInt lexNaming[]);
class DiffCoverCompareSuffices {
public:
UInt *lOrder;
DiffCoverDelta *delta;
UInt diffCoverSize;
UInt diffCoverLength;
UInt *diffCoverReverseLookup;
int operator()(UInt a, UInt b);
};
bool LightweightSuffixSort(unsigned char text[], UInt textLength, UInt *index, int diffCoverSize);
#endif
|
