Class Bzip2DivSufSort
- java.lang.Object
-
- io.netty.handler.codec.compression.Bzip2DivSufSort
-
final class Bzip2DivSufSort extends java.lang.ObjectDivSufSort 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 classBzip2DivSufSort.PartitionResultprivate static classBzip2DivSufSort.StackEntryprivate static classBzip2DivSufSort.TRBudget
-
Field Summary
Fields Modifier and Type Field Description private static intBUCKET_A_SIZEprivate static intBUCKET_B_SIZEprivate static intINSERTIONSORT_THRESHOLDprivate static int[]LOG_2_TABLEprivate intnprivate int[]SAprivate static intSS_BLOCKSIZEprivate static intSTACK_SIZEprivate 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 intBUCKET_B(int c0, int c1)private static intBUCKET_BSTAR(int c0, int c1)intbwt()Performs a Burrows Wheeler Transform on the input array.private intconstructBWT(int[] bucketA, int[] bucketB)private static intgetIDX(int a)private voidlsIntroSort(int isa, int isaD, int isaN, int first, int last)private voidlsSort(int isa, int n, int depth)private voidlsUpdateGroup(int isa, int first, int last)private intsortTypeBstar(int[] bucketA, int[] bucketB)private static voidssBlockSwap(int[] array1, int first1, int[] array2, int first2, int size)private intssCompare(int p1, int p2, int depth)private intssCompareLast(int pa, int p1, int p2, int depth, int size)private voidssFixdown(int td, int pa, int sa, int i, int size)private voidssHeapSort(int td, int pa, int sa, int size)private voidssInsertionSort(int pa, int first, int last, int depth)private static intssLog(int n)private intssMedian3(int td, int pa, int v1, int v2, int v3)private intssMedian5(int td, int pa, int v1, int v2, int v3, int v4, int v5)private voidssMerge(int pa, int first, int middle, int last, int[] buf, int bufoffset, int bufsize, int depth)private voidssMergeBackward(int pa, int[] buf, int bufoffset, int first, int middle, int last, int depth)private voidssMergeCheckEqual(int pa, int depth, int a)private voidssMergeForward(int pa, int[] buf, int bufoffset, int first, int middle, int last, int depth)private voidssMultiKeyIntroSort(int pa, int first, int last, int depth)private intssPivot(int td, int pa, int first, int last)private intssSubstringPartition(int pa, int first, int last, int depth)private voidsubStringSort(int pa, int first, int last, int[] buf, int bufoffset, int bufsize, int depth, boolean lastsuffix, int size)private static voidswapElements(int[] array1, int idx1, int[] array2, int idx2)private voidtrCopy(int isa, int isaN, int first, int a, int b, int last, int depth)private voidtrFixdown(int isa, int isaD, int isaN, int sa, int i, int size)private inttrGetC(int isa, int isaD, int isaN, int p)private voidtrHeapSort(int isa, int isaD, int isaN, int sa, int size)private voidtrInsertionSort(int isa, int isaD, int isaN, int first, int last)private voidtrIntroSort(int isa, int isaD, int isaN, int first, int last, Bzip2DivSufSort.TRBudget budget, int size)private static inttrLog(int n)private inttrMedian3(int isa, int isaD, int isaN, int v1, int v2, int v3)private inttrMedian5(int isa, int isaD, int isaN, int v1, int v2, int v3, int v4, int v5)private Bzip2DivSufSort.PartitionResulttrPartition(int isa, int isaD, int isaN, int first, int last, int v)private inttrPivot(int isa, int isaD, int isaN, int first, int last)private voidtrSort(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
-
-