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


/**
 *La classe Noeud permet de représenter les noeuds de l'arbre de Huffman.<br>
 *Seules les feuilles de l'arbre ont leur champs <i>lettre</i> défini.<br>
 *@version 1
 *@author Juba Hamid et Adrien Taieb
 */
public class Noeud{	
	public int label;
	public char lettre;
	public Noeud fg;
	public Noeud fd;
	
	/**pour l'écriture décalée
	 */
	public static int buffer=0,bufferp=0;
	public static Noeud buffernp=new Noeud();
	
	/**pour le calcul de la complexité
	 */
	public static int operations=0;
	/**
	 *Constructeur vide
	 */
	public Noeud(){operations++;}
	
	public Noeud(int freq){
		operations++;
		label=freq;
	}
	
	public char getlettre(){
		operations++;
		return lettre;
	}
	
	public int getlabel(){
		operations++;
		return label;
	}
	
	public Noeud getfg(){
		operations++;
		return fg;
	}
	
	public Noeud getfd(){
		operations++;
		return fd;
	}
	
	public void setlettre(char c){
		operations++;
		lettre=c;
	}
	
	public void setlabel(int l){
		operations++;
		label=l;
	}
	
	public void setfg(Noeud f){
		operations++;
		fg=f;
	}
	
	public void setfd(Noeud f){
		operations++;
		fd=f;
	}

	public boolean isequal(Noeud n){
		operations++;
		return n==this;
	}
	
	public String toString(){
		operations++;
		if(getfg()!=null)
			System.out.println("- Noeud -");
		else
			System.out.println("- Feuille -");
		System.out.println("Lettre : "+getlettre()+" Fréquence : "+getlabel());
		return "";
	}
	
	/**
	 *permet de cloner un noeud
     */	
	public void copier(Noeud a){
		operations++;
		setlabel(a.getlabel());
		setlettre(a.getlettre());
		setfg(a.getfg());
		setfd(a.getfd());
		
	}
	
	
	/**
	 *crée un nouveau noeud à partir de 2 noeuds qui seront les fils du nouveau
    */
	public void add(Noeud gauche,Noeud droit){
		operations++;
		setlabel(gauche.getlabel()+droit.getlabel());
		setfg(gauche);
		setfd(droit);
	}
	
	
	/**
	 *test l'appartenance d'un caractère dans un vecteur de Noeud<br>
	 *cf <i>trouver</i>
    */
	public static boolean belong (char c , Vector <Noeud> v){
		operations++;
		for(int i=0;i<v.size();i++){
			if(v.get(i).getlettre()==c)return true;
		}
		return false;
	}
	
	
	/**
	 *renvoi tous les caractères de l'alphabet sans répétition<br>
	 *cf <i>creerfeuilles</i>
    */
	public static Vector <Noeud> supprimerLesDoublons(Vector <Noeud> a){
		operations++;
		Vector <Noeud> b = new Vector <Noeud> ();
		for(int i=0;i<a.size();i++){
			if(!belong(a.get(i).getlettre(),b))
				b.addElement(a.get(i));
		}
		return b;
	}
	
	
	/**
	 *chaque noeud du vecteur retourné est à une fréquence 1 et est étiqueté d'une lettre
	 *de l'alphabet
    */
	public static Vector <Noeud> creerfeuilles(char [] alphabet){
		operations++;
		Vector <Noeud> v = new Vector <Noeud> ();
		Noeud n;
		for(int i=0;i<alphabet.length;i++){
			n = new Noeud(alphabet[i]);
			n.setlabel(1);
			n.setlettre(alphabet[i]);
			v.addElement(n);
		}
		return supprimerLesDoublons(v);
	}
	
	
	/**
	 *incremente la fréquence d'un noeud
    */
	public void incrementer(){
		operations++;
		setlabel(getlabel()+1);
	}

	/**
	 *renvoi une liste de 0 et de 1 décrivant le parcours dans l'arbre pour ariver
	 *à la lettre c<br>
	 *cf <i>ecrire</i>
    */
	public Liste <Integer> codage(char c){
		operations++;
		//test si c'est une feuille
		Liste <Integer> res = new Liste <Integer>();
		if(this==null)return res;
		if(getfg()==null){
			if(getlettre()==c)return null;
			else return null;
		}
		else{
			Noeud g = getfg().chercher(c);
			Noeud d = getfd().chercher(c);
			if(g!=null){
				return new Liste <Integer>(0,getfg().codage(c));
			}
			else{
				if(d!=null){
					return new Liste <Integer>(1,getfd().codage(c));
				}
				else {
					return null;
				}
			}
		}
	}
	
	/**Utilise l'algo de parcours de l'arbre de bas en haut et de droite à gauche<br>
	 *cf <i>trouver</i>
	 **/
	public Noeud chercher(char c){
		operations++;
		Vector <Noeud> v = new Vector <Noeud>();
		v.add(this);
		Noeud n;
		while(!v.isEmpty()){
			n = v.get(0);
			v.remove(0);
			if(n.getlettre()==c)return n;
			if(n.getfd()!=null) {v.add(n.getfd());}
			if(n.getfg()!=null) {v.add(n.getfg());}
		}
		return null;
	}
	
	/**
	 *vérifie que la lettre cherchée par la fonction <i>chercher</i> a été trouvée<br>
	 *renvoi une erreur sinon et arrete le programme<br>
	 *cf <i>chercher</i>
	 */
	public Noeud trouver(char c){
		operations++;
		Noeud n = chercher(c);
		if(n==null){
			System.out.println("Erreur -trouver : la lettre "+c+" n'appartient pas à l'alphabet");
			System.exit(0);
			return null;
		}
		return n;
	}
	
	/**
	 *Utilise l'algo de parcours de l'arbre de haut en bas et de gauche a droite<br>
	 *retoune le pere d'un noeud<br>
	 */
	public Noeud getpere(Noeud a){
		operations++;
		if(getfg()==null)return null;
		if(isequal(a))return null;
		else{
			if(getfg().isequal(a)||getfd().isequal(a)){
				return this;
			}
			else{
				Noeud g = getfg().getpere(a);
				Noeud d = getfd().getpere(a);
				if(g!=null){
					return g;
				}
				else{
					if(d!=null){
						return d;
					}
					else {
						return null;
					}
				}
			}
		}
	}


	/**voir 4.3 dans l'énoncé pour l'algo*/
	public void ajouter(char c){
		operations++;
		Noeud tmp = trouver(c);
		//test si tmp est la racine
		while(!isequal(tmp)){
			Noeud a = plusPetit(tmp.getlabel());
			echanger(tmp,a);
			a.incrementer();			
			tmp = getpere(a);
		}
		incrementer();
		
	}
	
	/**
	 *échange 2 adresses
	 */
	public void echanger(Noeud a,Noeud b){
		operations++;
		Noeud tmp=new Noeud();
		tmp.copier(a);
		a.copier(b);
		b.copier(tmp);
	}

	/**
	 *classement sur la fréquence
	 */
	public static int plusPetit(Vector <Noeud> v){
		operations++;
		int tmp=v.elementAt(0).getlabel();
		int indice=0;
		int i=0;
		for(i=0;i<v.size();i++){
			if(v.elementAt(i).getlabel()<tmp){tmp=v.elementAt(i).getlabel();indice=i;}
		}
		return indice;
	}
	
	/**
	 *cherche le premier noeud de fréquence freq par parcours de droite à gauche
	 */
	public Noeud plusPetit(int freq){
		operations++;
		Vector <Noeud> v = new Vector <Noeud>();
		v.add(this);
		Noeud n;
		while(!v.isEmpty()){
			n = v.get(0);
			v.remove(0);
			if(n.getlabel()==freq)return n;
			if(n.getfd()!=null) {v.add(n.getfd());}
			if(n.getfg()!=null) {v.add(n.getfg());}
		}
		return null;
	}
	
	/**
	 *crée un arbre à partir d'une liste de feuilles<br>
	 *en gérant l'addition des fréquences gràce à <i>add</i><br>
	 *cf <i>creerfeuilles</i>
	 */
	public static Noeud creerArbre(Vector <Noeud> v){
		operations++;
		while(v.size()!=1){
			int tmp = plusPetit(v);
			Noeud a1 = v.elementAt(tmp);
			v.remove(tmp);
			
			tmp = plusPetit(v);
			Noeud a2 = v.elementAt(tmp);
			v.remove(tmp);
			
			Noeud r = new Noeud();
			r.add(a1,a2);
			
			v.addElement(r);
		}
		return v.elementAt(0);
	}

	/**
	 *retourne le tableau des lettres contenues dans le fichier file<br>
	 *renvoi une exception en cas d'erreur d'accés au fichier<br>
	 */
	public static char [] getAlphabet(String file){
		operations++;
		try{
			File entree = new File(file);
			FileInputStream fis = new FileInputStream(entree);
			int octet_lu=0;
			int i=0;
			int taille = (int)(entree.length());
			char [] alphabet = new char[taille];
			while(octet_lu!=-1 && i!=taille){
				octet_lu = fis.read();
				alphabet[i]=(char)(octet_lu);
				i++;
			}
			fis.close();
			return alphabet;
		}
		catch(IOException ioe){
			System.out.println(file+ioe.toString());
			return new char[0];
		}
	}
	
	/**
	 *écrit une lettre dans un fichier<br>
	 *l'écriture n'est réalisée que si le tampon de bits est plein<br>
	 *cette fonction est utilisée pour la compression
	 */
	public void ecrire(char a, FileOutputStream fos){
		operations++;
		Liste <Integer> l = codage(a);
		try{
			while(l!=null){
				buffer = buffer * 2 + l.tete;
				//System.out.println(l.tete);
				bufferp++;
				if(bufferp==8){
					fos.write(buffer);
					bufferp=0;
				}
				l=l.suite;
			}
		}
		catch(IOException ioe){
			System.out.println(ioe.toString());
		}
	}
	/**
	 *produit une série de lettre lue sur l'arbre à partir de leurs codages extraits
	 *de l'entier a qui vient d'être lu sur le fichier compressé<br><br>
	 *écrit les lettres dans le fichier fos<br>
	 *utilisé pour la décompression
	 */
	public void ecrire2(int a,FileOutputStream fos){
		operations++;
		try{
			for(int i=7;i>=0;i--){
				if((int)(a/(Math.pow(2,i)))%2 == 0){
					buffernp=buffernp.getfg();
				}
				else{
					buffernp=buffernp.getfd();
				}
				if(buffernp.getfg()==null){
					fos.write(buffernp.getlettre());
					ajouter(buffernp.getlettre());
					buffernp = this;
				}
				
			}
		}
		catch(IOException ioe){
			System.out.println(ioe.toString());
		}
	}

	/**<b>fonction de test</b>
	 */
	public void afficher(){
		operations++;
		System.out.print(getlabel());
		System.out.println(getlettre());
		if(getfg()!=null){
			fg.afficher();
			fd.afficher();
		}
	}

	/**<b>fonction de test</b>
	 */
	public static void afficher(Vector <Noeud> v){
		operations++;
		for(int i=0;i<v.size();i++){
			System.out.println(v.get(i).getlettre()+" "+v.get(i).getlabel());
		}
	}

	/**<b>fonction de test</b>
	 */
	public static void afficher2(Vector <Integer> v){
		operations++;
		for(int i=0;i<v.size();i++){
			if(v.get(i)==0)System.out.println(0);
			else System.out.println(1);
		}
	}

	/**
	 *compresse le fichier file en utilisant l'arbre créé à partir de l'alphabet
	 *contenu dans le fichier file_alphabet<br>
	 *renvoi une exception en cas d'erreur d'ouverture des fichiers<br>
	 *@param file fichier à compresser
	 *@param file_alphabet fichier contenant l'alphabet
	 */
	public static Noeud compresser(String file,String file_alphabet){
		operations++;
		try{
			File entree = new File(file);
			FileInputStream fis = new FileInputStream(entree);
			int octet_lu=0;
			File sortie = new File(file+".x");
			FileOutputStream fos = new FileOutputStream(sortie);
			int i=0;
			int taille = (int)(entree.length());
			if(taille<5){
				System.out.println("Il n'est pas nécessaire de compresser ce fichier");
				System.exit(0);
			}
			System.out.println("\tCréation de l'arbre de départ");
			char [] tab = getAlphabet(file_alphabet);
			Vector <Noeud> v = creerfeuilles(tab);
			Noeud n = creerArbre(v);
			System.out.println("\t--Fin--");
			while(octet_lu!=-1 && i!=taille){
				octet_lu = fis.read();
				n.ecrire((char)(octet_lu),fos);
				n.ajouter((char)(octet_lu));
				int newi=100*i/taille;
				i++;
				if(100*i/taille!=newi)System.out.print(100*i/taille+" %|");
			}
			//flush
			while(bufferp!=8){
				buffer = buffer * 2;
				bufferp++;
			}
			fos.write(buffer);
			fis.close();
			fos.close();
			return n;
		}
		catch(IOException ioe){
			System.out.println(ioe.toString());
			return new Noeud();
		}
	}

	/**
	 *décompresse le fichier file en utilisant l'arbre créé à partir de l'alphabet
	 *contenu dans le fichier file_alphabet qui doit être le même que celui utilisé
	 *pour la compression - agi donc comme clef de codage<br>
	 *renvoi une exception en cas d'erreur d'ouverture des fichiers<br>
	 *@param file fichier à décompresser
	 *@param file_alphabet fichier contenant l'alphabet
	 */
	public static Noeud decompresser(String file,String file_alphabet){
		operations++;
		System.out.println("\tCréation de l'arbre de départ");
		char [] tab = getAlphabet(file_alphabet);
		Vector <Noeud> v = creerfeuilles(tab);
		Noeud n = creerArbre(v);
		System.out.println("\t--Fin--");
		try{
			File entree = new File(file);
			FileInputStream fis = new FileInputStream(entree);
			int octet_lu=0;
			File sortie = new File(file+".txt");
			FileOutputStream fos = new FileOutputStream(sortie);
			int i=0;
			int taille = (int)(entree.length());
			buffernp=n;
			while(octet_lu!=-1 && i!=taille){
				octet_lu = fis.read();
				n.ecrire2(octet_lu,fos);
				int newi=100*i/taille;
				i++;
				if(100*i/taille!=newi)System.out.print(100*i/taille+" %|");
			}
			fis.close();
			fos.close();
		}
		catch(IOException ioe){
			System.out.println(ioe.toString());
		}
		return n;
	}

	/**
	 *- lance la compression du fichier passé en args[0] avec l'alphabet contenu 
	 *dans args[1] et compresse dans le fichier [nom_du_fichier].x<br>
	 *- décompresse le fichier [nom_du_fichier].x<br>
	 *- lance la fenetre graphique si args[2] est spécifié<br>
	 */ 
	public static void main(String [] args){
		operations++;
		args = new String [3];
		args[0]="texte.txt";
		args[1]="texte.txt";
		args[2]="a";
		System.out.println("Début de la compression");
		Noeud n = compresser(args[0],args[1]);
		System.out.println("--Fin--"+operations);
		System.out.println("Début de la décompression");
		Noeud nn = decompresser(args[0]+".x",args[1]);
		System.out.println("--Fin--"+operations);
		if(args[2]!=null){
			HuffmanFrame hf = new HuffmanFrame(nn);
			hf.setVisible(true);
		}
	}	
}

class Liste <T>{
	T tete;
	Liste <T> suite;
	
	Liste(){}
	
	Liste(T a,Liste b){
		tete=a;
		suite=b;
	}
	
	int length(){
		if(suite == null){
			return 0;
		}
		else {
			return 1 + suite.length();
		}
	}
	
	void addElement(T a){
		suite = this;
		tete = a;
	}
	
	T gettete(){
		return tete;
	}
	//fonction de test
	void afficher(){
		if(suite!=null){
			System.out.println(tete.toString());
			suite.afficher();
		}
		else{
			System.out.println(tete.toString());
		}
	}
}