huffmantable.java

JAVA3D矩陈的相关类

	    if (colors[i] != null)
		colors[i].clear() ;

	for (int i = 0 ; i < normals.length ; i++)
	    if (normals[i] != null)
		normals[i].clear() ;
    }

    /**
     * Compute optimized tags for each position, color, and normal entry.
     */
    void computeTags() {
	LinkedList nodeList = new LinkedList() ;
	getEntries(positions, nodeList) ;
	computeTags(nodeList, 3) ;

	nodeList.clear() ;
	getEntries(colors, nodeList) ;
	computeTags(nodeList, 3) ;

	nodeList.clear() ;
	getEntries(normals, nodeList) ;
	computeTags(nodeList, 2) ;
    }
	
    //
    // Compute tags for a list of Huffman tokens.
    //
    private void computeTags(LinkedList nodes, int minComponentCount) {
	HuffmanNode node0, node1, node2 ;

	// Return if there's nothing to do.
	if (nodes.isEmpty())
	    return ;

	while (true) {
	    // Sort the nodes in ascending order by frequency.
	    Collections.sort(nodes, HuffmanNode.frequencyComparator) ;

	    // Apply Huffman's algorithm to construct a binary tree with a
	    // minimum total weighted path length.
	    node0 = (HuffmanNode)nodes.removeFirst() ;
	    while (nodes.size() > 0) {
		node1 = (HuffmanNode)nodes.removeFirst() ;
		node2 = new HuffmanNode() ;

		node2.addChildren(node0, node1) ;
		addNodeInOrder(nodes, node2, HuffmanNode.frequencyComparator) ;

		node0 = (HuffmanNode)nodes.removeFirst() ;
	    }

	    // node0 is the root of the resulting binary tree.  Traverse it
	    // assigning tags and lengths to the leaf nodes.  The leaves are
	    // collected into the now empty node list.
	    node0.collectLeaves(0, 0, nodes) ;

	    // Sort the nodes in descending order by tag length.
	    Collections.sort(nodes, HuffmanNode.tagLengthComparator) ;

	    // Check for tag length overrun.
	    if (((HuffmanNode)nodes.getFirst()).tagLength > MAX_TAG_LENGTH) {
		// Tokens need to be merged and the tree rebuilt with the new
		// combined frequencies.
		merge(nodes) ;
		
	    } else {
		// Increase tag length + data length if they're too small.
		expand(nodes, minComponentCount) ;
		break ;
	    }
	}
    }

    //
    // Merge a token with a long tag into some other token.  The merged token
    // will be removed from the list along with any duplicate node the merge
    // created, reducing the size of the list by 1 or 2 elements until only
    // unmergeable tokens are left.
    //
    private void merge(LinkedList nodes) {
	ListIterator i = nodes.listIterator(0) ;
	HuffmanNode node0, node1, node2 ;
	int index = 0 ;

	while (i.hasNext()) {
	    // Get the node with the longest possibly mergeable tag.
	    node0 = (HuffmanNode)i.next() ;
	    if (node0.unmergeable()) continue ;

	    // Try to find a node that can be merged with node0.  This is any
	    // node that matches its absolute/relative status.
	    i.remove() ;
	    while (i.hasNext()) {
		node1 = (HuffmanNode)i.next() ;
		if (node0.mergeInto(node1)) {
		    // Search for a duplicate of the possibly modified node1
		    // and merge into it so that node weights remain valid.
		    // If a duplicate exists it must be further in the list,
		    // otherwise node0 would have merged into it.
		    i.remove() ;
		    while (i.hasNext()) {
			node2 = (HuffmanNode)i.next() ;
			if (node1.tokenEquals(node2)) {
			    node1.mergeInto(node2) ;
			    return ;
			}
		    }
		    // node1 has no duplicate, so return it to the list.
		    i.add(node1) ;
		    return ;
		}
	    }

	    // node0 can't be merged with any other node; it must be the only
	    // relative or absolute node in the list.  Mark it as unmergeable
	    // to avoid unnecessary searches on subsequent calls to merge()
	    // and return it to the list.
	    node0.setUnmergeable() ;
	    i.add(node0) ;

	    // Restart the iteration.
	    i = nodes.listIterator(0) ;
	}
    }

    //
    // Empty bits within a compression command header are not allowed.  If
    // the tag length plus the total data length is less than 6 bits then
    // the token's length must be increased.
    //
    private void expand(LinkedList nodes, int minComponentCount) {
	Iterator i = nodes.iterator() ;

	while (i.hasNext()) {
	    HuffmanNode n = (HuffmanNode)i.next() ;

	    while (n.tagLength +
		   (minComponentCount * (n.dataLength - n.shift)) < 6) {

		n.incrementLength() ;
	    }
	}
    }

    //
    // Insert a node into the correct place in a sorted list of nodes.
    //
    private void addNodeInOrder(LinkedList l, HuffmanNode node, Comparator c) {
	ListIterator i = l.listIterator(0) ;
	
	while (i.hasNext()) {
	    HuffmanNode n = (HuffmanNode)i.next() ;
	    if (c.compare(n, node) > 0) {
		n = (HuffmanNode)i.previous() ;
		break ;
	    }
	}
	i.add(node) ;
    }

    /**
     * Create compression stream commands for decompressors to use to set up
     * their decompression tables.
     *
     * @param output CommandStream which receives the compression commands
     */
    void outputCommands(CommandStream output) {
	LinkedList nodeList = new LinkedList() ;
	getEntries(positions, nodeList) ;
	outputCommands(nodeList, output, CommandStream.POSITION_TABLE) ;

	nodeList.clear() ;
	getEntries(colors, nodeList) ;
	outputCommands(nodeList, output, CommandStream.COLOR_TABLE) ;

	nodeList.clear() ;
	getEntries(normals, nodeList) ;
	outputCommands(nodeList, output, CommandStream.NORMAL_TABLE) ;
    }

    //
    // Output a setTable command for each unique token.
    // 
    private void outputCommands(Collection nodes,
				CommandStream output, int tableId) {

	Iterator i = nodes.iterator() ;
	while (i.hasNext()) {
	    HuffmanNode n = (HuffmanNode)i.next() ;
	    int addressRange = (1 << n.tagLength) | n.tag ;
	    int dataLength = (n.dataLength == 16? 0 : n.dataLength) ;

	    int command =
		CommandStream.SET_TABLE | (tableId << 1) | (addressRange >> 6) ;

	    long body =
		((addressRange & 0x3f) << 9) | (dataLength << 5) |
		(n.absolute? 0x10 : 0) | n.shift ;

	    output.addCommand(command, 8, body, 15) ;
	}
    }

    /**
     * Print a collection of HuffmanNode objects to standard out.
     *
     * @param header descriptive string
     * @param nodes Collection of HuffmanNode objects to print
     */
    void print(String header, Collection nodes) {
	System.out.println(header + "\nentries: " + nodes.size() + "\n") ;

	Iterator i = nodes.iterator() ;
	while(i.hasNext()) {
	    HuffmanNode n = (HuffmanNode)i.next() ;
	    System.out.println(n.toString() + "\n") ;
	}
    }

    /**
     * Print the contents of this instance to standard out.
     */
    void print() {
	LinkedList nodeList = new LinkedList() ;

	getEntries(positions, nodeList) ;
	Collections.sort(nodeList, HuffmanNode.frequencyComparator) ;
	print("\nposition tokens and tags", nodeList) ;

	nodeList.clear() ;
	getEntries(colors, nodeList) ;
	Collections.sort(nodeList, HuffmanNode.frequencyComparator) ;
	print("\ncolor tokens and tags", nodeList) ;

	nodeList.clear() ;
	getEntries(normals, nodeList) ;
	Collections.sort(nodeList, HuffmanNode.frequencyComparator) ;
	print("\nnormal tokens and tags", nodeList) ;
    }
}