Huffman

1. Huffman.h

2. Huffman.cpp

3. main.cpp (main)

file name: Huffman.h

#ifndef HUFFMAN_H
#define HUFFMAN_H

#include <stdio.h>


template<class T>
class Huffnode
{
private:
	T element;
	Huffnode<T>* l;
	Huffnode<T>* r;
	int freq;
	char* path;
	//unsigned int bit;
	int length;
	bool isInternal;
public:
	int getLength(){return length;}
	//unsigned int getBit(){return bit;}
	Huffnode<T>* left(){return l;}
	Huffnode<T>* right(){return r;}
	int getFreq(){return freq;}
	T getElem(){return element;}
	void setPath(const char* str);
	char* getPath(){return path;}
	bool internal(){return isInternal;}
	void operator++();
	Huffnode(int weight);//constructor for internal
	Huffnode(T elem, int frequency);//constructor for leaf
	Huffnode<T>* operator+(Huffnode<T>& other);
	//static Huffnode<T>* root;
};


const int AlphaNumber=128;

class Huffman
{
private:
	Huffnode<char>* nodes[AlphaNumber];
	//Huffnode<char>* lists[AlphaNumber];
	Huffnode<char>* root;
	void initialize();
	void swapNode(Huffnode<char>* lists[], int i, int j);
	void insertList(Huffnode<char>* lists[], Huffnode<char>* ptr, int length);
	void assignPath();
	void sortList(Huffnode<char>* lists[], int length);
	void traverse(Huffnode<char>* ptr, char* pathStr);
	void traverse(Huffnode<char>* ptr);
public:
	Huffman();
	~Huffman();
	void readFile(const char* fileName);
	void buildTree();
	void compress(const char* sourceFile);
	void display();
};

/*
template<class T>
Huffnode<T>* Huffnode<T>::root=NULL;
*/

template<class T>
void Huffnode<T>::operator ++()
{
	freq++;
}


template<class T>
void Huffnode<T>::setPath(const char* str)
{	
	//unsigned int temp;
	length=strlen(str);
	path=new char[length+1];
	strcpy(path, str);
	/*
	bit=0;

	for (int index=length-1; index>=0; index--)
	{
		if (str[index]=='1')
		{
			temp=1;
			bit+=temp<<index;
			//bit+=temp;
		}

	}
	*/
}


template <class T>
Huffnode<T>::Huffnode<T>(T elem, int frequency)
{
	isInternal=false;
	element=elem;
	freq=frequency;
	l=r=NULL;
	path=NULL;
}

//internal node
template<class T>
Huffnode<T>::Huffnode<T>(int weight)
{
	freq=weight;
	isInternal=true;
	l=r=NULL;
	path=NULL;
}


template<class T>
Huffnode<T>* Huffnode<T>::operator +(Huffnode<T>& other)
{
	Huffnode<T>* result=new Huffnode<T>(freq+other.freq);
	if (freq<other.freq)
	{
		result->l=this;
		result->r=&other;
	}
	else
	{
		result->l=&other;
		result->r=this;
	}
	return result;
}

#endif

file name: Huffman.cpp

//#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "huffman.h"



Huffman::Huffman()
{
	initialize();
}

void Huffman::traverse(Huffnode<char>* ptr)
{
	if (ptr==NULL)
	{
		return;
	}
	//only delete the internal
	if (ptr->internal())
	{
		traverse(ptr->left());
		traverse(ptr->right());
		delete ptr;
	}

}



Huffman::~Huffman()
{
	Huffnode<char>* ptr=root;
	traverse(ptr);
	for (int i=0; i<AlphaNumber; i++)
	{
		delete nodes[i]->getPath();
		delete nodes[i];
		nodes[i]=NULL;
	}
}


void Huffman::display()
{
	for (int i=0; i<AlphaNumber; i++)
	{
		if (nodes[i]->getFreq()!=0)
		{
			//display char in form of int, otherwise invisible.
			printf("char %d is encoded:%s\t", nodes[i]->getElem(), nodes[i]->getPath());
			printf("the length:%d\n", nodes[i]->getLength()); 
				
		}
	}
}


void Huffman::initialize()
{
	for (int i=0; i<AlphaNumber; i++)
	{
		nodes[i]=new Huffnode<char>(i, 0);
		//lists[i]=nodes[i];//initially all nodes are in lists
	}
}

void Huffman::readFile(const char* fileName)
{
	FILE* stream;
	char ch;	
	if ((stream=fopen(fileName, "r"))==NULL)
	{
		printf("error open file %s\n", fileName);
		exit(1);
	}
	ch=fgetc(stream);
	while (!feof(stream))
	{		
		nodes[ch]->operator++();
		ch=fgetc(stream);
	}
}

void Huffman::buildTree()
{
	Huffnode<char>* lists[AlphaNumber];
	Huffnode<char>* ptr;
	int counter=0;
	for (int i=0; i<AlphaNumber; i++)
	{
		if (nodes[i]->getFreq()!=0)
		{
			lists[counter++]=nodes[i];
		}
	}
	sortList(lists, counter);//must be descending 
	while (counter>1)
	{
		ptr=lists[counter-2]->operator+(*lists[counter-1]);
		insertList(lists, ptr, --counter);//shrink size by 2, but add one
	}
	root=lists[0];
	assignPath();
}

void Huffman::swapNode(Huffnode<char>* lists[], int i, int j)
{
	Huffnode<char>* hold;
	hold=lists[i];
	lists[i]=lists[j];
	lists[j]=hold;
}

//descending
void Huffman::sortList(Huffnode<char>* lists[], int length)
{
	Huffnode<char>* current;
	
	for (int i=0; i<length-1; i++)
	{
		current=lists[i];
		for (int j=i+1; j<length; j++)
		{
			if (current->getFreq()<lists[j]->getFreq())
			{
				swapNode(lists, i, j);
			}
		}
	}
}

//length includes ptr itself
void Huffman::insertList(Huffnode<char>* lists[], Huffnode<char>* ptr, int length)
{
	bool shifting=false;
	Huffnode<char>* hold, *temp;
	for (int i=0; i<length; i++)
	{
		if (!shifting)
		{
			if (ptr->getFreq()>lists[i]->getFreq())
			{
				shifting=true;
				hold=ptr;
				//temp=lists[i];
			}
		}
		if (shifting)
		{
			temp=lists[i];
			lists[i]=hold;
			hold=temp;
		}
	}
	//if not find a suitable place, insert at last
	if (!shifting)
	{
		lists[length]=ptr;
	}
}

void Huffman::traverse(Huffnode<char>* ptr, char* pathStr)
{
	int len;
	if (ptr==NULL)
	{
		return;
	}
	len=strlen(pathStr);
	
	//strcpy(pathStr, "ok");
	if (ptr->internal())
	{		
		pathStr[len]='0';
		pathStr[len+1]='\0';//grows
		traverse(ptr->left(), pathStr);
		pathStr[len]='1';
		traverse(ptr->right(), pathStr);
		pathStr[len]='\0';//restores
	}
	else
	{
		//leaf
		ptr->setPath(pathStr);
	}
}

void Huffman::assignPath()
{
	Huffnode<char>* ptr=root;
	char buffer[AlphaNumber];
	buffer[0]='\0';
	traverse(root, buffer);
}

file name: main.cpp (main)

#include "huffman.h"



int main()
{
	//unsigned int i=0x80000000;
	//printf("i is %x\n", i);

	

	Huffman H;
	H.readFile("nicktest.txt");
	H.buildTree();
	H.display();
	
	return 0;
}