//Reference:A fast algorithm for optimal length-limited Huffman codes.pdf,http://pan.baidu.com/s/1o6E19Bs
//author:by Pan Yumin.2014-06-18
//with the method of BinaryTree and linked-list
#include <stdio.h>
#include <memory.h>
#include <malloc.h>

#define  MaxSymbols 256	//the Maximum Number of Symbols
#define  MaxHuffLen	16	//the Limited Length

typedef unsigned char boolean;
#ifndef FALSE			//in case these macros already exist
#define FALSE	0		//values of boolean
#endif

#ifndef TRUE
#define TRUE	1
#endif

typedef struct __Node{
	int width;
	int weight;
	int index;
	int depth;

	struct __Node *prev;	//double linked list
	struct __Node *next;	//double linked list
	struct __Node *left;	//left child
	struct __Node *right;	//right child
}Node;

typedef struct __HuffTable{
	unsigned int index;
	unsigned int len;
	unsigned int code;
}HuffTable;

//Test memory leak
/*int g_malloc = 0,g_free = 0;

void* my_malloc(int size){
	g_malloc++;
	return malloc(size);
}
void my_free(void *ptr){
	if(ptr){
		g_free++;
		free(ptr);
		ptr = NULL;
	}
}
#define malloc my_malloc
#define free my_free*/

//Get the smallest term in the diadic expansion of X
int GetSmallestTerm(int X)
{
	int N=0;
	while((X & 0x01) == 0){
		X >>= 1;
		N++;
	}
	return 1<<N;
}
void deleteNode(Node *head,unsigned char *Flag,int Symbols,boolean isDelete)
{
	if(head->left == NULL && head->right == NULL){
		if(isDelete)
			Flag[head->depth*Symbols+head->index] = 0;
		else
			Flag[head->depth*Symbols+head->index] = 1;
	}
	if(head->left){
		deleteNode(head->left,Flag,Symbols,isDelete);
	}
	if(head->right){
		deleteNode(head->right,Flag,Symbols,isDelete);
	}
	free(head);	head = NULL;
}

//N:the Num of node
void Package_Merge(Node *head,Node **tail,int minWidth,unsigned char * Flag,int Symbols)
{
	Node *tmp = NULL,*node_1 = NULL,*node_2 = NULL;
	Node *node_P_head = NULL,*node_P_tail = NULL;		//node_P_tail not store data,node_P_head store data
	Node *node_head = head;								//the head of 2*minWidth
	//package
	node_P_tail = (Node *)malloc(sizeof(Node));
	memset(node_P_tail,0,sizeof(Node));

	node_2 = node_P_tail;	node_1 = (*tail)->prev;
	for(;node_1 != NULL && node_1 != head; node_1=(*tail)->prev){
		if(node_1->width == minWidth){
			tmp = (Node*)malloc(sizeof(Node));
			tmp->right = node_1->next;				//insert from right to left,so the weight from small to large
			tmp->left = node_1;
			tmp->width = 2*minWidth;
			tmp->weight = node_1->weight+node_1->next->weight;
			tmp->next = node_2;
			tmp->prev = NULL;

			node_2->prev = tmp;
			node_2 = tmp;
			*tail = node_1->prev;	(*tail)->next = NULL;		//two intervals
		}else{
			break;
		}
	}
	node_P_head = node_2;

	if(*tail != head && (*tail)->width == minWidth){	//if the number of minwidth is odd,delete the max weight item of minwidth
		*tail = (*tail)->prev;
		deleteNode((*tail)->next,Flag,Symbols,TRUE);
		(*tail)->next = NULL;
	}

	//find the range of 2*minWidth
	node_1 = *tail;
	for(;node_1 != head && node_1->width == 2*minWidth;node_1 = node_1->prev){
	}
	node_head = node_1;		//the head of 2*minWidth, node_head not store 2*minWidth

	//merge
	node_1 = node_head->next;	node_2 = node_P_head;
	for(;node_1 != NULL && node_2 != node_P_tail;){
		if(node_1->weight >= node_2->weight){
			node_1 = node_1->next;
		}else{		//insert to the major list
			node_1->prev->next = node_2;
			node_2->prev = node_1->prev;
			node_1->prev = node_2;

			node_2 = node_2->next;
			node_2->prev->next = node_1;

			node_2->prev = NULL;
		}
	}
	if(node_1 == NULL){		//insert list 2 to the major list
		(*tail)->next = node_2;
		node_2->prev = *tail;
		*tail = node_P_tail->prev;
		(*tail)->next = NULL;
		free(node_P_tail);	node_P_tail = NULL;
	}else{
		free(node_P_tail);	node_P_tail = NULL;
	}
}

//N:the Num of node
int LengthLimitedHuffmanCode(Node *head,Node *tail,int X,unsigned char * Flag,int Symbols)
{
	int minwidth,r;

	while(X>0){
		minwidth = GetSmallestTerm(X);
		if( head->next == NULL)		//I empty
			return -1;
		r = tail->width;				//Just for Huffman Code,else r = GetMinWidth(head);
		if(r>minwidth){
			return -2;
		}else if(r == minwidth){
			tail = tail->prev;
			deleteNode(tail->next,Flag,Symbols,FALSE);
			tail->next = NULL;
			X = X-minwidth;
		}else{
			Package_Merge(head,&tail,r,Flag,Symbols);
		}		
	}

	return 0;
}
void PrintHuffCode(HuffTable Huffcode)
{
	int i;
	for(i=Huffcode.len-1;i>=0;i--){
		printf("%d",(Huffcode.code>>i) & 0x01);
	}
}
void GenerateHuffmanCode(HuffTable *HuffCode,unsigned char *Flag,int L,int Symbols,int *SortIndex)
{
	char Code[17];
	int Pre_L = 0;
	int i=0,j=0;
	unsigned int codes[MaxHuffLen+2]={0},rank[MaxHuffLen+1] = {0};	//rank: the number of symbols in every length
	//find the first code
	for(i=0;i<Symbols;i++){
		for(j=0;j<L;j++){
			HuffCode[i].len += Flag[j*Symbols+i];
		}
		if(HuffCode[i].len != 0)
			rank[HuffCode[i].len]++;
		HuffCode[i].index = SortIndex[i];
	}

	for(i=0;i<=L;i++){
		codes[i+1] = (codes[i]+rank[i])<<1;
		rank[i] = 0;
	}

	//code
	for(i=0;i<Symbols;i++){
		HuffCode[i].code = codes[HuffCode[i].len] + rank[HuffCode[i].len]++;
	}
}
float BitsPerSymbol(HuffTable *HuffCode,int *weight,int Symbols,int WeightSum)
{
	float bitspersymbol = 0.0;
	int i;
	for(i=0;i<Symbols;i++){
		bitspersymbol += (float)HuffCode[i].len*weight[i];
	}
	return bitspersymbol/WeightSum;
}

void FreqSort(int *Freq,int *SortIndex,int Symbols)
{
	int i,j,tmp;
	for(i=0;i<Symbols;i++){
		for(j=i+1;j<Symbols;j++){
			if(Freq[i]<Freq[j]){
				tmp = Freq[i];
				Freq[i] = Freq[j];
				Freq[j] = tmp;

				tmp = SortIndex[i];
				SortIndex[i] = SortIndex[j];
				SortIndex[j] = tmp;
			}
		}
	}
}

int GenLenLimitedOptHuffCode(int *Freq,int Symbols)
{
	int i,j;
	unsigned char *Flag = NULL;	//record the state of the node
	unsigned int rank[MaxHuffLen];
	Node *node = NULL,*head = NULL,*tail = NULL,*tmp = NULL;	//head not store data,just a head,tail store data
	int Ret = 0;
	HuffTable HuffCode[MaxSymbols];
	float bitspersymbols = 0.0;
	int WeightSum = 0;
	int SortIndex[MaxSymbols];

	if(Symbols > (1<<MaxHuffLen)){
		printf("Symbols > (1<<MaxHuffLen)\n");
		return -1;
	}

	for(i=0;i<MaxSymbols;i++){
		SortIndex[i] = i;
	}
	FreqSort(Freq,SortIndex,Symbols);		//sort

	for(i=0;i<Symbols;i++){	
		WeightSum += Freq[i];
	}

	head = (Node*)malloc(sizeof(Node));
	memset(head,0,sizeof(Node));
	Flag = (unsigned char*)malloc(MaxHuffLen*Symbols*sizeof(unsigned char));
	memset(Flag,1,MaxHuffLen*Symbols*sizeof(unsigned char));

	memset(HuffCode,0,sizeof(HuffCode));
	node = head;

	for(i=0;i<MaxHuffLen;i++){
		for(j=0;j<Symbols;j++){
			tmp = (Node*)malloc(sizeof(Node));
			tmp->prev = node;							tmp->next = NULL;
			tmp->left = NULL;							tmp->right = NULL;
			tmp->width = 1<<(MaxHuffLen-i-1);
			tmp->weight = Freq[j];
			tmp->index = j;								tmp->depth = i;
			node->next = tmp;
			node = tmp;
		}
	}
	tail = node;	//tail
	Ret = LengthLimitedHuffmanCode(head,tail,(Symbols-1)<<MaxHuffLen,Flag,Symbols);

	GenerateHuffmanCode(HuffCode,Flag,MaxHuffLen,Symbols,SortIndex);
	
	//print HuffCode
	for(i=0;i<Symbols;i++){
		printf("%03d weight:%04d Code:",HuffCode[i].index,Freq[i]);
		PrintHuffCode(HuffCode[i]);
		printf("\tCodeLen:%02d",HuffCode[i].len);
		printf("\n");
	}
	bitspersymbols = BitsPerSymbol(HuffCode,Freq,Symbols,WeightSum);
	printf("average code length:%f bits/symbol.\n",bitspersymbols);

	free(head);	head = NULL;
	free(Flag);	Flag = NULL;

	return Ret;
}
#include <time.h>
int main()
{
	//int Freq[MaxSymbols] = {1,25,3,4,9,6,4,6,26,15,234,4578};	//weight is not zero.
 	int Freq[MaxSymbols] = {10,6,2,1,1};	//weight is not zero.
 	GenLenLimitedOptHuffCode(Freq,5);
 	return 0;
}

运行上述程序输出结果如下所示：