final class Bzip2HuffmanAllocator
extends java.lang.Object
Modifier | Constructor and Description |
---|---|
private |
Bzip2HuffmanAllocator() |
Modifier and Type | Method and Description |
---|---|
(package private) static void |
allocateHuffmanCodeLengths(int[] array,
int maximumLength)
Allocates Canonical Huffman code lengths in place based on a sorted frequency array.
|
private static void |
allocateNodeLengths(int[] array)
A final allocation pass with no code length limit.
|
private static void |
allocateNodeLengthsWithRelocation(int[] array,
int nodesToMove,
int insertDepth)
A final allocation pass that relocates nodes in order to achieve a maximum code length limit.
|
private static int |
findNodesToRelocate(int[] array,
int maximumLength)
Finds the number of nodes to relocate in order to achieve a given code length limit.
|
private static int |
first(int[] array,
int i,
int nodesToMove) |
private static void |
setExtendedParentPointers(int[] array)
Fills the code array with extended parent pointers.
|
private static int first(int[] array, int i, int nodesToMove)
array
- The code length arrayi
- The input positionnodesToMove
- The number of internal nodes to be relocatedk
such that nodesToMove <= k <= i
and
i <= (array[k] % array.length)
private static void setExtendedParentPointers(int[] array)
array
- The code length arrayprivate static int findNodesToRelocate(int[] array, int maximumLength)
array
- The code length arraymaximumLength
- The maximum bit length for the generated codesprivate static void allocateNodeLengths(int[] array)
array
- The code length arrayprivate static void allocateNodeLengthsWithRelocation(int[] array, int nodesToMove, int insertDepth)
array
- The code length arraynodesToMove
- The number of internal nodes to be relocatedinsertDepth
- The depth at which to insert relocated nodesstatic void allocateHuffmanCodeLengths(int[] array, int maximumLength)
array
- On input, a sorted array of symbol frequencies; On output, an array of Canonical
Huffman code lengthsmaximumLength
- The maximum code length. Must be at least ceil(log2(array.length))