Dynamic Huffman Coding

#include<stdio.h>
#include<conio.h>
#include<ctype.h>
#include<math.h>
#define max 50 
#define ascmax 130


struct tree
{
  int posn;     
  char ct;
  int frq;     
  int rgt;     
  int lft;       
}tr[ascmax+max];






int size =2;
int epos;




void init_node(char tmp)
{
  tr[0].posn = 1;
  tr[0].ct = '~'; 
  tr[0].lft = 1;
  tr[0].rgt = 2;
  tr[0].frq = 1; 
  
  tr[1].posn = 2*tr[0].posn;
  tr[1].ct = 'E';
  tr[1].frq = 0;
  
  tr[2].posn = 2*tr[0].posn+1;
  tr[2].ct = tmp;
  tr[2].frq = 1;
    
  tr[1].lft = tr[2].lft = -1;
  tr[1].rgt = tr[2].rgt = -1;  


  epos = 1;
  
  printf("\n '%c'\t\t '%c'",tmp,tmp);
  printf("\n Traversing :- ('E',0) ('%c',1)",tmp); 
  printf("\n The Tree is in weight order\n"); 
}






void add_node(char ctc)
{
 char bits[max];
 int bsize=0,ps,j; 

 printf("\n '%c'\t\t '%c' ",ctc,ctc);
 int tp = tr[epos].posn;
 while(tp > 1)
 {
   bits[bsize] = 48+(tp%2);
   tp /= 2;      
   ++bsize;         
 }  
 for(tp=bsize-1;tp>=0;tp--)
  printf("%c",bits[tp]); 

 ++size;
 tr[size] = tr[epos];
 tr[size].posn = 2*tr[epos].posn;
 tr[size].lft = -1;    
 tr[size].rgt = -1;    



 tr[epos].ct = '^';
 tr[epos].frq = 1;    
 tr[epos].lft = size;    
 tr[epos].rgt = size+1;    




 epos = size;

 ++size;

 tr[size].posn = tr[epos].posn+1;
 tr[size].ct = ctc;
 tr[size].frq = 1;
 tr[size].lft = -1;
 tr[size].rgt = -1;  

 ps = (tr[size].posn/2)/2;
  

  
  while(ps >= 1)
  {
   j = 0;
   while(tr[j].posn != ps)
    j++;
   
   tr[j].frq += 1;         
   ps /= 2;           
  }  



}




void update_node(char ctc)
{
  char bits[max];
 int bsize=0;    

  int i=1,j;
  int ps;
  while(ctc != tr[i].ct)
   i++; 
    
  tr[i].frq += 1;
  
  ps = tr[i].posn/2;
  

  
  while(ps >= 1)
  {
   j = 0;
   while(tr[j].posn != ps)
    j++;
   

   tr[j].frq += 1;         
   ps /= 2;           
  }  
  
  printf("\n '%c'\t\t   ",ctc);
 int tp = tr[i].posn;
 while(tp > 1)
 {
   bits[bsize] = 48+(tp%2);
   tp /= 2;      
   ++bsize;         
 }  
 for(tp=bsize-1;tp>=0;tp--)
  printf("%c",bits[tp]); 

}


void reset_node(int nm)
{
 ///printf("\n\n %c/%d(pos=%d)",tr[nm].ct,tr[nm].frq,tr[nm].posn);    
 if(tr[nm].ct == 'E')
  epos = nm;
  
 if(tr[nm].lft != -1)
 {
   //printf("\n Lft Case");            
   tr[tr[nm].lft].posn = 2*tr[nm].posn;
   reset_node(tr[nm].lft);        
 }

 if(tr[nm].rgt != -1 )
 {
   //printf("\n Rgt Case");
   tr[tr[nm].rgt].posn = 2*tr[nm].posn+1;
   reset_node(tr[nm].rgt);      
 }
     
}


void balance_tree()
{
  //printf("\n%d",tr[epos].posn);
  struct tree tn;
  double lvl;
  int i,ilvl,j,ind;
  int optnsize;
  int init; 
  //= tr[epos].posn;
  
  struct outptn
  {
   int psn;
   int frq;      
  }optn[ascmax+max];
  
 do
 {
  optnsize = 0;
  //printf("\n %d %d %c",epos,tr[epos].posn,tr[epos].ct);
  
  lvl = log((double)tr[epos].posn)/log (2);
  ilvl = (int) lvl;
  init = tr[epos].posn;
  
 // printf("\n level=%d ",ilvl);
  while(ilvl>0)
  {
    for(i=init;i<=pow(2,ilvl+1)-1;i++)
    {
      j = 0;
      while(j<=size && tr[j].posn != i)
       j++;    
      if(j<=size)
      {
        optn[optnsize].psn = j;
        optn[optnsize].frq = tr[j].frq;
        ++optnsize;         
      }        
    }    
    --ilvl;     
    init = pow(2,ilvl);          
  }
    
  optn[optnsize].psn = 0;
  optn[optnsize].frq = tr[0].frq;
  ++optnsize;      
  
  ind = -1;
  printf("\n Traversing :-");
  for(i=0;i<optnsize;i++)  
  {
    printf(" ('%c',%d)",tr[optn[i].psn].ct,optn[i].frq);
     if(i < optnsize-1 && optn[i].frq > optn[i+1].frq && ind == -1)
       ind = i;   
  } 
  
  if(ind != -1)
  {
   printf("\n The Tree is not in weight order");     
   
   int ind2 = ind+1;
   
   while(optn[ind2].frq == optn[ind2+1].frq)
    ind2++;
   
   while(optn[ind].frq == optn[ind-1].frq)
    ind--;
    
   printf("\n Swapping ('%c',%d) and ('%c',%d)",tr[optn[ind].psn].ct,optn[ind].frq,tr[optn[ind2].psn].ct,optn[ind2].frq);
   
   int tmp = tr[optn[ind].psn].posn;
     tmp /= 2;
     int k=0;
   
     while(tr[k].posn != tmp)
      k++;
      
   tmp = tr[optn[ind2].psn].posn;
     tmp /= 2;
     int l=0;
     while(tr[l].posn != tmp)
      l++;
     
      
     if(tr[optn[ind].psn].posn%2 == 0)
     {
      tmp = tr[k].lft;                           
      tr[k].lft = optn[ind2].psn;
      if(tr[optn[ind2].psn].posn%2 == 0)
      {
       tr[l].lft = tmp;  
       tr[tr[l].lft].posn = 2*tr[l].posn;
      }
      else
      { 
       tr[l].rgt = tmp;
       tr[tr[l].rgt].posn = 2*tr[l].posn+1;
      }
      tr[tr[k].lft].posn = 2*tr[k].posn;
     }
     
     else
     {
      tmp = tr[k].rgt;                           
      tr[k].rgt = optn[ind2].psn;
      if(tr[optn[ind2].psn].posn%2 == 0)
      {
       tr[l].lft = tmp;  
       tr[tr[l].lft].posn = 2*tr[l].posn;
      }
      else
      { 
       tr[l].rgt = tmp;
       tr[tr[l].rgt].posn = 2*tr[l].posn+1;
      }
      tr[tr[k].rgt].posn = 2*tr[k].posn+1;
     }
     
     

   reset_node(optn[ind].psn);
   reset_node(optn[ind2].psn);     
   
   for(j=size;j>=0;j--) 
   {
     if(tr[j].ct == '~' || tr[j].ct == '^') 
       tr[j].frq = tr[tr[j].lft].frq + tr[tr[j].rgt].frq ;              
   }    
  }
  else
   printf("\n The Tree is in weight order");  
  optnsize = 0;
 }while(ind != -1);
 printf("\n");
}




int main()
{
 char msg[max]; 
 printf("\n Enter the string : "); 
 gets(msg);
 printf("\n Dynamic Huffman Coding \n");
 printf("\n Input\t\t Output");
 printf("\n -----\t\t ------\n");
  int i=1;
 int j; 
 init_node(msg[0]);
 while(msg[i]!='\0')
 {
   j=i;
   do
   {
     --j;  
   }while(j>=0 && msg[j] != msg[i]);     
   if(j>=0)
    update_node(msg[i]);
   else
    add_node(msg[i]);
   balance_tree();
  i++;   
  getch(); 
 }
 getch();
 return 0;   
}