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

/* File compression - Huffman code */
/* Bil Stefanidis */

void insert(int, int);
void swap(int *, int, int);
void bin(int,int);

int removee(void);

int aa[42] ;
int p[42], info[42];
int N,L;


FILE *fpi, *fpo;

void main(void){

char a[500];
int val[240] , j ,l,x;
int count[44], count2[44],code[44],len[44];
char i ;
int t,k,t1,t2,flag,cout;
int dad[44];

clrscr();
N=0;

for (i=0;i<=43;i++){
code[i]=0;
count[i]=0;
len[i]=0;
dad[i]=0;
aa[i]=0;

}

i=0;

fpi=fopen("input.txt" , "r");


if (fpi==NULL) { printf("The file dont exist\n");}


for(j=0;j<=201;j++){
a[j]='';
}

for(j=0;j<=130;j++){
val[j]=0;
}

j=0;
while ( !feof(fpi) ) {
fscanf(fpi,"%c",&i);
printf("%c",i);
a[j]=i;
j=j+1;
}
printf("\n\n");

for(j=0;j<=200;j++){
printf("%c",a[j]);

}

getch();
getch();

/* Edw metrame poses fores emfanizetai kathe character se ascII morfh */

for (j=0;j<=200;j++){
printf("a[j]=%d , val[a[j]]=%d \n",a[j],val[a[j]]);
val[a[j]]++;
}

/* Edw arxikopoioume enan counter */

for(j=0;j<=26;j++){
count[j]=0;
}

/* Edw topothetoume tiw metrhseis se enan counter */

count[0]=val[32];
printf("Oi syxnothtes twn xarakthrwn symfwna me to ASCII tous\n");
for(j=97;j<=121;j++){
if (val[j]!=0) {
count[j-96]=val[j];
}
printf(" val[%c]=%d \n",j,val[j]);
getch();
}

/* parousiazoume ta apotelesmata gia tous 26 xarakthres */

printf("Oi syxnothtes twn 26 xarakthrwn tou alfabhtou\n");
for(j=1;j<=26;j++){
printf(" count[%d]=%d \n",j,count[j]);
getch();
}

/* parousiazoume th syxnothta emfanishs tou space */

printf(" sp is appear ");
for (l=0;l<val[32];l++){
printf("%c",'*');
}
/* ------------------ */

/* parousiazoume th suxnothta emfanishs twn allwn xarakthrwn */

printf(" %d times , count[%d]=%d\n",l,0,count[0]);
for (j=97;j<=121;j++){
printf(" %c is appear ",j);
for (l=0;l<val[j];l++){
printf("%c",'*');
}
printf(" %d times , count[%d]=%d\n",l,j-96,count[j-96]);
getch();
}
/* ------------------ */

fclose(fpi);

l=0;
printf("To count2 periexei th syxnothta emfanishs mono twn\n");
printf("xarakthrwn pou yparxoun sto keimeno\n");
for (j=0;j<=26;j++){
if (count[j]!=0) {
count2[l]=count[j];
printf("count2[%d]=%d \n",l,count2[l]);
l++;
}
}
getch();
getch();

/* The finish of character counting */

for (i = 0; i <= 26; i++)
if (count[i]){
insert(count[i],i);

}

t1=t2=0;
N=N-1;
L=N-1;
for ( ; !empty(); i++) {

/* ta t1, t2 exoun tis theseis me tis mikroteres syxnothtes */

t1=removee();
printf("t1=%d \n",t1);
getch();
t2=removee();
printf("t2=%d \n",t2);
getch();

printf("\narxizei h dhmiourgia twn dendrwn\n");
printf("\nDhmiourgia stoixeiou .........%d......(ftanei ws to 44)\n",i);
dad[i] = 0;
printf("dad[%d]=%d \n",i,dad[i]);
getch();
dad[t1] = i;
printf("dad[%d]=%d \n",t1,dad[t1]);
getch();
dad[t2] = -i;
printf("dad[%d]=%d \n",t2,dad[t2]);

count[i] = count[t1] + count[t2];
printf("\nTo t1 kai t2 einai ta paidia tou dendrou\n ");
printf("To i einai h riza (pateras) tou dendrou\n ");
printf("kai ta count einai oi suxnothtes tous\n");

printf("t1=%d , t2=%d , i=%d , count[%d]=%d , count[%d]=%d , count[%d]=%d \n",
t1,t2,i,t1,count[t1],t2,count[t2],i,count[i]);

N=N+2;
if (N==17){dad[N+1]=0;flag=1;aa[N+1]=aa[N];info[N+1]=info[N];p[N+1]=p[N];}
if (flag){flag=0;aa[N]=aa[N-1];info[N]=info[N-1];p[N]=p[N-1];}
N=N-2;
N=N+1;



if (!empty())
insert(count[i], i);
N=N-1;

if (i>30) printf("\nprosoxh meta to 30 de fainontai ola ta apotelesmata\n\n");
for (j=0;j<=43;j++){
if (i<30) {
printf("\nO count exei tis syxnothtes olwn twn xarakthrwn tou alfabhtoy\n");
printf("me 27o to space\n");
printf("O info exei tis xyxnothtes twn xarakthrwn pou den einai 0\n");
printf("count[%d]=%d , info[%d]=%d , aa[%d]=%d\n",j,count[j],j,info[j],j,aa[j]);
getch();
}

}


}
printf("Edw parousiazontai oles oi rizes twn korufwn\n");
for (i=0;i<=43;i++){
printf("dad[%d]=%d \n",i,dad[i]);
getch();
}


for (k = 0; k <=26 ; k++) {
i = 0;
x = 0;
j = 1;
if (count[k])
for (t=dad[k]; t; t=dad[t], j+=j, i++)
if (t < 0) {
x += j;
t = -t;
}
code[k] = x;
len[k] = i;
}


for (k=0;k<26;k++){
printf("k=%d , code[%d]=%d , len[%d]=%d \n",k,k,code[k],k,len[k]);
}


/* for (j = 0; j < 26; j++)
for (i = len[index(a[j])]; i > 0; i--) {
cout << ( (code[index(a[j])] >> i-1) & 1);
printf("%b",cout);
} */

printf("\nEdw parousiazetai h telikh kwdikopoihsh\n");
printf("sp 0 ");bin(code[0],len[0]);printf(" %d",len[0]);
printf("\n");
for (j=1;j<=26;j++){
if ( (code[j]) || ( (!code[j]) && (count[j]!=0) ) ){
printf("%c %d ",j+96,j);bin(code[j],len[j]);printf(" %d",len[j]);
printf("\n");
}
}
getch();getch();
}


/* H bin metatrepei se dyadiko */

void bin(x,len){
unsigned int MASK = 0X800 ;
char mas[500];
int ll,i,size;

i=0;
for (;MASK;) {mas[i++]=( (MASK & x ) ? '1' : '0') ; MASK >>= 1;}
size=i;
ll=size-len;
for (i=ll;i<=size-1;i++){printf("%c",mas[i]);}

getch();
}


int index(char xx) {
if (xx=='') return 0;
else return xx;
}

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



void insert(int x, int v) {

/* aa take the value the position of element */
/* info take the frequency of element */

printf("x=%d v=%d \n",x,v);
getch();

aa[N] = v;


p[x]= N;
info[N] = x;

/* printf("aa[%d]=%d , p[%d]=%d ,info[%d]=%d \n",N,aa[N],x,p[x],N,info[N]);
getch(); */
N=N+1;
}


void change(int x, int v) {
aa[p[x]] = v;
}

int search(){
int j;


}


/* remove smallest */

int removee(void){
int j, min = 0,flag;

printf("L=%d, N=%d\n",L,N);
for (j = N-1; j >= 1; j--)
if (info[j] < info[min])
min = j;

swap(aa, min, N);
swap(info, min, N);
p[info[min]] = min;

return aa[N--];
}

int empty() {
return (N <= 0);
}

void swap(int bn[], int ii,int jj){
int temp;

temp=bn[ii];
bn[ii]=bn[jj];
bn[jj]=temp;
}