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

   Optimize run-length huffman codes.  For use with output from
   'rlfreq | huffman'

   Algorithm works by optimizing shorter huffman codes first, see
   if they can be replaced by a sequence of shorter huffman codes.
   Algorithm used is brute force search with branch and bound.

   11/27/01
                                                                           */
/*@ -branchstate -compdestroy -compmempass -nullpass -nullstate @*/
/*@ -onlytrans -temptrans @*/

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


#define MAX_LINE_SIZE   128

typedef struct _node
{
   int c, clen, hlen, freq;
   struct _node *next;

} Node;


static void DelList(Node *list);
static int GetNode(Node **list, FILE *infile);
static void OptimizeList(Node **list, FILE *hintfile);

/******************************************************************** main */
int main(int argc, char **argv)
{
   FILE *infile, *outfile, *hintfile;
   Node *list, *cursor;

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


   for(list = NULL; GetNode(&list, infile) == 0;);
   OptimizeList(&list, hintfile);
   for(cursor = list; cursor != NULL; cursor = cursor->next)
   {
      fprintf(outfile, "%d char %d, len %d\n",
         cursor->freq, cursor->c, cursor->clen);
   }


   (void)fclose(hintfile);
   (void)fclose(infile);
   (void)fclose(outfile);
   DelList(list);
   return 0;

} /* main() */

/***************************************************************** DelList */
static void DelList(Node *list)
{
   Node *next;

   for(; list != NULL; list = next)
   {
      next = list->next;
      free(list);
   }

} /* DelList() */

/***************************************************************** GetNode */
static int GetNode(Node **list, FILE *infile)
{
   char buffer[MAX_LINE_SIZE + 1], *p;
   Node *node, **cursor;

   if( fgets(buffer, MAX_LINE_SIZE, infile) == NULL )
      return 1;

   if( (node = (Node*)malloc(sizeof(Node))) == NULL )
      return 1;
   node->hlen = 0;
   for(p = buffer; *p == '0' || *p == '1'; p++)
      node->hlen++;
   if( sscanf(p, " (x %d) -> char %d, len %d",
         &(node->freq), &(node->c), &(node->clen)) != 3 )
   {
      free(node);
      return 1;
   }

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

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

} /* GetNode() */

/************************************************************ OptimizeList */
static void OptimizeList(Node **list, FILE *hintfile)
{
   Node **stack, **bstack, *cursor;
   int stack_size, bstack_size, c, i;
   int clen_current, clen_target, hlen_current, hlen_best;

   if( *list == NULL )
      return;

   OptimizeList(&((*list)->next), hintfile);
   if( *list == NULL || (*list)->next == NULL )
      return;

   c = (*list)->c;
   hlen_best = (*list)->hlen;
   clen_target = (*list)->clen;
   if( (stack = (Node**)malloc(sizeof(Node*) * (hlen_best + 1))) == NULL )
      return;
   if( (bstack = (Node**)malloc(sizeof(Node*) * (hlen_best + 1))) == NULL )
   {
      free(stack);
      return;
   }


   bstack[0] = stack[0] = *list;
   stack_size = bstack_size = 1;
   hlen_current = clen_current = 0;
   while( stack_size > 0 )
   {
      for(stack[stack_size - 1] = stack[stack_size - 1]->next;
          (cursor = stack[stack_size - 1]) != NULL;
          stack[stack_size - 1] = cursor->next)
      {
         if( cursor->c != c )
            continue;
         if( (hlen_current += cursor->hlen) > hlen_best )
         {
            hlen_current -= cursor->hlen;
            continue;
         }
         clen_current += cursor->clen;

         if( clen_current == clen_target )
         {
            assert(hlen_current <= hlen_best);
            bstack_size = stack_size;
            hlen_best = hlen_current;
            memcpy(bstack, stack, stack_size * sizeof(Node*));
         }
         else if( clen_current < clen_target )
         {
            stack[stack_size++] = *list;
            break;
         }
         hlen_current -= cursor->hlen;
         clen_current -= cursor->clen;
      }

      if( stack[stack_size - 1] == NULL )
      {
         stack_size--;
         if( stack_size > 0 )
         {
            hlen_current -= stack[stack_size - 1]->hlen;
            clen_current -= stack[stack_size - 1]->clen;
         }
      }
   }
   assert(hlen_current == 0 && clen_current == 0);


   if( bstack[0] != *list )
   {
      fprintf(hintfile, "char %d, len %d = %d",
         c, clen_target, bstack[0]->clen);
      for(i = 1; i < bstack_size; i++)
         fprintf(hintfile, " %d", bstack[i]->clen);
      (void)fputc('\n', hintfile);

      for(i = 0; i < bstack_size; i++)
         bstack[0]->freq += (*list)->freq;
      cursor = *list;
      *list = (*list)->next;
      free(cursor);
   }

   free(stack);
   free(bstack);

} /* OptimizeList() */