#include "huffman_g.h"/*A. Moffat和J. Katajainen設計的使用最少內存空間計算最小冗余編碼（Huffman編碼）的算法源代碼。在元素權值已從小到大排序的前提下，此算法通過對數組進行3次遍歷，不使用額外數組空間，即可得到所有元素的Huffman碼長（bit length）。經此函數計算碼長后，利用Canonical Huffman編碼方法，可以得到所有元素的編碼。參數	A	包含各元素的權值的數組，調用前，應將數組A中的權值按從小到大排序	n	數組A中元素的個數*/void huffman_g::calculate_minimum_redundancy(unsigned long A[], int n) {	int root; /* 在第1次遍歷中是當前子樹的根結點，在第3次遍歷中是當前深度中的分支結點 */	int leaf; /* 只用于第1次遍歷，是下一個要考察的葉子結點 */	int next; /* 在第1次遍歷中，是下一個合并用的結點（子樹），該位置將存儲該子樹					的兩個分支合并后的權值總和；					在第2次遍歷中，是簡單循環變量；					在第3次遍歷中，是將要填入碼長值的元素位置 */	int avbl; /* 用于第3次遍歷，是當前深度中可用結點數量。					最初等于該層結點總數，由上一層分支結點總數乘2得來。					然后逐一排除分支結點，剩下的就是該層葉子結點總數 */	int used; /* 用于第3次遍歷，是當前深度中分支結點總數 */	int dpth; /* 用于第3次遍歷，當前深度，如果當前層有葉子結點，即為該葉子結點的碼長 */	/* 邊界條件檢查	*/	if (n==0) {	return;	}	if (n==1) {	A[0] = 0; return; }	/* 		第1次遍歷，從左至右。		第1次遍歷的結果是，A[0]..A[n-3]對應于所有分支結點（不包含根結點），其中的數值為該		分支結點的雙親結點索引；A[n-2]對應于根結點，其中的數值是所有權值的總和。所有分支		結點的排列順序：從左到右是二叉樹中從下向上的順序（假定樹根在上），深度相同的分支		結點排列在一起。		參考：在Huffman樹中，所有分支結點都有左、右兩個子樹，這樣的二叉樹中，當葉子結點數		量為n時，分支結點（含根結點）數量為n-1	*/	/*		首先將最小的兩個元素（葉子結點）合并為子樹，其權值之和存入A[0]中。這時，當前子樹		根為數組中第0個元素，因此root=0，下一個要考察的葉子結點是第3個元素，因此leaf=2	*/	A[0] +=	A[1]; root = 0;	leaf = 2;	/* 從1到n-1循環，生成所有分支結點，并將它們連成完整的二叉樹	*/	for	(next=1; next <	n-1; next++) {		/* 在root所指的當前子樹和leaf所指的葉子結點中選一個最小的，作為下一個子樹的一個分支	*/		if (leaf>=n	|| A[root]<A[leaf])	{			/* 如果root所指的當前子樹比leaf所指的葉子結點小				則將root所指的當前子樹作為下一個子樹的第一個分支				其值（當前子樹的權值總和）存入next所指的下一子樹的根結點中				然后令root所指的當前子樹的雙親結點等于next				同時root加1，考察下一個子樹 */			/* 如果已考察完所有葉子結點，而next還小于n-1，則表明現有的子樹還沒有完全連入				1棵完整的Huffman樹（這相當于沒有深度為n-1-next的葉子結點），這時也需要執				行同樣的操作，以便將現有子樹連在一起	*/			A[next]	= A[root]; A[root++] = next;		} else			/* 如果root所指的當前子樹大于等于leaf所指的葉子結點				則將leaf所指的葉子結點作為下一個子樹的第一個分支				其值（當前子樹的權值總和）存入next所指的下一子樹的根結點中				leaf加1，繼續考察下一個葉子結點 */			A[next]	= A[leaf++];		/* 在root所指的當前子樹和leaf所指的葉子結點中選一個最小的，作為下一個子樹的另一個分支 */		if (leaf>=n	|| (root<next && A[root]<A[leaf])) {			A[next]	+= A[root];	A[root++] =	next;		} else			A[next]	+= A[leaf++];	}		/* 		第2次遍歷，從右至左，設置所有分支結點的深度。		第2次遍歷的結果是，A[n-2]..A[0]順序保存了從根結點到最底層的所有分支結點的深度信息。	*/	/* 將根結點的深度設置為0 */	A[n-2] = 0;	for	(next=n-3; next>=0;	next--)		/* 將每個分支結點的深度設置為其雙親結點深度加1 */ 		A[next]	= A[A[next]]+1;	/* 		第3次遍歷，從右至左，設置所有葉子結點的深度（碼長） 		第3次遍歷的結果是，A[0]..A[n-1]順序保存了每個元素的碼長（即元素在二叉樹中的深度）	*/	/* 		從根出發，因此root為n-2，當前深度dpth為0；		used用于統計當前深度中分支結點數目，其初始值為0；		avbl為根據上一層分支結點算出的當前層結點數目，因初始時是根結點，所有結點數目為1；		next指向下一個要設置的元素位置，從最后一個元素開始；		說明：從右向左看，傳入此函數的元素權值最初是從大到小排列的，其深度值或碼長必然是		從小到大排列的，而第2次遍歷后得到的分支結點深度是從0逐漸增大的，因此，只要從根開		始，知道每一層葉子結點數目，在數組中填相應數目的當前深度值就可以了。	*/	avbl = 1; used = dpth =	0; root	= n-2; next	= n-1;	while (avbl>0) {		/* 對當前層的所有分支結點循環 */		while (root>=0 && A[root]==(unsigned int)dpth) { 			/* 分支結點計數used加1 */			used++;	root--;		}		/* 這時，avbl和used的差值就是當前層的葉子結點數目 */		/* 對當前層所有葉子結點循環 */ 		while (avbl>used) { 			/* 從右至左設置元素的深度值（碼長） */			A[next--] =	dpth; avbl--;		}		/* 下一層的結點總數等于當前層分支結點乘2；深度值加1；used清0 */		avbl = 2*used; dpth++; used	= 0;	}}void huffman_g::generate_codes(int num, const unsigned long* weights){	if (num <= 1 || weights == NULL)		throw new huffman_exception("參數非法");	unsigned long* A = new unsigned long[num];		memcpy(A, weights, num * sizeof(unsigned long));	// 只計算權值非0的元素（因為傳入的數據已從小到大排序，只簡單忽略前面的0即可）	int i = 0;	while (A[i] == 0) i++;	calculate_minimum_redundancy(A + i, num - i);	code_lens.clear();	for (int i = 0; i < num; i++)		code_lens.push_back(A[i]);	generate_canonical_codes();		delete[] A;}