/*Hoffmans algorithm in C Language*/
 #include  
 #include  
 #include  
 #define MAX 26  
 typedef struct str  
 {  
 int freq;  
 char alpha;  
 }str;  
 typedef struct huff  
 {  
 struct str info;  
 struct huff *lc,*rc;  
 }huff;  
 typedef struct sll  
 {  
 int flag;  
 union data  
 {  
 struct huff * addr;  
 struct str info;  
 }data;  
 struct sll *link;  
 }sll;  
 sll *insert(sll *,huff*,sll *);  
 void insertsort(str *,int );  
 sll * createsll(str *);  
 sll * input(str*);  
 huff * huffman(sll *,huff *);  
 void itpost(huff *);  
 huff *freepa(huff *);  
 void leveldis(huff *f);  
 void prefix(huff *,int [],int );  
 void main()  
 {  
 int ch,a[25],i;  
 str *s;  
 sll *f=NULL;  
 huff *pa=NULL;  
 s=(str *)calloc(1,26*sizeof(str));  
 do  
 {  
 clrscr();  
 printf("\n\t\tHUFFMAN TREE CREATION\n\t\t1.INPUT\n\t\t2.HUFFMAN TREE\n\t\t3.DISPLAY\n\t\t4.PREFIX CODE\n\t\t5.LEVEL VISE DISPLAY\n\t\t6.EXIT");  
 printf("\n\t\tENTER UR CHOICE");  
 scanf("%d",&ch);  
 switch(ch)  
 {  
 case 1:  
 printf("INPUT");  
 f=input(s);  
 break;  
 case 2:  
 if(pa!=NULL)  
 pa=freepa(pa);  
 printf("HUFFMAN TREE");  
 pa=huffman(f,pa);  
 printf("HUFFMAN TREE IS CREATED");  
 break;  
 case 3:  
 if(pa==NULL)  
 printf("MAKE HUFFMAN TREE FIRST");  
 else  
 {  
 printf("DISPLAY");  
 itpost(pa);  
 }  
 break;  
 case 4:  
 if(pa==NULL)  
 printf("MAKE HUFFMAN TREE FIRST");  
 else  
 {  
 printf("PREFIX CODE");  
 i=-1;  
 prefix(pa,a,i);  
 getch();  
 }  
 break;  
 case 5:  
 if(pa==NULL)  
 printf("MAKE HUFFMAN TREE FIRST");  
 else  
 {  
 printf("LEVEL VISE DISPLAY");  
 leveldis(pa);  
 }  
 break;  
 }  
 getch();  
 }while(ch!=6);  
 }  
 sll* input(str *s)  
 {  
 sll *f=NULL;  
 char st[100];  
 int k=0,j,i;  
 for(i=0;i<max;i++) <br=""> (s+i)->freq=0;  
 flushall();  
 gets(st);  
 for(i=0;st[i]!=NULL;i++)  
 {  
 if((64<st[i]&&st[i]<91)||(96<st[i]&&st[i]<123)) <br=""> {  
 for(j=0;j<k;j++) <br=""> {  
 if(st[i]==(s+j)->alpha)  
 break;  
 }  
 if(j==k||i==0)  
 {  
 (s+k)->alpha=st[i];  
 (s+k)->freq++;  
 k++;  
 }  
 else  
 {  
 (s+j)->freq++;  
 }  
 }  
 }  
 insertsort(s,k);  
 f=createsll(s);  
 return f;  
 }  
 sll * createsll(str *s)  
 {  
 sll *nw,*t,*f=NULL;  
 int i;  
 for(i=0;(s+i)->freq!=0;i++)  
 {  
 nw=(sll *)malloc(sizeof(sll));  
 nw->flag=0;  
 nw->link=NULL;  
 nw->data.info.freq=(s+i)->freq;  
 nw->data.info.alpha=(s+i)->alpha;  
 nw->link=NULL;  
 if(f==NULL)  
 f=nw;  
 else  
 {  
 t=f;  
 while(t->link!=NULL)  
 t=t->link;  
 t->link=nw;  
 }  
 }  
 return f;  
 }  
 void insertsort(str *a,int n)  
 {  
 int i,j;  
 str temp;  
 for(i=1;i<n;i++) <br=""> {  
 temp.freq=(a+i)->freq;  
 temp.alpha=(a+i)->alpha;  
 for(j=i-1;j>=0&&(a+j)->freq>temp.freq;j--)  
 {  
 (a+j+1)->freq=(a+j)->freq;  
 (a+j+1)->alpha=(a+j)->alpha;  
 }  
 (a+j+1)->freq=temp.freq;  
 (a+j+1)->alpha=temp.alpha;  
 }  
 }  
 huff * huffman(sll *f,huff *pa)  
 {  
 huff *q=NULL,*nw,*lch,*rch,*p;  
 sll *t,*s;  
 while(f!=NULL)  
 {  
 if(f->flag==0)  
 {  
 nw=(huff *)malloc(sizeof(huff));  
 nw->info=f->data.info;  
 nw->lc=nw->rc=NULL;  
 lch=nw;  
 }  
 else  
 lch=f->data.addr;  
 t=f;  
 f=f->link;  
 free(t);  
 if(f!=NULL)  
 {  
 if(f->flag==0)  
 {  
 nw=(huff *)malloc(sizeof(huff));  
 nw->info=f->data.info;  
 nw->lc=nw->rc=NULL;  
 rch=nw;  
 }  
 else  
 rch=f->data.addr;  
 t=f;  
 f=f->link;  
 nw=(huff *)malloc(sizeof(huff));  
 nw->info.freq=lch->info.freq+rch->info.freq;  
 nw->lc=lch;  
 nw->rc=rch;  
 p=nw;  
 p->info.alpha='\0';  
 t->flag=1;  
 t->data.addr=p;  
 t->link=NULL;  
 f=insert(f,p,t);  
 }  
 else  
 p=lch;  
 }  
 q=p;  
 free(t);  
 return(q);  
 }  
 sll *insert(sll *f,huff*p,sll *t)  
 {  
 sll *s;  
 s=f;  
 if(f!=NULL)  
 {  
 if(((p->info.freqdata.info.freq)&&f->flag==0)||((p->info.freqdata.addr->info.freq)&&f->flag==1))  
 {  
 t->link=f;  
 f=t;  
 }  
 else  
 {  
 while(s->link!=NULL)  
 {  
 if(s->link->data.info.freq>t->data.addr->info.freq&&s->link->flag==0)  
 {  
 t->link=s->link;  
 break;  
 }  
 else if(s->link->data.addr->info.freq>t->data.addr->info.freq&&s->link->flag==1)  
 {  
 t->link=s->link;  
 break;  
 }  
 s=s->link;  
 }  
 }  
 }  
 s->link=t;  
 if(s->link==NULL)  
 t->link=NULL;  
 return f;  
 }  
 /*void itpost(huff *root)  
 {  
 huff *t;  
 stack *top,*nw;  
 top=NULL;  
 t=root;  
 while(t!=NULL||top!=NULL)  
 {  
 if(t!=NULL)  
 {  
 nw=(stack*)malloc(sizeof(stack));  
 nw->ad=t;  
 nw->next=top;  
 nw->flag=0;  
 top=nw;  
 t=t->lc;  
 }  
 else  
 {  
 t=top->ad;  
 if(top->flag==0)  
 {  
 top->flag=1;  
 t=t->rc;  
 }  
 else  
 {  
 if(t->lc==NULL&&t->rc==NULL)  
 printf("%c",t->info.alpha);  
 else  
 printf("%d",t->info.freq);  
 nw=top;  
 top=top->next;  
 free(nw);  
 t=NULL;  
 }  
 }  
 }  
 getch();  
 } */  
 huff *freepa(huff *t)  
 {  
 huff *q,*n;  
 if(t!=NULL)  
 {  
 q=t->lc;  
 n=t->rc;  
 if(q->lc==NULL&&q->rc==NULL)  
 q=freepa(q);  
 if(n->lc==NULL&&n->rc==NULL)  
 n=freepa(n);  
 }  
 return q;  
 }  
 void leveldis(huff *f)  
 {  
 huff *queue[MAX],*t;  
 int front=-1,rear=-1,i=-1,pl=0,cl=1;  
 t=f;  
 if(front==-1)  
 front++;  
 rear=(rear+1)%MAX;  
 queue[rear]=t;  
 while(cl!=0||pl!=0)  
 {  
 if(pl==0)  
 {  
 i++;  
 printf("\nELEMENT IN %d LEVEL:",i);  
 pl=cl;  
 cl=0;  
 }  
 t=queue[front];  
 if(front==rear)  
 front=rear=-1;  
 else  
 front=(front+1)%MAX;  
 if(t->info.alpha!='\0')  
 printf("\t%c",t->info.alpha);  
 else  
 printf("\t%d",t->info.freq);  
 if(t->lc!=NULL)  
 {  
 if(front==-1)  
 front++;  
 rear=(rear+1)%MAX;  
 queue[rear]=t->lc;  
 cl++;  
 }  
 if(t->rc!=NULL)  
 {  
 if(front==-1)  
 front++;  
 rear=(rear+1)%MAX;  
 queue[rear]=t->rc;  
 cl++;  
 }  
 pl--;  
 }  
 getch();  
 }  
 void prefix(huff *f,int a[],int i)  
 {  
 huff *t;  
 int m;  
 t=f;  
 i++;  
 if(t!=NULL)  
 {  
 if(t->lc==NULL&&t->rc==NULL)  
 {  
 printf("\nPREFIX OF %c:",t->info.alpha);  
 for(m=0;m<i;m++) <br=""> printf("\t%d",a[m]);  
 printf("\tFREQUENCY:%d",t->info.freq);  
 }  
 if(t->lc!=NULL)  
 {  
 a[i]=0;  
 prefix(t->lc,a,i);  
 }  
 if(t->rc!=NULL)  
 {  
 a[i]=1;  
 prefix(t->rc,a,i);  
 }  
 }  
 }