00001
00020 #ifndef TRIE_H
00021 #define TRIE_H
00022
00023
00024
00025
00026 #include "dawg.h"
00027 #include "cutil.h"
00028
00029
00030
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
00041
00042
00043
00044
00045
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
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
00172
00173
00174
00175
00176
00177
00178
00179
00180
00181
00182
00183
00184
00185
00186
00187
00188
00189
00190
00191
00192
00193
00194
00195
00196
00197
00198
00199
00200
00201
00202
00203
00204
00205
00206
00207
00208
00209
00210
00211
00212
00213
00214
00215
00216
00217
00218
00219
00220
00221
00222
00223
00224
00225
00226
00227
00228
00229
00230
00231
00232
00233
00234
00235
00236
00237
00238
00239
00240
00241
00242
00243
00244
00245
00246
00247
00248
00249
00250 #endif