com.sun.j3d.utils.geometry.compression
Class HuffmanNode

java.lang.Object
  extended by com.sun.j3d.utils.geometry.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
(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
(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
HuffmanNode()
           
HuffmanNode(int length, int shift, boolean absolute)
           
 
Method Summary
(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


Copyright 1996-2008 Sun Microsystems, Inc. All Rights Reserved. Use is subject to license terms.