#include "huffman.h"
//2006-11-04
/*利用哈夫曼樹很容易求出給定字符集及其概率(或頻度)分布的最佳不等長編碼。哈夫曼編碼正是一種應用廣泛
  且非常有效的數據壓縮技術。該技術一般可將數據文件壓縮掉20％至90％，其壓縮效率取決于被壓縮文件
  的特征。
*/
/*由哈夫曼樹求得編碼為最優異字頭碼的原因：
①每個葉子字符ci的碼長恰為從根到該葉子的路徑長度li，平均碼長(或文件總長)又是二叉樹的帶權路徑長度WPL。而哈夫曼樹是WPL最小的二叉樹，因此編碼的平均碼長(或文件總長)亦最小。
②樹中沒有一片葉子是另一葉子的祖先，每片葉子對應的編碼就不可能是其它葉子編碼的前綴。即上述編碼是二進制的異字頭碼。
*/

/*-------------------------------------------------------------------------------------*/
//在函數InputWeightData()中調用函數characters_analysis()從而求出了N和M的大小。
void CreateHuffmanTree(HuffmanTree T,const char* const FILENAME) //構造哈夫曼樹;T[M-1]為其根結點
{
	int i;
	int p1;
	int p2;    

	InitHuffmanTree(T); //將T初始化,T有M個結點，即T是有M個元素的數組。
	InputWeightData(T,FILENAME);//輸入N個葉子的權值及數據至T[0．．N-1]的weight域及data域
	for(i = N;i < M;++i){ //共進行N-1次合并，新結點依次存于T[i]中
		SelectMin(T,i - 1,&p1,&p2); //在T[0．．i-1]中選擇兩個權最小的根結點，其序號分別為p1和p2
        T[p1].parent = i; //數組下標；其值>=0。
		T[p2].parent = i;        
        T[i].lchild = p1; //最小權的根結點是新結點的左孩子
		T[i].rchild = p2; //次小權的根結點是新結點的右孩子
		T[i].weight = T[p1].weight + T[p2].weight;
	} 
}

/*-------------------------------------------------------------------------------------*/
//哈夫曼編碼算法——由哈夫曼樹T求得字符集的"哈夫曼編碼表H"
void SetHuffmanEncodeTable(HuffmanTree T,HuffmanCodeTable H) //根據哈夫曼樹T求哈夫曼編碼表H
{
	int child;
	int parent; // c和p分別指示T中孩子和雙親的位置
	int i; 
    char code[N1 + 1]; //臨時存放編碼，數組大小為N1 + 1。
	int start; //指示編碼在code中的起始位置

	code[N1] = '\0'; //編碼結束符
	for(i = 0;i < N;++i){ //依次求N個葉子結點T[i]的編碼
		H[i].ch = T[i].data;//讀入葉子T[i]對應的字符
		start = N1; //編碼起始位置的初值
		child = i; //從葉子T[i]開始上溯
		while((parent = T[child].parent) >= 0){//直至上溯到T[c]是樹根為止,樹根時parent為-1。
			code[--start] = (T[parent].lchild == child) ? '0' : '1';//用一個三目運算符表示
//若T[child]是T[parent]的左孩子，則生成代碼0；否則生成代碼1
            child = parent; //繼續上溯
		}
		strcpy(H[i].bits,&code[start]); //復制編碼位串,在此好好理解字符串拷貝
/*&code[start]表示是以字符串code的從start位置開始到結束的一個code的字符子串。因為start是字符串
  開始的有效位置，所以從此地方開始拷貝字符串。*/
	}
}

/*-------------------------------------------------------------------------------*/
//哈夫曼編碼——對原始數據文件"DATAFILE"的編碼：
//對數據文件中的1個字符進行編碼
char HuffmanEncode(HuffmanCodeTable H,FILE* fp1,FILE* fp2)
{
	int i = 0;
	char ch;
	char code[N1 + 1]; //臨時存放編碼	

	ch = ReadACharFromFile(fp1); //從原始數據文件中讀取一個字符
	if(ch == '\0') //當讀到文件尾標記EOF時返回了標記'\0'
		return ch; //返回'\0'標記讀到文件尾標記EOF

	FindChar(H,ch,&i); //在哈夫曼編碼表H中找到字符ch的位置i
	if(ch == H[i].ch)
		strcpy(code,H[i].bits); //編碼結果存在code中
	WriteStringsToFile(fp2,code);//把字符串code寫入編碼文件保存
	return '!'; //返回非'\0'
}

/*----------------------------------------------------------------------------------*/
//哈夫曼譯碼——對已編碼文件"ENCODEFILE"的譯碼：
/*算法中可以使用T[i].lchild是否為-1來判定T[i]是否為葉子結點，是因為哈夫曼樹是嚴格二叉樹，樹中
  沒有度數為1的分支結點。*/
//哈夫曼樹的根結點為T[M-1]。 
//對1個字符對應的編碼序列進行譯碼
char HuffmanDecode(HuffmanTree T,HuffmanCodeTable H,FILE* fp1,FILE* fp2)
{
	int i;
	char ch;
	char ch1; //臨時存儲所譯碼的對應字符集中的字符。

	i = M -1; //指向樹的根結點。此地方要用M,不能用M1,注意!!!因為Huffman樹的結點總數是M。
	while(1){
		ch = ReadACharFromFile(fp1); //從編碼文件中讀取一個二進制碼'0'或'1'字符
		if(ch == '\0')  //當讀到文件尾標記EOF時返回了標記'\0'
			return ch; //返回'\0'標記讀到文件尾標記EOF

		if(ch == '0')
			i = T[i].lchild; //轉向左孩子
		else
			i = T[i].rchild; //轉向右孩子
		if(T[i].lchild == -1){ //則已到葉子結點
			ch1 = H[i].ch;//對應哈夫曼碼表中的字符
			WriteACharToFile(ch1,fp2); //把譯碼結果寫入譯碼文件保存
			break; //結束此次譯碼
		}
	}
    return '!'; //返回非'\0'
}

/*--------------------------------------------------------------------------------------------*/
void InitHuffmanTree(HuffmanTree T) //將T初始化,T有M個結點，即T是有M個元素的數組。
{
	int i;

/*初始定義的數組大小為M1；其有效數據元素為M個。M是在程序中所求；M1是一個常量,以聲明數組的
  大小(編譯時就要確定數組的大小)。*/
	for(i = 0;i < M1;++i){ //這里M的值還沒有求出來，故對整個初始數組進行初始化
		T[i].data = '\0';
		T[i].weight = 0.0;
		T[i].lchild = -1;
		T[i].rchild = -1;
		T[i].parent = -1;
	}
}	

/*--------------------------------------------------------------------------------------*/
//輸入N個葉子的權值及數據至T[0．．N-1]的weight域及data域
//由分析原始數據文件后得到字符集F的字符個數N。在函數characters_analysis()中求出了N和M。
void InputWeightData(HuffmanTree T,const char* const FILENAME) 
{
	int i;
    StrSetFrequencyTable F; //字符集的頻率(頻度)表F(數組),有N個元素(對應N個字符)

    characters_analysis(F,FILENAME);//分析數據文本文件的字符構成及各字符的頻率(頻度)
//到此已求出了N和M的大小。
	for(i = 0;i < N;++i){ //這里要用N，表示N個葉子結點。不能用N1。注意!!!
		T[i].data = F[i].data;
		T[i].weight = F[i].weight;
	}
}

/*---------------------------------------------------------------------------------*/
void SelectMin(HuffmanTree T,int i,int* p1,int* p2)//在T[0．．i]中選擇兩個權最小的根結點，由p1,p2返回其位置
{
	int minimum1; //最小值位置標記
	int minimum2; //次小值位置標記
	int j;
	int flag1;
	int flag2;
	int FLAG;

	FLAG = 0;
	for(j = 0;j <= i;++j){//在當前的(i+1)個結點中選取兩個權值最小的根結點
		while(T[j].parent != -1)//找一個樹根；為-1時即為求解問題時森林中某孤立樹的樹根。
			++j; 		
		flag1 = j;
		if(FLAG == 0){//第一次要找兩個孤立樹的樹根，以后每次只需找一個；以后不再執行此代碼段。
			while(T[++j].parent != -1)//找下一個孤立樹的樹根；
				continue;
			flag2 = j;
			if(T[flag1].weight < T[flag2].weight){
				minimum1 = flag1;
				minimum2 = flag2;
				FLAG = 1;
				continue;//繼續找下一個孤立樹的樹根;進行下一次for循環
			}
		}
		if(T[flag1].weight < T[minimum1].weight){
            minimum2 = minimum1; //修正次小值
			minimum1 = flag1; //修正最小值
		}			
		else if(T[flag1].weight < T[minimum2].weight)//只需修正次小值
			minimum2 = flag1; 			
	}
	*p1 = minimum1;
	*p2 = minimum2;
}

/*------------------------------------------------------------------------------*/
void FindChar(HuffmanCodeTable H,char ch,int* ptr_i)
{
	int j;

	for(j = 0;j < N;++j){
		if(H[j].ch == ch){
			*ptr_i = j;
			break;
		}
	}
}

/*-------------------------------------------------------------------------------*/
/*① 初始森林中的n棵二叉樹，每棵樹有一個孤立的結點，它們既是根，又是葉子
  ② n個葉子的哈夫曼樹要經過n-1次合并，產生n-1個新結點。最終求得的哈夫曼樹中共有2n-1個結點。
  ③ 哈夫曼樹是嚴格的二叉樹，沒有度數為1的分支結點。

哈夫曼算法的簡要描述:
    　在上述存儲結構上實現的哈夫曼算法可大致描述為(設T的類型為HuffmanTree)：
(1)初始化
將T[0．．m-1]中2n-1個結點里的三個指針均置為空(即置為-1,因為數組下標從0開始)，權值置為0.0，
數據值置為'0'。
(2)輸入
讀人n個葉子的權值存于向量的前n個分量(即T[0．．n-1])中。它們是初始森林中n個孤立的根結點上的權值。
(3)合并
對森林中的樹共進行n-1次合并，所產生的新結點依次放人向量T的第i個分量中(n≤i≤m-1)。每次合并分兩步：
①在當前森林T[0．．i-1]的所有結點中，選取權最小和次小的兩個根結點[p1]和T[p2]作為合并對象，
  這里0≤p1，p2≤i-1。
②將根為T[p1]和T[p2]的兩棵樹作為左右子樹合并為一棵新的樹，新樹的根是新結點T[i]。具體操作：
　將T[p1]和T[p2]的parent置為i，
　將T[i]的lchild和rchild分別置為p1和p2
　新結點T[i]的權值置為T[p1]和T[p2]的權值之和。
注意：合并后T[pl]和T[p2]在當前森林中已不再是根，因為它們的雙親指針均已指向了T[i]，所以下一次合并
      時不會被選中為合并對象。
*/