Back to index

im-sdk  12.3.91
tree.c
Go to the documentation of this file.
00001 #include <stdio.h>
00002 #include <stdlib.h>
00003 #include <string.h>
00004 #include <assert.h>
00005 #include "hhentry.h"
00006 #include "tree.h"
00007 
00008 static TreeNode *
00009 _tree_search_hangul (TreeNode *node, unsigned char *hangul);
00010 
00011 static void tree_init (Tree *tree);
00012 
00013 Tree *
00014 tree_new ()
00015 {
00016   Tree *new_tree;
00017   new_tree = (Tree *) calloc (1, sizeof (Tree));
00018   new_tree->root = NULL;
00019   return new_tree;
00020 }
00021 
00022 Tree *
00023 tree_n_new (int n)
00024 {
00025   Tree *trees;
00026   int i;
00027 
00028   if (!n)
00029     return NULL;
00030   
00031   trees = (Tree *) calloc (n, sizeof (Tree));
00032   if (!trees){
00033     fprintf (stderr, "tree_n_new error: memory allocation error\n");
00034     return NULL;
00035   }
00036 
00037   for (i = 0 ; i < n; i++){
00038     trees[i].root = NULL;
00039   }
00040 
00041   return trees;
00042 }
00043 
00044 static void
00045 tree_init (Tree *tree)
00046 {
00047   assert (tree != NULL);
00048   if (tree->root != NULL){
00049     /* This function is meant to be called at the very begining.
00050        I'll not take care of this case for now...no time.. */
00051     fprintf (stderr, "I can't initialize non-empty tree");
00052     exit (-1);
00053   }
00054 
00055   tree->root = NULL;
00056 }
00057 
00058 
00059 void
00060 tree_inorder_traverse (TreeNode *node, void *( *func)(void *))
00061 {
00062   if (node != NULL){
00063     tree_inorder_traverse (node->left, func);
00064     func ((void *)node->data);
00065     tree_inorder_traverse (node->right, func);
00066   }
00067 }
00068 
00069 int
00070 tree_compare_hangul (TreeNode *a, unsigned char *b)
00071 {
00072   return  strcmp (a->data->hangul, b);
00073 }
00074 
00075 TreeNode *
00076 tree_search_hangul (Tree *tree, unsigned char *hangul)
00077 {
00078   TreeNode *ret_node = NULL;
00079   ret_node = _tree_search_hangul (tree->root, hangul);
00080   return ret_node;
00081 }
00082 
00083 static TreeNode *
00084 _tree_search_hangul (TreeNode *node, unsigned char *hangul)
00085 {
00086   assert (hangul != NULL);
00087   if (hangul == NULL)
00088     return NULL;
00089 
00090   while (node){
00091     if (!strcmp (node->data->hangul, hangul))
00092       return node;
00093     else if (strcmp (node->data->hangul, hangul) > 0)
00094       node = node->right;
00095     else
00096       node = node->left;
00097   }
00098   return NULL;
00099 }
00100 
00101 static void
00102 _tree_clear (TreeNode *node)
00103 {
00104   if (node){
00105     _tree_clear (node->right);
00106     _tree_clear (node->left);
00107     node->right = NULL;
00108     node->left = NULL; 
00109     hhitem_free (node->data);
00110     node->data = NULL;
00111     free (node);
00112   }
00113 }
00114 
00115 void
00116 tree_clear (Tree *tree)
00117 {
00118   _tree_clear (tree->root);
00119 }
00120 
00121 void
00122 tree_print (Tree *tree, void * (*print_function) (void *))
00123 {
00124   TreeNode *root = tree->root;
00125   tree_inorder_traverse (root, print_function);
00126 }
00127 
00128 
00129 
00130 /* I'll do only shallow copy here, under the assumption that
00131    the tnode passed as an argument is being held by the caller.
00132    I do this, because this function will be used only create
00133    dictionary structure, not for general use.
00134 */
00135 void
00136 tree_shallow_insert (Tree *tree, TreeNode *tnode)
00137 {
00138   TreeNode *ptr = tree->root ;
00139   TreeNode *prev;
00140   
00141   int comp_return;
00142 
00143   assert (tree != NULL);
00144   assert (tnode != NULL);
00145 
00146   if (tree == NULL || tnode == NULL){
00147     fprintf (stderr, "wrong parameter passed\n");
00148     exit (-1);
00149   }
00150   if (!ptr){
00151     tree->root = tnode;
00152     return;
00153   }
00154 
00155   while (ptr){
00156     prev = ptr;
00157     comp_return = hhitem_comp (ptr->data, tnode->data);
00158     if (comp_return < 0)
00159       ptr = ptr->left;
00160     else if (comp_return >0)
00161       ptr = ptr->right;
00162     else {
00163       /* no duplication expected, just return */
00164       return;
00165     }
00166   }
00167   if (hhitem_comp (prev->data, tnode->data) < 0)
00168     prev->left = tnode;
00169   else
00170     prev->right = tnode;
00171   
00172 }
00173 
00174 
00175 void
00176 tree_node_copy (TreeNode *dst, TreeNode *src)
00177 {
00178   assert (dst != NULL);
00179   assert (src != NULL);
00180 
00181   if (dst == NULL || src == NULL){
00182     fprintf (stderr, "tree_node_copy error: dst or src is NULL\n");
00183     return;
00184   }
00185 
00186   dst->left = src->left;
00187   dst->right = src->right;
00188   if (dst->data && src->data)
00189     hhitem_copy (dst->data, src->data);
00190 }
00191 
00192 void
00193 tree_insert (Tree *tree, TreeNode *tnode)
00194 {
00195   TreeNode *ptr = tree->root ;
00196   TreeNode *prev;
00197   int comp_return;
00198 
00199   assert (tree != NULL);
00200   assert (tnode != NULL);
00201 
00202   if (tree == NULL || tnode == NULL){
00203     fprintf (stderr, "wrong parameter passed\n");
00204     exit (-1);
00205   }
00206   if (!ptr){
00207     tree->root = tnode;
00208     return;
00209   }
00210 
00211   while (ptr){
00212     prev = ptr;
00213     comp_return = hhitem_comp (ptr->data, tnode->data);
00214     if (comp_return < 0)
00215       ptr = ptr->left;
00216     else if (comp_return >0)
00217       ptr = ptr->right;
00218     else {
00219       /* no duplication expected, just return */
00220       return;
00221     }
00222   }
00223   if (hhitem_comp (prev->data, tnode->data) < 0)
00224     prev->left = tnode;
00225   else
00226     prev->right = tnode;
00227   
00228 }
00229 
00230 
00231 /* this function assumes data are sorted already */
00232 void
00233 tree_build_from_array (Tree *tree, TreeNode *data, int first, int last)
00234 {
00235   int middle;
00236   if (first <= last){
00237     middle = (first + last) / 2;
00238     tree_shallow_insert (tree, data + middle);
00239     tree_build_from_array (tree, data, first, middle - 1);
00240     tree_build_from_array (tree, data, middle + 1, last);
00241   }
00242     
00243 }
00244 
00245 
00246 TreeNode *
00247 tree_node_new_skeleton ()
00248 {
00249   TreeNode *new_node;
00250   new_node = (TreeNode *)calloc (1, sizeof (TreeNode));
00251   if (!new_node){
00252     fprintf (stderr, "tree_node_new_skeleton error: "
00253             "memory allocation failure\n");
00254     return NULL;
00255   }
00256   new_node->left = new_node->right = NULL;
00257   new_node->data = NULL;
00258   return new_node;
00259 }
00260 
00261 TreeNode *
00262 tree_node_new_with_hhitem (HHItem *data)
00263 {
00264   TreeNode *p_newnode =
00265     (TreeNode *) calloc (1, sizeof (TreeNode));
00266   
00267   p_newnode->left = NULL;
00268   p_newnode->right = NULL;
00269   
00270   p_newnode->data = hhitem_new ();
00271   hhitem_copy (p_newnode->data, data);
00272 
00273   return p_newnode;
00274 }
00275 
00276 void
00277 tree_node_free (TreeNode *tnode)
00278 {
00279   assert (tnode != NULL);
00280   if (!tnode)
00281     return;
00282   if (tnode->data){
00283     tnode->left = NULL;
00284     tnode->right = NULL;
00285     hhitem_free (tnode->data);
00286     tnode->data = NULL;
00287     free (tnode);
00288   }
00289 }