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

#define MAXLEN 10

typedef struct
{ 
 char elem;
 unsigned int m_weight; 
 unsigned int parent,lchild,rchild; 
}HTNode,HuffmanTree; 

typedef char HuffmanCode; 

typedef struct _Weight
{
 char elem; 
 unsigned int m_weight; 
}Weight; 

void Print_Menu();
int  Initialize(HuffmanTree&, HuffmanCode&);
void HuffmanCoding(HuffmanTree&,HuffmanCode&,Weight,int); 
void Coding(HuffmanTree& HT,HuffmanCode& HC,int n);
void Select(HuffmanTree&,int,int,int); 
void OutputHuffman(HuffmanTree,HuffmanCode,int); 
int  Write_hfmTree_to_file(HuffmanTree,HuffmanCode,int );
int  Encoding(HuffmanTree&,HuffmanCode&);
int  Findchar(HuffmanTree,char,int);
int  Print();
int  Decoding(HuffmanTree,int);

void main() 
{ 
 char cX;
 int n;
 HuffmanTree HT = NULL; 
 HuffmanCode HC = NULL; 
 
 while(1)
 {
  Print_Menu();
  
  scanf(%1s,&cX);
  getchar();
  if(cX == 'Q') 
  {
   printf(Bye!n);
   break;
  }
        
        switch(cX)
  {
  case 'I'  n = Initialize(HT,HC); break;
  case 'E'  n = Encoding(HT,HC); break;
  case 'P'  Print(); break;
  case 'D'  Decoding(HT,n); break;
  case 'T'  OutputHuffman(HT,HC,n); break;
  default   printf(Input Error!); break;
  }
  
 }
 
 
} 

void Print_Menu()
{
 printf(n Huffman Arithmetic Demonstration );
    printf(nI---Initialize     E---Encoding   P---Print);
    printf(nT---Tree printing  D---Decoding   Q---Quit program);
 printf(n                                                       Codz By EvilCat);
    printf(n Huffman Arithmetic Demonstration );
 printf(nPlease choose a menu item and press enter to continue.n);
}

int Initialize(HuffmanTree& HT,HuffmanCode &HC)
{
 Weight w; 
 char c; 
 int i,n;    
 int wei;   
 printf(Please input the value of n  ); 
 scanf(%d,&n); 
 w = (Weight)malloc((n+1)  sizeof(Weight)); 
 for(i = 1; i = n; i++)
 { 
  printf(Input the element); 
  scanf(%1s,&c); 
  printf(Input its weight);
  scanf(%d,&wei);
  w[i].elem = c; 
  w[i].m_weight = wei; 
 } 
 
 HuffmanCoding(HT,HC,w,n);
 Write_hfmTree_to_file(HT,HC,n);
 return n;
}

void HuffmanCoding(HuffmanTree &HT,HuffmanCode& HC,Weight w, int n)
{
 int m,i,s1,s2;
 if(n = 1) return;
 m = 2  n - 1;
 HT = (HuffmanTree)malloc((m+1)  sizeof(HTNode));
 for( i = 1; i = n; ++i)
 {
  HT[i].elem = w[i].elem;
  HT[i].m_weight = w[i].m_weight;
  HT[i].parent = 0;
  HT[i].lchild = 0;
  HT[i].rchild = 0;
 }
 for(; i = m; ++i)
 {
  HT[i].elem = '0';
  HT[i].m_weight = 0;
  HT[i].parent = 0;
  HT[i].lchild = 0;
  HT[i].rchild = 0;
 }
 for( i = n + 1; i = m; ++i)
 {
  Select(HT,i-1,&s1,&s2);
  HT[s1].parent = i; HT[s2].parent = i;
  HT[i].lchild = s1; HT[i].rchild = s2;
  HT[i].m_weight = HT[s1].m_weight + HT[s2].m_weight;
 }
 Coding(HT,HC,n);
 
}

void Coding(HuffmanTree& HT,HuffmanCode& HC,int n)
{
 int i,start,c,f; 
 char cd;
 HC = (HuffmanCode)malloc((n + 1)  sizeof(char));
 cd = (char)malloc(n  sizeof(char));
 cd[n-1] = '0';
 for(i=1;i=n;++i)
 { 
  start=n-1; 
  for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
  { 
   if(HT[f].lchild == (unsigned int)c) cd[--start]='0'; 
   else cd[--start]='1'; 
  } 
  
  HC[i]=(char )malloc((n-start)sizeof(char));
  strcpy(HC[i],&cd[start]); 
 } 
 free(cd);
}

void Select(HuffmanTree& HT,int n,int s1,int s2) 
{ 
 int i; 
 (s1) = (s2) = 0; 
 for(i = 1;i = n;i++)
 { 
  if(HT[i].m_weight  HT[(s2)].m_weight&&HT[i].parent == 0&&(s2)!=0)
  { 
   if(HT[i].m_weightHT[(s1)].m_weight)
   { 
    (s2) = (s1); 
    (s1) = i; 
   } 
   else (s2) = i; 
   
  } 
  
  if(((s1) == 0(s2) == 0)&&HT[i].parent == 0)
  { 
   if((s1) == 0) (s1) = i; 
   else if((s2) == 0)
   { 
    if(HT[i].m_weightHT[(s1)].m_weight)
    { 
     (s2) = (s1); 
     (s1) = i; 
    } 
    else (s2) = i; 
   } 
  }  
 } 
 
 if((s1)  (s2))
 { 
  i = (s1); 
  (s1) = (s2); 
  (s2) = i; 
 } 
 return; 
} 

void OutputHuffman(HuffmanTree HT,HuffmanCode HC,int n) 
{ 
 FILE fp;
    fp = fopen( TreePrint.txt, w );
 if(!HT&&!HC)
 {
  printf(Please Initialize First!n);
  return;
 }
 
 int i; 
 printf(Number--Element--Weight--Parent--Lchild--Rchildn);
 fprintf(fp,Number--Element--Weight--Parent--Lchild--Rchildn);
 for(i = 1;i = 2  n - 1;i++) 
 {
  printf(%3d%8c%8d%8u%8u%8un,i,HT[i].elem,HT[i].m_weight,HT[i].parent,HT[i].lchild,HT[i].rchild); 
  fprintf(fp,%3d%8c%8d%8u%8u%8un,i,HT[i].elem,HT[i].m_weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
 }
 fclose(fp);
}  

int Write_hfmTree_to_file(HuffmanTree HT,HuffmanCode HC,int n)
{
    FILE fp;
    fp = fopen( hfmTree.txt, w );
 fprintf(fp,%dn,n);
 for( int i = 1; i  2n; i++)
 {
  fprintf( fp,
   %c %u %u %u %un, 
   HT[i].elem, HT[i].m_weight, HT[i].parent, HT[i].lchild, HT[i].rchild );
 }
    fclose( fp );
 return 1;
}

int Encoding(HuffmanTree& HT,HuffmanCode& HC)
{
 int m,n,c;
 char x;
 FILE tfp,sfp,dfp;
    
 if(!HT&&!HC)
 {
  if((tfp = fopen( hfmTree.txt, r )) == NULL)
  {
   printf(cannot open hfmTree.txtn);
   return 0;
  }
  
  fscanf(tfp,%dn,&n);
  m = 2  n - 1; 
  HT = (HuffmanTree)malloc((m+1)sizeof(HTNode));
  for(int i = 1; i  2  n; i++)
  {
   fscanf(tfp,
    %c %u %u %u %un, 
    &HT[i].elem, &HT[i].m_weight, &HT[i].parent, &HT[i].lchild, &HT[i].rchild );
  }
  
  Coding(HT,HC,n);
  fclose(tfp);
 }
 
 if((tfp = fopen( hfmTree.txt, r )) == NULL)
 {
  printf(cannot open hfmTree.txtn);
  return 0;
 }
 
 fscanf(tfp,%dn,&n);
 
 if((sfp = fopen( ToBeTran.txt, r )) == NULL)
 {
  printf(cannot open ToBeTran.txtn);
  return 0;
 }
 dfp = fopen( CodeFile.txt, w );
 
 while((x = fgetc(sfp)) != -1)
 {
  c = Findchar(HT,x,n);
  fputs(HC[c],dfp);
  
 }
 
    fclose(tfp);
 fclose(sfp);
 fclose(dfp);
 return n;
}

int Findchar(HuffmanTree HT,char x,int n)
{
 int i = 1;
 while( x != HT[i].elem && i = n )
 {
  i++;
 }
 if( i  n ) return 0;
 else return i;
}

int Print()
{
 char x;
 int counter = 0;
 FILE sfp,dfp;
 
 if((sfp = fopen( CodeFile.txt, r )) == NULL)
 {
  printf(cannot open CodeFile.txtn);
  return 0;
 }
 dfp = fopen( CodePrin.txt, w );
    
 while((x = fgetc(sfp)) != -1)
 {
  
  if(counter != 0 && counter % MAXLEN == 0) 
  {
   printf(n);
   fputc('n',dfp);
  }
  printf(%c,x);
  fputc(x,dfp);
  counter++;
  
 }
 
 fclose(sfp);
 fclose(dfp);
 return 1;
}

int Decoding(HuffmanTree HT,int n)
{
 int t = 2  n - 1;
 char x;
 FILE sfp,dfp;
 
 if(!HT)
 {
  printf(Please Initialize First!n);
  return 0;
 }
    
 if((sfp = fopen( CodeFile.txt, r )) == NULL)
 {
  printf(cannot open CodeFile.txtn);
  return 0;
 }
 dfp = fopen( TextFile.txt, w );
 
 while(1)
 {
  if(HT[t].lchild!=0)
  {
   x = fgetc(sfp);
   if(x == '0')
    t = HT[t].lchild;
   else if(x == '1') 
    t = HT[t].rchild;
   else break;
  }
  else 
  {
   printf(%c,HT[t].elem);
   fputc(HT[t].elem,dfp);
   t = 2  n-1;
  }
 }
 fclose(sfp);
 fclose(dfp);
 return 1;
}