huffmantree.cpp

Implementation for the Huffman Cod in Visual C++. Both, the encoder and the decoder take as input

#include "HuffmanTree.h"
#include "Tail.h"
#include <iostream>

using namespace std;

// Constructor
HuffmanTree::HuffmanTree(void)
{
	
	m_pRoot = new NOD_HUFFMAN;
	m_pRoot->nrAparition = 0;
	nrLeaves = 0;
	m_leaves[nrLeaves++] = m_pRoot;
}

// Destructor
HuffmanTree::~HuffmanTree(void)
{
}

// Insert a symbol
void HuffmanTree::Insert(SYMBOL_TYPE symbol)
{
	for(unsigned int i = 0; i < nrLeaves; i++)
	{
		// Daca simbolul exista in arbore , actualizam arborele
		if(m_leaves[i]->symbol == symbol)
		{			
			m_leaves[i]->nrAparition++;
			
			NOD_HUFFMAN *pAux = m_leaves[i]->pParrent;
			while(pAux != NULL)
			{
				pAux->nrAparition++;
				pAux = pAux->pParrent;
			}
						
			return;
		}
	}

	NOD_HUFFMAN* nod = new NOD_HUFFMAN;
	NOD_HUFFMAN* root = new NOD_HUFFMAN;

	nod->symbol = symbol;
	nod->pParrent = root;
	
	root->nrAparition = m_pRoot->nrAparition + nod->nrAparition;

	root->pLeftChild = nod;
	root->pRightChild = m_pRoot;
	m_pRoot->pParrent = root;

	m_pRoot = root;
	
	m_leaves[nrLeaves++] = nod;

}

// verify the property of sibling
void HuffmanTree::Sibling()
{
	Tail tail;
	
	bool isSibling = false;

	while(!isSibling)
	{
		isSibling = true;
		
		// Parcurg BFS si interschimb nodurile
			
		if(m_pRoot == NULL)
			return;
	
		NOD_HUFFMAN *i = m_pRoot;
		NOD_HUFFMAN *j = NULL;
		tail.Insert(i);	
		while((tail.GetFirst() != NULL))
		{
			j = i;
			i = tail.GetFirst()->pInf;
			tail.Delete();

			if(i->pRightChild != NULL) tail.Insert(i->pRightChild);
			if(i->pLeftChild != NULL) tail.Insert(i->pLeftChild);
			
			if(j->nrAparition < i->nrAparition)
			{
				ChangeNods(j,i);
				isSibling = false;
				break;
			}
		}

		tail.~Tail();
	}
}

// Change 2 nods
void HuffmanTree::ChangeNods(NOD_HUFFMAN* &nod1, NOD_HUFFMAN* &nod2)
{
	NOD_HUFFMAN* pAux = nod1->pParrent;

	// Daca au acelasi parinte interchimb numai fii
	if(nod1->pParrent == nod2->pParrent)
	{
		pAux = nod1->pParrent->pLeftChild;
		nod1->pParrent->pLeftChild = nod1->pParrent->pRightChild;
		nod1->pParrent->pRightChild = pAux;
		return;
	}
	
	// Interscimb Parintii
	nod1->pParrent = nod2->pParrent;
	nod2->pParrent = pAux;
	
	if(nod1->pParrent->pLeftChild == nod2)
		nod1->pParrent->pLeftChild = nod1;
	else
		nod1->pParrent->pRightChild = nod1;

	if(nod2->pParrent->pLeftChild == nod1)
		nod2->pParrent->pLeftChild = nod2;
	else
		nod2->pParrent->pRightChild = nod2;

	// Actualizez numarul de aparitii
	nod1->pParrent->nrAparition = nod1->pParrent->pLeftChild->nrAparition + nod1->pParrent->pRightChild->nrAparition;
	nod2->pParrent->nrAparition = nod2->pParrent->pLeftChild->nrAparition + nod2->pParrent->pRightChild->nrAparition;
}

NOD_HUFFMAN* HuffmanTree::GetRoot() const
{
	return m_pRoot;
}