001: /*
002: * $RCSfile: HuffmanNode.java,v $
003: *
004: * Copyright (c) 2007 Sun Microsystems, Inc. All rights reserved.
005: *
006: * Redistribution and use in source and binary forms, with or without
007: * modification, are permitted provided that the following conditions
008: * are met:
009: *
010: * - Redistribution of source code must retain the above copyright
011: * notice, this list of conditions and the following disclaimer.
012: *
013: * - Redistribution in binary form must reproduce the above copyright
014: * notice, this list of conditions and the following disclaimer in
015: * the documentation and/or other materials provided with the
016: * distribution.
017: *
018: * Neither the name of Sun Microsystems, Inc. or the names of
019: * contributors may be used to endorse or promote products derived
020: * from this software without specific prior written permission.
021: *
022: * This software is provided "AS IS," without a warranty of any
023: * kind. ALL EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND
024: * WARRANTIES, INCLUDING ANY IMPLIED WARRANTY OF MERCHANTABILITY,
025: * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE HEREBY
026: * EXCLUDED. SUN MICROSYSTEMS, INC. ("SUN") AND ITS LICENSORS SHALL
027: * NOT BE LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF
028: * USING, MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS
029: * DERIVATIVES. IN NO EVENT WILL SUN OR ITS LICENSORS BE LIABLE FOR
030: * ANY LOST REVENUE, PROFIT OR DATA, OR FOR DIRECT, INDIRECT, SPECIAL,
031: * CONSEQUENTIAL, INCIDENTAL OR PUNITIVE DAMAGES, HOWEVER CAUSED AND
032: * REGARDLESS OF THE THEORY OF LIABILITY, ARISING OUT OF THE USE OF OR
033: * INABILITY TO USE THIS SOFTWARE, EVEN IF SUN HAS BEEN ADVISED OF THE
034: * POSSIBILITY OF SUCH DAMAGES.
035: *
036: * You acknowledge that this software is not designed, licensed or
037: * intended for use in the design, construction, operation or
038: * maintenance of any nuclear facility.
039: *
040: * $Revision: 1.3 $
041: * $Date: 2007/02/09 17:20:23 $
042: * $State: Exp $
043: */
044:
045: package com.sun.j3d.utils.geometry.compression;
046:
047: import java.util.Collection;
048: import java.util.Comparator;
049:
050: /**
051: * Instances of this class are used as the nodes of binary trees representing
052: * mappings of tags to compression stream elements. Tags are descriptors
053: * inserted into the compression command stream that specify the encoding of
054: * immediately succeeding data elements.<p>
055: *
056: * The tag assignments in such a tree are computed from the paths taken from
057: * the root to the leaf nodes. Each leaf node represents the particular way
058: * one or more compression stream elements wound up being encoded with respect
059: * to various combinations of data lengths, shifts, and absolute/relative
060: * status.<p>
061: *
062: * Huffman's algorithm for constructing binary trees with minimal weighted
063: * path lengths can be used to optimize the bit lengths of the tags with
064: * respect to the frequency of occurrence of their associated data encodings
065: * in the compression stream. The weighted path length is the sum of the
066: * frequencies of all the leaf nodes times their path lengths to the root of
067: * the tree.<p>
068: *
069: * The length of the longest tag determines the size of the table mapping tags
070: * to data representations. The geometry compression specification limits the
071: * size of the table to 64 entries, so tags cannot be longer than 6 bits. The
072: * depth of the tree is reduced through a process of increasing the data
073: * lengths of less frequently occuring nodes so they can be merged with other
074: * more frequent nodes.
075: */
076: class HuffmanNode {
077: int tag, tagLength;
078: int shift, dataLength;
079: boolean absolute;
080:
081: private int frequency;
082: private HuffmanNode child0, child1, mergeNode;
083: private boolean merged, unmergeable, cleared;
084:
085: void clear() {
086: tag = -1;
087: tagLength = -1;
088:
089: shift = -1;
090: dataLength = -1;
091: absolute = false;
092:
093: child0 = null;
094: child1 = null;
095: mergeNode = null;
096:
097: frequency = 0;
098: merged = false;
099: unmergeable = false;
100: cleared = true;
101: }
102:
103: HuffmanNode() {
104: clear();
105: }
106:
107: HuffmanNode(int length, int shift, boolean absolute) {
108: this ();
109: set(length, shift, absolute);
110: }
111:
112: final void set(int length, int shift, boolean absolute) {
113: this .dataLength = length;
114: this .shift = shift;
115: this .absolute = absolute;
116: this .cleared = false;
117: }
118:
119: final boolean cleared() {
120: return cleared;
121: }
122:
123: final void addCount() {
124: frequency++;
125: }
126:
127: final boolean hasCount() {
128: return frequency > 0;
129: }
130:
131: final boolean tokenEquals(HuffmanNode node) {
132: return this .absolute == node.absolute
133: && this .dataLength == node.dataLength
134: && this .shift == node.shift;
135: }
136:
137: void addChildren(HuffmanNode child0, HuffmanNode child1) {
138: this .child0 = child0;
139: this .child1 = child1;
140: this .frequency = child0.frequency + child1.frequency;
141: }
142:
143: void collectLeaves(int tag, int tagLength, Collection collection) {
144: if (child0 == null) {
145: this .tag = tag;
146: this .tagLength = tagLength;
147: collection.add(this );
148: } else {
149: child0.collectLeaves((tag << 1) | 0, tagLength + 1,
150: collection);
151: child1.collectLeaves((tag << 1) | 1, tagLength + 1,
152: collection);
153: }
154: }
155:
156: boolean mergeInto(HuffmanNode node) {
157: if (this .absolute == node.absolute) {
158: if (this .dataLength > node.dataLength)
159: node.dataLength = this .dataLength;
160:
161: if (this .shift < node.shift)
162: node.shift = this .shift;
163:
164: node.frequency += this .frequency;
165: this .mergeNode = node;
166: this .merged = true;
167: return true;
168:
169: } else
170: return false;
171: }
172:
173: int incrementLength() {
174: if (shift > 0)
175: shift--;
176: else
177: dataLength++;
178:
179: return dataLength - shift;
180: }
181:
182: final boolean merged() {
183: return merged;
184: }
185:
186: final HuffmanNode getMergeNode() {
187: return mergeNode;
188: }
189:
190: void setUnmergeable() {
191: unmergeable = true;
192: }
193:
194: final boolean unmergeable() {
195: return unmergeable;
196: }
197:
198: public String toString() {
199: return "shift " + shift + " data length " + dataLength
200: + (absolute ? " absolute " : " relative ") + "\ntag 0x"
201: + Integer.toHexString(tag) + " tag length " + tagLength
202: + "\nfrequency: " + frequency;
203: }
204:
205: /**
206: * Sorts nodes in ascending order by frequency.
207: */
208: static class FrequencyComparator implements Comparator {
209: public final int compare(Object o1, Object o2) {
210: return ((HuffmanNode) o1).frequency
211: - ((HuffmanNode) o2).frequency;
212: }
213: }
214:
215: /**
216: * Sorts nodes in descending order by tag bit length.
217: */
218: static class TagLengthComparator implements Comparator {
219: public final int compare(Object o1, Object o2) {
220: return ((HuffmanNode) o2).tagLength
221: - ((HuffmanNode) o1).tagLength;
222: }
223: }
224:
225: static FrequencyComparator frequencyComparator = new FrequencyComparator();
226: static TagLengthComparator tagLengthComparator = new TagLengthComparator();
227: }
|