#include <stdio.h>


// pointer to Huffman node struct
typedef struct thuff_struct *thuffp;

/*
 *  Huffman node struct
 */

typedef struct thuff_struct
{
	char symb;		// symbol
	int freq;		// symbol's frequency
	thuffp next;		// next symbol in stack
	thuffp left, righ;	// Huffman Tree left & right children
} thuff;


/*
 *  hpush (head, symb, freq, left, righ): inserts node in ordered stack
 *
 * input:
 *		head	: pointer to stack's head
 *		symb	: symbol
 *		freq	: symbol's frequency
 *		left	: Huffman Tree left child
 *		righ	: Huffman Tree right child
 *
 * output:
 *		pointer to stack's head, NULL if operation fails
 *
 */

thuffp hpush (thuffp *head, char symb, int freq, thuffp left, thuffp righ)
{
	thuffp node, p, q;

	// allocate new node
	node = (thuffp) malloc (sizeof(thuff));

	// success?
	if (node == NULL)
		return NULL;

	// define new node
	node->symb = symb;
	node->freq = freq;
	node->next = NULL;
	node->left = left;
	node->righ = righ;

	// is stack empty?
	if (*head == NULL)
	{
		*head = node;
		return node;
	}

	// seek where to insert node
	for (p = *head, q = NULL; p != NULL && p->freq < freq; q = p, p = p->next);

	// insert node
	node->next = p;
	if (q != NULL)
		q->next = node;
	else
		*head = node;

	return *head;
}

/*
 *  hpop (head): returns last node in ordered stack
 *
 * input:
 *		head	: pointer to stack's head
 *
 * output:
 *		pointer to last node
 *
 */

thuffp hpop (thuffp *head)
{
	// return current head
	thuffp ret = *head;
	// scrolls head
	*head = (*head)->next;

	return ret;
}

/*
 *  htree (head): builds Huffman Tree from ordered stack
 *
 * input:
 *		head	: stack's head
 *
 * output:
 *		pointer to Huffman Tree head
 *
 */

thuffp htree (thuffp head)
{
	thuffp left, righ;

	// process stack
	for (; head->next != NULL; hpush(&head, '\0', left->freq + righ->freq, left, righ))
	{
		left = hpop(&head);
		righ = hpop(&head);
	}

	return head;
}


/***********************************************
	T E S T I N G   R O U T I N E S
 ***********************************************/
void hscan (thuffp p, char *shot)
{
	char buf[10];
	memset(buf, '\0', sizeof buf);

	if (p == NULL)
		return;

	if (p->symb)
		printf("%c: %s\n", p->symb, shot);

	if (shot != NULL)
		strcpy(buf, shot);
	strcat(buf, "0");
	hscan(p->left, buf);

	if (shot != NULL)
		strcpy(buf, shot);
	strcat(buf, "1");
	hscan(p->righ, buf);
}

main ()
{
	thuffp head = NULL;

	hpush(&head, 'a', 4, NULL, NULL);
	hpush(&head, 'b', 63, NULL, NULL);
	hpush(&head, 'c', 86, NULL, NULL);
	hpush(&head, 'd', 23, NULL, NULL);
	hpush(&head, 'e', 21, NULL, NULL);
	hpush(&head, 'f', 4, NULL, NULL);
	hpush(&head, 'g', 7, NULL, NULL);
	hpush(&head, 'h', 72, NULL, NULL);
	hpush(&head, 'i', 54, NULL, NULL);


	//clrscr();
	printf("Built Huffman tree:\n\n");
	hscan(htree(head), NULL);

	return 0;
}