dave

package compression;

import java.util.Vector;

public class DynHuffmanTree extends HuffmanTree
{
	private Vector<Node> nodeNums;
	
	DynHuffmanTree(int val, int _weight) 
	{
		root = new Node(val, _weight);
		nodeNums = new Vector<Node> (256);
		codeTable.put(0, root);
		rebuildNodeNums();
	}

	public Vector<Boolean> GetLeafCode(int data)
	{
		Node n;
		if ((n = codeTable.get(data)) != null)
			return n.GetEncodValue();
		else
			return null;
	}
	
	private Node addNode(int data, int weight, Node parent)
	{
		Node newNode = new Node(data, weight, parent);
		nodeNums.add(newNode);
		
		return newNode;
	}
	
	public void AddNewLeaf(int data)
	{
		Node oldNYT, newNYT, newLeaf;
		oldNYT = codeTable.get(0);
		newNYT = addNode(0, 0, oldNYT.parent);
		codeTable.put(0, newNYT);
		newLeaf = addNode(data, 1, oldNYT);
		oldNYT.left = newNYT;
		oldNYT.right = newLeaf;
		oldNYT.incWeight();
		
		makeTreeConform(oldNYT);
	}
	
	private void makeTreeConform(Node curNode)
	{
		Node parent = curNode.parent;
		
		if (parent == null)
			return;
		
		int i, j;
		i = nodeNums.indexOf(parent);
		int blockWeight = parent.GetWeight();
		for (j = i; j >= 0 && nodeNums.get(j).GetWeight() == blockWeight; j--);
		
		if (j+1 < i)
			swapNodes(i, j);
		
		parent.incWeight();
		makeTreeConform(parent.parent);
	}
	
	private void swapNodes(int i, int j)
	{
		if (i == j)
			return;
		
		if (j == 0)
		{
			swapNodes(j, i);
			return;
		}
		
		Node n_i, n_j, temp_left, temp_right;
		
		n_i = nodeNums.get(i);
		n_j = nodeNums.get(j);
		
		if (i == 0) // special case: i (or j) is the root node
		{
			root = n_j;
			n_i.parent = n_j.parent;
			n_j.parent = null;
		}
		
		temp_left = n_i.left;
		temp_right = n_i.right;
		n_i.left = n_j.left;
		n_i.right = n_j.right;
		n_j.left = temp_left;
		n_j.right = temp_right;
		
		rebuildNodeNums();
	}
	
	private void rebuildNodeNums()
	{
		nodeNums.clear();
		nodeNums.set(0, root);
		int start, end, i, j;
		
		start = 0;
		end = 1;
		while(start != end)
		{
			for (i = start, j = end; i < end; i++)
			{
				if (nodeNums.get(i).left != null)
					nodeNums.set(j++, nodeNums.get(i).left);
				if (nodeNums.get(i).right != null)
					nodeNums.set(j++, nodeNums.get(i).right);
			}
			start = end;
			end = j-1;
		}
	}
}