import java.util.List;
/**
* Génération de codage de Huffman
*/
public class HuffmanCode {
	/**
	* Classe pour représenter chacun des noeuds de l'arbre
	*/
	public static class Noeud {
		/**
		* Caractère (n'a de sens que pour une feuille)
		*/
		char caractere;
		/**
		* Nombre d'occurence du caractère
		* dans le texte ou des caractères des
		* fils si ce n'est pas une 'feuille'
		*/
		int nbOccurences;
		/**
		* Pere du noeud
		*/
		Noeud pere;
		/**
		* Fils gauche du noeud (toujours null pour une feuille)
		*/
		Noeud filsgauche;
		/**
		* Fils droit du noeud (toujours null pour une feuille)
		*/
		Noeud filsdroite;
		/**
		* Codage calculé
		*/
		String codage;
	}
	/**
	* Construit les feuilles de l'arbre où chaque
	* noeud correspond à un caractère du texte
	*
	* @param texte le texte à coder
	* @return les feuilles de l'arbre
	*/
	public static List<Noeud> creationDesFeuilles(String texte) {
		// TODO
		throw new UnsupportedOperationException();
	}
	/**
	* Connaissant le codage du noeud n, on code ses fils
	* (0 à gauche, 1 à droite) et récursivement
	* les fils de ses fils 
	*
	* @param n le noeud à coder
	*/
	public static void code(Noeud n) {
		// TODO
		throw new UnsupportedOperationException();
	}
	/**
	* Créé un père pour les 2 noeuds de poids le
	* plus faible qui n'ont pas encore de "père".
	* Le "père" doit être ajouté à la liste de noeuds
	* @param noeuds
	* @return false s'il n'y a plus de noeud sans pere
	*/
	public static boolean join(List<Noeud> noeuds) {
		// TODO
		throw new UnsupportedOperationException();
	}
	public static Noeud[] deuxPlusPetits(List<Noeud> noeuds) {
		// TODO
		throw new UnsupportedOperationException();
	}
	/**
	*
	* @param noeuds
	* @return
	* @throws IllegalArgumentException
	* si plus d'un noeud ne contient pas de père
	*/
	public static Noeud racine(List<Noeud> noeuds) {
		// TODO
		throw new UnsupportedOperationException();
	}
	/**
	* Génère le texte codé en binaire avec le codage
	* de Huffman inscrit dans les noeuds
	*
	* @param noeuds
	* @return
	*/
	public static String texteCode(List<Noeud> noeuds,
	String texteOriginal){
		// TODO
		throw new UnsupportedOperationException();
	}
	public static void main(String[] args) {
		try {
			// le teste à coder
			String texte = "Lorem ipsum dolor sit amet, consectetur adipisicing elit, "+
			"sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim "+
			"ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip "+
			"ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate "+
			"velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat "+
			"cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id "+
			"est laborum.";
			List<Noeud> noeuds = creationDesFeuilles(texte);
			// le nombre de feuilles
			int nbfeuilles = noeuds.size();
			// tant qu'on n'a pas joint toutes les feuilles, on contruit l'arbre
			boolean termine = false;
			while (!termine) {
				termine = !join(noeuds);
			}
			// on recupère la racine de l'arbre
			Noeud pere = racine(noeuds);
			// on redescend pour écrire le codage dans chacun des noeuds
			code(pere);
			// on affiche le resultat :-)
			for (Noeud n : noeuds) {
				if (n.filsdroite == null) {// i.e. c'est une feuille
					System.out.println(n.caractere + " occurence="
					+ n.nbOccurences + " codage=" + n.codage);
				}
			}
			System.out.println("Espace utilisé avec le codage de Huffman "+
			"(sans coder l'arbre): " + texteCode(noeuds,texte));
			int espaceParCaractere = (int) Math.ceil(Math.log(nbfeuilles) / Math.log(2));
			int espaceCodageBinaireSimple = texte.length() * espaceParCaractere;
			System.out.println("Espace utilisé avec un codage classique: "
			+ espaceCodageBinaireSimple);
		} catch (Throwable e) {
			e.printStackTrace();
			System.exit(1);
		}
	}
}