#include <conio.h>
#include <graphics.h>
#include <stdio.h>

int gdriver, gmode, errorcode;
char text[512];
int coduri[256][100];
int N,nr_aparitii[256];
float vector[256];
typedef struct arbore {
	struct arbore *rad;
	int cod;
	float prob;
	} simbol;
simbol  *s,*radacina;
simbol *varfuri[256];
simbol *vecttemp[256];
int min1,min2;

/**********************************************************/

void border(void)             /* afiseaza marginea ferestrei */
{
unsigned char v=186, o=205, ss=201, ds=187, sj=200, dj=188;
struct text_info cw;
int i, dx, dy;
	gettextinfo(&cw);	     /* det dimensiunile ferestrei */
	dx=cw.winright-cw.winleft+1;
	dy=cw.winbottom-cw.wintop+1; /* desenare margine superioara */
	gotoxy(1,1);
	putch(ss);
	for(i=2;i<dx;i++) putch(o);
	putch(ds);                   /* desenare margine inferioara */
	gotoxy(1,dy);
	putch(sj);
	for(i=2;i<dx;i++) putch(o);
	_wscroll=0;
	putch(dj);
	_wscroll=1;                  /* desenare margine stanga si dreapta */
	for(i=2;i<dy;i++) {
					  gotoxy(1,i);
					  putch(v);
					  gotoxy(dx,i);
					  putch(v);
					  }
}

/**********************************************************/

void afisareheader(void)     /* afisare header */
{
	window(1,1,80,3);
	border();
	gotoxy(22,2);cputs("Huffcode ver 1.0  Copyright 2002 by LP");
}

/**********************************************************/

void afisaremeniu(void)     /* afisare meniu optiuni*/
{
	window(1,23,80,25);
	border();
	gotoxy(5,2);cputs("Sursa de intrare");
	gotoxy(24,2);cputs("Sursa de iesire");
	gotoxy(42,2);cputs("Optiuni");
	gotoxy(52,2);cputs("Iesire");
	textcolor(4);
	gotoxy(14,2);cputs("i");
	gotoxy(34,2);cputs("e");
	gotoxy(42,2);cputs("O");
	gotoxy(54,2);cputs("s");
	textcolor(15);
}

/**********************************************************/

void get_text_console(void)
{
	window(1,4,80,22);
	clrscr();
	window(20,6,61,18);
	border();
	gotoxy(11,1);cputs("  Introduceti textul  ");
	gotoxy(8,13);cputs(" La sfarsit apasati Enter ");
	window(22,7,59,17);
	cscanf("%s",text);
	window(1,4,80,22);
	clrscr();
}

/**********************************************************/

void get_text_file(void)
{
}

/**********************************************************/

void put_text_file(void)
{
}

/**********************************************************/

void creare_coduri(void)
{
int i,nr,j,jj,v[256];
	nr=0;
	for(i=1;i<=256;i++) coduri[i][1]=-1;
	for(i=1;i<=256;i++)
		{
		if (nr_aparitii[i]!=0)
		   {
		   nr++;
		   s=varfuri[nr];
		   j=1;
		   do {
			  v[j]=s->cod;
			  j++;
			  s=s->rad;
			  } while (s->rad!=NULL);
		   for(jj=j-1;jj>=1;jj--) coduri[i][j-jj+1]=v[jj];
		   coduri[i][j+1]=-1;
		   }
		}
}

/**********************************************************/

void put_text_console(void)
{
int j,nr,i;
	window(1,4,80,22);
	clrscr();
	window(20,6,61,18);
	border();
	gotoxy(9,1);cputs(" Textul codat Huffman este ");
	gotoxy(12,13);cputs(" ENJOY HUFFCODE 1.0 ");
	window(22,7,59,17);
	for(j=0;j<strlen(text);j++)
		{
		i=2;
		do {
			cprintf("%d",coduri[text[j]][i]);
			i++;
		   } while (coduri[text[j]][i]!=-1);
		cprintf(" ");
		}
	getch();
	window(1,4,80,22);
	clrscr();
}

/**********************************************************/

void calcul_probabilitati(void)
{
int i,dim,j;
	dim=strlen(text);
//	cprintf("%d",dim);
	for(i=1;i<=256;i++) nr_aparitii[i]=0;
	for(i=0;i<=dim;i++) nr_aparitii[text[i]]++;
//	for(i=1;i<=256;i++) cprintf("%d",nr_aparitii[i]);
	j=0;
	for(i=1;i<=256;i++) if (nr_aparitii[i]!=0)
						   {
							j++;
							vector[j]=((float)nr_aparitii[i]/(float)dim);
						   }
	N=j;          /* numarul de simboluri*/
}

/**********************************************************/

void afla_minime(int m)
{
int i,temp;
float temp1,temp2;
	if (m>=3)
	   {
		temp1=vecttemp[1]->prob;
		min1=1;
		for(i=2;i<=N;i++)
			if ((vecttemp[i]!=NULL)&&(vecttemp[i]->prob<temp1))
			   {
				temp1=vecttemp[i]->prob;
				min1=i;
			   }
		min2=2;
		temp2=vecttemp[1]->prob;
		for(i=2;i<=N;i++)
			if ((vecttemp[i]!=NULL)&&(i!=min1)&&(vecttemp[i]->prob<=temp2)&&(vecttemp[i]->prob>=temp1))
			   {
				temp2=vecttemp[i]->prob;
				min2=i;
			   }
	   }
	if (m==2)
	   {
		min1=0;
		min2=0;
		for(i=1;i<=N;i++)
			if ((min1==0)&&(vecttemp[i]!=NULL))
			   {
				min1=i;
				temp1=vecttemp[i]->prob;
			   }
			   else if ((min1!=0)&&(vecttemp[i]!=NULL))
					   {
						min2=i;
						temp2=vecttemp[i]->prob;
					   }
		if (temp1>temp2)
		   {
			temp=min1;
			min1=min2;
			min2=temp;
		   }
	   }
}

/*********************************************************/

void gen_arbore(void)
{
int i,M;
simbol *vecttemp1[256];
					/* initializam arborele de la stanga */
	for(i=1;i<=N;i++) {
		s=(simbol *)malloc(sizeof(simbol));
		s->rad=NULL;
		s->prob=vector[i];
		varfuri[i]=s;
		vecttemp[i]=s;
					  }
	M=N;
	do {
		afla_minime(M);
		s=(simbol *)malloc(sizeof(simbol));
		vecttemp[min1]->rad=s;
		vecttemp[min2]->rad=s;

		s->prob=vecttemp[min1]->prob+vecttemp[min2]->prob;
		s->rad=NULL;
		vecttemp[min1]->cod=0;
		vecttemp[min2]->cod=1;
		vecttemp[min1]=s;       // generam noul vector temporar
		vecttemp[min2]=NULL;
		M--;
	} while (M>=2);
}

/**********************************************************/

void codare_Huff(void)
{
int i;
	window(32,10,46,12);
	clrscr();
	border();
	gotoxy(3,1);cputs(" Calculez! ");
	gotoxy(2,2);
	for(i=1;i<=13;i++) {printf("%c",1);delay(100);}
	clrscr();
	calcul_probabilitati();
	gen_arbore();
	creare_coduri();
}

/**********************************************************/

void decodare_Huff(void)
{
}

/**********************************************************/

void afisareinput(void)
{
char ch;
	window(5,19,23,22);
	border();
	gotoxy(3,1);cputs(" Alegeti sursa ");
	gotoxy(3,2);cputs("Fisier");
	gotoxy(3,3);cputs("Consola");
	textcolor(4);
	gotoxy(3,2);cputs("F");
	gotoxy(3,3);cputs("C");
	textcolor(15);
	ch=getch();
	if (ch=='f') get_text_file();
	if (ch=='c') get_text_console();
	window(1,4,80,21);
	clrscr();
}

/**********************************************************/

void afisareoutput(void)
{
char ch;

	window(22,19,45,22);
	border();
	gotoxy(3,1);cputs(" Alegeti destinatia ");
	gotoxy(3,2);cputs("Fisier");
	gotoxy(3,3);cputs("Consola");
	textcolor(4);
	gotoxy(3,2);cputs("F");
	gotoxy(3,3);cputs("C");
	textcolor(15);
	ch=getch();
	if (ch=='f') put_text_file();
	if (ch=='c') put_text_console();
	window(1,4,80,21);
	clrscr();
}

/**********************************************************/

void afisareoptiuni(void)
{
char ch;
	window(37,17,60,22);
	border();
	gotoxy(4,1);cputs(" Alegeti operatia ");
	gotoxy(3,2);cputs("Codare");
	gotoxy(3,3);cputs("Decodare");
	gotoxy(3,4);cputs("Codare pas cu pas");
	gotoxy(3,5);cputs("Decodare pas cu pas");
	textcolor(4);
	gotoxy(3,2);cputs("C");
	gotoxy(3,3);cputs("D");
	gotoxy(4,4);cputs("o");
	gotoxy(4,5);cputs("e");
	textcolor(15);
	ch=getch();
	if (ch=='c') {window(1,4,80,22);clrscr();codare_Huff();}
	if (ch=='d') {window(1,4,80,22);clrscr();decodare_Huff();}
	window(1,4,80,22);
	clrscr();
}

/**********************************************************/

void prezentare()
{
int i;
struct text_info cw;
float suma, sirtemp[8];
char ch;
	afisareheader();
	window(1,4,80,22);
	border();
	gotoxy(15,10);cputs("Aceasta este o demonstratie pentru codarea Huffman");
	gotoxy(22,12);cputs("Apasati o tasta pentru a continua ...");
	getch();
	clrscr();
	afisareheader();
	afisaremeniu();
do {
	ch=getch();
	if (ch=='i') afisareinput();
	if (ch=='e') afisareoutput();
	if (ch=='o') afisareoptiuni();
	if (ch=='s') {
				  window(31,10,49,12);
				  clrscr();
				  border();
				  gotoxy(3,1);cputs(" S-a terminat! ");
				  gotoxy(2,2);
				  for(i=1;i<=16;i++) {printf("%c",1);delay(62);}
				  clrscr();
				  exit(0);
				 }
	window(1,4,80,22);
	clrscr();
   } while (1);
}

/**********************************************************/

void main(void)
{
	clrscr();
	prezentare();
}