import java.io.*;
import java.util.*;
import BitOutputStream;

class Symbol
{
	public Symbol(int sym, int len)
	{
		symbol = sym;
		length = len;
	}

	public int symbol;
	public int length;
}

class Node
{
	public Node(Node p, Node c1, Node c2, int n, int d, int c, int w)
	{
		child = new Node[2];
		parent = p;
		child[0] = c1;
		child[1] = c2;
		code = n;
		depth = d;
		count = c;
		which = w;
	}

	public Node parent;
	public Node child[];
	public int code;
	public int depth;
	public int count;
	public int which;
}

public class HuffmanOutputStream extends FilterOutputStream
{
	private Hashtable Table;
	private Node RootNode;
	private Node ZeroNode;
	private Node EscapeNode;
	private BitOutputStream BitOut;
	int bits;

	private Node addnode()
	{
		ZeroNode.child[0] = new Node(ZeroNode,  null, null, ZeroNode.code << 1, ZeroNode.depth + 1, 1, 0);
		Node n = new Node(ZeroNode, null, null, (ZeroNode.code << 1) + 1, ZeroNode.depth + 1, 0, 1);
		ZeroNode.child[1] = n;
		ZeroNode = ZeroNode.child[0];
		return n;
	}

	private void docodes(Node n)
	{
		if(n != null)
		{
			n.depth = n.parent.depth + 1;
			n.code = ((n.parent.code) << 1) + n.which;
			docodes(n.child[0]);
			docodes(n.child[1]);
		}
	}

	private void swap(Node a, Node b)
	{
		a.parent.child[a.which] = b;
		b.parent.child[b.which] = a;
		
		Node tn = a.parent;
		a.parent = b.parent;
		b.parent = tn;

		int t = a.which;
		a.which = b.which;
		b.which = t;
		
		docodes(a);
		docodes(b);
	}

	private void update(Node n)
	{
		while(n != null)
		{
			n.count++;
			if((n.parent != null) && (n.parent.parent != null))
			{
				Node uncle = n.parent.parent.child[n.parent.which ^ 1];
				if(n.count > uncle.count)
				{
					swap(n, uncle);
				}
			}
			n = n.parent;
		}
	}

	public void flush() throws IOException
	{
		BitOut.flush();
	}

	//pass straight to bit writer
	public void writeEscape(int actual, int bits) throws IOException
	{
		BitOut.write(EscapeNode.code, EscapeNode.depth);
		EscapeNode.count++;
		update(EscapeNode.parent);
		BitOut.write(actual, bits);
	}

	public void writeInt(int actual) throws IOException
	{
		Node n = (Node)Table.get(new Integer(actual));
		if(n == null)
		{
			BitOut.write(ZeroNode.code, ZeroNode.depth);
			BitOut.write(actual, bits);
			n = addnode();
			Table.put(new Integer(actual), n);			
		}
		else
		{
			BitOut.write(n.code, n.depth);
		}
		n.count++;
		update(n.parent);
	}
	
	public HuffmanOutputStream(OutputStream _out, int b) throws IOException
	{
		super(_out);
		bits = b;
		BitOut = new BitOutputStream(out);
		Table = new Hashtable(257);
		RootNode = new Node(null, null, null, 0, 0, 2, 0);
		ZeroNode = new Node(RootNode, null, null, 0, 1, 1, 0);
		EscapeNode = new Node(RootNode, null, null, 1, 1, 1, 1);
		RootNode.child[0] = ZeroNode;
		RootNode.child[1] = EscapeNode;
	}
}