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

   Generate frequencies for run length data.

   11/21/01
                                                                           */
/*@ -branchstate -compmempass -nullpass -nullstate -temptrans @*/

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

typedef struct _node
{
   int c, len, freq;
   struct _node *left, *right;

} Node;


static int AddNode(Node **bst, int c, int len);
static void DelTree(Node *bst);
static void DumpTree(Node *bst, FILE *outfile);

/******************************************************************** main */
int main(int argc, char **argv)
{
   FILE *infile, *outfile;
   int i, c, len;
   Node *data;

   infile = stdin;
   outfile = stdout;
   if( argc > 1 )
   {
      if( (infile = fopen(argv[1], "rb")) == 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]);
         }
      }
   }


   data = NULL;
   c = EOF;
   len = 0;
   do
   {
      i = fgetc(infile);
      if( i != c )
      {
         if( c != EOF )
         {
            if( AddNode(&data, c, len) != 0 )
            {
               (void)puts("Out of memory");
               break;
            }
         }
         c = i;
         len = 1;
      }
      else
      {
         len++;
      }
   } while( i != EOF );


   DumpTree(data, outfile);

   (void)fclose(infile);
   (void)fclose(outfile);
   DelTree(data);
   return 0;

} /* main() */

/***************************************************************** AddNode */
static int AddNode(Node **bst, int c, int len)
{
   Node **cursor;
   Node *node;

   for(cursor = bst;
      *cursor != NULL && ((*cursor)->c != c || (*cursor)->len != len);)
   {
      if( (*cursor)->c == c )
      {
         if( (*cursor)->len == len )
            break;
         cursor = (*cursor)->len < len ? &((*cursor)->left)
                                       : &((*cursor)->right);
      }
      else
      {
         cursor = (*cursor)->c < c ? &((*cursor)->left)
                                   : &((*cursor)->right);
      }
   }

   if( *cursor != NULL )
   {
      (*cursor)->freq++;
      return 0;
   }

   if( (node = (Node*)malloc(sizeof(Node))) == NULL )
      return 1;
   node->c = c;
   node->len = len;
   node->freq = 1;
   node->left = node->right = NULL;
   *cursor = node;
   return 0;

} /* AddNode() */

/***************************************************************** DelTree */
static void DelTree(Node *bst)
{
   Node *cursor, *next;

   for(cursor = bst; cursor != NULL; cursor = next)
   {
      DelTree(cursor->left);
      next = cursor->right;
      free(cursor);
   }

} /* DelTree() */

/**************************************************************** DumpTree */
static void DumpTree(Node *bst, FILE *outfile)
{
   Node *cursor;

   for(cursor = bst; cursor != NULL; cursor = cursor->right)
   {
      DumpTree(cursor->left, outfile);
      fprintf(outfile, "%d char %d, len %d\n",
         cursor->freq, cursor->c, cursor->len);
   }

} /* DumpTree() */