Back to index

im-sdk  12.3.91
tree.c
Go to the documentation of this file.
00001 #include <stdio.h>
00002 #include <assert.h>
00003 #include "tree.h"
00004 
00005 TreeNode *
00006 _tree_search_hangul (TreeNode *node, unsigned char *hangul);
00007 
00008 void
00009 tree_init (Tree *tree)
00010 {
00011   assert (tree != NULL);
00012   if (tree->root != NULL){
00013     /* This function is meant to be called at the very beginnin.
00014        I'll not take care of this case for now...no time.. */
00015     
00016     fprintf (stderr, "I can't initialize non-empty tree");
00017     exit (-1);
00018   }
00019 
00020   tree->root = NULL;
00021 }
00022 
00023 
00024 
00025 
00026 void
00027 tree_inorder_traverse (TreeNode *node, void *( *func)(void *))
00028 {
00029   if (node != NULL){
00030     tree_inorder_traverse (node->left, func);
00031     func ((void *)node->data);
00032     tree_inorder_traverse (node->right, func);
00033   }
00034 }
00035 
00036 int
00037 tree_compare_hangul (TreeNode *a, unsigned char *b)
00038 {
00039   return  strcmp (a->data->hangul, b);
00040 }
00041 
00042 TreeNode *
00043 tree_search_hangul (Tree *tree, unsigned char *hangul)
00044 {
00045   TreeNode *ret_node = NULL;
00046   ret_node = _tree_search_hangul (tree->root, hangul);
00047   return ret_node;
00048 }
00049 
00050 TreeNode *
00051 _tree_search_hangul (TreeNode *node, unsigned char *hangul)
00052 {
00053   assert (hangul != NULL);
00054   if (hangul == NULL)
00055     return NULL;
00056 
00057   while (node){
00058     if (!strcmp (node->data->hangul, hangul))
00059       return node;
00060     else if (strcmp (node->data->hangul, hangul) > 0)
00061       node = node->right;
00062     else
00063       node = node->left;
00064   }
00065   return NULL;
00066 }
00067 
00068 /*
00069 TreeNode *
00070 tree_inorder_search_candidates (TreeNode *node, unsigned char *hangul)
00071 {
00072   TreeNode *ret;
00073   if (node != NULL){
00074     if (
00075     if ((ret = tree_inorder_search_candidates (node->left, hangul)))
00076       return ret;
00077 
00078     else if ((ret = tree_inorder_search_candidates (node->right, hangul)))
00079       return ret;
00080     else 
00081       ret = tree_inorder_search_candidates (node->right, hangul);
00082 
00083 
00084     if (!_utfstr_comp (node->data->hangul, hangul)){
00085       return node;
00086     }
00087     
00088     
00089     
00090   }
00091 }
00092 */
00093 void
00094 tree_print (Tree *tree, void * (*print_function) (void *))
00095 {
00096   TreeNode *root = tree->root;
00097   tree_inorder_traverse (root, print_function);
00098 }
00099 
00100 /* I'll do only shallow copy here, under the assumption that
00101    the tnode passed as an argument is being held by the caller.
00102    I do this, because this function will be used only create
00103    dictionary structure, not for general use.
00104 */
00105 void
00106 tree_shallow_insert (Tree *tree, TreeNode *tnode)
00107 {
00108   TreeNode *ptr = tree->root ;
00109   TreeNode *prev;
00110   
00111   int comp_return;
00112 
00113   assert (tree != NULL);
00114   assert (tnode != NULL);
00115 
00116   if (tree == NULL || tnode == NULL){
00117     fprintf (stderr, "wrong parameter passed\n");
00118     exit (-1);
00119   }
00120   if (!ptr){
00121     tree->root = tnode;
00122     return;
00123   }
00124 
00125   while (ptr){
00126     prev = ptr;
00127     comp_return = hhitem_comp (ptr->data, tnode->data);
00128     if (comp_return < 0)
00129       ptr = ptr->left;
00130     else if (comp_return >0)
00131       ptr = ptr->right;
00132     else {
00133       /* no duplication expected, just return */
00134       return;
00135     }
00136   }
00137   if (hhitem_comp (prev->data, tnode->data) < 0)
00138     prev->left = tnode;
00139   else
00140     prev->right = tnode;
00141   
00142 }
00143 
00144 /* this function assumes data are sorted already */
00145 void
00146 tree_build_from_array (Tree *tree, TreeNode *data, int first, int last)
00147 {
00148   int middle;
00149   if (first <= last){
00150     middle = (first + last) / 2;
00151     tree_shallow_insert (tree, data + middle);
00152     tree_build_from_array (tree, data, first, middle - 1);
00153     tree_build_from_array (tree, data, middle + 1, last);
00154   }
00155     
00156 }
00157 
00158 
00159 /* this returns new TreeNode.
00160    this does only shallow copy,
00161    thus HHEntry passed as argument should always be there
00162 */
00163 TreeNode *
00164 tree_node_shallow_new (HHEntry data)
00165 {
00166   TreeNode *p_newnode =
00167     (TreeNode *) calloc (1, sizeof (TreeNode));
00168   p_newnode->data = data;
00169   return p_newnode;
00170 }
00171