#include"heap.h"
#include<stdlib.h>
#include<string.h>
#include<stddef.h>
#define LIBRARYIMPLEMENTATION

typedef struct{
 heap *lib_on_which_heap;
 struct libnode *root;
 long number_of_entries;
}library;

struct libnode{
 struct libnode *left;
 struct libnode *right;
 long how_often_occurred;
 unsigned char *string;
};

#include "library.h"

static void fill_nodelist( struct libnode *node, struct libnode ***nodelist );
static int compare( struct libnode **first, struct libnode **second );
static void fill_tree_hist(struct libnode *node,long tree_hist[],long weight_hist[],long histlenght,long *deepest_branch,int depth);
static struct libnode *reorder(struct libnode *node, long *depth,long level);


library *library_create( long blocksize )
{
 library *lib;
 heap *lib_heap;
 if( NULL == ( lib_heap = heap_create( blocksize ))) return(NULL);
 if( NULL == ( lib = heap_allocate( lib_heap, sizeof( library )))) return(NULL);
 lib->lib_on_which_heap = lib_heap;
 lib->root = NULL;
 lib->number_of_entries = 0;
 return(lib);
}                                                                               /* library_create */

void library_delete( library *lib )
{
 heap_delete( lib->lib_on_which_heap );
}


int library_read( library *lib, FILE *libfile ) /* reads library */
{
 long occurrences;
 unsigned char string[256];

 while(!feof(libfile))
   {
     if (!fscanf(libfile,"%s\t%ld\n", string, &occurrences)) break;
     if ( occurrences <= 0 ) break;
     if (!library_enter_entry( lib, string, occurrences ))
       return(0);      /* eintragen hat nicht geklappt */

   }                                   /* while !feof() */
 return(1);
}


int library_write( library *lib, FILE *libfile )
{
 long i;
 struct libnode **localptr;
 struct libnode **nodelist;
 if ( NULL == (nodelist = (struct libnode **)malloc( sizeof(struct libnode *)*lib->number_of_entries))) return(0);
 localptr = nodelist;
 fill_nodelist( lib->root, &localptr );
 qsort( nodelist, lib->number_of_entries, sizeof( struct libnode *), (int  (*)(const void *, const void *)) compare );
/* the qsort is buggy in some libraries, to have a look at the result!! */
 for(i = 0; i < lib->number_of_entries; i++ )
   fprintf( libfile, "%s\t%ld\n", nodelist[i]->string, nodelist[i]->how_often_occurred);
 fprintf( libfile, "end-of-file\t-1\n");
 free(nodelist);
 return(1);
}                                                                                       /* library_write */

static void fill_nodelist( struct libnode *node, struct libnode ***nodelist )
{
 if( node )
   {
     *((*nodelist)++) = node;
     fill_nodelist( node->left, nodelist );
     fill_nodelist( node->right, nodelist );
   }
}                                                       /* fill_nodelist */

static int compare( struct libnode **first, struct libnode **second )
{
 long local;

 local =(*first)->how_often_occurred - (*second)->how_often_occurred;
 if (local < 0 ) return( 1 );
 if (local > 0 ) return( -1 );
 return( 0 );
}


int library_enter_entry( library *lib, const unsigned char *string, long occurrences_so_far )
{
 int comp = 1;
 struct libnode *node;
 struct libnode **dest;

 if( lib->root == NULL ) /* leere lib */
   dest = &(lib->root);
 else
   {
     node = lib->root;
     while( 0 != ( comp = strcmp(node->string,string)))
       {
         if ( comp > 0 )
           {
             if ( node->left )
               {
                 node = node->left;
                 continue;
               }
             else
               {
                 dest = &(node->left);
                 break;
               }
           }
         else if( comp < 0 )
           {
             if ( node->right )
               {
                 node = node->right;
                 continue;
               }
             else
               {
                 dest = &(node->right);
                 break;
               }
           }
       }
   }
 if ( comp == 0 )
   {
     node->how_often_occurred += occurrences_so_far;
     return( 1 );
   }

 *dest = heap_allocate( lib->lib_on_which_heap, sizeof(struct libnode)+ strlen(string)+1 );
 if(!*dest ) return( 0 );
 (*dest)->left = NULL;
 (*dest)->right = NULL;
 (*dest)->string = (unsigned char *)( *dest + 1 ); /* da soll der string hin (hinter libnode) */
 (*dest)->how_often_occurred = occurrences_so_far;
 strcpy((*dest)->string, string );
 lib->number_of_entries++;
 return( 1 );
}                                                               /* library_enter_entry */

int library_find_entry( library *lib, const unsigned char *string )
{
 struct libnode *node;
 int comp;

 if ( lib->root == NULL ) return( 0 );
 node = lib->root;
 while( 0 != ( comp = strcmp(node->string,string)))
   {
     if (( comp > 0 )&&(node->left))
       {
         node = node->left;
         continue;
       }
     else if(( comp < 0 )&&( node->right ))
       {
         node = node->right;
         continue;
       }
     return( 0 );
   }
 return( 1 );
}                       /* find_entry liefert pointer auf libnode */


void library_fill_hist(library *lib,long tree_hist[],long weight_hist[],long histlenght,long *deepest_branch)
{

 fill_tree_hist( lib->root,tree_hist,weight_hist,histlenght,deepest_branch,0);
}

static void fill_tree_hist(struct libnode *node,long tree_hist[],long weight_hist[],long histlenght,long *deepest_branch,int depth)

{
 if (node)
   {
     fill_tree_hist(node->left,tree_hist,weight_hist,histlenght,deepest_branch,depth+1);
     if (depth < histlenght)
       {
         tree_hist[depth]++;
         weight_hist[depth] += node->how_often_occurred;
       }
     else
       tree_hist[histlenght]++;
     if (depth > *deepest_branch) *deepest_branch = depth;
     fill_tree_hist(node->right,tree_hist,weight_hist,histlenght,deepest_branch,depth+1);
   }
}

int library_reorganize(library *lib)
{
 long depth = 0;

 lib->root = reorder(lib->root,&depth,0);
return((int)lib->root);
}

static struct libnode *reorder(struct libnode *node, long *depth, long level)
{
 if (node)
   {
     long left_depth;
     long right_depth;
     long newdepth;
     struct libnode *help;

     help = node;
     newdepth = *depth;
     node->left = reorder(node->left, depth, level + 1);
     left_depth = *depth;
     *depth = newdepth;
     node->right = reorder(node->right, depth, level + 1);
     right_depth = *depth;
     *depth = right_depth > left_depth ? right_depth : left_depth;

     if (right_depth > left_depth)
       {   /* rechts rotieren */
         if (node->right)
           {
             if (node->right->how_often_occurred == node->how_often_occurred)
               {
                 help = node->right;
                 node->right = help->left;
                 help->left = node;
               };
           };
       }   /* links rotieren */
     else if (left_depth > right_depth)
       {
         if (node->left)
           {
             if (node->left->how_often_occurred == node->how_often_occurred)
               {
                 help = node->left;
                 node->left = help->right;
                 help->right = node;
               };
           };
       };
     return(help);
   };
 if (level > *depth) *depth = level;
 return(node);
}

You are viewing proxied material from ftp.icm.edu.pl. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.