dict/trie.h

Go to the documentation of this file.
00001 
00020 #ifndef TRIE_H
00021 #define TRIE_H
00022 
00023 /*----------------------------------------------------------------------
00024               I n c l u d e s
00025 ----------------------------------------------------------------------*/
00026 #include "dawg.h"
00027 #include "cutil.h"
00028 
00029 /*----------------------------------------------------------------------
00030               T y p e s
00031 ----------------------------------------------------------------------*/
00033 #define NUM_PLACEMENT_ATTEMPTS (INT32) 100
00034 #define EDGE_NUM_MARGIN        (INT32) 2
00035 #define DEFAULT_NODE_SIZE      (INT32) 2
00036 #define FORWARD_EDGE           (INT32) 0
00037 #define BACKWARD_EDGE          (INT32) 1
00038 
00039 /*----------------------------------------------------------------------
00040               V a r i a b l e s
00041 ----------------------------------------------------------------------*/
00042 //?extern INT32 max_new_attempts;
00043 
00044 /*----------------------------------------------------------------------
00045               M a c r o s
00046 ----------------------------------------------------------------------*/
00050 #define link_edge(edges,e,nxt,ch,flgs)                \
00051 (edges[e] = ((INT32) (nxt)                        | \
00052                ((INT32) (ch)   << LETTER_START_BIT) | \
00053                ((INT32) (flgs) << FLAG_START_BIT)))
00054 
00058 #define set_last_flag(edges,e)   \
00059 (edges[e] |= (LAST_FLAG << FLAG_START_BIT))
00060 
00065 #define copy_edge(dawg,from,to)              \
00066    dawg[to] = dawg[from]
00067 
00074 #define move_edges(dawg,from,to,num)              \
00075 {                                               \
00076    INT32 i;                                     \
00077    for (i=0; i<num; i++) {                      \
00078       copy_edge(dawg,from+i,to+i);              \
00079       dawg[from+i] = NO_EDGE;                   \
00080    }                                            \
00081 }                                               \
00082 
00083 
00091 #define copy_edges(dawg,from,to,num)            \
00092 {                                             \
00093    INT32 i;                                   \
00094    for (i=num-1; i>=0; i--) {                 \
00095       copy_edge(dawg,from+i,to+i);            \
00096    }                                          \
00097 }                                             \
00098 
00099 
00104 #define move_node_if_needed(dawg,node,max_num_edges,reserved_edges)     \
00105 if (! room_in_node (dawg, node)) {                                    \
00106    node = move_node (dawg, node, max_num_edges, reserved_edges);      \
00107 }                                                                     \
00108 
00109 
00110 /*----------------------------------------------------------------------
00111               F u n c t i o n s
00112 ----------------------------------------------------------------------*/
00113 void add_edge_linkage(EDGE_ARRAY dawg,
00114                       NODE_REF node1,
00115                       NODE_REF node2,
00116                       INT32 direction,
00117                       char character,
00118                       INT32 word_end);
00119 
00120 void add_new_edge(EDGE_ARRAY dawg,
00121                   NODE_REF *node1,
00122                   NODE_REF *node2,
00123                   char character,
00124                   INT32 word_end,
00125                   INT32 max_num_edges,
00126                   INT32 reserved_edges);
00127 
00128 void add_word_to_dawg(EDGE_ARRAY dawg,
00129                       char *string,
00130                       INT32 max_num_edges,
00131                       INT32 reserved_edges);
00132 
00133 void initialize_dawg(EDGE_ARRAY dawg, INT32 max_num_edges); 
00134 
00135 NODE_REF move_node(EDGE_ARRAY dawg,
00136                    NODE_REF node,
00137                    INT32 max_num_edges,
00138                    INT32 reserved_edges);
00139 
00140 NODE_REF new_dawg_node(EDGE_ARRAY dawg,
00141                        INT32 num_edges,
00142                        INT32 max_num_edges,
00143                        INT32 reserved_edges);
00144 
00145 void read_word_list(char *filename,
00146                     EDGE_ARRAY dawg,
00147                     INT32 max_num_edges,
00148                     INT32 reserved_edges);
00149 
00150 void relocate_edge(EDGE_ARRAY dawg,
00151                    NODE_REF node,
00152                    NODE_REF old_node,
00153                    NODE_REF new_node);
00154 
00155 void remove_edge(EDGE_ARRAY dawg,
00156                  NODE_REF node1,
00157                  NODE_REF node2,
00158                  char character,
00159                  INT32 word_end);
00160 
00161 void remove_edge_linkage(EDGE_ARRAY dawg,
00162                          NODE_REF node,
00163                          NODE_REF next,
00164                          INT32 direction,
00165                          char character,
00166                          INT32 word_end);
00167 
00168 INT32 room_in_node(EDGE_ARRAY dawg, NODE_REF node); 
00169 
00170 /*
00171 #if defined(__STDC__) || defined(__cplusplus)
00172 # define _ARGS(s) s
00173 #else
00174 # define _ARGS(s) ()
00175 #endif*/
00176 
00177 /* trie.c *
00178 void add_edge_linkage
00179   _ARGS((EDGE_ARRAY dawg,
00180   NODE_REF node1,
00181   NODE_REF node2,
00182   INT32 direction,
00183   int character,
00184   INT32 word_end));
00185 
00186 void add_new_edge
00187   _ARGS((EDGE_ARRAY dawg,
00188   NODE_REF *node1,
00189   NODE_REF *node2,
00190   int character,
00191   INT32 word_end,
00192   INT32 max_num_edges,
00193   INT32 reserved_edges));
00194 
00195 void add_word_to_dawg
00196   _ARGS((EDGE_ARRAY dawg,
00197   char *string,
00198   INT32 max_num_edges,
00199   INT32 reserved_edges));
00200 
00201 void initialize_dawg
00202   _ARGS((EDGE_ARRAY dawg,
00203   INT32 max_num_edges));
00204 
00205 NODE_REF move_node
00206   _ARGS((EDGE_ARRAY dawg,
00207   NODE_REF node,
00208   INT32 max_num_edges,
00209   INT32 reserved_edges));
00210 
00211 NODE_REF new_dawg_node
00212   _ARGS((EDGE_ARRAY dawg,
00213   INT32 num_edges,
00214   INT32 max_num_edges,
00215   INT32 reserved_edges));
00216 
00217 void read_word_list
00218   _ARGS((char *filename,
00219   EDGE_ARRAY dawg,
00220   INT32 max_num_edges,
00221   INT32 reserved_edges));
00222 
00223 void relocate_edge
00224   _ARGS((EDGE_ARRAY dawg,
00225   NODE_REF node,
00226   NODE_REF old_node,
00227   NODE_REF new_node));
00228 
00229 void remove_edge
00230   _ARGS((EDGE_ARRAY dawg,
00231   NODE_REF node1,
00232   NODE_REF node2,
00233   int character,
00234   INT32 word_end));
00235 
00236 void remove_edge_linkage
00237   _ARGS((EDGE_ARRAY dawg,
00238   NODE_REF node,
00239   NODE_REF next,
00240   INT32 direction,
00241   int character,
00242   INT32 word_end));
00243 
00244 INT32 room_in_node
00245   _ARGS((EDGE_ARRAY dawg,
00246   NODE_REF node));
00247 
00248 #undef _ARGS
00249 */
00250 #endif

Generated on Wed Feb 28 19:49:10 2007 for Tesseract by  doxygen 1.5.1