Class Bzip2DivSufSort
- java.lang.Object
-
- io.netty.handler.codec.compression.Bzip2DivSufSort
-
final class Bzip2DivSufSort extends java.lang.Object
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.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description private static class
Bzip2DivSufSort.PartitionResult
private static class
Bzip2DivSufSort.StackEntry
private static class
Bzip2DivSufSort.TRBudget
-
Field Summary
Fields Modifier and Type Field Description private static int
BUCKET_A_SIZE
private static int
BUCKET_B_SIZE
private static int
INSERTIONSORT_THRESHOLD
private static int[]
LOG_2_TABLE
private int
n
private int[]
SA
private static int
SS_BLOCKSIZE
private static int
STACK_SIZE
private byte[]
T
-
Constructor Summary
Constructors Constructor Description Bzip2DivSufSort(byte[] block, int[] bwtBlock, int blockLength)
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description private 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 Detail
-
STACK_SIZE
private static final int STACK_SIZE
- See Also:
- Constant Field Values
-
BUCKET_A_SIZE
private static final int BUCKET_A_SIZE
- See Also:
- Constant Field Values
-
BUCKET_B_SIZE
private static final int BUCKET_B_SIZE
- See Also:
- Constant Field Values
-
SS_BLOCKSIZE
private static final int SS_BLOCKSIZE
- See Also:
- Constant Field Values
-
INSERTIONSORT_THRESHOLD
private static final int INSERTIONSORT_THRESHOLD
- See Also:
- Constant Field Values
-
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
-
-
Method Detail
-
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
-
-