Viewing file: c/huffman1/NodeTree.cpp | Back to directory listing
Author: Loren Segal | Last modified: February 21 2006 12:00 am | Download

#include "huffman.h"
 
int NodeTree::addBitCode(int charCode, int bitCode, int bitLength)
{
	for (int i = 0; i < this->listSize; i++)
	{
		if (cParent->bitCodeList[i].bitLength == 0)
		{
			cParent->bitCodeList[i].charCode = charCode;
			cParent->bitCodeList[i].bitCode = bitCode;
			cParent->bitCodeList[i].bitLength = bitLength;
			return i;
		}
	}
	return 0;
}
 
int compar(const void *a, const void *b)
{
	Node **fA = (Node **)a,
		 **fB = (Node **)b;
	int ret;
	
	if (*fA == NULL) return 1;
	if (*fB == NULL) return -1;
 
	ret = (*fA)->freqTotal > (*fB)->freqTotal ? 1 : -1;
	
	if ((*fA)->freqTotal == 0) return 1;
	if ((*fB)->freqTotal == 0) return -1;
	else					return ret;
}
 
void NodeTree::sortList(Node **nodeList, size_t count)
{
	qsort(nodeList, count, sizeof(Node *), compar);
}
 
void NodeTree::orderNodeTree(Node **nodeList)
{
	sortList(nodeList, cParent->numUniqueChars);
	for (int remainingNodes = cParent->numUniqueChars; remainingNodes > 1; remainingNodes--)
	{		
		Node *pNode = new Node();			// parent node
 
		// add the first pair of nodes (smallest in frequency) to a new parent
		nodeList[0]->addParentNode(pNode);	
		nodeList[1]->addParentNode(pNode);	
 
		// remove the pair from the nodeList and replace it with parent node
		// this will be sorted and the empty node will be placed at the end 
		// of the list.
		nodeList[0] = NULL;
		nodeList[1] = pNode;
 
		// sort the list from min to max frequency
		// only sort the first remainingNodes.
		sortList(nodeList, remainingNodes);
	}
}
 
void NodeTree::calculateBitCodes(Node *startNode, int isLeftRight, int level, int bitCode)
{
	// set the bitCode for this branch
	if (isLeftRight) 
	{
		bitCode |= (0x01 << (level-1));
	}
 
	if (startNode->pLeftChild != NULL)
	{
		calculateBitCodes(startNode->pLeftChild, 0, level + 1, bitCode);
	}
	if (startNode->pRightChild != NULL)
	{
		calculateBitCodes(startNode->pRightChild, 1, level + 1, bitCode);
	}
	if (startNode->pLeftChild == NULL &&
		startNode->pRightChild == NULL)
	{
		this->addBitCode(startNode->charCode, bitCode, level?level:1);
	}
}
 
NodeTree::NodeTree(CompressionSet *c, char *buffer, int size)
{
	Node **nodeList;
    int i, x, indexNum, cValue;
 
	this->cParent = c;
	this->listSize = (int)pow(2, BITSIZE(cParent->bitCompression));
	cParent->numUniqueChars = 0;
	cParent->bitCodeList = new BitCodeInfo[listSize];
	nodeList = (Node **)malloc(sizeof(Node *) * listSize);
 
	for (i = 0; i < size; i += cParent->bitCompression)
	{
		indexNum = -1;
		cValue = cParent->makeCharCode(&buffer[i]);
 
		for (x = 0; x < cParent->numUniqueChars; x++)
		{
			if (nodeList[x]->charCode == cValue)
			{
				indexNum = x;
			}
		}
		if (indexNum < 0)
		{
			cParent->numUniqueChars++;
			nodeList[cParent->numUniqueChars-1] = new Node(cValue);
			indexNum = cParent->numUniqueChars-1;
		}
		nodeList[indexNum]->freqTotal++;
	}
	
	this->orderNodeTree(nodeList);
    this->calculateBitCodes(*nodeList);
 
	for (i = 0; i < cParent->numUniqueChars; i++)
	{
		free(nodeList[i]);
	}
	free(nodeList);
}