Class Bzip2DivSufSort
java.lang.Object
io.netty.handler.codec.compression.Bzip2DivSufSort
DivSufSort suffix array generator.
Based on libdivsufsort 1.2.3 patched to support Bzip2.
This is a simple conversion of the original C with two minor bugfixes applied (see "BUGFIX" comments within the class). Documentation within the class is largely absent.
Based on libdivsufsort 1.2.3 patched to support Bzip2.
This is a simple conversion of the original C with two minor bugfixes applied (see "BUGFIX" comments within the class). Documentation within the class is largely absent.
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprivate static class
private static class
private static class
-
Field Summary
FieldsModifier and TypeFieldDescriptionprivate static final int
private static final int
private static final int
private static final int[]
private final int
private final int[]
private static final int
private static final int
private final byte[]
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionprivate static int
BUCKET_B
(int c0, int c1) private static int
BUCKET_BSTAR
(int c0, int c1) int
bwt()
Performs a Burrows Wheeler Transform on the input array.private int
constructBWT
(int[] bucketA, int[] bucketB) private static int
getIDX
(int a) private void
lsIntroSort
(int isa, int isaD, int isaN, int first, int last) private void
lsSort
(int isa, int n, int depth) private void
lsUpdateGroup
(int isa, int first, int last) private int
sortTypeBstar
(int[] bucketA, int[] bucketB) private static void
ssBlockSwap
(int[] array1, int first1, int[] array2, int first2, int size) private int
ssCompare
(int p1, int p2, int depth) private int
ssCompareLast
(int pa, int p1, int p2, int depth, int size) private void
ssFixdown
(int td, int pa, int sa, int i, int size) private void
ssHeapSort
(int td, int pa, int sa, int size) private void
ssInsertionSort
(int pa, int first, int last, int depth) private static int
ssLog
(int n) private int
ssMedian3
(int td, int pa, int v1, int v2, int v3) private int
ssMedian5
(int td, int pa, int v1, int v2, int v3, int v4, int v5) private void
ssMerge
(int pa, int first, int middle, int last, int[] buf, int bufoffset, int bufsize, int depth) private void
ssMergeBackward
(int pa, int[] buf, int bufoffset, int first, int middle, int last, int depth) private void
ssMergeCheckEqual
(int pa, int depth, int a) private void
ssMergeForward
(int pa, int[] buf, int bufoffset, int first, int middle, int last, int depth) private void
ssMultiKeyIntroSort
(int pa, int first, int last, int depth) private int
ssPivot
(int td, int pa, int first, int last) private int
ssSubstringPartition
(int pa, int first, int last, int depth) private void
subStringSort
(int pa, int first, int last, int[] buf, int bufoffset, int bufsize, int depth, boolean lastsuffix, int size) private static void
swapElements
(int[] array1, int idx1, int[] array2, int idx2) private void
trCopy
(int isa, int isaN, int first, int a, int b, int last, int depth) private void
trFixdown
(int isa, int isaD, int isaN, int sa, int i, int size) private int
trGetC
(int isa, int isaD, int isaN, int p) private void
trHeapSort
(int isa, int isaD, int isaN, int sa, int size) private void
trInsertionSort
(int isa, int isaD, int isaN, int first, int last) private void
trIntroSort
(int isa, int isaD, int isaN, int first, int last, Bzip2DivSufSort.TRBudget budget, int size) private static int
trLog
(int n) private int
trMedian3
(int isa, int isaD, int isaN, int v1, int v2, int v3) private int
trMedian5
(int isa, int isaD, int isaN, int v1, int v2, int v3, int v4, int v5) private Bzip2DivSufSort.PartitionResult
trPartition
(int isa, int isaD, int isaN, int first, int last, int v) private int
trPivot
(int isa, int isaD, int isaN, int first, int last) private void
trSort
(int isa, int n, int depth)
-
Field Details
-
STACK_SIZE
private static final int STACK_SIZE- See Also:
-
BUCKET_A_SIZE
private static final int BUCKET_A_SIZE- See Also:
-
BUCKET_B_SIZE
private static final int BUCKET_B_SIZE- See Also:
-
SS_BLOCKSIZE
private static final int SS_BLOCKSIZE- See Also:
-
INSERTIONSORT_THRESHOLD
private static final int INSERTIONSORT_THRESHOLD- See Also:
-
LOG_2_TABLE
private static final int[] LOG_2_TABLE -
SA
private final int[] SA -
T
private final byte[] T -
n
private final int n
-
-
Constructor Details
-
Bzip2DivSufSort
Bzip2DivSufSort(byte[] block, int[] bwtBlock, int blockLength) - Parameters:
block
- The input arraybwtBlock
- The output arrayblockLength
- The length of the input data
-
-
Method Details
-
swapElements
private static void swapElements(int[] array1, int idx1, int[] array2, int idx2) -
ssCompare
private int ssCompare(int p1, int p2, int depth) -
ssCompareLast
private int ssCompareLast(int pa, int p1, int p2, int depth, int size) -
ssInsertionSort
private void ssInsertionSort(int pa, int first, int last, int depth) -
ssFixdown
private void ssFixdown(int td, int pa, int sa, int i, int size) -
ssHeapSort
private void ssHeapSort(int td, int pa, int sa, int size) -
ssMedian3
private int ssMedian3(int td, int pa, int v1, int v2, int v3) -
ssMedian5
private int ssMedian5(int td, int pa, int v1, int v2, int v3, int v4, int v5) -
ssPivot
private int ssPivot(int td, int pa, int first, int last) -
ssLog
private static int ssLog(int n) -
ssSubstringPartition
private int ssSubstringPartition(int pa, int first, int last, int depth) -
ssMultiKeyIntroSort
private void ssMultiKeyIntroSort(int pa, int first, int last, int depth) -
ssBlockSwap
private static void ssBlockSwap(int[] array1, int first1, int[] array2, int first2, int size) -
ssMergeForward
private void ssMergeForward(int pa, int[] buf, int bufoffset, int first, int middle, int last, int depth) -
ssMergeBackward
private void ssMergeBackward(int pa, int[] buf, int bufoffset, int first, int middle, int last, int depth) -
getIDX
private static int getIDX(int a) -
ssMergeCheckEqual
private void ssMergeCheckEqual(int pa, int depth, int a) -
ssMerge
private void ssMerge(int pa, int first, int middle, int last, int[] buf, int bufoffset, int bufsize, int depth) -
subStringSort
private void subStringSort(int pa, int first, int last, int[] buf, int bufoffset, int bufsize, int depth, boolean lastsuffix, int size) -
trGetC
private int trGetC(int isa, int isaD, int isaN, int p) -
trFixdown
private void trFixdown(int isa, int isaD, int isaN, int sa, int i, int size) -
trHeapSort
private void trHeapSort(int isa, int isaD, int isaN, int sa, int size) -
trInsertionSort
private void trInsertionSort(int isa, int isaD, int isaN, int first, int last) -
trLog
private static int trLog(int n) -
trMedian3
private int trMedian3(int isa, int isaD, int isaN, int v1, int v2, int v3) -
trMedian5
private int trMedian5(int isa, int isaD, int isaN, int v1, int v2, int v3, int v4, int v5) -
trPivot
private int trPivot(int isa, int isaD, int isaN, int first, int last) -
lsUpdateGroup
private void lsUpdateGroup(int isa, int first, int last) -
lsIntroSort
private void lsIntroSort(int isa, int isaD, int isaN, int first, int last) -
lsSort
private void lsSort(int isa, int n, int depth) -
trPartition
private Bzip2DivSufSort.PartitionResult trPartition(int isa, int isaD, int isaN, int first, int last, int v) -
trCopy
private void trCopy(int isa, int isaN, int first, int a, int b, int last, int depth) -
trIntroSort
private void trIntroSort(int isa, int isaD, int isaN, int first, int last, Bzip2DivSufSort.TRBudget budget, int size) -
trSort
private void trSort(int isa, int n, int depth) -
BUCKET_B
private static int BUCKET_B(int c0, int c1) -
BUCKET_BSTAR
private static int BUCKET_BSTAR(int c0, int c1) -
sortTypeBstar
private int sortTypeBstar(int[] bucketA, int[] bucketB) -
constructBWT
private int constructBWT(int[] bucketA, int[] bucketB) -
bwt
public int bwt()Performs a Burrows Wheeler Transform on the input array.- Returns:
- the index of the first character of the input array within the output array
-