/****************************************************************************************************/
/*  This class Written by Sourena Maroofi maroofi[at]Gmail.com   				    */
/*  simple and easy to use class implementing huffman algorithm to En/Decode file...      	    */
/*  use it like this:       									    */
/*                                                                                        	    */
/*       int main()   										    */
/*       {   											    */
/*              make a class instance.get file1 as input and write output to file2      	    */
/*        	huffman instance1("file1","file2");						    */
/*              instance1.encode();								    */
/*              get file2 as a compress file and decompress and save it to file1  		    */
/*              huffman instance2("file2","file1");						    */
/*              instance2.decode();								    */
/*              return 0;									    */
/*        }      										    */
/*       		                                                                       	    */
/*        USE IT AT YOUR OWN RISK,I'M NOT RESPONSIBLE FOR ANY DAMAGE OR LOSS OF DATA  	            */
/*        CAUSED BY THIS CLASS..........     							    */
/*                										    */
/*                  										    */
/*                  										    */
/*             											    */
/*             											    */
/****************************************************************************************************/


#include "stdafx.h"
#include <iostream>   //for cout and cin
#include <iomanip>	//manipulating input output  using hex and dec
#include <string>    //using string variable

#include "bitio.h"     //input output bitoperation using this class in current directory

#include <fstream>   //working with input and output file

#include <vector>	//using vector template


#ifndef huffman_h
#include "huffman.h"	
#endif


using namespace std;

/**************************************************************************************/

huffman::huffman(char const * inputFileName,char const * outputFileName)

{

	vec.resize(VEC_SIZE);
	errorMessage="No Error Yet!!!";
	print_detail=false;
	error_occured=false;
	this->inputFileName=inputFileName;
	this->outputFileName=outputFileName;
	for (int i=0;i<vec.size();i++)
	
	{
		vec[i].left=-2;
		vec[i].right=-2;
		vec[i].parent=-2;
		vec[i].count=0;
		vec[i].ignore=false;
		vec[i].ch=-1;
		vec[i].len=0;
		vec[i].codeWord=0;
	}

}

/******************************************************************************/

void huffman::readInputFile(void)

{

	

	myFileIn.open(inputFileName,ios::in|ios::binary);

	if (!myFileIn.is_open())

	{

	
		errorMessage="can not open input file " + (string) inputFileName + " .check if file exist!!!";
		getLastError();
		error_occured=true;
		return;
	}
	
	unsigned char * byte;

	byte=new unsigned char;

	while (! myFileIn.eof())

	{

		myFileIn.read((char *)byte,1);

		(vec[*byte].count)++;

		vec[*byte].ch=(unsigned char)(*byte);
		
		
	}
	
		for (int i=0;i<vec.size();i++)
	
		{
	
			if (vec[i].count==0)

			{

				vec[i].ignore=true;
				vec[i].len=0;
				vec[i].ch=-1;
				

			}	

		}

	myFileIn.close();

}

/***********************************************************************/


void huffman::getLastError(void)

	{
	
	cout<<endl<<errorMessage<<endl;

	}
/************************************************************************/
void huffman::printProbility(void)
{
	if (print_detail==false)
	{
		return;
	}
	//cout<<"characters and their probilities in " + (string)inputFileName +" : "<<endl;
	int rowCount=0;	// print out 4 char each line...
	for (int i=0;i<vec.size();i++)
	{
		if (vec[i].ch != -1)
		{
			cout<<setw(8)<<"0x"<<hex<<vec[i].ch<<" => "<<dec<<vec[i].count;
			cout<<" => "<<vec[i].codeWord<<" => "<<vec[i].len<<endl;
			//rowCount++;
		}
		//if (rowCount==4)
		//{
		//	cout<<endl;
		//	rowCount=0;
		//}
	}
	cout<<endl;
	return;
}
/***********************************************************************************/
int huffman::smallestProbility(void)
{	
	unsigned long int i,min,j=0;

	for (i=0;i<vec.size();i++)
	{
		if (vec[i].ignore==false)
		{
			min=vec[i].count;
			j=i;
			break;
		}	
	}

	for (i=0;i<vec.size();i++)
	{
		
			if (vec[i].count<min && vec[i].ignore !=true)
			{	
				min=vec[i].count;
				j=i;
			}
	}
	return (int)j;

}
/***********************************************************************************/
void huffman::encodeHuffman(void)
{
	int min1,min2;
	vector_size=checkVectorSize();
	if (print_detail==true)
	{
		cout<<endl<<dec<<"vector size is : "<<(int)vector_size<<endl;
	}
	if (print_detail==true)
	{	
	cout<<endl<<"character -> probilities -> code -> code length : "<<endl;
	}
	while(true)
	{		
		if (checkVectorSize() > 1 )
		{
			//cout<<dec<<"vector size is : "<<checkVectorSize()<<endl;
			min1=smallestProbility();
			vec[min1].ignore=true;
			min2=smallestProbility();
			vec[min2].ignore=true;
			struct huff_node node;
			node.ch=-1;
			node.count=(vec[min1].count) + (vec[min2].count);
			node.ignore=false;
			node.parent=-3;
			node.left=min1;
			node.right=min2;
			vec.push_back(node);
			vec[min1].parent=vec.size()-1;
			vec[min2].parent=vec.size()-1;
			
			
		}
		else
		{
			// there is only one unused node in the list so call huffman tree search
			
			for(int i=0;i<vec.size();i++)
			{
				if (vec[i].ignore !=true)
				{
					break;
				}
			}	
			break;		//break from while-loop	
		}
	}
	return;
}
/************************************************************************************/
int huffman::checkVectorSize(void)
{
	int sizeCount=0;		//store the number of ignore=false in vector
	for(int i=0;i<vec.size();i++)
	{
		if (vec[i].ignore==false)
		sizeCount++;
	}
	return sizeCount;

}
/************************************************************************************/
void huffman::encode(void)
{
readInputFile();
encodeHuffman();	
cop(); 
writeHuffman();
printProbility();
if (print_detail==true)
{
	cout<<endl<<"bit rate is : "<<(double)bitRate()<<endl;
}
return;
}
/**************************************************************************************/
void huffman::decode(void)
{

return;
}
/***************************************************************************************/
double huffman::bitRate(void)
{
	double rate;
	unsigned long int countLen=0;
	unsigned long int sum_of_count=0;
	for (int i=0;i<vec.size();i++)
	{
		if (vec[i].count !=0 && vec[i].ch !=-1 )
		{	
			sum_of_count+=vec[i].count;
			countLen+=(vec[i].count*(unsigned long int)vec[i].len);
		}
	}
	rate=((double)countLen/sum_of_count);
	return rate;
}
/**************************************************************************************/

void huffman::cop(void)
{


	
	for(int i=0;i<vec.size();i++)
	{
		if (vec[i].ch !=-1 && vec[i].count !=0)
		{
			int j;
			j=i;
			struct huff_node node;
			node=vec[i];
			int depth=0;
			while(vec[j].parent !=-3)
			{
				depth++;
				j=vec[j].parent;
				node=vec[j];
			}
			vec[i].len=depth;
			depth=0;
		}
	}
	return;
}
/********************************************************************************************/
void huffman::writeHuffman(void)
{
	int maxCodeLen=0;
	for (int i=0;i<vec.size();i++)
	{
		if (vec[i].ch !=-1)
		{
			if (vec[i].len > maxCodeLen)
			{
				maxCodeLen=vec[i].len;
			}
		}
	}
	if (print_detail==true)
	{
		cout<<endl<<"maximum Code Length is : "<<maxCodeLen<<endl;
	}
	if (maxCodeLen>32)
	{
		cout<<"can not encode with length greater than 32...maybe next version"<<endl;
		return;
	}
	unsigned char * nrcode;
	nrcode=new unsigned char [maxCodeLen];
	for(int i=0;i<maxCodeLen;i++)
	{
		nrcode[i]=0;
	}
	unsigned char * values;
	values=new unsigned char [vector_size];
	for(int i=0;i<vec.size();i++)
	{
		if (vec[i].ch !=-1)
		{
			(nrcode[vec[i].len])++;
		}
	}
	int j=0;
	int i=0;
	for(i=0;i<maxCodeLen;i++)
	{
		for(int k=0;k<vec.size();k++)
		{
			if (vec[k].ch !=-1)
			{
				if (vec[k].len == nrcode[i])
				{
					values[j]=vec[k].ch;
					j++;
				}
			}
		}
	}
	generateHuffmanCode(nrcode,values,maxCodeLen);
	bitio huffOut(outputFileName,bitio::out);
	huffOut.writeByte((unsigned char *)magicWord,4);
	unsigned char  * temp2;
	temp2=new unsigned char;
	unsigned char temp1;
	temp1=(unsigned char)maxCodeLen;
	huffOut.writeByte(&temp1,1);
	huffOut.writeByte(&vector_size,1);
	huffOut.writeByte(nrcode,maxCodeLen);
	huffOut.writeByte(values,vector_size);
	
	
	myFileIn.open(inputFileName,ios::in|ios::binary);
	if (!myFileIn.is_open())

	{
		errorMessage="can not open input file " + (string) inputFileName + " .check if file exist!!!";
		getLastError();
		error_occured=true;
		return;
	}
	
	while(! myFileIn.eof())
	{
		
		myFileIn.read((char *)temp2,1);
		for (i=0;i<vec.size();i++)
		{
			if (vec[i].ch==(*temp2))
			{
				unsigned long int code;
				code=vec[i].codeWord;
				for(j=0;j<vec[i].len;j++)
				{
					huffOut.outputBit((code & 0x1));
					code=code >> 1;
				}
			}
		}
	}
	huffOut.flushBuffer();
	return;
}



/********************************************************************************************/
void huffman::generateHuffmanCode(unsigned char * nrcode,unsigned char * values,int maxCodeLen)
{
	int minCodeLen;
	unsigned long int codeLen,temp;
	minCodeLen=maxCodeLen;
	for (int i=0;i<vec.size();i++)
	{
		if (vec[i].ch !=-1)
		{
			if (vec[i].len <minCodeLen)
			{
				minCodeLen=vec[i].len;
			}
		}
	}
	if (print_detail==true)
	{
		cout<<"min code length is: "<<minCodeLen<<endl;
	}
	temp=0;
	codeLen=minCodeLen;
	temp=temp << (codeLen-1);
	int ncount=0;
	while(codeLen<=maxCodeLen)
	{
		for(int i=0;i<vec.size();i++)
		{
			if (vec[i].ch !=-1)
			{
				if(vec[i].len ==codeLen)
				{
					if (ncount==0)
					{
						vec[i].codeWord=temp;
						ncount++;
						continue;
					}
					temp+=1;
					ncount++;
					vec[i].codeWord=temp;
					continue;
				}
			}
		}
		ncount=0;
		codeLen++;
		temp+=1;
		temp=temp<<1;
	}
	
	return;
}
/**********************************************************************************************/