#include <stdio.h>

#include <stdlib.h>

#include <string.h>



#define MAX 20

#define INFINIT	65535



typedef struct _HTNode{

	int weight;

	int parent;

	int left;

	int right;

}HTNode;



void HuffmanCoding(HTNode **HT, char ***HC, int *w, int n)

{

	int i;

	int m;

	int ma,mb,mt;

	int sa,sb;

	int j;



	HTNode *p = NULL;

	char **q = NULL;

	char *cd = NULL;

	int start;



	/* Initial the huffman tree */



	m = 2*n-1;

	p = (HTNode *)malloc(sizeof(HTNode)*(m+1));

	*HT = p;

	for(i=1; i<=n; i++){

		p[i].weight = w[i];

		p[i].parent = p[i].left = p[i].right = 0;

	}

	for(;i<=m;i++){

		p[i].weight = 0;

		p[i].parent = p[i].left = p[i].right = 0;

	}



	/* Create the huffman tree */



	for(i=n+1; i<=m; i++){

		/* Select two minimal number from 1 to i-1 */

		ma = mb = INFINIT;

		for(j=1; j<=i-1; j++){

			if(p[j].parent == 0){

				if(mb > p[j].weight){

					mb = p[j].weight;



					sb = j;

				}

				if(ma > mb){

					mt = ma;

					ma = mb;

					mb = mt;



					mt = sa;

					sa = sb;

					sb = mt;

				}		

			}

		}



		p[sa].parent = i;

		p[sb].parent = i;

		p[i].left = sa;

		p[i].right = sb;

		p[i].weight = p[sa].weight + p[sb].weight;

	}





	/* Encode every character from bottom to top.

	 * Of course you can also do it from top to bottom. */



	q = (char **)malloc(sizeof(char *)*(n+1));

	*HC = q;



	cd = (char *)malloc(sizeof(char)*n);

	for(i=1; i<=n; i++){

		start = n-1;

		cd[start] = 0;

		for(j=i; p[j].parent; j=p[j].parent){

			if(p[ p[j].parent ].left == j){

				cd[--start] = '0';

			}else{

				cd[--start] = '1';

			}

		}

		q[i] = (char *)malloc(sizeof(char)*(n-start));

		strcpy(q[i], &cd[start]);

	}



	free(cd);

	cd = NULL;

}



void main()

{

	HTNode *HT;	

	char **HC;



	int weight[] = {-1, 7, 5, 2, 4}; /* From 1 */

	int data[] = {' ', 'a', 'b', 'c', 'd'};

	int n = sizeof(data)/sizeof(int)-1;

	int i,j;



	printf("log.anycle.com\n\n");

	printf("Original data:\n");

	for(i=1; i<=n; i++){

		printf("  %c(%2d)", data[i], weight[i]);

	}

	printf("\n");



	printf("Huffman coding:\n");

	HuffmanCoding(&HT, &HC, weight, n);



	for(i=1; i<=n; i++){

		printf("  %c(%s)", data[i], HC[i]);

	}

	printf("\n");

}