huffmantable.java

JAVA3D矩陈的相关类

/*
 * $RCSfile: HuffmanTable.java,v $
 *
 * Copyright (c) 2007 Sun Microsystems, Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistribution of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 *
 * - Redistribution in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in
 *   the documentation and/or other materials provided with the
 *   distribution.
 *
 * Neither the name of Sun Microsystems, Inc. or the names of
 * contributors may be used to endorse or promote products derived
 * from this software without specific prior written permission.
 *
 * This software is provided "AS IS," without a warranty of any
 * kind. ALL EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND
 * WARRANTIES, INCLUDING ANY IMPLIED WARRANTY OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE HEREBY
 * EXCLUDED. SUN MICROSYSTEMS, INC. ("SUN") AND ITS LICENSORS SHALL
 * NOT BE LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF
 * USING, MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS
 * DERIVATIVES. IN NO EVENT WILL SUN OR ITS LICENSORS BE LIABLE FOR
 * ANY LOST REVENUE, PROFIT OR DATA, OR FOR DIRECT, INDIRECT, SPECIAL,
 * CONSEQUENTIAL, INCIDENTAL OR PUNITIVE DAMAGES, HOWEVER CAUSED AND
 * REGARDLESS OF THE THEORY OF LIABILITY, ARISING OUT OF THE USE OF OR
 * INABILITY TO USE THIS SOFTWARE, EVEN IF SUN HAS BEEN ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGES.
 *
 * You acknowledge that this software is not designed, licensed or
 * intended for use in the design, construction, operation or
 * maintenance of any nuclear facility.
 *
 * $Revision: 1.3 $
 * $Date: 2007/02/09 17:20:23 $
 * $State: Exp $
 */

package com.sun.j3d.utils.geometry.compression;

import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.ListIterator;

/**
 * This class maintains a map from compression stream elements (tokens) onto
 * HuffmanNode objects.  A HuffmanNode contains a tag describing the
 * associated token's data length, right shift value, and absolute/relative
 * status.<p>
 * 
 * The tags are computed using Huffman's algorithm to build a binary tree with
 * a minimal total weighted path length.  The frequency of each token is
 * used as its node's weight when building the tree. The path length from the
 * root to the token's node then indicates the bit length that should be used
 * for that token's tag in order to minimize the total size of the compressed
 * stream.
 */
class HuffmanTable {
    private static final int MAX_TAG_LENGTH = 6 ;

    private HuffmanNode positions[] ;
    private HuffmanNode normals[] ;
    private HuffmanNode colors[] ;

    /**
     * Create a new HuffmanTable with entries for all possible position,
     * normal, and color tokens.
     */
    HuffmanTable() {
	//
	// Position and color components can have data lengths up to 16
	// bits, with right shifts up to 15 bits.  The position and color
	// lookup tables are therefore 2*17*16=544 entries in length to
	// account for all possible combinations of data lengths, shifts,
	// and relative or absolute status.
	// 
	colors = new HuffmanNode[544] ;
	positions = new HuffmanNode[544] ;

	//
	// Delta normals can have uv components up to 7 bits in length with
	// right shifts up to 6 bits.  Absolute normals can have uv components
	// up to 6 bits in length with right shifts up to 5 bits.  The normal
	// lookup table is therefore 2*8*7=112 entries in length.
	//
	normals = new HuffmanNode[112] ;
    }

    private final int getPositionIndex(int len, int shift, boolean absolute) {
	return (absolute? 1:0)*272 + len*16 + shift ;
    }

    private final int getNormalIndex(int length, int shift, boolean absolute) {
	return (absolute? 1:0)*56 + length*7 + shift ;
    }

    private final int getColorIndex(int length, int shift, boolean absolute) {
	return getPositionIndex(length, shift, absolute) ;
    }


    /**
     * Add a position entry with the given length, shift, and absolute
     * status.
     *
     * @param length number of bits in each X, Y, and Z component
     * @param shift number of trailing zeros in each component
     * @param absolute if false, value represented is a delta from the
     * previous vertex in the compression stream
     */
    void addPositionEntry(int length, int shift, boolean absolute) {
	addEntry(positions, getPositionIndex(length, shift, absolute),
		 length, shift, absolute) ;
    }

    /**
     * Get the position entry associated with the specified length, shift, and
     * absolute status.  This will contain a tag indicating the actual
     * encoding to be used in the compression command stream, not necessarily
     * the same as the original length and shift with which the the entry was
     * created.
     *
     * @param length number of bits in each X, Y, and Z component
     * @param shift number of trailing zeros in each component
     * @param absolute if false, value represented is a delta from the
     * previous vertex in the compression stream
     * @return HuffmanNode mapped to the specified parameters
     */
    HuffmanNode getPositionEntry(int length, int shift, boolean absolute) {
	return getEntry(positions, getPositionIndex(length, shift, absolute)) ;
    }

    /**
     * Add a color entry with the given length, shift, and absolute
     * status.
     *
     * @param length number of bits in each R, G, B, and A component
     * @param shift number of trailing zeros in each component
     * @param absolute if false, value represented is a delta from the
     * previous color in the compression stream
     */
    void addColorEntry(int length, int shift, boolean absolute) {
	addEntry(colors, getColorIndex(length, shift, absolute),
		 length, shift, absolute) ;
    }

    /**
     * Get the color entry associated with the specified length, shift, and
     * absolute status.  This will contain a tag indicating the actual
     * encoding to be used in the compression command stream, not necessarily
     * the same as the original length and shift with which the the entry was
     * created.
     *
     * @param length number of bits in each R, G, B, and A component
     * @param shift number of trailing zeros in each component
     * @param absolute if false, value represented is a delta from the
     * previous color in the compression stream
     * @return HuffmanNode mapped to the specified parameters
     */
    HuffmanNode getColorEntry(int length, int shift, boolean absolute) {
	return getEntry(colors, getColorIndex(length, shift, absolute)) ;
    }

    /**
     * Add a normal entry with the given length, shift, and absolute
     * status.
     *
     * @param length number of bits in each U and V component
     * @param shift number of trailing zeros in each component
     * @param absolute if false, value represented is a delta from the
     * previous normal in the compression stream
     */
    void addNormalEntry(int length, int shift, boolean absolute) {
	addEntry(normals, getNormalIndex(length, shift, absolute),
		 length, shift, absolute) ;
    }

    /**
     * Get the normal entry associated with the specified length, shift, and
     * absolute status.  This will contain a tag indicating the actual
     * encoding to be used in the compression command stream, not necessarily
     * the same as the original length and shift with which the the entry was
     * created.
     *
     * @param length number of bits in each U and V component
     * @param shift number of trailing zeros in each component
     * @param absolute if false, value represented is a delta from the
     * previous normal in the compression stream
     * @return HuffmanNode mapped to the specified parameters
     */
    HuffmanNode getNormalEntry(int length, int shift, boolean absolute) {
	return getEntry(normals, getNormalIndex(length, shift, absolute)) ;
    }


    private void addEntry(HuffmanNode table[], int index,
			  int length, int shift, boolean absolute) {

	if (table[index] == null)
	    table[index] = new HuffmanNode(length, shift, absolute) ;

	else if (table[index].cleared())
	    table[index].set(length, shift, absolute) ;

	table[index].addCount() ;
    }

    private HuffmanNode getEntry(HuffmanNode table[], int index) {
	HuffmanNode t = table[index] ;

	while (t.merged())
	    t = t.getMergeNode() ;

	return t ;
    }

    private void getEntries(HuffmanNode table[], Collection c) {
	for (int i = 0 ; i < table.length ; i++)
	    if (table[i] != null && !table[i].cleared() &&
		table[i].hasCount() && !table[i].merged())
		c.add(table[i]) ;
    }


    /**
     * Clear this HuffmanTable instance.
     */
    void clear() {
	for (int i = 0 ; i < positions.length ; i++)
	    if (positions[i] != null)
		positions[i].clear() ;

	for (int i = 0 ; i < colors.length ; i++)