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

   Construct generic huffman trees.  Takes line delimited files as input,
   where each line contains decimal frequency, followed by whitespace,
   followed by node description.  Writes huffman codes for each node to
   output.

   11/19/01
                                                                           */
/*@ -branchstate -compdef -compmempass -mustfree -nullret -nullstate @*/
/*@ -onlytrans -temptrans -unqualifiedtrans @*/

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


#define INIT_BUFFER_SIZE     32

typedef struct _node
{
   int freq;
   char *name;
   struct _node *next, *left, *right, *parent;

} Node;

static int ConvertToTree(Node **heap);
static void DumpNode(Node *node, FILE *outfile);
static void DumpTree(Node *node, FILE *outfile);
static void FreeHeap(Node *heap);
static /*@null@*/Node *GetNode(FILE *infile, char **buffer, size_t *size);
static void InsertHeap(Node **heap, Node *node);
static Node *PopHeap(Node **heap);

/******************************************************************** main */
int main(int argc, char **argv)
{
   FILE *infile, *outfile;
   Node *heap, *node;
   char *buffer;
   size_t size;

   infile = stdin;
   outfile = stdout;
   if( argc > 1 )
   {
      if( (infile = fopen(argv[1], "rt")) == NULL )
         return printf("Can not open %s\n", argv[1]);
      if( argc > 2 )
      {
         if( (outfile = fopen(argv[2], "wt+")) == NULL )
         {
            (void)fclose(infile);
            return printf("Can not create %s\n", argv[2]);
         }
      }
   }

   if( (buffer = (char*)malloc(size = INIT_BUFFER_SIZE)) == NULL )
   {
      (void)fclose(infile);
      (void)fclose(outfile);
      return puts("Not enough memory.");
   }


   heap = NULL;
   while( (node = GetNode(infile, &buffer, &size)) != NULL )
   {
      assert(node->name != NULL);
      if( node->freq > 0 && *(node->name) != '\0' )
      {
         InsertHeap(&heap, node);
      }
      else
      {
         free(node->name);
         free(node);
      }
   }
   (void)fclose(infile);
   free(buffer);

   if( heap == NULL )
   {
      (void)fclose(outfile);
      printf("No node loaded from %s\n", argv[1]);
      return 0;
   }
   if( heap->next == NULL )
   {
      assert(heap->name != NULL);
      free(heap->name);
      free(heap);
      (void)fclose(outfile);
      printf("Only one node in %s\n", argv[1]);
      return 0;
   }

   if( ConvertToTree(&heap) != 0 )
   {
      (void)fclose(outfile);
      return puts("Not enough memory.");
   }
   assert(heap != NULL && heap->left != NULL && heap->right != NULL);
   DumpTree(heap, outfile);


   (void)fclose(outfile);
   FreeHeap(heap);
   return 0;

} /* main() */


/*********************************************************** ConvertToTree */
static int ConvertToTree(Node **heap)
{
   Node *node, *a, *b;

   while( (*heap)->next != NULL )
   {
      if( (node = (Node*)malloc(sizeof(Node))) == NULL )
         return 1;
      a = PopHeap(heap);
      b = PopHeap(heap);
      assert(a != NULL && b != NULL);
      node->freq = (node->left = a)->freq + (node->right = b)->freq;
      node->next = node->parent = NULL;
      a->parent = b->parent = node;
      node->name = NULL;
      InsertHeap(heap, node);
   }

   return 0;

} /* ConvertToTree() */

/**************************************************************** DumpNode */
static void DumpNode(Node *node, FILE *outfile)
{
   if( node->parent == NULL )
      return;
   DumpNode(node->parent, outfile);
   (void)fputc(node->parent->left == node ? '0' : '1', outfile);

} /* DumpNode() */

/**************************************************************** DumpTree */
static void DumpTree(Node *node, FILE *outfile)
{
   if( node == NULL )
      return;
   if( node->name != NULL )
   {
      DumpNode(node, outfile);
      fprintf(outfile, " (x %d) -> %s\n", node->freq, node->name);
   }
   DumpTree(node->left, outfile);
   DumpTree(node->right, outfile);

} /* DumpTree() */

/**************************************************************** FreeHeap */
static void FreeHeap(Node *heap)
{
   Node *cursor, *next;

   for(cursor = heap; cursor != NULL; cursor = next)
   {
      FreeHeap(cursor->left);
      next = cursor->right;
      if( cursor->name != NULL )
         free(cursor->name);
      free(cursor);
   }

} /* FreeHeap() */

/***************************************************************** GetNode */
static Node *GetNode(FILE *infile, char **buffer, size_t *size)
{
   size_t pos;
   char *p;
   Node *r;

   assert(infile != NULL);
   assert(buffer != NULL && *buffer != NULL);
   assert(size != NULL);

   if( fgets(*buffer, (int)*size, infile) == NULL )
      return NULL;
   while( (pos = strlen(*buffer)) + 1 == *size )
   {
      if( *(*buffer + pos - 1) == '\n' || *(*buffer + pos - 1) == '\r' )
         break;
      if( (p = (char*)malloc(*size * 2)) == NULL )
         break;

      *size *= 2;
      strcpy(p, *buffer);
      free(*buffer);
      *buffer = p;

      if( fgets(*buffer + pos, (int)(*size - pos), infile) == NULL )
         break;
   }

   for(p = *buffer + strlen(*buffer) - 1;
       p > *buffer && isspace((int)*p);
       *(p--) = '\0');

   if( (r = (Node*)malloc(sizeof(Node))) == NULL )
      return NULL;
   r->freq = atoi(*buffer);

   for(p = *buffer; *p != '\0' && isspace((int)*p); p++);
   for(; *p != '\0' && isdigit((int)*p); p++);
   for(; *p != '\0' && isspace((int)*p); p++);

   if( (r->name = (char*)malloc(strlen(p) + 1)) == NULL )
   {
      free(r);
      return NULL;
   }
   strcpy(r->name, p);

   r->next = r->parent = r->left = r->right = NULL;
   return r;

} /* GetNode() */

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

   assert(node != NULL);
   for(cursor = heap;
      *cursor != NULL && (*cursor)->freq < node->freq;
       cursor = &((*cursor)->next));

   node->next = *cursor;
   *cursor = node;

} /* InsertHeap() */

/***************************************************************** PopHeap */
static Node *PopHeap(Node **heap)
{
   Node *r;

   assert(heap != NULL && *heap != NULL);
   r = *heap;
   *heap = r->next;
   return r;

} /* PopHeap() */