1 | /**************************************************************************
|
---|
2 | *
|
---|
3 | * bool_tree.c -- Boolean parse tree ADT
|
---|
4 | * Copyright (C) 1994 Tim Shimmin
|
---|
5 | *
|
---|
6 | * This program is free software; you can redistribute it and/or modify
|
---|
7 | * it under the terms of the GNU General Public License as published by
|
---|
8 | * the Free Software Foundation; either version 2 of the License, or
|
---|
9 | * (at your option) any later version.
|
---|
10 | *
|
---|
11 | * This program is distributed in the hope that it will be useful,
|
---|
12 | * but WITHOUT ANY WARRANTY; without even the implied warranty of
|
---|
13 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
---|
14 | * GNU General Public License for more details.
|
---|
15 | *
|
---|
16 | * You should have received a copy of the GNU General Public License
|
---|
17 | * along with this program; if not, write to the Free Software
|
---|
18 | * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
|
---|
19 | *
|
---|
20 | * @(#)query.bool.y 1.9 16 Mar 1994
|
---|
21 | *
|
---|
22 | **************************************************************************/
|
---|
23 |
|
---|
24 | #include "sysfuncs.h"
|
---|
25 |
|
---|
26 | #include "memlib.h"
|
---|
27 | #include "messages.h"
|
---|
28 | #include "bool_tree.h"
|
---|
29 |
|
---|
30 | static char *RCSID = "$Id: bool_tree.c 16583 2008-07-29 10:20:36Z davidb $";
|
---|
31 |
|
---|
32 |
|
---|
33 | /* =========================================================================
|
---|
34 | * Function: CreateBoolNode
|
---|
35 | * Description:
|
---|
36 | * Input:
|
---|
37 | * Output:
|
---|
38 | * ========================================================================= */
|
---|
39 | bool_tree_node *
|
---|
40 | CreateBoolNode (N_Tag tag)
|
---|
41 | {
|
---|
42 | bool_tree_node *n;
|
---|
43 | if (!(n = Xmalloc (sizeof (bool_tree_node))))
|
---|
44 | FatalError (1, "Can not create bool_tree_node for boolean query");
|
---|
45 | n->tag = tag;
|
---|
46 | BOOL_SIBLING (n) = NULL;
|
---|
47 | return n;
|
---|
48 | }
|
---|
49 |
|
---|
50 | /* =========================================================================
|
---|
51 | * Function:
|
---|
52 | * Description:
|
---|
53 | * Input:
|
---|
54 | * Output:
|
---|
55 | * ========================================================================= */
|
---|
56 | bool_tree_node *
|
---|
57 | CreateBoolTermNode (TermList ** tl, char *text, int Count, int word_num,
|
---|
58 | u_long count, u_long doc_count, u_long invf_ptr, u_long invf_len, /* [RPAP - Feb 97: Term Frequency] */
|
---|
59 | int stemmer_num)
|
---|
60 | {
|
---|
61 | bool_tree_node *n = NULL;
|
---|
62 |
|
---|
63 | /* allocate bool_tree_node */
|
---|
64 | n = CreateBoolNode (N_term);
|
---|
65 |
|
---|
66 | BOOL_TERM (n) = AddTerm (tl, (u_char *) text, Count, word_num, count, doc_count,
|
---|
67 | invf_ptr, invf_len, stemmer_num); /* [RPAP - Feb 97: Term Frequency] */
|
---|
68 |
|
---|
69 | return n;
|
---|
70 | }
|
---|
71 |
|
---|
72 |
|
---|
73 | /* =========================================================================
|
---|
74 | * Function: CreateTreeNode
|
---|
75 | * Description:
|
---|
76 | * Input:
|
---|
77 | * Output:
|
---|
78 | * ========================================================================= */
|
---|
79 |
|
---|
80 | bool_tree_node *
|
---|
81 | CreateBoolTreeNode (N_Tag tag, bool_tree_node * left, bool_tree_node * right)
|
---|
82 | {
|
---|
83 | bool_tree_node *n = CreateBoolNode (tag);
|
---|
84 |
|
---|
85 | BOOL_CHILD (n) = left;
|
---|
86 | if (left)
|
---|
87 | BOOL_SIBLING (left) = right;
|
---|
88 | if (right)
|
---|
89 | BOOL_SIBLING (right) = NULL;
|
---|
90 |
|
---|
91 | return (n);
|
---|
92 | }
|
---|
93 |
|
---|
94 | /* =========================================================================
|
---|
95 | * Function:
|
---|
96 | * Description:
|
---|
97 | * Input:
|
---|
98 | * Output:
|
---|
99 | * ========================================================================= */
|
---|
100 |
|
---|
101 | int
|
---|
102 | EqualBoolNodes (bool_tree_node * a, bool_tree_node * b)
|
---|
103 | {
|
---|
104 | if (BOOL_TAG (a) == N_term && BOOL_TAG (a) == N_term)
|
---|
105 | return BOOL_TERM (a) == BOOL_TERM (b);
|
---|
106 | return 0;
|
---|
107 | }
|
---|
108 |
|
---|
109 | /* =========================================================================
|
---|
110 | * Function: FreeBoolTree
|
---|
111 | * Description:
|
---|
112 | * Notes: does not fix up any parent or sibling links around given tree
|
---|
113 | * Input:
|
---|
114 | * Output:
|
---|
115 | * ========================================================================= */
|
---|
116 |
|
---|
117 | static void
|
---|
118 | FreeTree (bool_tree_node * tree)
|
---|
119 | {
|
---|
120 | bool_tree_node *sibling;
|
---|
121 |
|
---|
122 | while (tree)
|
---|
123 | {
|
---|
124 | if (BOOL_HAS_CHILD (tree))
|
---|
125 | FreeTree (BOOL_CHILD (tree));
|
---|
126 | sibling = BOOL_SIBLING (tree);
|
---|
127 | Xfree (tree);
|
---|
128 | tree = sibling;
|
---|
129 | }
|
---|
130 | }
|
---|
131 |
|
---|
132 | void
|
---|
133 | FreeBoolTree (bool_tree_node ** the_tree)
|
---|
134 | {
|
---|
135 | bool_tree_node *tree = *the_tree;
|
---|
136 |
|
---|
137 | if (!tree)
|
---|
138 | return;
|
---|
139 |
|
---|
140 | FreeTree (tree);
|
---|
141 | *the_tree = NULL;
|
---|
142 | /*********************************/
|
---|
143 | /* THIS IS POTENTIALLY DANGEROUS */
|
---|
144 | /* FIX UP LATER */
|
---|
145 | /* Need to correct the links for parent/siblings */
|
---|
146 | /*********************************/
|
---|
147 |
|
---|
148 | }
|
---|
149 |
|
---|
150 | /* =========================================================================
|
---|
151 | * Function: PrintBoolTree
|
---|
152 | * Description:
|
---|
153 | * Print out a text version of the tree to the file
|
---|
154 | * Input:
|
---|
155 | * Output:
|
---|
156 | * ========================================================================= */
|
---|
157 |
|
---|
158 | static void
|
---|
159 | PrintBinaryOp (bool_tree_node * tree, FILE * file, char op)
|
---|
160 | {
|
---|
161 | bool_tree_node *child = NULL;
|
---|
162 | assert (BOOL_HAS_CHILD (tree));
|
---|
163 |
|
---|
164 | child = BOOL_CHILD (tree);
|
---|
165 | while (child)
|
---|
166 | {
|
---|
167 | PrintBoolTree (child, file);
|
---|
168 | child = BOOL_SIBLING (child);
|
---|
169 | if (child)
|
---|
170 | fprintf (file, " %c ", op);
|
---|
171 | }
|
---|
172 | }
|
---|
173 |
|
---|
174 | static void
|
---|
175 | PrintUnaryOp (bool_tree_node * tree, FILE * file, char op)
|
---|
176 | {
|
---|
177 | bool_tree_node *child = NULL;
|
---|
178 |
|
---|
179 | fprintf (file, " %c ", op);
|
---|
180 | assert (BOOL_HAS_CHILD (tree));
|
---|
181 | child = BOOL_CHILD (tree);
|
---|
182 | PrintBoolTree (child, file);
|
---|
183 | }
|
---|
184 |
|
---|
185 | void
|
---|
186 | PrintBoolTree (bool_tree_node * tree, FILE * file)
|
---|
187 | {
|
---|
188 | if (!tree)
|
---|
189 | return;
|
---|
190 |
|
---|
191 | fprintf (file, "(");
|
---|
192 | switch (BOOL_TAG (tree))
|
---|
193 | {
|
---|
194 | case N_term:
|
---|
195 | fprintf (file, "term %d", BOOL_TERM (tree));
|
---|
196 | break;
|
---|
197 | case N_and:
|
---|
198 | PrintBinaryOp (tree, file, '&');
|
---|
199 | break;
|
---|
200 | case N_or:
|
---|
201 | PrintBinaryOp (tree, file, '|');
|
---|
202 | break;
|
---|
203 | case N_or_terms:
|
---|
204 | PrintBinaryOp (tree, file, '+');
|
---|
205 | break;
|
---|
206 | case N_diff:
|
---|
207 | PrintBinaryOp (tree, file, '-');
|
---|
208 | break;
|
---|
209 | case N_not:
|
---|
210 | PrintUnaryOp (tree, file, '!');
|
---|
211 | break;
|
---|
212 | case N_all:
|
---|
213 | fprintf (file, " TRUE ");
|
---|
214 | break;
|
---|
215 | case N_none:
|
---|
216 | fprintf (file, " FALSE ");
|
---|
217 | break;
|
---|
218 | default:
|
---|
219 | break;
|
---|
220 | }
|
---|
221 |
|
---|
222 | fprintf (file, ")");
|
---|
223 | }
|
---|
224 |
|
---|
225 |
|
---|
226 | /* =========================================================================
|
---|
227 | * Function: CopyBoolTree
|
---|
228 | * Description:
|
---|
229 | * Input:
|
---|
230 | * Output:
|
---|
231 | * ========================================================================= */
|
---|
232 |
|
---|
233 | bool_tree_node *
|
---|
234 | CopyBoolTree (bool_tree_node * tree)
|
---|
235 | {
|
---|
236 | bool_tree_node *sibling = NULL;
|
---|
237 | bool_tree_node *tree_copy = NULL;
|
---|
238 | bool_tree_node *prev = NULL;
|
---|
239 |
|
---|
240 | if (!tree)
|
---|
241 | return NULL;
|
---|
242 |
|
---|
243 | sibling = tree;
|
---|
244 | prev = NULL;
|
---|
245 | while (sibling)
|
---|
246 | {
|
---|
247 | /* copy sibling */
|
---|
248 | bool_tree_node *sibling_copy = (bool_tree_node *) malloc (sizeof (bool_tree_node));
|
---|
249 | if (!sibling_copy)
|
---|
250 | FatalError (1, "No memory for bool tree copy");
|
---|
251 | bcopy ((char *) sibling, (char *) sibling_copy, sizeof (bool_tree_node));
|
---|
252 |
|
---|
253 | if (BOOL_HAS_CHILD (sibling))
|
---|
254 | {
|
---|
255 | BOOL_CHILD (sibling_copy) = CopyBoolTree (BOOL_CHILD (sibling));
|
---|
256 | }
|
---|
257 |
|
---|
258 | /* do the link up of copies */
|
---|
259 | if (prev)
|
---|
260 | BOOL_SIBLING (prev) = sibling_copy;
|
---|
261 | else
|
---|
262 | tree_copy = sibling_copy;
|
---|
263 | prev = sibling_copy;
|
---|
264 |
|
---|
265 | sibling = BOOL_SIBLING (sibling);
|
---|
266 | }
|
---|
267 | return tree_copy;
|
---|
268 | }
|
---|
269 |
|
---|
270 |
|
---|
271 | /* =========================================================================
|
---|
272 | * Function: LastBoolSibling
|
---|
273 | * Description:
|
---|
274 | * Input:
|
---|
275 | * Output:
|
---|
276 | * ========================================================================= */
|
---|
277 |
|
---|
278 | bool_tree_node *
|
---|
279 | LastBoolSibling (bool_tree_node * tree)
|
---|
280 | {
|
---|
281 |
|
---|
282 | if (!tree)
|
---|
283 | return NULL;
|
---|
284 |
|
---|
285 | do
|
---|
286 | {
|
---|
287 | tree = BOOL_SIBLING (tree);
|
---|
288 | }
|
---|
289 | while (BOOL_SIBLING (tree));
|
---|
290 |
|
---|
291 | return tree;
|
---|
292 | }
|
---|