#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);
}