#include<stdio.h>
#include<conio.h>
#define NULL 0


struct HUFFMEN
{
 int data;
 int freq;
 char symb;
 int hfbit;
 struct HUFFMEN *left;
 struct HUFFMEN *right;
 struct HUFFMEN *parent;
};

typedef struct HUFFMEN nodeptr;
nodeptr *head;

void h_code(int *,int);
nodeptr * getnode();
void code_generate(char *,int);

static nodeptr *leafarr[15],*tstack[15];

void main()
{
 int choice,no,i,freq[20];
 char symb[20];
 clrscr();

 while(1)
 {
   printf("\n ******* Menu ********");
   printf("\n 1 Create Huffmen Code.");
   printf("\n 2 Display Huffmen Code.");
   printf("\n 0 Exit ");
   printf("\n ********************* ");
   printf("\n Enter the Choice =>");
   scanf("%d",&choice);

   switch(choice)
   {
	case 1:
		   printf("\n Enter How Many Symbol's => ");
		   scanf("%d",&no);
		   for(i=0;i<no;i++)
		   {
			 printf("\n Enter The %d'th Symbol  ->  ",i+1);
			 flushall();
			 scanf("%c",&symb[i]);
			 flushall();
			 printf("\t Enter it's Frequency -> ");
			 scanf("%d",&freq[i]);
		   }

		h_code(freq,no);

		break;
	case 2:
		printf("\n ----*-- HUFFMEN CODE --*---- \n");
		code_generate(symb,no);
		break;
	case 0:
		exit(0);
		break;
	default:
		printf("\n Wrong Choice. ");
		break;
   }
 }
}

nodeptr * getnode()
{
  nodeptr *temp;

  temp=(nodeptr *)malloc(sizeof(nodeptr));
  temp->left=temp->right=temp->parent=NULL;

  temp->data=NULL;
  temp->freq=NULL;
  temp->symb=NULL;

  return(temp);
}

void h_code(int arr[],int no)
{
 int t=10000,indx1,indx2,i;           // here, 10000 is considered as MAX value
 int min[3];
 nodeptr *root,*temp1,*temp2;

  while(1)
  {
	t=10000;

	for(i=0;i<no;i++)
	{
	  if(arr[i]<t && arr[i]!=0)
	  {
		t=arr[i];
		indx1=i;
	  }
	}
	min[0]=t;
	arr[indx1]=0;

	t=10000;

	for(i=0;i<no;i++)
	{
	  if(arr[i]<t && arr[i]!=0)
	  {
		t=arr[i];
		indx2=i;
	  }
	}
	min[1]=t;
	arr[indx2]=0;

	if(min[1]==10000)
	   return;

	min[2] = min[0] + min[1] ;

	arr[indx2] = min[2] ;     // Addition of 2 min no's is again added to arr

	  if(tstack[indx1]==0)
	  {
		temp1 = getnode();
		temp1->data = min[0];
		leafarr[indx1]=temp1;
	  }
	  else
		temp1 = tstack[indx1];

	  temp1->hfbit=0;

	  if(tstack[indx2]==0)
	  {
		temp2 = getnode();
		temp2->data = min[1];
		leafarr[indx2]=temp2;
	  }
	  else
		temp2 = tstack[indx2];

	  temp2->hfbit=1;

		root = getnode();
		root->data = min[2];

		tstack[indx2]=root;
		root->left=temp1;
		root->right=temp2;
		temp1->parent=temp2->parent=root;

  }  // while(1) end

}

void code_generate(char symb[],int no)
{
  nodeptr *moving;
  int i,j,code[15],MBITS=0;

  for(i=0;i<no;i++)
  {
	printf("\n The code for '%c' is ->   ",symb[i]);
	moving=leafarr[i];
	j=0;

		while(moving->parent!=NULL)
		{
		  code[j] = moving->hfbit;
		  moving=moving->parent;
		  j++;
		}
		for(j=j-1;j>=0;j--)
		{
		  printf(" %d ",code[j]);
		  MBITS++;
		}
  }

  printf("\n\n Total Message Bits = %d \n",MBITS);

}