#include<iostream.h>
#include<fstream.h>
#include <string>
#include<math.h>
#include<stdlib.h>
#include "Mot2.h"

using std::string;

//permet de permuter deux variables
void permute(Mot2 tab[], int prem, int deux){
double stock=tab[prem].prob;
tab[prem].prob=tab[deux].prob;
tab[deux].prob=stock;
int perm=tab[prem].ind;
tab[prem].ind=tab[deux].ind;
tab[deux].ind=perm;
char car=tab[prem].lettre1;
tab[prem].lettre1=tab[deux].lettre1;
tab[deux].lettre1=car;
car=tab[prem].lettre2;
tab[prem].lettre2=tab[deux].lettre2;
tab[deux].lettre2=car;
}

//permet de trier un tableau dans l'ordre décroissant
void trier(Mot2 t[], int debut, int fin){
for(int pass=0;pass<fin-debut;pass++)
for(int i=debut;i<fin;i++)
if(t[i].prob<t[i+1].prob) permute(t, i, i+1);
}

//permet de corriger l'indice pour remonter le tableau
void corriger(Mot2 tableau[], int t, int p, int d){
for(int i=p;i<=d;i++) tableau[i].ind-=t;
}

void main(){
	//calcul des probabilités à priori et de l'entropie
	double *prob=new double[676];
	string *c=new string[676];
	double nb=0, H=0;
	for(int i=0;i<676;i++){
		prob[i]=0;
		c[i]="";
	}
	ifstream is;
	is.open("titania2.txt");
	string cc;
	char a,d;
	int num=0;
	int test, tot=0;
	while(!is.eof()){
		cc="";
		is>>a;
		is>>d;
		cc+=a;
		cc+=d;
		test=1;
		for(int ii=0;ii<676;ii++){ 
			if(cc==c[ii]){ 
				prob[ii]++;
				test=0;
				tot++;
				break;
			}
		}
			if(test==1){
				c[num]+=a;
				c[num]+=d;
				prob[num]++;
			    num++;
				tot++;
		}
	}		   
	for(int k=0;k<num;k++){
		prob[k]/=tot;
		H-=prob[k]*log(prob[k])/log(2);
	}

	is.close();	

	 	 
	//classement des probabilités 
	int ta=(num+1)/2*(num)-1;
	
	int *liste=new int[ta];
	Mot2 *dico=new Mot2[ta];	 
	for(int l=0;l<ta;l++) dico[l]=Mot2(l);
	int indice, taille=num;
	for(indice=0;indice<num;indice++){
		dico[indice].prob=prob[indice];
		dico[indice].lettre1=c[indice][0];
		dico[indice].lettre2=c[indice][1];
	}
	trier(dico, 0, num-1); 
	for(int m=0;m<num-2;m++){
		for(int n=0;n<taille-2;n++){
			dico[indice].prob=dico[indice-taille].prob;
			indice++;
			}
		dico[indice].prob=dico[indice-taille].prob+dico[indice-taille+1].prob;
		indice++;
		taille--;
		trier(dico, indice-taille, indice-1);
		corriger(dico, taille+1, indice-taille, indice-1);
		for(int o=indice-taille;o<indice;o++) liste[dico[o].ind]=o;
		liste[indice-taille-1]=liste[indice-taille-2]; 
	} 
	for(int ll=0;ll<ta;ll++){
		dico[ll].ind=liste[ll];
	}

	 
	//élaboration des codes binaires
	taille++;
	int lim=ta-taille;
	dico[ta-2].code="0";
	dico[ta-1].code="1";
	for(int p=0;p<num-2;p++){
		for(indice=lim;indice>lim-taille;indice--){
			dico[indice].code=dico[dico[indice].ind].code;
		}
		dico[indice+taille-1].code+="0";
		dico[indice+taille].code+="1";
		taille++;
		lim=indice;
	}
	double R=0;
	for(int lll=0;lll<num;lll++)	R+=dico[lll].code.length()*dico[lll].prob;
	//écriture des résultats dans un fichier
	ofstream os;
	os.open("res.txt");
	for(int llll=0;llll<num;llll++)
		for(int lllm=0;lllm<num;lllm++)
			if(c[llll][0]==dico[lllm].lettre1 && c[llll][1]==dico[lllm].lettre2){
				os<<dico[lllm].lettre1<<dico[lllm].lettre2<<" : "<<100*dico[lllm].prob<<" %\t\t\t"<<dico[lllm].lettre1<<dico[lllm].lettre2<<" : ";
				for(int y=0;y<dico[lllm].code.length();y++) os<<dico[lllm].code[y];
				os<<"\n";
			}
	os<<"\nH="<<H<<"\t\t\t"<<"R="<<R<<"\n\n";
	os<<"efficacite="<<H/R;
	os.close();
	
	//écriture du fichier en utilisant les codes binaires
	ofstream os2;
	os2.open("huffman.txt");
	ifstream is2;
	is2.open("titania2.txt");
	char b,e;
	while(!is2.eof()){
		is2>>b;
		is2>>e;
		for(int q=0;q<num;q++){
			if(b==dico[q].lettre1 && e==dico[q].lettre2){
				for(int yy=0;yy<dico[q].code.length();yy++) os2<<dico[q].code[yy];	
			}
		}
	}
	is2.close();
	os2.close();
}