1 /*
2 * tree.c -- a general tree structure for use with hnb
3 *
4 * Copyright (C) 2001,2002 �yvind Kol�s <pippin@users.sourceforge.net>
5 *
6 * This program is free software; you can redistribute it and/or modify it under
7 * the terms of the GNU General Public License as published by the Free
8 * Software Foundation; either version 2, or (at your option) any later
9 * version.
10 *
11 * This program is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
14 * more details.
15 *
16 * You should have received a copy of the GNU General Public License along with
17 * this program; if not, write to the Free Software Foundation, Inc., 59
18 * Temple Place - Suite 330, Boston, MA 02111-1307, USA.
19 */
20
21
22 /* there is one a little bit strange thing about
23 this tree, it have the root at the top but
24 at the left.. (like the model presented to the
25 user) */
26
27 #include <stdio.h>
28 #include <ctype.h>
29 #include <string.h>
30 #include <stdlib.h>
31 #include "tree.h"
32
33 char TEXT[5] = "text";
34
node_recurse(Node * node)35 Node *node_recurse (Node *node)
36 {
37 if (node_right (node))
38 return node_right (node);
39 if (node_down (node))
40 return node_down (node);
41
42 while (node_left (node)) {
43 if (node_down (node_left (node)))
44 return node_down (node_left (node));
45 node = node_left (node);
46 }
47 return 0;
48 }
49
node_backrecurse(Node * node)50 Node *node_backrecurse (Node *node)
51 {
52 if (node_up (node)) {
53 node = node_up (node);
54 while (node_right (node)) {
55 node = node_right (node);
56 node = node_bottom (node);
57 }
58 return (node);
59 }
60 return (node_left (node));
61 }
62
node_no(Node * node)63 int node_no (Node *node)
64 {
65 int no = 0;
66
67 while (node) {
68 node = node_backrecurse (node);
69 no++;
70 }
71 return no;
72 }
73
node_top(Node * node)74 Node *node_top (Node *node)
75 {
76 if (node == 0)
77 return 0;
78
79 while (node_up (node))
80 node = node_up (node);
81 return (node);
82 }
83
node_bottom(Node * node)84 Node *node_bottom (Node *node)
85 {
86 if (node == 0)
87 return 0;
88 while (node_down (node))
89 node = node_down (node);
90 return node;
91 }
92
node_insert_up(Node * node)93 Node *node_insert_up (Node *node)
94 {
95 Node *temp, *new = node_new ();
96
97 temp = node->up;
98 new->up = temp;
99 new->down = node;
100
101 node->up = new;
102 if (temp)
103 temp->down = new;
104
105 new->left = node->left;
106
107 if (node_left (new)) { /* make tree consistent */
108 if (node_right (node_left (node)) == node) {
109 temp = node_left (new);
110 temp->right = new;
111 }
112 }
113
114 return new;
115 }
116
node_insert_down(Node * node)117 Node *node_insert_down (Node *node)
118 {
119 Node *temp, *new = node_new ();
120
121 temp = node->down;
122 new->down = temp;
123 new->up = node;
124
125 node->down = new;
126 if (temp)
127 temp->up = new;
128
129 new->left = node->left;
130
131 return new;
132 }
133
node_insert_right(Node * node)134 Node *node_insert_right (Node *node)
135 {
136 Node *new = node_new ();
137
138 if ((!node) || (node->right)) {
139 free (new);
140 return 0;
141 }
142
143 new->left = node;
144 node->right = new;
145
146 return new;
147 }
148
nodes_left(Node * node)149 unsigned int nodes_left (Node *node)
150 {
151 unsigned int level = 0;
152
153 while ((node = node_left (node)))
154 level++;
155 return level;
156 }
157
nodes_up(Node * node)158 unsigned int nodes_up (Node *node)
159 {
160 unsigned int level = 0;
161
162 while ((node = node_up (node)))
163 level++;
164 return level;
165 }
166
nodes_down(Node * node)167 unsigned int nodes_down (Node *node)
168 {
169 unsigned int level = 0;
170
171 while ((node = node_down (node)))
172 level++;
173 return level;
174 }
175
nodes_right(Node * node)176 unsigned int nodes_right (Node *node)
177 {
178 unsigned int level = 0;
179
180 while ((node = node_right (node)))
181 level++;
182 return (level);
183 }
184
node_remove(Node * node)185 Node *node_remove (Node *node)
186 {
187 Node *tup = node->up, *tdown = node->down;
188
189 /* if we're wiping the tree, add a temp node for later reference to the empty tree */
190 if ((node_left (node) == 0) && (node_up (node) == 0)
191 && (node_down (node) == 0)) {
192 Node *tnode = node_insert_down (node);
193
194 node_setflag (tnode, F_temp, 1);
195 tdown = node_down (node);
196 }
197
198 /* remove all children */
199 while (node_right (node))
200 node_remove (node_right (node));
201
202 /* close the gap in the linked list */
203 if (tup)
204 tup->down = tdown;
205 if (tdown)
206 tdown->up = tup;
207
208 /* if we are a top-most child (parent says we are master of our siblings) */
209 if ((node_left (node)) && (node_right (node_left (node)) == node)) {
210 if (tdown) /* rearrange parents pointer */
211 node->left->right = tdown;
212 else { /* if no siblings remove ourselves, and return parent */
213 Node *tnode = node_left (node);
214
215 node->left->right = 0;
216 node_free (node);
217 return tnode;
218 }
219 }
220
221 node_free (node);
222
223 if (tup)
224 return tup;
225 if (tdown)
226 return tdown;
227 printf ("we're not where we should be\n");
228 return 0;
229 }
230
node_match(char * match,Node * where)231 Node *node_match (char *match, Node *where)
232 {
233 Node *node;
234
235 node = node_top (where); /* do I want a match from top, or from where? */
236 if (!match[0])
237 return 0;
238
239 do {
240 if (strncmp
241 (fixnullstring (node_get (node, TEXT)), match,
242 strlen (match)) == 0)
243 return node;
244 } while ((node = node_down (node)));
245
246 return 0;
247 }
248
node_exact_match(char * match,Node * where)249 Node *node_exact_match (char *match, Node *where)
250 {
251 Node *node;
252
253 node = node_top (where); /* see node_match */
254 if (!match[0])
255 return 0;
256
257 do {
258 if (strcmp (fixnullstring (node_get (node, TEXT)), match) == 0)
259 return node;
260 } while ((node = node_down (node)));
261
262 return 0;
263 }
264
265 /* this is a commodity funciton, and I didn't want to code it myself,.. I
266 searched the fine web, found, cut'd, 'n', pasted..
267 url: http://www.brokersys.com/snippets/STRISTR.C
268 */
269
270 /*
271 ** Designation: StriStr
272 **
273 ** Call syntax: char *stristr(char *String, char *Pattern)
274 **
275 ** Description: This function is an ANSI version of strstr() with
276 ** case insensitivity.
277 **
278 ** Return item: char *pointer if Pattern is found in String, else
279 ** pointer to 0
280 **
281 ** Rev History: 07/04/95 Bob Stout ANSI-fy
282 ** 02/03/94 Fred Cole Original
283 **
284 ** Hereby donated to public domain.
285 */
286
stristr(const char * String,const char * Pattern)287 static char *stristr (const char *String, const char *Pattern)
288 {
289 char *pptr, *sptr, *start;
290 int slen, plen;
291
292 for (start = (char *) String, pptr = (char *) Pattern, slen = strlen (String), plen = strlen (Pattern); /* while string length not shorter than pattern length */
293 slen >= plen; start++, slen--) {
294 /* find start of pattern in string */
295 while (toupper (*start) != toupper (*Pattern)) {
296 start++;
297 slen--; /* if pattern longer than string */
298 if (slen < plen)
299 return (NULL);
300 }
301 sptr = start;
302 pptr = (char *) Pattern;
303 while (toupper (*sptr) == toupper (*pptr)) {
304 sptr++;
305 pptr++; /* if end of pattern then pattern was found */
306 if ('\0' == *pptr)
307 return (start);
308 }
309 }
310 return (NULL);
311 }
312
313 /*returns the next recursive node having match as a substring, or NULL if not found
314 starting from where.
315 */
316
node_recursive_match(char * match,Node * where)317 Node *node_recursive_match (char *match, Node *where)
318 {
319 if (!match[0])
320 return NULL;
321
322 where = node_recurse (where); /* skip forward */
323 while (where) {
324 if (stristr (fixnullstring (node_get (where, TEXT)), match) != NULL) /* case insensitive */
325 return where;
326 where = node_recurse (where);
327 }
328
329 return NULL;
330 }
331
node_backrecursive_match(char * match,Node * where)332 Node *node_backrecursive_match (char *match, Node *where)
333 {
334 if (!match[0])
335 return NULL;
336
337 where = node_backrecurse (where); /* skip forward */
338 while (where) {
339 if (stristr (fixnullstring (node_get (where, TEXT)), match) != NULL) /* case insensitive */
340 return where;
341 where = node_backrecurse (where);
342 }
343
344 return NULL;
345 }
346
347
348
tree_new()349 Node *tree_new ()
350 {
351 Node *root;
352
353 root = node_new ();
354 node_setflags (root, F_temp);
355 return root;
356 }
357
node_root(Node * node)358 Node *node_root (Node *node)
359 {
360 while (node_left (node))
361 node = node_left (node);
362 node = node_top (node);
363 return node;
364 }
365
tree_free(Node * node)366 void tree_free (Node *node)
367 {
368 Node *root = node_root (node);
369
370 while (node_down (root))
371 node_remove (node_down (root));
372
373 root = node_remove (root);
374 node_free (root);
375
376 return;
377 }
378
379 /*
380 swaps the positions in the tree of the two specified nodes
381 */
node_swap(Node * nodeA,Node * nodeB)382 void node_swap (Node *nodeA, Node *nodeB)
383 {
384 Node *Aup, *Aleft, *Aright, *Adown;
385 Node *Bup, *Bleft, *Bright, *Bdown;
386
387 if ((!nodeB) || (!nodeA))
388 return;
389
390 if (nodeB == nodeA)
391 return;
392
393 if (nodeB->right == nodeA || nodeA->right == nodeB) {
394 return; /* can't swap parent and child,.. (nor deeper levels actually) */
395 }
396
397 if ((nodeB->down == nodeA) && (nodeA->up == nodeB)) { /* special case neighbours,.. normalize first */
398 Node *tnode = nodeA;
399
400 nodeA = nodeB;
401 nodeB = tnode;
402 }
403
404 Aup = node_up (nodeA);
405 Adown = node_down (nodeA);
406 Aleft = node_left (nodeA);
407 Aright = node_right (nodeA);
408 Bup = node_up (nodeB);
409 Bdown = node_down (nodeB);
410 Bleft = node_left (nodeB);
411 Bright = node_right (nodeB);
412
413 if ((nodeA->down == nodeB) && (nodeB->up == nodeA)) { /* special case, neighbours */
414 if (Aup)
415 Aup->down = nodeB;
416 nodeB->up = Aup;
417 if (Bdown)
418 Bdown->up = nodeA;
419 nodeA->down = Bdown;
420 nodeA->up = nodeB;
421 nodeB->down = nodeA;
422 if (Aleft)
423 if (Aleft->right == nodeA)
424 Aleft->right = nodeB;
425 return;
426 }
427
428 if (Aup)
429 Aup->down = nodeB;
430 nodeB->up = Aup;
431 if (Adown)
432 Adown->up = nodeB;
433 nodeB->down = Adown;
434 if (Aleft) {
435 if (Aleft->right == nodeA)
436 Aleft->right = nodeB;
437
438 }
439 nodeB->left = Aleft;
440
441 if (Bup)
442 Bup->down = nodeA;
443 nodeA->up = Bup;
444 if (Bdown)
445 Bdown->up = nodeA;
446 nodeA->down = Bdown;
447
448 if (Bleft) {
449 if (Bleft->right == nodeB)
450 Bleft->right = nodeA;
451 }
452 nodeA->left = Bleft;
453 }
454
455
456 #include "file.h"
457
tree_duplicate(Node * source,Node * target)458 Node *tree_duplicate (Node *source, Node *target)
459 {
460 int level, startlevel;
461 import_state_t ist;
462 Node *tnode;
463
464 tnode = node_duplicate (source);
465 tnode->up = tnode->down = tnode->left = tnode->right = NULL;
466 node_swap (tnode, target);
467 node_free (target);
468 target = tnode;
469
470 init_import (&ist, target);
471
472 if (node_right (source)) {
473 source = node_right (source);
474 startlevel = nodes_left (source);
475 while ((source) && (nodes_left (source) >= startlevel)) {
476 Node *tnode;
477
478 level = nodes_left (source) - startlevel + 1;
479 tnode = node_duplicate (source);
480
481 /* clear out all references to other nodes */
482 tnode->up = tnode->down = tnode->left = tnode->right = NULL;
483 import_node (&ist, level, tnode);
484 source = node_recurse (source);
485 }
486 }
487
488 return target;
489 }
490