com.sun.j3d.utils.compression

Class HuffmanNode

java.lang.Object

com.sun.j3d.utils.compression.HuffmanNode

 class HuffmanNode
extends java.lang.Object

Instances of this class are used as the nodes of binary trees representing mappings of tags to compression stream elements. Tags are descriptors inserted into the compression command stream that specify the encoding of immediately succeeding data elements.

The tag assignments in such a tree are computed from the paths taken from the root to the leaf nodes. Each leaf node represents the particular way one or more compression stream elements wound up being encoded with respect to various combinations of data lengths, shifts, and absolute/relative status.

Huffman's algorithm for constructing binary trees with minimal weighted path lengths can be used to optimize the bit lengths of the tags with respect to the frequency of occurrence of their associated data encodings in the compression stream. The weighted path length is the sum of the frequencies of all the leaf nodes times their path lengths to the root of the tree.

The length of the longest tag determines the size of the table mapping tags to data representations. The geometry compression specification limits the size of the table to 64 entries, so tags cannot be longer than 6 bits. The depth of the tree is reduced through a process of increasing the data lengths of less frequently occuring nodes so they can be merged with other more frequent nodes.

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
(package private) static class	HuffmanNode.FrequencyComparator Sorts nodes in ascending order by frequency.
(package private) static class	HuffmanNode.TagLengthComparator Sorts nodes in descending order by tag bit length.

Field Summary

Fields

Modifier and Type	Field and Description
(package private) boolean	absolute
private HuffmanNode	child0
private HuffmanNode	child1
private boolean	cleared
(package private) int	dataLength
private int	frequency
(package private) static HuffmanNode.FrequencyComparator	frequencyComparator
private boolean	merged
private HuffmanNode	mergeNode
(package private) int	shift
(package private) int	tag
(package private) int	tagLength
(package private) static HuffmanNode.TagLengthComparator	tagLengthComparator
private boolean	unmergeable

Constructor Summary

Constructors

Constructor and Description
HuffmanNode()
HuffmanNode(int length, int shift, boolean absolute)

Method Summary

Methods

Modifier and Type	Method and Description
(package private) void	addChildren(HuffmanNode child0, HuffmanNode child1)
(package private) void	addCount()
(package private) void	clear()
(package private) boolean	cleared()
(package private) void	collectLeaves(int tag, int tagLength, java.util.Collection collection)
(package private) HuffmanNode	getMergeNode()
(package private) boolean	hasCount()
(package private) int	incrementLength()
(package private) boolean	merged()
(package private) boolean	mergeInto(HuffmanNode node)
(package private) void	set(int length, int shift, boolean absolute)
(package private) void	setUnmergeable()
(package private) boolean	tokenEquals(HuffmanNode node)
java.lang.String	toString()
(package private) boolean	unmergeable()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

tag

int tag

tagLength

int tagLength

shift

int shift

dataLength

int dataLength

absolute

boolean absolute

frequency

private int frequency

child0

private HuffmanNode child0

child1

private HuffmanNode child1

mergeNode

private HuffmanNode mergeNode

merged

private boolean merged

unmergeable

private boolean unmergeable

cleared

private boolean cleared

frequencyComparator

static HuffmanNode.FrequencyComparator frequencyComparator

tagLengthComparator

static HuffmanNode.TagLengthComparator tagLengthComparator

Constructor Detail

HuffmanNode

HuffmanNode()

HuffmanNode

HuffmanNode(int length,
           int shift,
           boolean absolute)

Method Detail

clear

void clear()

set

final void set(int length,
       int shift,
       boolean absolute)

cleared

final boolean cleared()

addCount

final void addCount()

hasCount

final boolean hasCount()

tokenEquals

final boolean tokenEquals(HuffmanNode node)

addChildren

void addChildren(HuffmanNode child0,
               HuffmanNode child1)

collectLeaves

void collectLeaves(int tag,
                 int tagLength,
                 java.util.Collection collection)

mergeInto

boolean mergeInto(HuffmanNode node)

incrementLength

int incrementLength()

merged

final boolean merged()

getMergeNode

final HuffmanNode getMergeNode()

setUnmergeable

void setUnmergeable()

unmergeable

final boolean unmergeable()

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object