summaryrefslogtreecommitdiff
path: root/support/spelchek/library.c
diff options
context:
space:
mode:
authorNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
committerNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
commite0c6872cf40896c7be36b11dcc744620f10adf1d (patch)
tree60335e10d2f4354b0674ec22d7b53f0f8abee672 /support/spelchek/library.c
Initial commit
Diffstat (limited to 'support/spelchek/library.c')
-rw-r--r--support/spelchek/library.c262
1 files changed, 262 insertions, 0 deletions
diff --git a/support/spelchek/library.c b/support/spelchek/library.c
new file mode 100644
index 0000000000..45b7673403
--- /dev/null
+++ b/support/spelchek/library.c
@@ -0,0 +1,262 @@
+#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);
+}