// HuffmanTree.cpp: implementation of the CHuffmanTree class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "Huffman.h"
#include "HuffmanTree.h"
#include "fstream.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

CHuffmanTree::CHuffmanTree(int* pWeightTab, int n)
{
	int m=2*n-1;
	int i;
	int s1,s2;

	nNodeCount=n;
	pHTN=(HuffmanTreeNode*)malloc((m+1)*sizeof(HuffmanTreeNode));

	//-----------初始化哈夫曼樹-------------
	for(i=0;i<n;i++,pWeightTab++)
	{
		pHTN[i].nLChild=0;
		pHTN[i].nParent=0;
		pHTN[i].nRChild=0;
		pHTN[i].fWeight=*pWeightTab;
	}
	for(i=n;i<m;i++)
	{
		pHTN[i].nLChild=0;
		pHTN[i].nParent=0;
		pHTN[i].nRChild=0;
		pHTN[i].fWeight=0;
	}
	//--------------------------------------

	//建哈夫曼樹
	for(i=n;i<m;i++)
	{
		//在HT[1..i－1]選擇parent為0且weight最小的兩個點，其序號分別為s1,s2，其中s1比s2小
		SelectNode(i-1,s1,s2);
		pHTN[s1].nParent=i;
		pHTN[s2].nParent=i;
		pHTN[i].nLChild=s1;
		pHTN[i].nRChild=s2;
		pHTN[i].fWeight=pHTN[s1].fWeight+pHTN[s2].fWeight;
	}
}

CHuffmanTree::~CHuffmanTree()
{
//	free(pHTN);
}

HuffmanCode CHuffmanTree::HuffmanCode()
{
	int i;
	char* TempStr;
	int nStart;
	int c;
	int f;
	char** pHC;
	//HuffmanCode pHC;

	//從葉子到根逆向求每個字符的哈夫曼編碼
	pHC=(char**)malloc((nNodeCount+1)*sizeof(char));
	TempStr=(char*)malloc(nNodeCount*sizeof(char));
	TempStr[nNodeCount-1]='\0';//編碼結束符
	for(i=0;i<nNodeCount;i++)//逐個字符求哈夫曼編碼
	{
		nStart=nNodeCount-1;//編碼結束符位置
		for(c=i,f=pHTN[i].nParent;f!=0;c=f,f=pHTN[f].nParent)//從葉子到根逆向求編碼
			if(pHTN[f].nLChild==c)
				TempStr[--nStart]='0';
			else
				TempStr[--nStart]='1';

		pHC[i]=(char*)malloc((nNodeCount-nStart)*sizeof(char));
		strcpy(pHC[i],&TempStr[nStart]);
	}
	free(TempStr);

	return pHC;
}

void CHuffmanTree::HuffmanTreeDecode()
{

}

void CHuffmanTree::SelectNode(int n,int& s1,int& s2)
{
	float w1,w2;
	int i;

	w1=w2=65536;

	for(i=0;i<=n;i++)
		if(pHTN[i].nParent==0 && pHTN[i].fWeight<w1 && pHTN[i].fWeight>0)
		{
			w1=pHTN[i].fWeight;
			s1=i;
		}
		
	for(i=0;i<=n;i++)
		if(pHTN[i].nParent==0 && pHTN[i].fWeight<w2 && i!=s1 && pHTN[i].fWeight>0)
		{
			w2=pHTN[i].fWeight;
			s2=i;
		}
}