Huffman Coding.cpp

#include <iostream>
#include <cmath>
using namespace std;
struct node
{
   char info;
   int freq;
   char *code;
   node *Llink;
   node *Rlink;
};

class BinaryTree // Coding Tree
{
  private:
      node *root;
	public:
	    BinaryTree() { root=NULL; }
	    void print();
	    
	    // Symbols with their frequencies are stored in the leaf nodes.
	    // The path from the root to the leaf node is the code of the symbol
	    // By convention, '0' is for left sub-tree and '1' for right sub-tree. 
	    void assign_code(int i);
	    void print_code(char c);
	    void encode(const char str[]);
	    void print_symbol(char cd[], int &f, int length);
	    void decode(char cd[], int size);
	    	    
      friend class minHeap;	
      friend class HuffmanCode;			  			
};

class minHeap
{
    private:
      BinaryTree *T; // Array of Binary Trees
      int n;// Number of symbols
      public:						
        minHeap();
        void heapify(int i); 
        BinaryTree remove(); // Returns the first Binary Tree of the min heap and then 
				// heapify the array of Binary trees in order of the frequencies of their root nodes.
        void insert(BinaryTree b);// To insert another Binary tree 
				// and then heapify the array of Binary trees          
        void print(); // To print the frequencies of the root nodes of the array of Binary Trees
        friend class HuffmanCode; // It can access the private data i.e. the array of Binary Trees       
};

class HuffmanCode 
{
    private:
        BinaryTree HuffmanTree;//A Huffman Tree (a minimum weighted external path length tree) 
														//with symbols as external nodes.
        public:
            HuffmanCode();					   
};

HuffmanCode::HuffmanCode()
{
	minHeap Heap;
	// Huffman Tree is build from bottom to top.
	// The symbols with lowest frequency are at the bottom of the tree 
	// that leads to longer codes for lower frequency symbols and hence
	// shorter codes for higher frequency symbol giving OPTIMAL codelength.
	while (Heap.T[0].root->freq>1)
	{
		// The first two trees with min. priority (i.e. frequency) are taken and		
		BinaryTree l=Heap.remove();
		cout<<"\nAfter removing "<<l.root->freq<<endl;
		Heap.print();
		BinaryTree r=Heap.remove();
		cout<<"\nAfter removing "<<r.root->freq<<endl;
		Heap.print();
		// a new tree is constructed taking the above trees as left and right sub-trees 
		// with the frequency of root node as the sum of frequencies of left and right child.		
		HuffmanTree.root=new node;
		HuffmanTree.root->info='\0';
		HuffmanTree.root->freq=l.root->freq + r.root->freq;
		HuffmanTree.root->Llink=l.root;
		HuffmanTree.root->Rlink=r.root;
		// then it is inserted in the array and array is heapified again.
		// Deletion and Insertion at an intermediate step is facilitated in heap-sort.
		Heap.insert(HuffmanTree);
		cout<<"\nAfter inserting "<<l.root->freq<<"+"<<r.root->freq<<"= "<<HuffmanTree.root->freq<<endl;
		Heap.print();	
	}
	//The process continues till only one tree is left in the array of heap.	
	cout<<"\nThe process is completed and Huffman Tree is obtained\n";
	system ("pause"); 	
	HuffmanTree=Heap.T[1];// This tree is our HuffmanTree used for coding 
	delete []Heap.T;
	cout<<"Traversal of Huffman Tree\n\n";
	HuffmanTree.print();
	system ("pause");
	cout<<"\nThe symbols with their codes are as follows\n";
	HuffmanTree.assign_code(0);
	system ("pause");// Codes are assigned to the symbols
	cout<<"Enter the string to be encoded by Huffman Coding: ";
	char *str;
	str=new char[50];
	cin>>str;
	HuffmanTree.encode(str);
	system ("pause");
	int length;
	cout<<"Enter the code to be decoded by Huffman Coding: ";	
	char *cd;
	cd=new char[60];
    cin>>cd;
	cout<<"Enter its code length: ";
	cin>>length;	
	HuffmanTree.decode(cd,length);
	system ("pause");
}

minHeap::minHeap()
{
	cout<<"Enter no. of symbols:";
  cin>>n;				
	T= new BinaryTree [n+1];
	T[0].root=new node;
	T[0].root->freq=n; //Number of elements in min. Heap is stored in the zeroth element of the heap
	for (int i=1; i<=n; i++)
  {
      T[i].root=new node;
			cout<<"Enter characters of string :- ";
      cin>>T[i].root->info;
      cout<<"and their frequency of occurence in the string:- ";
      cin>>T[i].root->freq;
      T[i].root->code=NULL;
      T[i].root->Llink=NULL;
			T[i].root->Rlink=NULL;
			// Initially, all the nodes are leaf nodes and stored as an array of trees.
  }
  cout<<endl;
	int i=(int)(n / 2);// Heapification will be started from the PARENT element of 
	//the last ( 'n th' ) element in the heap.
	cout<<"\nAs elements are entered\n";
	print();
  while (i>0)
  {
      heapify(i); 
      i--;        
  }
  cout<<"\nAfter heapification \n";
  print();
}

int min(node *a, node *b)
{if (a->freq <= b->freq) return a->freq; 		else return b->freq;}

void swap(BinaryTree &a, BinaryTree &b)
{BinaryTree c=a;		a=b;		b=c;}

void minHeap::heapify(int i)
{
    while(1)
    {
				if (2*i > T[0].root->freq)
				return;
				if (2*i+1 > T[0].root->freq)
				{ 
					if (T[2*i].root->freq <= T[i].root->freq)
					swap(T[2*i],T[i]);
					return;
				}
        int m=min(T[2*i].root,T[2*i+1].root); 
        if (T[i].root->freq <= m)
        return;
        if (T[2*i].root->freq <= T[2*i+1].root->freq)
        {
					swap(T[2*i],T[i]); 
					i=2*i;
				}
        else
        {
					swap(T[2*i+1],T[i]); 
					i=2*i+1;
				}    
    }
}

BinaryTree minHeap::remove()
{
	BinaryTree b=T[1];    
  T[1]= T[T[0].root->freq];	    
  T[0].root->freq--;
  if (T[0].root->freq!=1)
  heapify(1);
	return b;
}

void minHeap::insert(BinaryTree b)
{
	T[0].root->freq++;
	T[T[0].root->freq]=b;
	int i=(int) (T[0].root->freq /2 );
	while (i>0)
	{
		heapify (i);
		i=(int) (i /2 );
	} 
}

int isleaf(node *nd) 
{ if(nd->info=='\0') return 0; else return 1;}

void BinaryTree::assign_code(int i)
{
		if (root==NULL)
        return;  
		if (isleaf(root))
		{ 
			root->code[i]='\0';
			cout<<root->info<<"\t"<<root->code<<"\n";
			return;
		}
		BinaryTree l,r; 
		l.root=root->Llink;
		r.root=root->Rlink;
		l.root->code=new char[i+1];
		r.root->code=new char[i+1];
		for (int k=0; k<i; k++)
		{
			l.root->code[k]=root->code[k];
			r.root->code[k]=root->code[k];
		}		
		l.root->code[i]='0';
		r.root->code[i]='1';
		i++;
		l.assign_code(i);
		r.assign_code(i);
}

void BinaryTree::encode(const char str[])
{
	if (root==NULL)
    return;
	int i=0;
	cout<<"Encoded code for the input string '"<<str<<"' is\n";
	while (1)
	{
		if (str[i]=='\0')
		{
			cout<<endl; 
			return;
		}
		print_code(str[i]);			
		i++;		
	}	
}

void BinaryTree::print_code(char c)
{
	int f=0;		
	if (isleaf(root))
	{ 
		if (c==root->info) 
		{
			f=1;
		 	cout<<root->code;
		}
		return ; 
	}		
	BinaryTree l,r; 
	l.root=root->Llink;
	if (f!=1)
	l.print_code(c);			
	r.root=root->Rlink;
	if (f!=1)
	r.print_code(c);			
}

int isequal(const char a[], const char b[], int length)
{
	int i=0;
	while (i<length)
	{
		if(b[i]!=a[i])
		return 0;
		i++;
	}
	if (a[i]!='\0')
	return 0;
	return 1;
}

void BinaryTree::decode(char cd[], int size)
{
	if (root==NULL)
  return;
	int i=0;
	int length=0;
	int f;
	char *s;
	cout<<"Decoded string for the input code '"<<cd<<"' is\n";
	while (i<size)
	{
		f=0;		
		s=&cd[i];
		while (f==0)
		{
			length++;
			print_symbol(s,f,length);			
		}							
		i=i+length;
		length=0;		
	}
	cout<<endl;
}

void BinaryTree::print_symbol(char cd[], int &f, int length)
{
	if (isleaf(root))
	{ 
		if (isequal(root->code, cd, length))
		{
			f=1;
			cout<<root->info;
		}
		return; 
	}		
	BinaryTree l,r; 
	l.root=root->Llink;
	if (f!=1)
	l.print_symbol(cd,f,length);			
	r.root=root->Rlink;
	if (f!=1)
	r.print_symbol(cd,f,length);		
}

void BinaryTree::print()
{
  if (root==NULL)
  return;
  cout<<root->info<<"\t"<<root->freq<<"\n";
	if (isleaf(root))
	return;
	BinaryTree l,r; 
	l.root=root->Llink;
	r.root=root->Rlink;
	l.print();
	r.print();
}

int power(int i, int j)
{
	int n=1;
	for (int k=1; k<=j; k++)
	n=n*i;
	return n;
}

int ispowerof2(int i)
{
	if (i==1)
	return 0;
	if (i==0)
	return 1;
	while (i>2)
	{
		if (i%2!=0)
		return 0;
		i=i/2;
	}
	return 1;
}

int fn(int l)
{
	if (l==1||l==0) 
	return 0;
	return 2*fn(l-1)+1;
}
 
void minHeap::print()
{
	cout<<"The Heap showing the root frequencies of the Binary Trees are:\n";
	if (T[0].root->freq==0)
	{
		cout<<endl;
		system ("pause");
		return;
	}
	int level=1;
	while( T[0].root->freq >= power(2,level) )// 2^n-1 is the max. no. of nodes 
	///in a complete tree of n levels
	level++;
	if(level==1)
	{
		cout<<T[1].root->freq<<"\n";
		system ("pause");
		return;
	}	
	for (int i=1; i<=T[0].root->freq; i++)
	{
		if (ispowerof2(i))
		{cout<<"\n"; level--;}
		for (int k=1; k<=fn(level); k++)
		cout<<" ";
		cout<<T[i].root->freq<<" "; 
		for (int k=1; k<=fn(level); k++)
		cout<<" ";
	}
	cout<<endl;
	system ("pause");
}

int main()
{
    HuffmanCode c;
    system ("pause");
    return 0;    
}