package cf1;


public class Huffman {	
	public static int MAX = 256;
	
	byte[] input;
	Node[] nodes;

	public Huffman(String str) {
		this.input = str.getBytes();
		this.nodes = new Node[MAX];
	}
	
	// non demandée au contrôle
	public void dump(String message) {
		System.out.println("---" + message + "---");
		for(int i=0; i<MAX; i++)
			if(nodes[i] != null)
				System.out.println((char)i + ": " + nodes[i].weight() + " " + nodes[i].encode());
	}
	
	public Node[] computeFrequencies() {		
		for(int i=0; i<input.length; i++) {
			int cur = input[i] & 0xff; // le 0xff n'est pas demandé, évite les index négatifs
			if(nodes[cur] == null)
				nodes[cur] = new Node();
				
			nodes[cur].incWeight();
		}
		
		dump("After computeFrequencies"); // non demandé au contrôle
		return nodes;
	}
	
	public void computeTree() {
		PriorityQueue<Node> queue = new PriorityQueue<>();
		
		for(int i=0; i<MAX; i++)
			if(nodes[i] != null)
				queue.add(nodes[i]);

		while(queue.size() > 1) {
			Node left = queue.poll();
			Node right = queue.poll();
			Node internal = new Node(left, right);
			queue.add(internal);
		}
		
		dump("After computeTree"); // non demandé au contrôlé
	}
	
	public String encode() {
		String res = "";
		for(int i=0; i<input.length; i++)
			res += nodes[input[i] & 0xff].encode(); // le 0xff n'est pas demandé
		
		System.out.println("--- Encoding ---"); // non demandé au contrôlé
		System.out.println(res); // non demandé au contrôlé
		
		return res;
	}
	
	// non demandé au contrôlé
	public static void main(String[] args) {
		Huffman h = new Huffman("A_DEAD_DAD_CEDED_A_BAD_BABE_A_BEADED_ABACA_BED");
		h.computeFrequencies();
		h.computeTree();	
		h.encode();
	}
}