package Révision;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Stack;
import java.util.TreeSet;
import java.util.Vector;

public class Huffman {
	public static final int N = 256; // nb car
	static class Node implements Comparable<Node> {
		public char ch;
		public int freq;
		private final Node left, right;

		public Node(char ch, int freq, Node left, Node right) {
			this.ch = ch;
			this.freq = freq;
			this.left = left;
			this.right = right;
		}

		public boolean isLeaf() {
			return left == null && right == null;
		}

		public int compareTo(Node that) {
			return this.freq - that.freq;
		}

		public String toString() {
			return this.ch + " " + this.freq;
		}
	}

	private static Node buildTrie(int[] freq) {
		PriorityQueue<Node> pq = new PriorityQueue<Node>();

		for (char c = 0; c < N; c++) {
			if (freq[c] > 0) {
				pq.offer(new Node(c, freq[c], null, null));
			}
		}
		while (pq.size() > 1) {
			Node x = pq.poll();
			Node y = pq.poll();
			System.out.println((x.ch == '\0' ? 'x' : x.ch) + " " + (y.ch == '\0' ? 'x' : y.ch) + " = " + (x.freq + y.freq));
			Node parent = new Node('\0', x.freq + y.freq, x, y);
			pq.offer(parent);
		}

		return pq.poll();
	}

	public static void buildCode(String[] st, Node x, String s) {
		if (x.isLeaf()) {
			st[x.ch] = s;
			return;
		}

		buildCode(st, x.left, s + '0');
		buildCode(st, x.right, s + '1');
	}

	public static void writeTrie(Node x) {
		if (x.isLeaf()) {
			BinaryStdOut.write(true);
			BinaryStdOut.write(x.ch, 8);
			return;
		}
		BinaryStdOut.write(false);
		writeTrie(x.left);
		writeTrie(x.right);
	}

	public static Node readTrie() {
		if (BinaryStdIn.readBoolean())
			return new Node(BinaryStdIn.readChar(), 0, null, null);

		return new Node('\0', 0, readTrie(), readTrie());
	}

	public static void expand() {
		Node root = readTrie();
		int N = BinaryStdIn.readInt();
		for (int i = 0; i < N; i++) {
			Node x = root;
			while (!x.isLeaf())
				if (BinaryStdIn.readBoolean())
					x = x.right;
				else x = x.left;
			BinaryStdOut.write(x.ch, 8);
		}
	}

	public static void main(String[] args) {
		char[] input = "abteehhwwwiiiissssss           ".toCharArray();

		// étape 0 : remplir un tableau de fréquence des caractères
		int[] charFreq = new int[N];
		for (char c : input) {
			charFreq[c]++;
		}

		// étape 1 : construire l'arbre de trie
		Node root = buildTrie(charFreq);

		// étape 2 : construction des codes
		String[] st = new String[N];
		buildCode(st, root, "");
		for (int i = 0; i < N; i++) {
			if (charFreq[i] > 0)
				System.out.println((char)i + " -> " + st[i]);
		}


		// étape 3 : encodage de l'input avec les codes
		// écriture du trie
		writeTrie(root);
		BinaryStdOut.write(input.length);
		// encodage du message
		for (int i = 0; i < input.length; i++) {
			String code = st[input[i]];
			for (int j = 0; j < code.length(); j++)
				if (code.charAt(j) == '1')
					BinaryStdOut.write(true);
				else BinaryStdOut.write(false);
		}
		// Décodage de la chaine encodée
		//expand();
		BinaryStdOut.close();

	}
}