#include <stdio.h>
#include <math.h>
#define TABLELENGTH 128
#define MAXSIZE 512
typedef struct tagHTNode
{
	int Parent;
	int LeftChild;
	int RightChild;
	int Weight;
}HTNode;
typedef struct tagCode
{
	char code[MAXSIZE];
	int Weight;
}Code;
typedef HTNode HuffTree[2*TABLELENGTH];
typedef Code HuffCode[TABLELENGTH];
int SelectHTNode(HuffTree HT,int n,int *min1,int *min2)
{
	int cnt=0;
	for(int i=0;i<n;i++)
	{	
		if(HT[i].Weight>0 && HT[i].Parent==-1)
			cnt++;
	}
	if(cnt<=1)
		return 0;
	for(i=0;i<n;i++)
	{
		if(HT[i].Parent==-1 && HT[i].Weight>0)
		{
			*min1=i;
			break;
		}
	}
	for(i=0;i<n;i++)
	{
		if(HT[i].Parent==-1 && HT[i].Weight>0 && i!=*min1)
		{
			*min2=i;
			break;
		}
	}
	for(i=0;i<n;i++)
	{
		if(HT[i].Parent==-1 && HT[i].Weight>0)
		{
			if(HT[*min1].Weight>HT[i].Weight)
			{
				*min2=*min1;
				*min1=i;
			}
			else if(HT[*min2].Weight>HT[i].Weight && i!=*min1)
				*min2=i;
		}
	}
	return 1;
}
void GenerateTree(HuffTree HT,HuffCode hc)
{
	int min1,min2;
	for(int i=0;i<TABLELENGTH;i++)
	{
		HT[i].Weight=hc[i].Weight;
		HT[i].LeftChild=HT[i].RightChild=HT[i].Parent=-1;
	}
	for(;i<2*TABLELENGTH-1;i++)
	{
		HT[i].LeftChild=HT[i].RightChild=HT[i].Parent=-1;
	}
	for(i=TABLELENGTH;i<2*TABLELENGTH-1;i++)
	{
		int r=SelectHTNode(HT,i,&min1,&min2);
		if(r<1)
			break;
		HT[min1].Parent=i;
		HT[min2].Parent=i;
		HT[i].LeftChild=min1;
		HT[i].RightChild=min2;
		HT[i].Weight=HT[min1].Weight+HT[min2].Weight;
	}
}
void GenerateCode(HuffTree HT,HuffCode hc)
{
	int Stack[MAXSIZE],top=-1,tc;
	char flag[MAXSIZE];
	HTNode th;
	for(int i=0;i<TABLELENGTH /*&& HT[i].Weight>0*/;i++)
	{
		top=-1;
		int j=0;
		th=HT[i];
		tc=i;
		while(th.Parent!=-1)
		{
			Stack[++top]=th.Parent;
			if(HT[th.Parent].LeftChild==tc)
			{
				flag[top]='L';
				tc=th.Parent;
			}
			else if(HT[th.Parent].RightChild==tc)
			{
				flag[top]='R';
				tc=th.Parent;
			}
			th=HT[Stack[top]];
		}
		while(top!=-1)
		{
			if(flag[top]=='L')
				hc[i].code[j++]='0';
			else
				hc[i].code[j++]='1';
			top--;
		}
		hc[i].code[j]='\0';
	}
}
int GetProbability(HuffCode hc)
{
	FILE *in;
	int c,nTotal=0;
	for(int i=0;i<TABLELENGTH;i++)
	{
		hc[i].Weight=0;
	}
	in=fopen("Huffman.cpp","rb");
	if(in==NULL)
	{
		printf("No such file!");
		return 0;
	}
	while((c=fgetc(in))!=EOF)
	{
		hc[c].Weight++;
		nTotal++;
	}
	return nTotal;
}
void main()
{
	int nCount;
	HuffTree HT;
	HuffCode hc;
	nCount=GetProbability(hc);
	GenerateTree(HT,hc);
	GenerateCode(HT,hc);	
	for(int i=0;i<TABLELENGTH;i++)
	{
		if(hc[i].Weight!=0)
		{
			printf("Ascii Code:%c,Weight:%3.2lf,Encode to:%s\n",i,(double)hc[i].Weight/nCount,hc[i].code);
		}
	}
}