/* ===================================================================*\



  filename: huffman_code.c

  THIS PROGRAM IS DESIGNED TO DETERMINE THE COMPRESSION RATIO
  ACHIEVED WHEN A FILE IS COMPRESSED USING HUFFMAN CODING.

  PROGRAMMER:  RiNN
  INSTRUCTOR:  Dr. Robert Sczech 
  Class:       CS102 S98
  Date:        Monday April 13, 1998 

\*=====================================================================*/

#include                   //iostream Header
#include                     //assert   Header
#include                    //fstream  Header

//Type Declarations

struct listnode{
    char data; 
    listnode* next;
 };
typedef listnode* list;

struct treenode{
    char letter;
    int number;
    list code;
    treenode *left, *right;
 };
typedef treenode* tree;

struct slistnode{
    tree treeptr;
    slistnode* next;
 };
typedef slistnode* slist;

//GLOBAL VARIABLES
 const int MAX = 128;
 int frequency[MAX];
 slist decodelist;
 tree decodetree;
 list encode[MAX];                         //ENCODE TABLE

 void init();                              //initializations
 void insert(slist &s, int i, int j);      //insert into sorted list
 void tinsert(slist &s, tree t);           //insert tree into sorted list
 void printfreqtable();                    //Print table - debugging
 void printdecodelist();                   //Debugging
 void printencodetable();
 void printlist(list l);
 void print(tree t);

//UTILITY FUNCTIONS
 tree slistpop(slist &s);
 int slistlength(slist s);
 int listlength(list s);
 void listappend(list &l, char c);
 void listcopy(list source, list &dest);
 void decodelist2tree();                   //Converts decodelist to tree
 void decode2encode(tree t);               //Create table from decode tree

 
 int main(int argc, char *argv[]){
     init();
     ifstream file(argv[1]);
     if (file){
         char c;
         while(file.get(c)) 
            frequency[c]++;
         file.close();
     }
     else
        cerr << "' " << argv[1] << "' is not a valid filename" << endl;
    for(int i=0; i 0)
           insert(decodelist, i, frequency[i]);
    decodelist2tree();
    decode2encode(decodetree);
    printencodetable();
    double count = 16 * 128;               //count output bits+overhead
    double incount = 0.0;                  //count input bits
    for(i=0; iletter=(char)i;
  t->number=j;
  t->code=NULL;
  t->left=NULL;
  t->right=NULL;
  tinsert(s, t);
 }

 void tinsert(slist &s, tree t){
  if(s == NULL){
   s =new slistnode;  s->treeptr = t;
   s->next = NULL;
  }
  else if(t->number <= s->treeptr->number){
    slist q=new slistnode;
    q->next = s;
    q->treeptr = t;
    s = q;
  }
 else tinsert(s->next, t);
 }

 void printfreqtable(){
  char ch;
  for(int i=0; i0){
     ch=i;
     cout << ch << "     " << frequency[i] << endl;
  }
 }

 void printdecodelist(){
  slist sl=decodelist;
  while(sl !=NULL){
    cout << sl->treeptr->letter << ", " << sl->treeptr->number << endl;
    sl = sl->next;
  }
 }

 void printencodetable(){
  char ch;
  for(int i=0; idata;
    l = l->next;
  }
  cout << endl;
 }

 void print(tree t){
  if(t !=NULL){
   print(t->left);
   cout << t->number << endl;
   print(t->right);
  }
 }

 tree slistpop(slist &s){
  assert(s !=NULL);
  slist sl = s;
  s = s->next;
  tree t = sl->treeptr;
  delete sl;
  return t;
 }

 int slistlength(slist s){
  int count = 0;
  while(s !=NULL){
    count++;
    s = s->next;
  }
  return count;
 }

 int listlength(list s){
  int count = 0;
  while(s !=NULL){
    count++;
    s = s->next;
  }
  return count;
 }

 void listappend(list &l, char c){
  if(l !=NULL)
    listappend(l->next,c);
  else{
    l = new listnode;
    l->data = c;
    l->next = NULL;
  }
 }

 void listcopy(list source, list &dest){
  while(source !=NULL){
    listappend(dest, source->data);
    source = source->next;
  }
 }



 void decodelist2tree(){
  tree x, y, t;
   while(slistlength(decodelist)>1){
     x=slistpop(decodelist);
     y=slistpop(decodelist);
     t=new treenode;
     t->left = x;
     t->right = y;
     t->number = ((t->left->number) + (t->right->number));
     tinsert(decodelist, t);
   }
   decodetree = slistpop(decodelist);
 }

 void decode2encode(tree t){
  if(t !=NULL){
   if ((t->left==NULL)){
       encode[t->letter] = t->code;
   }
   else{
       listcopy(t->code, t->left->code);
       listappend(t->left->code,'0');
       listcopy(t->code, t->right->code);
       listappend(t->right->code, '1');
       decode2encode(t->left);
       decode2encode(t->right);
    }
  }
 }