/* gentree.c - Don Yang (uguu.org)

   Generate Huffman tree from frequency table.

   09/13/01
                                                                           */

#include<assert.h>
#include<ctype.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include"freq.h"

#define CHAR_COUNT      256
#define INTERNAL_NODE   -1


typedef struct _node
{
   int key, data;
   struct _node *left, *right;
   struct _node *next;

} Node;

static void AssignIndex(Node *node, int *index, int depth, int *maxdepth);
static Node *CreateNode(int key, int data);
static Node *CreateTree(int *freq);
static void DeleteTree(Node *root);
static void FlattenIndex(Node *node, int *left, int *right);
static void FlattenTree(Node *root, int *left, int *right, int *depth);
static Node *HeapPop(Node **heap);
static void HeapPush(Node **heap, Node *node);
static void PrintArray(int *array, char *name);
static void PrintBitStrings(int *left, int *right, int node, char *string);

/******************************************************************** main */
int main(void)
{
   char *bitstring;
   int left[CHAR_COUNT - 1], right[CHAR_COUNT - 1];
   int depth;
   Node *tree;

   tree = CreateTree(Frequencies);
   depth = 0;
   FlattenTree(tree, left, right, &depth);
   DeleteTree(tree);

   printf("#define HUFFMAN_TREE_DEPTH  %d\n", depth);
   PrintArray(left, "Left");
   PrintArray(right, "Right");

   (void)puts("/*");
   bitstring = (char*)malloc((size_t)(depth + 1));
   assert(bitstring != NULL);

   bitstring[0] = '\0';
   PrintBitStrings(left, right, 0, bitstring);

   free(bitstring);
   (void)puts("*/");
   return 0;

} /* main() */


/************************************************************* AssignIndex */
static void AssignIndex(Node *node, int *index, int depth, int *maxdepth)
{
   assert(node != NULL);

   if( depth > *maxdepth )
      *maxdepth = depth;

   if( node->data == INTERNAL_NODE )
   {
      node->key = (*index)++;
      AssignIndex(node->left, index, depth + 1, maxdepth);
      AssignIndex(node->right, index, depth + 1, maxdepth);
   }
   else
   {
      node->key = -node->data;
   }

} /* AssignIndex() */

/************************************************************** CreateNode */
static Node *CreateNode(int key, int data)
{
   Node *node;

   node = (Node*)malloc(sizeof(Node));
   assert(node != NULL);
   node->key = key;
   node->data = data;
   node->left = node->right = NULL;
   return node;

} /* CreateNode() */

/************************************************************** CreateTree */
static Node *CreateTree(int *freq)
{
   Node *heap, *n1, *n2, *node;
   int i;

   /* Create forest */
   heap = NULL;
   for(i = 0; i < CHAR_COUNT; i++)
      HeapPush(&heap, CreateNode(freq[i], i));

   /* Create tree */
   for(i = 0; i < CHAR_COUNT - 1; i++)
   {
      n1 = HeapPop(&heap);
      n2 = HeapPop(&heap);
      assert(n1 != NULL && n2 != NULL);
      node = CreateNode(n1->key + n2->key, INTERNAL_NODE);
      node->left = n1;
      node->right = n2;
      HeapPush(&heap, node);
   }

   /* Return root node */
   return HeapPop(&heap);

} /* CreateTree() */

/************************************************************** DeleteTree */
static void DeleteTree(Node *root)
{
   if( root == NULL )
      return;
   DeleteTree(root->left);
   DeleteTree(root->right);
   free(root);

} /* DeleteTree() */

/************************************************************ FlattenIndex */
static void FlattenIndex(Node *node, int *left, int *right)
{
   assert(node->data == INTERNAL_NODE && node->key < CHAR_COUNT);

   if( (left[node->key] = node->left->key) > 0 )
      FlattenIndex(node->left, left, right);
   if( (right[node->key] = node->right->key) > 0 )
      FlattenIndex(node->right, left, right);

} /* FlattenIndex() */

/************************************************************* FlattenTree */
static void FlattenTree(Node *root, int *left, int *right, int *depth)
{
   int i;

   /* Assign indexes to internal nodes */
   i = 0;
   AssignIndex(root, &i, 1, depth);

   /* Write indexes */
   FlattenIndex(root, left, right);

} /* FlattenTree() */

/***************************************************************** HeapPop */
static Node *HeapPop(Node **heap)
{
   Node *node;

   if( heap == NULL || *heap == NULL )
      return NULL;

   node = *heap;
   *heap = (*heap)->next;
   return node;

} /* HeapPop() */

/**************************************************************** HeapPush */
static void HeapPush(Node **heap, Node *node)
{
   Node **cursor;

   for(cursor = heap; *cursor != NULL; cursor = &((*cursor)->next))
   {
      if( (*cursor)->key > node->key )
         break;
   }
   node->next = *cursor;
   *cursor = node;

} /* HeapPush() */

/************************************************************** PrintArray */
static void PrintArray(int *array, char *name)
{
   int i;

   printf("int %s[%d] =\n{\n", name, CHAR_COUNT - 1);
   for(i = 0; i < CHAR_COUNT - 1; i++)
   {
      if( i % 10 == 0 )
         printf("   ");
      printf("%4d", array[i]);
      printf((i < CHAR_COUNT - 2) ? "," : "\n};\n");
      if( (i + 1) % 10 == 0 )
         (void)putchar('\n');
   }

} /* PrintArray() */

/********************************************************* PrintBitStrings */
static void PrintBitStrings(int *left, int *right, int node, char *string)
{
   size_t x;
   int c;

   x = strlen(string);
   string[x] = '0';
   string[x + 1] = '\0';
   if( (c = left[node]) <= 0 )
   {
      if( isprint(-c) )
         printf("   %02x %c -> %s\n", (unsigned)(-c), -c, string);
      else
         printf("   %02x   -> %s\n", (unsigned)(-c), string);
   }
   else
   {
      PrintBitStrings(left, right, c, string);
   }

   string[x] = '1';
   if( (c = right[node]) <= 0 )
   {
      if( isprint(-c) )
         printf("   %02x %c -> %s\n", (unsigned)(-c), -c, string);
      else
         printf("   %02x   -> %s\n", (unsigned)(-c), string);
   }
   else
   {
      PrintBitStrings(left, right, c, string);
   }

   string[x] = '\0';

} /* PrintBitStrings() */