/**
* Created by:	Eduard Aumüller
* Date:			2004
*
* huffman_lib.h
* This library consist of a basic huffman tree implementation,
* plus some derivations for special purposes.
* CHuffmanTree:	-contains the basic routines (see underneath)
* CHexDecimalHuffmanTree:	- devides bytes into hex decimals and 
*							builds a huffman tree on the top of it
*/

#include <stdio.h>

typedef unsigned char BYTE;
typedef unsigned int  BOOL;

#define NULL 0
#define FALSE 0
#define TRUE 1

#define HEX_LEFT	0x000000F0
#define HEX_RIGHT	0x0000000F

class CCodeWord
{
public:
	//constructor
	CCodeWord()
	{
		m_iFrequency = 0;
		m_iCodeWord = 0;
		m_iSize = 0;
		m_pLeft = NULL;
		m_pRight = NULL;
		m_pParent = NULL;
	};

	//destructor
	~CCodeWord()
	{
		//set the parent pointers to NULL
		if(m_pLeft)
			m_pLeft->m_pParent = NULL;
		if(m_pRight)
			m_pRight->m_pParent = NULL;

		//delete knots only not the ends of the list
		if(m_pLeft && m_pLeft->m_pLeft)
			delete m_pLeft;

		if(m_pRight && m_pRight->m_pRight)
			delete m_pRight;
	};

	//operator overloading
	CCodeWord& operator=(CCodeWord& word)
	{
		m_iFrequency = word.m_iFrequency;
		m_iCodeWord = word.m_iCodeWord;

		return *this;
	};

	//print to console for debugging purposes only
	void Print()
	{
		printf("(%X,%d)\n",m_iCodeWord,m_iFrequency);
		if(m_pParent)
			m_pParent->Print();
		else
			printf("end\n");
	};

	//unsigned int variables
	unsigned int m_iFrequency;
	unsigned int m_iCodeWord;
	unsigned int m_iSize;

	//pointers
	CCodeWord *m_pLeft;
	CCodeWord *m_pRight;
	CCodeWord *m_pParent;
};

class CHuffmanTree
{
public:
	//constructor
	CHuffmanTree()
	{
		m_iCodeWords = 0;
		m_iCodeWordLength = 0;
		m_iCodeWordsInUse = 0;
		m_iCodeWordsLeft = 0;

		m_iInputSize;
		m_iOutputSize;

		m_pCodeWords = NULL;
		m_pHead = NULL;

		m_pInputBuffer = NULL;
		m_pOutputBuffer = NULL;
	};

	//destructor
	~CHuffmanTree()
	{
		//delete the left buffers
		if(m_pHead)
			delete  m_pHead;

		if(m_pCodeWords)
			delete[] m_pCodeWords;

		if(m_pOutputBuffer)
			delete[] m_pOutputBuffer;
	};

	//set the input buffer and its size
	void SetInput(int iSize, BYTE *pInput)
	{
		if(!iSize && pInput == NULL)
			return;

		m_iInputSize = iSize;
		m_pInputBuffer = pInput;
	};

	//returns a pointer to the output buffer
	BYTE* GetOutput()
	{
		return m_pOutputBuffer;
	};
	
	//returns the size of the output buffer
	int GetOutputSize()
	{
		return m_iOutputSize;
	};

	//get the frequencies (overwrite in subclasses)
	void GetFrequencies()	{};

	//print the codewords' frequencies to the console
	void OutFrequencies()
	{
		printf("HEX | Frequency\n");
		for(int i=0;i<m_iCodeWordsInUse;i++)
		{
			printf("%X | %d\n",m_pCodeWords[i].m_iCodeWord,m_pCodeWords[i].m_iFrequency);
		}
	};

	//sort the codewords by value with zeros at the back
	void SortCodeWords()
	{
		int i=0,a=0;

		CCodeWord swap;

		for(i=0;i<m_iCodeWords;i++)
		{
			for(a=i+1;a<m_iCodeWords;a++)
			{
				if(m_pCodeWords[a].m_iFrequency == 0)
					continue;
				if( ( m_pCodeWords[a].m_iFrequency < m_pCodeWords[i].m_iFrequency) || m_pCodeWords[i].m_iFrequency == 0 )
				{
					swap = m_pCodeWords[i];
					m_pCodeWords[i] = m_pCodeWords[a];
					m_pCodeWords[a] = swap;
				}
			}
			if( m_pCodeWords[i].m_iFrequency == 0 )
				--m_iCodeWordsInUse;
		}
	};

	//build a huffman tree out of the code words
	void BuildTree()
	{
		int i;

		if(m_iCodeWordsInUse < 3)
			return;

		//creates a dynamic pointer array of the size m_iCodeWordsInUse
		m_ppWords = new CCodeWord*[m_iCodeWordsInUse];

		//copy the code word addresses into the pointer array
		for(i=0;i<m_iCodeWordsInUse;i++)
			m_ppWords[i] = &m_pCodeWords[i];

		m_iCodeWordsLeft = m_iCodeWordsInUse;
		
		//proceed until there s only one code word left in m_ppWords, the head of the tree
		while(m_iCodeWordsLeft > 1)
		{
			LinkCodeWords();
		}

		m_pHead = m_ppWords[0];
		m_ppWords[0] = NULL;

		//delete the dynamic pointer array
		delete m_ppWords;

	};

	//links two codewords and rebuilds the m_ppWords list
	void LinkCodeWords()
	{	
		int i;
		CCodeWord *w = NULL;
		CCodeWord *p = new CCodeWord();

		//assign the pointers
		p->m_pLeft = m_ppWords[0];
		p->m_pRight = m_ppWords[1];

		m_ppWords[0]->m_pParent = p;
		m_ppWords[1]->m_pParent = p;

		//sum up the frequencies for the new link
		p->m_iFrequency = m_ppWords[0]->m_iFrequency + m_ppWords[1]->m_iFrequency;

		//replacing some pointers
		m_ppWords[0] = p;
		m_ppWords[1] = NULL;

		//move the elemts one slot to the left n->0
		for(i=1;i<(m_iCodeWordsLeft-1);i++)
		{
			m_ppWords[i] = m_ppWords[i+1];
		}

		m_ppWords[m_iCodeWordsLeft-1] = NULL;

		--m_iCodeWordsLeft;

		if(m_iCodeWordsLeft < 2)
			return;
		
		//sort the left code words by frequency
		for(i=0;i<(m_iCodeWordsLeft-1);i++)
		{
			if(m_ppWords[i]->m_iFrequency > m_ppWords[i+1]->m_iFrequency)
			{
				//swap m_ppWords[i] with m_ppWords[i+1]
				w = m_ppWords[i];
				m_ppWords[i] = m_ppWords[i+1];
				m_ppWords[i+1] = w;
			}
		};

		
	};
	//print the tree structure as far as possible with plain text
	void PrintTree()
	{
		for(int i=0;i<m_iCodeWordsInUse;i++)
			m_pCodeWords[i].Print();
	};


	//integer member variables
	int	m_iCodeWords;
	int m_iCodeWordsInUse;
	int m_iCodeWordsLeft;
	int	m_iCodeWordLength;

	int m_iInputSize;
	int m_iOutputSize;


	//pointers
	CCodeWord *m_pCodeWords;
	CCodeWord *m_pHead;
	CCodeWord **m_ppWords;

	BYTE *m_pInputBuffer;
	BYTE *m_pOutputBuffer;
};

class CHexDecimalHuffmanTree : public CHuffmanTree
{
public:
	//constructor for hex decimal huffman tree
	CHexDecimalHuffmanTree()
	{
		CHuffmanTree::CHuffmanTree();

		m_iCodeWordsInUse = m_iCodeWords = 16;

		m_pCodeWords = new CCodeWord[m_iCodeWords]();

		int i=0;

		for(i=0;i<m_iCodeWords;i++)
		{
			m_pCodeWords[i].m_iCodeWord = i;
		}
	};

	//get the frequencies of  hexa decimals in the input buffer
	void GetFrequencies()
	{
		if(!m_iInputSize && m_pInputBuffer == NULL)
			return;
		int i=0;

		//make the left 4 bits zero to get the right hex decimal 
		//and use the shift operator to get the left hex decimal
		for(i=0;i<m_iInputSize;i++)
		{
			++m_pCodeWords[(m_pInputBuffer[i] | HEX_LEFT ) & HEX_RIGHT].m_iFrequency;
			++m_pCodeWords[ m_pInputBuffer[i] >> 4].m_iFrequency;
		}
	};

};