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

using std::string;

//permet de permuter deux variables
void permute(Mot 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].lettre;
tab[prem].lettre=tab[deux].lettre;
tab[deux].lettre=car;
}

//permet de trier un tableau dans l'ordre décroissant
void trier(Mot 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(Mot 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
	char t[]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
	double *prob=new double[26];
	double nb=0, H=0;
	for(int i=0;i<26;i++){
		prob[i]=0;
	}

	ifstream is;
	is.open("titania.txt");
	char a;
	while(!is.eof()){
		is>>a;
		for(int j=0;j<26;j++){
			if(a==t[j] || a==t[j+26]){
				prob[j]++; 
				nb++;
			}
		}
	}
	for(int k=0;k<26;k++){
		prob[k]/=nb;
		H-=prob[k]*log(prob[k])/log(2);
	}
	is.close();	

	
	//classement des probabilités
	int *liste=new int[350];
	Mot *dico=new Mot[350];
	for(int l=0;l<350;l++) dico[l]=Mot(l);
	int indice, taille=26;
	for(indice=0;indice<26;indice++){
		dico[indice].prob=prob[indice];
		dico[indice].lettre=t[indice];
	}
	trier(dico, 0, 25);
	for(int m=0;m<24;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<350;ll++){
		dico[ll].ind=liste[ll];
	}

	
	//élaboration des codes binaires
	taille++;
	int lim=350-taille;
	dico[348].code="0";
	dico[349].code="1";
	for(int p=0;p<24;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<26;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<26;llll++)
		for(int lllm=0;lllm<26;lllm++)
			if(t[llll]==dico[lllm].lettre){
				os<<dico[lllm].lettre<<" : "<<100*dico[lllm].prob<<" %\t\t\t"<<dico[lllm].lettre<<" : ";
				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("titania.txt");
	char b;
	while(!is2.eof()){
		is2>>b;
		for(int qq=0;qq<26;qq++) if(b==t[qq+26]) b=t[qq];
		for(int q=0;q<26;q++){
			if(b==dico[q].lettre){
				for(int yy=0;yy<dico[q].code.length();yy++) os2<<dico[q].code[yy];	
			}
		}
	}
	is2.close();
	os2.close();
}