Top Description Inners Fields Constructors Methods
io.netty5.handler.codec.compression

pack-priv final Class Bzip2DivSufSort

extends Object
Class Inheritance
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 and Inner Type Summary

Modifier and TypeClass and Description
private static class
Bzip2DivSufSort.PartitionResult

private static class
Bzip2DivSufSort.StackEntry

private static class
Bzip2DivSufSort.TRBudget

Field Summary

Modifier and TypeField and Description
private static final int
BUCKET_A_SIZE

private static final int
BUCKET_B_SIZE

private static final int
INSERTIONSORT_THRESHOLD

private static final int[]
LOG_2_TABLE

private final int
n

private final int[]
SA

private static final int
SS_BLOCKSIZE

private static final int
STACK_SIZE

private final byte[]
T

Constructor Summary

AccessConstructor and Description
pack-priv
Bzip2DivSufSort(final byte[]
The input array
block, final int[]
The output array
bwtBlock, final int
The length of the input data
blockLength)

Method Summary

Modifier and TypeMethod and Description
private static int
BUCKET_B(final int c0, final int c1)

private static int
BUCKET_BSTAR(final int c0, final int c1)

public int

Returns:

the index of the first character of the input array within the output array
bwt()

Performs a Burrows Wheeler Transform on the input array.

private int
constructBWT(final int[] bucketA, final int[] bucketB)

private static int
getIDX(final int a)

private void
lsIntroSort(final int isa, final int isaD, final int isaN, int first, int last)

private void
lsSort(final int isa, final int n, final int depth)

private void
lsUpdateGroup(final int isa, final int first, final int last)

private int
sortTypeBstar(final int[] bucketA, final int[] bucketB)

private static void
ssBlockSwap(final int[] array1, final int first1, final int[] array2, final int first2, final int size)

private int
ssCompare(final int p1, final int p2, final 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(final int n)

private int
ssMedian3(final int td, final int pa, int v1, int v2, int v3)

private int
ssMedian5(final int td, final int pa, int v1, int v2, int v3, int v4, int v5)

private void
ssMerge(final int pa, int first, int middle, int last, int[] buf, final int bufoffset, final int bufsize, final int depth)

private void
ssMergeBackward(final int pa, int[] buf, final int bufoffset, final int first, final int middle, final int last, final int depth)

private void
ssMergeCheckEqual(final int pa, final int depth, final int a)

private void
ssMergeForward(final int pa, int[] buf, final int bufoffset, final int first, final int middle, final int last, final int depth)

private void
ssMultiKeyIntroSort(final int pa, int first, int last, int depth)

private int
ssPivot(final int td, final int pa, final int first, final int last)

private int
ssSubstringPartition(final int pa, final int first, final int last, final int depth)

private void
subStringSort(final int pa, int first, final int last, final int[] buf, final int bufoffset, final int bufsize, final int depth, final boolean lastsuffix, final int size)

private static void
swapElements(final int[] array1, final int idx1, final int[] array2, final int idx2)

private void
trCopy(final int isa, final int isaN, final int first, final int a, final int b, final int last, final int depth)

private void
trFixdown(final int isa, final int isaD, final int isaN, final int sa, int i, final int size)

private int
trGetC(final int isa, final int isaD, final int isaN, final int p)

private void
trHeapSort(final int isa, final int isaD, final int isaN, final int sa, final int size)

private void
trInsertionSort(final int isa, final int isaD, final int isaN, int first, int last)

private void
trIntroSort(final int isa, int isaD, int isaN, int first, int last, final Bzip2DivSufSort.TRBudget budget, final int size)

private static int
trLog(int n)

private int
trMedian3(final int isa, final int isaD, final int isaN, int v1, int v2, int v3)

private int
trMedian5(final int isa, final int isaD, final int isaN, int v1, int v2, int v3, int v4, int v5)

private Bzip2DivSufSort.PartitionResult
trPartition(final int isa, final int isaD, final int isaN, int first, int last, final int v)

private int
trPivot(final int isa, final int isaD, final int isaN, final int first, final int last)

private void
trSort(final int isa, final int n, final int depth)

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

BUCKET_A_SIZEback to summary
private static final int BUCKET_A_SIZE
BUCKET_B_SIZEback to summary
private static final int BUCKET_B_SIZE
INSERTIONSORT_THRESHOLDback to summary
private static final int INSERTIONSORT_THRESHOLD
LOG_2_TABLEback to summary
private static final int[] LOG_2_TABLE
nback to summary
private final int n
SAback to summary
private final int[] SA
SS_BLOCKSIZEback to summary
private static final int SS_BLOCKSIZE
STACK_SIZEback to summary
private static final int STACK_SIZE
Tback to summary
private final byte[] T

Constructor Detail

Bzip2DivSufSortback to summary
pack-priv Bzip2DivSufSort(final byte[] block, final int[] bwtBlock, final int blockLength)
Parameters
block:byte[]

The input array

bwtBlock:int[]

The output array

blockLength:int

The length of the input data

Method Detail

BUCKET_Bback to summary
private static int BUCKET_B(final int c0, final int c1)
BUCKET_BSTARback to summary
private static int BUCKET_BSTAR(final int c0, final int c1)
bwtback to summary
public int bwt()

Performs a Burrows Wheeler Transform on the input array.

Returns:int

the index of the first character of the input array within the output array

constructBWTback to summary
private int constructBWT(final int[] bucketA, final int[] bucketB)
getIDXback to summary
private static int getIDX(final int a)
lsIntroSortback to summary
private void lsIntroSort(final int isa, final int isaD, final int isaN, int first, int last)
lsSortback to summary
private void lsSort(final int isa, final int n, final int depth)
lsUpdateGroupback to summary
private void lsUpdateGroup(final int isa, final int first, final int last)
sortTypeBstarback to summary
private int sortTypeBstar(final int[] bucketA, final int[] bucketB)
ssBlockSwapback to summary
private static void ssBlockSwap(final int[] array1, final int first1, final int[] array2, final int first2, final int size)
ssCompareback to summary
private int ssCompare(final int p1, final int p2, final int depth)
ssCompareLastback to summary
private int ssCompareLast(int pa, int p1, int p2, int depth, int size)
ssFixdownback to summary
private void ssFixdown(int td, int pa, int sa, int i, int size)
ssHeapSortback to summary
private void ssHeapSort(int td, int pa, int sa, int size)
ssInsertionSortback to summary
private void ssInsertionSort(int pa, int first, int last, int depth)
ssLogback to summary
private static int ssLog(final int n)
ssMedian3back to summary
private int ssMedian3(final int td, final int pa, int v1, int v2, int v3)
ssMedian5back to summary
private int ssMedian5(final int td, final int pa, int v1, int v2, int v3, int v4, int v5)
ssMergeback to summary
private void ssMerge(final int pa, int first, int middle, int last, int[] buf, final int bufoffset, final int bufsize, final int depth)
ssMergeBackwardback to summary
private void ssMergeBackward(final int pa, int[] buf, final int bufoffset, final int first, final int middle, final int last, final int depth)
ssMergeCheckEqualback to summary
private void ssMergeCheckEqual(final int pa, final int depth, final int a)
ssMergeForwardback to summary
private void ssMergeForward(final int pa, int[] buf, final int bufoffset, final int first, final int middle, final int last, final int depth)
ssMultiKeyIntroSortback to summary
private void ssMultiKeyIntroSort(final int pa, int first, int last, int depth)
ssPivotback to summary
private int ssPivot(final int td, final int pa, final int first, final int last)
ssSubstringPartitionback to summary
private int ssSubstringPartition(final int pa, final int first, final int last, final int depth)
subStringSortback to summary
private void subStringSort(final int pa, int first, final int last, final int[] buf, final int bufoffset, final int bufsize, final int depth, final boolean lastsuffix, final int size)
swapElementsback to summary
private static void swapElements(final int[] array1, final int idx1, final int[] array2, final int idx2)
trCopyback to summary
private void trCopy(final int isa, final int isaN, final int first, final int a, final int b, final int last, final int depth)
trFixdownback to summary
private void trFixdown(final int isa, final int isaD, final int isaN, final int sa, int i, final int size)
trGetCback to summary
private int trGetC(final int isa, final int isaD, final int isaN, final int p)
trHeapSortback to summary
private void trHeapSort(final int isa, final int isaD, final int isaN, final int sa, final int size)
trInsertionSortback to summary
private void trInsertionSort(final int isa, final int isaD, final int isaN, int first, int last)
trIntroSortback to summary
private void trIntroSort(final int isa, int isaD, int isaN, int first, int last, final Bzip2DivSufSort.TRBudget budget, final int size)
trLogback to summary
private static int trLog(int n)
trMedian3back to summary
private int trMedian3(final int isa, final int isaD, final int isaN, int v1, int v2, int v3)
trMedian5back to summary
private int trMedian5(final int isa, final int isaD, final int isaN, int v1, int v2, int v3, int v4, int v5)
trPartitionback to summary
private Bzip2DivSufSort.PartitionResult trPartition(final int isa, final int isaD, final int isaN, int first, int last, final int v)
trPivotback to summary
private int trPivot(final int isa, final int isaD, final int isaN, final int first, final int last)
trSortback to summary
private void trSort(final int isa, final int n, final int depth)
io.netty5.handler.codec.compression back to summary

private Class Bzip2DivSufSort.PartitionResult

extends Object
Class Inheritance
  • java.lang.Object
  • io.netty5.handler.codec.compression.Bzip2DivSufSort.PartitionResult

Field Summary

Modifier and TypeField and Description
pack-priv final int
first

pack-priv final int
last

Constructor Summary

AccessConstructor and Description
pack-priv
PartitionResult(final int first, final int last)

Method Summary

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

firstback to summary
pack-priv final int first
lastback to summary
pack-priv final int last

Constructor Detail

PartitionResultback to summary
pack-priv PartitionResult(final int first, final int last)
io.netty5.handler.codec.compression back to summary

private Class Bzip2DivSufSort.StackEntry

extends Object
Class Inheritance
  • java.lang.Object
  • io.netty5.handler.codec.compression.Bzip2DivSufSort.StackEntry

Field Summary

Modifier and TypeField and Description
pack-priv final int
a

pack-priv final int
b

pack-priv final int
c

pack-priv final int
d

Constructor Summary

AccessConstructor and Description
pack-priv
StackEntry(final int a, final int b, final int c, final int d)

Method Summary

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

aback to summary
pack-priv final int a
bback to summary
pack-priv final int b
cback to summary
pack-priv final int c
dback to summary
pack-priv final int d

Constructor Detail

StackEntryback to summary
pack-priv StackEntry(final int a, final int b, final int c, final int d)
io.netty5.handler.codec.compression back to summary

private Class Bzip2DivSufSort.TRBudget

extends Object
Class Inheritance

Field Summary

Modifier and TypeField and Description
pack-priv int
budget

pack-priv int
chance

Constructor Summary

AccessConstructor and Description
pack-priv
TRBudget(final int budget, final int chance)

Method Summary

Modifier and TypeMethod and Description
pack-priv boolean
update(final int size, final int n)

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

budgetback to summary
pack-priv int budget
chanceback to summary
pack-priv int chance

Constructor Detail

TRBudgetback to summary
pack-priv TRBudget(final int budget, final int chance)

Method Detail

updateback to summary
pack-priv boolean update(final int size, final int n)