#include<stdlib.h>
#include<stdio.h>
#include<string.h>

typedef struct treenode
{
 float freq;
 char data[10];
 struct treenode *left,*right;
}treenode;

typedef struct node
{
 treenode *data; 
 struct node *next;
}node;

node *insert(node *,treenode *);
treenode *create();
void encode();
void decode(treenode *);
int n=0;
char alphabets[30][10];
char codes[30][10];

void preorder(treenode *p,int i ,char word[])
 {
 if(p!=NULL)
    {
  if(p->left==NULL && p->right==NULL)
     {
   word[i]=0;
   printf("\n%s --- %s",p->data,word);
                        strcpy(alphabets[n],p->data);
   strcpy(codes[n++],word);
     }
  word[i]='0';
  preorder(p->left,i+1,word);
  word[i]='1';
  preorder(p->right,i+1,word);
    }
 }

void main()
 {
 int op;
 char word[10];
 treenode *root=NULL;
 do
    {
  printf("\n\n1)Create Huffman Tree ");
  printf("\n2)Encode a Message ");
  printf("\n3)Decode a message ");
  printf("\n4)Quit");
  printf("\nEnter Your Choice : ");
  scanf("%d",&op);
  switch(op)
     {
   case 1: root=create();
    printf("\nPrefix codes : \n");
    preorder(root,0,word); 
    break;
   case 2: encode(); break;
   case 3: decode(root);break;
     }
    }while(op!=4);
}

treenode *create()
{
 treenode *p,*t1,*t2;
 node *head;
 int n,i;
 char x[10];
 float probability;
 head=NULL;      
 printf("\nEnter No. of alphabets :");
 scanf("%d",&n);
 for(i=0;i<n;i++)
    {
  
  printf("\nEnter alphabet :");
  scanf("%s",x);
  printf("\nEnter frequency :");
  scanf("%f",&probability);
 
  p=(treenode*)malloc(sizeof(treenode));
  p->left=p->right=NULL;
  strcpy(p->data,x);
  p->freq=probability;
  head=insert(head,p);
   }
 
 for(i=1;i<n;i++)
    {
  t1=head->data;        
  t2=head->next->data;  
  head=head->next->next; 
  p=(treenode *)malloc(sizeof(treenode));
  p->left=t1;
  p->right=t2;
  p->freq=t1->freq+t2->freq;
  head=insert(head,p); 
    }
  
 return(head->data);

} 
 
node *insert(node *head,treenode *t)
{ 
 node *p,*q;
 p=(node *)malloc(sizeof(node));
 p->data=t;
 p->next=NULL;
 if(head==NULL) 
  return(p);
 if(t->freq<head->data->freq)
    {
  p->next=head;
  return(p);
    }
 
 q=head;
 while(q->next!=NULL && t->freq>q->next->data->freq)
  q=q->next;
 p->next=q->next;
 q->next=p;
 return(head);
}

void encode()
{
 char word[30],temp[30];
        int i,j;
 //flushall();
        for(i=0;i<n;i++)
         temp[i]=alphabets[i][0];
        temp[i]='\0';
 printf("\n Enter a Message : ");
 scanf("%s",word);
 printf("\n Encoded Message :");
 for(i=0;word[i]!='\0';i++)
   {
                  for(j=0;j<n;j++) 
                   {
   if(temp[j]==word[i])
    printf("%s",codes[j]);
                    }
   }
          
}

void decode(treenode *p)
{
 char word[90];
        int i;treenode *q;
 //flushall();
 printf("\nEnter an Encoded message : ");
 scanf("%s",word);
 q=p;i=0;
 printf("\nDecoded Message = ");
 while(word[i]!='\0')
    {
  if(word[i]=='0')
   q=q->left;
  else
   q=q->right;
  if(q->left==NULL && q->right==NULL)
      {
   printf("%s",q->data);
   q=p;
      }
  i++;
    }

}
/*
[ProfessionalCipherwww.professionalcipher.blogspot.com]$ 
[ProfessionalCipherwww.professionalcipher.blogspot.com]$ gcc huf.c
[ProfessionalCipherwww.professionalcipher.blogspot.com]$ ./a.out


1)Create Huffman Tree 
2)Encode a Message 
3)Decode a message 
4)Quit
Enter Your Choice : 1

Enter No. of alphabets :6

Enter alphabet :d

Enter frequency :0.1

Enter alphabet :-

Enter frequency :0.2

Enter alphabet :b

Enter frequency :0.35

Enter alphabet :e

Enter frequency :0.4

Enter alphabet :a

Enter frequency :0.5

Enter alphabet :c

Enter frequency :0.5

Prefix codes : 

e --- 00
c --- 01
a --- 10
d --- 1100
- --- 1101
b --- 111

1)Create Huffman Tree 
2)Encode a Message 
3)Decode a message 
4)Quit
Enter Your Choice : 
*/