Mercurial > hg > xemacs-beta

comparison pkg-src/tree-x/tree.c @ 167:85ec50267440 r20-3b10

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Import from CVS: tag r20-3b10
author cvs
date Mon, 13 Aug 2007 09:45:46 +0200
parents 0132846995bd
children 15872534500d
comparison
equal deleted inserted replaced
166:7a77eb660975 167:85ec50267440
7 #include "defs.h" 7 #include "defs.h"
8 #include "tree.h" 8 #include "tree.h"
9 #include "dbl.h" 9 #include "dbl.h"
10 #include "intf.h" 10 #include "intf.h"
11 #include <string.h> 11 #include <string.h>
12 #include <stdlib.h>
12 13
13 /* ------------------------------------------------------------------------- */ 14 /* ------------------------------------------------------------------------- */
14 /* Global Variables */ 15 /* Global Variables */
15 /* ------------------------------------------------------------------------- */ 16 /* ------------------------------------------------------------------------- */
16 17
17 int NumLines = 0; 18 static int NumLines = 0;
18 int NumNodes = 0; 19 static int NumNodes = 0;
19 20
20 21
21 /* ---------------------------------------------------------------------------- 22 /* ----------------------------------------------------------------------------
22 * 23 *
23 * MakeLine() allocates the memory required for a Polyline and 24 * MakeLine() allocates the memory required for a Polyline and
24 * initializes the fields of a Polyline to the arguments. The 25 * initializes the fields of a Polyline to the arguments. The
25 * newly-allocated Polyline is returned by the function. 26 * newly-allocated Polyline is returned by the function.
26 * 27 *
27 * ---------------------------------------------------------------------------- 28 * ----------------------------------------------------------------------------
28 */ 29 */
29 30
30 Polyline* 31 Polyline*
31 MakeLine(dx, dy, link) 32 MakeLine(short dx, short dy, Polyline *line)
32 short dx; 33 {
33 short dy; 34 Polyline *new_line = (Polyline *) malloc(sizeof(Polyline));
34 Polyline *link; 35
35 { 36 NASSERT(new_line, "could not allocate memory for polyline");
36 Polyline *new;
37
38 new = (Polyline *) malloc(sizeof(Polyline));
39 NASSERT(new, "could not allocate memory for polyline");
40 NumLines++; 37 NumLines++;
41 38
42 new->dx = dx; 39 new_line->dx = dx;
43 new->dy = dy; 40 new_line->dy = dy;
44 new->link = link; 41 new_line->link = line;
45 42
46 return (new); 43 return new_line;
47 } 44 }
48 45
49 /* ---------------------------------------------------------------------------- 46 /* ----------------------------------------------------------------------------
50 * 47 *
51 * MakeNode() allocates the memory required for a tree node, and 48 * MakeNode() allocates the memory required for a tree node, and
52 * zeros out all the fields in the Node. It returns a pointer to the 49 * zeros out all the fields in the Node. It returns a pointer to the
53 * tree node upon success, and NULL upon failure. 50 * tree node upon success, and NULL upon failure.
54 * 51 *
55 * ---------------------------------------------------------------------------- 52 * ----------------------------------------------------------------------------
56 */ 53 */
57 54
58 Tree* 55 Tree*
59 MakeNode() 56 MakeNode(void)
60 { 57 {
61 Tree *node; 58 Tree *node = (Tree *) malloc(sizeof(Tree));
62 59
63 node = (Tree *) malloc(sizeof(Tree));
64 NASSERT(node, "could not allocate memory for node"); 60 NASSERT(node, "could not allocate memory for node");
65 NumNodes++; 61 NumNodes++;
66 62
67 if (node == NULL) 63 if (node == NULL)
68 return (NULL); 64 return (NULL);
69 else { 65 else {
70 #ifdef SYSV 66 memset((char *) node, 0, sizeof(Tree));
71 memset((char *) node, 0, sizeof(Tree)); 67 return (node);
72 #else 68 }
73 bzero((char *) node, sizeof(Tree)); 69 }
74 #endif 70
75 return (node); 71 /* ----------------------------------------------------------------------------
76 } 72 *
77 }
78
79 /* ----------------------------------------------------------------------------
80 *
81 * MakeBridge() 73 * MakeBridge()
82 * 74 *
83 * ---------------------------------------------------------------------------- 75 * ----------------------------------------------------------------------------
84 */ 76 */
85 77
86 Polyline* 78 static Polyline*
87 MakeBridge(line1, x1, y1, line2, x2, y2) 79 MakeBridge(Polyline *line1, int x1, int y1, Polyline *line2, int x2, int y2)
88 Polyline *line1, *line2;
89 int x1, x2, y1, y2;
90 { 80 {
91 int dx, dy, s; 81 int dx, dy, s;
92 Polyline *r; 82 Polyline *r;
93 83
94 dx = x2 + line2->dx - x1; 84 dx = x2 + line2->dx - x1;
103 93
104 return (r); 94 return (r);
105 } 95 }
106 96
107 /* ---------------------------------------------------------------------------- 97 /* ----------------------------------------------------------------------------
108 * 98 *
109 * Offset() computes the necessary offset that prevents two line segments 99 * Offset() computes the necessary offset that prevents two line segments
110 * from intersecting each other. This is the "heart" of the merge step 100 * from intersecting each other. This is the "heart" of the merge step
111 * that computes how two subtree contours should be separated. 101 * that computes how two subtree contours should be separated.
112 * 102 *
113 * The code is taken directly from Sven Moen's paper, with changes in 103 * The code is taken directly from Sven Moen's paper, with changes in
114 * some variable names to give more meaning: 104 * some variable names to give more meaning:
115 * 105 *
116 * - px,py indicate the x- and y-coordinates of the point on the longer 106 * - px,py indicate the x- and y-coordinates of the point on the longer
117 * segment if the previous Offset() call had two unequal segments 107 * segment if the previous Offset() call had two unequal segments
118 * 108 *
119 * - lx,ly indicate the dx and dy values of the "lower" line segment 109 * - lx,ly indicate the dx and dy values of the "lower" line segment
120 * 110 *
121 * - ux,uy indicate the dx and dy values of the "upper" line segment 111 * - ux,uy indicate the dx and dy values of the "upper" line segment
122 * 112 *
123 * ---------------------------------------------------------------------------- 113 * ----------------------------------------------------------------------------
124 */ 114 */
125 115
126 int 116 static int
127 Offset(px, py, lx, ly, ux, uy) 117 Offset(int px, int py, int lx, int ly, int ux, int uy)
128 int px, py, lx, ly, ux, uy;
129 { 118 {
130 int d, s, t; 119 int d, s, t;
131 120
132 if (ux <= px || px+lx <= 0) 121 if (ux <= px || px+lx <= 0)
133 return 0; 122 return 0;
163 152
164 return MAX(0, d); 153 return MAX(0, d);
165 } 154 }
166 155
167 /* ---------------------------------------------------------------------------- 156 /* ----------------------------------------------------------------------------
168 * 157 *
169 * Merge() 158 * Merge()
170 * 159 *
171 * ---------------------------------------------------------------------------- 160 * ----------------------------------------------------------------------------
172 */ 161 */
173 162
174 int 163 static int
175 Merge(c1, c2) 164 Merge(Polygon *c1, Polygon *c2)
176 Polygon *c1, *c2;
177 { 165 {
178 int x, y, total, d; 166 int x, y, total, d;
179 Polyline *lower, *upper, *bridge; 167 Polyline *lower, *upper, *bridge;
180 168
181 x = y = total = 0; 169 x = y = total = 0;
182 170
183 /* compare lower part of upper child's contour 171 /* compare lower part of upper child's contour
184 * with upper part of lower child's contour 172 * with upper part of lower child's contour
185 */ 173 */
186 upper = c1->lower.head; 174 upper = c1->lower.head;
187 lower = c2->upper.head; 175 lower = c2->upper.head;
188 176
200 x -= upper->dx; 188 x -= upper->dx;
201 y -= upper->dy; 189 y -= upper->dy;
202 upper = upper->link; 190 upper = upper->link;
203 } 191 }
204 } 192 }
205 193
206 if (lower) { 194 if (lower) {
207 bridge = MakeBridge(c1->upper.tail, 0, 0, lower, x, y); 195 bridge = MakeBridge(c1->upper.tail, 0, 0, lower, x, y);
208 c1->upper.tail = (bridge->link) ? c2->upper.tail : bridge; 196 c1->upper.tail = (bridge->link) ? c2->upper.tail : bridge;
209 c1->lower.tail = c2->lower.tail; 197 c1->lower.tail = c2->lower.tail;
210 } 198 }
211 else { 199 else {
212 bridge = MakeBridge(c2->lower.tail, x, y, upper, 0, 0); 200 bridge = MakeBridge(c2->lower.tail, x, y, upper, 0, 0);
213 if (!bridge->link) 201 if (!bridge->link)
214 c1->lower.tail = bridge; 202 c1->lower.tail = bridge;
215 } 203 }
216 c1->lower.head = c2->lower.head; 204 c1->lower.head = c2->lower.head;
217 205
218 return (total); 206 return (total);
219 } 207 }
220 208
221 /* ---------------------------------------------------------------------------- 209 /* ----------------------------------------------------------------------------
222 * 210 *
223 * DetachParent() reverses the effects of AttachParent by removing 211 * DetachParent() reverses the effects of AttachParent by removing
224 * the four line segments that connect the subtree contour to the 212 * the four line segments that connect the subtree contour to the
225 * node specified by 'tree'. 213 * node specified by 'tree'.
226 * 214 *
227 * ---------------------------------------------------------------------------- 215 * ----------------------------------------------------------------------------
228 */ 216 */
229 217
230 void 218 static void
231 DetachParent(tree) 219 DetachParent(Tree *tree)
232 Tree *tree;
233 { 220 {
234 free(tree->contour.upper.head->link); 221 free(tree->contour.upper.head->link);
235 free(tree->contour.upper.head); 222 free(tree->contour.upper.head);
236 tree->contour.upper.head = NULL; 223 tree->contour.upper.head = NULL;
237 tree->contour.upper.tail = NULL; 224 tree->contour.upper.tail = NULL;
243 230
244 NumLines -= 4; 231 NumLines -= 4;
245 } 232 }
246 233
247 /* ---------------------------------------------------------------------------- 234 /* ----------------------------------------------------------------------------
248 * 235 *
249 * AttachParent() 236 * AttachParent()
250 * This function also establishes the position of the first child 237 * This function also establishes the position of the first child
251 * The code follows Sven Moen's version, with slight modification to 238 * The code follows Sven Moen's version, with slight modification to
252 * support varying borders at different levels. 239 * support varying borders at different levels.
253 * 240 *
254 * ---------------------------------------------------------------------------- 241 * ----------------------------------------------------------------------------
255 */ 242 */
256 243
257 void 244 static void
258 AttachParent(tree, h) 245 AttachParent(Tree *tree, int h)
259 Tree *tree;
260 int h;
261 { 246 {
262 int x, y1, y2; 247 int x, y1, y2;
263 248
264 if (TreeAlignNodes) 249 if (TreeAlignNodes)
265 x = tree->border + (TreeParentDistance * 2) + 250 x = tree->border + (TreeParentDistance * 2) +
266 (TreeParentDistance - tree->width); 251 (TreeParentDistance - tree->width);
267 else 252 else
268 x = tree->border + TreeParentDistance; 253 x = tree->border + TreeParentDistance;
269 y2 = (h - tree->height)/2 - tree->border; 254 y2 = (h - tree->height)/2 - tree->border;
270 y1 = y2 + tree->height + (2 * tree->border) - h; 255 y1 = y2 + tree->height + (2 * tree->border) - h;
271 tree->child->offset.x = x + tree->width; 256 tree->child->offset.x = x + tree->width;
272 tree->child->offset.y = y1; 257 tree->child->offset.y = y1;
273 tree->contour.upper.head = MakeLine(tree->width, 0, 258 tree->contour.upper.head = MakeLine(tree->width, 0,
274 MakeLine(x, y1, 259 MakeLine(x, y1,
275 tree->contour.upper.head)); 260 tree->contour.upper.head));
277 MakeLine(x, y2, 262 MakeLine(x, y2,
278 tree->contour.lower.head)); 263 tree->contour.lower.head));
279 } 264 }
280 265
281 /* ---------------------------------------------------------------------------- 266 /* ----------------------------------------------------------------------------
282 * 267 *
283 * Split() 268 * Split()
284 * The tree passed to Split() must have at least 1 child, because 269 * The tree passed to Split() must have at least 1 child, because
285 * it doesn't make sense to split a leaf (there are no bridges) 270 * it doesn't make sense to split a leaf (there are no bridges)
286 * 271 *
287 * ---------------------------------------------------------------------------- 272 * ----------------------------------------------------------------------------
288 */ 273 */
289 274
290 void 275 static void
291 Split(tree) 276 Split(Tree *tree)
292 Tree *tree;
293 { 277 {
294 Tree *child; 278 Tree *child;
295 Polyline *link; 279 Polyline *link;
296 280
297 FOREACH_CHILD(child, tree) { 281 FOREACH_CHILD(child, tree) {
298 if (link = child->contour.upper.tail->link) { 282 if ((link = child->contour.upper.tail->link)) {
299 free(link->link); 283 free(link->link);
300 free(link); 284 free(link);
301 child->contour.upper.tail->link = NULL; 285 child->contour.upper.tail->link = NULL;
302 NumLines -= 2; 286 NumLines -= 2;
303 } 287 }
304 if (link = child->contour.lower.tail->link) { 288 if ((link = child->contour.lower.tail->link)) {
305 free(link->link); 289 free(link->link);
306 free(link); 290 free(link);
307 NumLines -= 2; 291 NumLines -= 2;
308 child->contour.lower.tail->link = NULL; 292 child->contour.lower.tail->link = NULL;
309 } 293 }
310 } 294 }
311 } 295 }
312 296
313 /* ---------------------------------------------------------------------------- 297 /* ----------------------------------------------------------------------------
314 * 298 *
315 * Join() merges all subtree contours of the given tree and returns the 299 * Join() merges all subtree contours of the given tree and returns the
316 * height of the entire tree contour. 300 * height of the entire tree contour.
317 * 301 *
318 * ---------------------------------------------------------------------------- 302 * ----------------------------------------------------------------------------
319 */ 303 */
320 304
321 int 305 static int
322 Join(tree) 306 Join(Tree *tree)
323 Tree *tree;
324 { 307 {
325 Tree *child; 308 Tree *child;
326 int d, h, sum; 309 int d, h, sum;
327 310
328 /* to start, set the parent's contour and height 311 /* to start, set the parent's contour and height
329 * to contour and height of first child 312 * to contour and height of first child
330 */ 313 */
331 child = tree->child; 314 child = tree->child;
332 tree->contour = child->contour; 315 tree->contour = child->contour;
333 sum = h = child->height + (2 * child->border); 316 sum = h = child->height + (2 * child->border);
334 317
343 } 326 }
344 return sum; 327 return sum;
345 } 328 }
346 329
347 /* ---------------------------------------------------------------------------- 330 /* ----------------------------------------------------------------------------
348 * 331 *
349 * RuboutLeaf() accepts a single node (leaf) and removes its contour. 332 * RuboutLeaf() accepts a single node (leaf) and removes its contour.
350 * The memory associated with the contour is deallocated. 333 * The memory associated with the contour is deallocated.
351 * 334 *
352 * ---------------------------------------------------------------------------- 335 * ----------------------------------------------------------------------------
353 */ 336 */
354 337
355 void 338 void
356 RuboutLeaf(tree) 339 RuboutLeaf(Tree *tree)
357 Tree *tree;
358 { 340 {
359 free(tree->contour.upper.head); 341 free(tree->contour.upper.head);
360 free(tree->contour.lower.tail); 342 free(tree->contour.lower.tail);
361 free(tree->contour.lower.head); 343 free(tree->contour.lower.head);
362 tree->contour.upper.head = NULL; 344 tree->contour.upper.head = NULL;
363 tree->contour.upper.tail = NULL; 345 tree->contour.upper.tail = NULL;
364 tree->contour.lower.head = NULL; 346 tree->contour.lower.head = NULL;
365 tree->contour.lower.tail = NULL; 347 tree->contour.lower.tail = NULL;
366 NumLines -= 3; 348 NumLines -= 3;
367 } 349 }
368 350
369 /* ---------------------------------------------------------------------------- 351 /* ----------------------------------------------------------------------------
370 * 352 *
371 * LayoutLeaf() accepts a single node (leaf) and forms its contour. This 353 * LayoutLeaf() accepts a single node (leaf) and forms its contour. This
372 * function assumes that the width, height, and border fields of the 354 * function assumes that the width, height, and border fields of the
373 * node have been assigned meaningful values. 355 * node have been assigned meaningful values.
374 * 356 *
375 * ---------------------------------------------------------------------------- 357 * ----------------------------------------------------------------------------
376 */ 358 */
377 359
378 void 360 void
379 LayoutLeaf(tree) 361 LayoutLeaf(Tree *tree)
380 Tree *tree;
381 { 362 {
382 tree->node_height = 0; 363 tree->node_height = 0;
383 tree->border = TreeBorderSize; 364 tree->border = TreeBorderSize;
384 365
385 tree->contour.upper.tail = MakeLine(tree->width + 2 * tree->border, 0, 366 tree->contour.upper.tail = MakeLine(tree->width + 2 * tree->border, 0,
386 NULL); 367 NULL);
387 tree->contour.upper.head = tree->contour.upper.tail; 368 tree->contour.upper.head = tree->contour.upper.tail;
388 369
389 tree->contour.lower.tail = MakeLine(0, -tree->height - 2 * tree->border, 370 tree->contour.lower.tail = MakeLine(0, -tree->height - 2 * tree->border,
390 NULL); 371 NULL);
391 tree->contour.lower.head = MakeLine(tree->width + 2 * tree->border, 0, 372 tree->contour.lower.head = MakeLine(tree->width + 2 * tree->border, 0,
392 tree->contour.lower.tail); 373 tree->contour.lower.tail);
393 374
394 } 375 }
395 376
396 /* ---------------------------------------------------------------------------- 377 /* ----------------------------------------------------------------------------
397 * 378 *
398 * LayoutTree() traverses the given tree (in depth-first order), and forms 379 * LayoutTree() traverses the given tree (in depth-first order), and forms
399 * subtree or leaf contours at each node as needed. Each node's contour is 380 * subtree or leaf contours at each node as needed. Each node's contour is
400 * stored in its "contour" field. Elision is also supported by generating 381 * stored in its "contour" field. Elision is also supported by generating
401 * the contour for both the expanded and collapsed node. This routine 382 * the contour for both the expanded and collapsed node. This routine
402 * also computes the tree height of each node in the tree, so that variable 383 * also computes the tree height of each node in the tree, so that variable
403 * density layout can be demonstrated. 384 * density layout can be demonstrated.
404 * 385 *
405 * ---------------------------------------------------------------------------- 386 * ----------------------------------------------------------------------------
406 */ 387 */
407 388
408 void 389 void
409 LayoutTree(tree) 390 LayoutTree(Tree *tree)
410 Tree *tree;
411 { 391 {
412 Tree *child; 392 Tree *child;
413 int height = 0; 393 int height = 0;
414 394
415 FOREACH_CHILD(child, tree) { 395 FOREACH_CHILD(child, tree) {
422 402
423 } 403 }
424 404
425 if (tree->child) { 405 if (tree->child) {
426 406
427 FOREACH_CHILD(child, tree) 407 FOREACH_CHILD(child, tree)
428 height = MAX(child->node_height, height); 408 height = MAX(child->node_height, height);
429 tree->node_height = height + 1; 409 tree->node_height = height + 1;
430 410
431 if (TreeLayoutDensity == Fixed) 411 if (TreeLayoutDensity == Fixed)
432 tree->border = TreeBorderSize; 412 tree->border = TreeBorderSize;
441 } 421 }
442 422
443 /* ------------------------------------------------------------------------- */ 423 /* ------------------------------------------------------------------------- */
444 424
445 void 425 void
446 Unzip(tree) 426 Unzip(Tree *tree)
447 Tree *tree;
448 { 427 {
449 Tree *child; 428 Tree *child;
450 429
451 #ifdef INTF 430 #ifdef INTF
452 if (TreeShowSteps) { 431 if (TreeShowSteps) {
453 HiliteNode(tree, New); 432 HiliteNode(tree, New);
454 tree->on_path = TRUE; 433 tree->on_path = TRUE;
455 StatusMsg("Unzip: follow parent links up to root"); 434 StatusMsg("Unzip: follow parent links up to root", 0);
456 Pause(); 435 Pause();
457 } 436 }
458 #endif 437 #endif
459 438
460 if (tree->parent) 439 if (tree->parent)
461 Unzip(tree->parent); 440 Unzip(tree->parent);
462 441
463 if (tree->child) { 442 if (tree->child) {
464 443
465 #ifdef INTF 444 #ifdef INTF
466 /* draw entire contour; do it only for root, because the last 445 /* draw entire contour; do it only for root, because the last
467 * frame drawn in this function will have already drawn the 446 * frame drawn in this function will have already drawn the
468 * contour for the most recently split subtree. 447 * contour for the most recently split subtree.
469 */ 448 */
470 if (TreeShowSteps) { 449 if (TreeShowSteps) {
471 if (tree->parent == NULL) { 450 if (tree->parent == NULL) {
472 BeginFrame(); 451 BeginFrame();
473 DrawTreeContour(tree, New, CONTOUR_COLOR, FALSE, FALSE, FALSE); 452 DrawTreeContour(tree, New, CONTOUR_COLOR, FALSE, FALSE, FALSE);
474 DrawTree(TheTree, New); 453 DrawTree(TheTree, New);
475 EndFrame(); 454 EndFrame();
476 StatusMsg("Unzip: disassemble entire contour"); 455 StatusMsg("Unzip: disassemble entire contour", 0);
477 Pause(); 456 Pause();
478 } 457 }
479 } 458 }
480 #endif 459 #endif
481 460
482 #ifdef INTF 461 #ifdef INTF
483 /* draw contour as it would appear after DetachParent() */ 462 /* draw contour as it would appear after DetachParent() */
484 if (TreeShowSteps) { 463 if (TreeShowSteps) {
485 BeginFrame(); 464 BeginFrame();
465 #if 0 /* mrb */
486 DrawTreeContour(tree, New, CONTOUR_COLOR, TRUE, 466 DrawTreeContour(tree, New, CONTOUR_COLOR, TRUE,
487 FALSE, FALSE, FALSE); 467 FALSE, FALSE, FALSE);
468 #endif
469 DrawTreeContour(tree, New, CONTOUR_COLOR, TRUE,
470 FALSE, FALSE);
488 DrawTree(TheTree, New); 471 DrawTree(TheTree, New);
489 EndFrame(); 472 EndFrame();
490 StatusMsg("Unzip: detach parent"); 473 StatusMsg("Unzip: detach parent", 0);
491 Pause(); 474 Pause();
492 } 475 }
493 #endif 476 #endif
494 477
495 DetachParent(tree); 478 DetachParent(tree);
499 if (TreeShowSteps) { 482 if (TreeShowSteps) {
500 BeginFrame(); 483 BeginFrame();
501 /* mark other subtree contours as split, and */ 484 /* mark other subtree contours as split, and */
502 /* draw only the contour on path in full */ 485 /* draw only the contour on path in full */
503 FOREACH_CHILD(child, tree) { 486 FOREACH_CHILD(child, tree) {
504 if (!child->on_path) 487 if (!child->on_path)
505 child->split = TRUE; 488 child->split = TRUE;
506 else 489 else
507 DrawTreeContour(child, New, CONTOUR_COLOR, 490 DrawTreeContour(child, New, CONTOUR_COLOR,
508 FALSE, FALSE, FALSE); 491 FALSE, FALSE, FALSE);
509 } 492 }
510 DrawTree(TheTree, New); 493 DrawTree(TheTree, New);
511 EndFrame(); 494 EndFrame();
512 StatusMsg("Unzip: split tree"); 495 StatusMsg("Unzip: split tree", 0);
513 Pause(); 496 Pause();
514 } 497 }
515 #endif 498 #endif
516 499
517 } 500 }
520 } 503 }
521 504
522 /* ------------------------------------------------------------------------- */ 505 /* ------------------------------------------------------------------------- */
523 506
524 void 507 void
525 Zip(tree) 508 Zip(Tree *tree)
526 Tree *tree;
527 { 509 {
528 if (tree->child) 510 if (tree->child)
529 AttachParent(tree, Join(tree)); 511 AttachParent(tree, Join(tree));
530 else 512 else
531 LayoutLeaf(tree); 513 LayoutLeaf(tree);
533 if (tree->parent) 515 if (tree->parent)
534 Zip(tree->parent); 516 Zip(tree->parent);
535 } 517 }
536 518
537 /* ---------------------------------------------------------------------------- 519 /* ----------------------------------------------------------------------------
538 * 520 *
539 * Insert() adds the specified child to parent, just after the specified 521 * Insert() adds the specified child to parent, just after the specified
540 * sibling. If 'sibling' is Null, the child is added as the first child. 522 * sibling. If 'sibling' is Null, the child is added as the first child.
541 * 523 *
542 * ---------------------------------------------------------------------------- 524 * ----------------------------------------------------------------------------
543 */ 525 */
544 526
545 void 527 void
546 Insert(parent, child, sibling) 528 Insert(Tree *parent, Tree *child, Tree *sibling)
547 Tree *parent, *child, *sibling;
548 { 529 {
549 Unzip(parent); 530 Unzip(parent);
550 child->parent = parent; 531 child->parent = parent;
551 if (sibling) { 532 if (sibling) {
552 child->sibling = sibling->sibling; 533 child->sibling = sibling->sibling;
561 542
562 543
563 544
564 545
565 /* ---------------------------------------------------------------------------- 546 /* ----------------------------------------------------------------------------
566 * 547 *
567 * Delete() traverses the specified tree and frees all storage 548 * Delete() traverses the specified tree and frees all storage
568 * allocated to the subtree, including contours and bridges. 549 * allocated to the subtree, including contours and bridges.
569 * If the tree had a preceding sibling, the preceding sibling is 550 * If the tree had a preceding sibling, the preceding sibling is
570 * modified to point to the tree's succeeding sibling, if any. 551 * modified to point to the tree's succeeding sibling, if any.
571 * 552 *
572 * ---------------------------------------------------------------------------- 553 * ----------------------------------------------------------------------------
573 */ 554 */
574 555
575 Delete(tree) 556 void
576 Tree *tree; 557 Delete(Tree *tree)
577 { 558 {
578 Tree *sibling = NULL; 559 Tree *sibling = NULL;
579 Tree *parent, *child; 560 Tree *parent, *child;
580 561
581 /* find sibling */ 562 /* find sibling */
589 } 570 }
590 if (sibling) 571 if (sibling)
591 sibling->sibling = tree->sibling; 572 sibling->sibling = tree->sibling;
592 else if (parent) 573 else if (parent)
593 parent->child = tree->sibling; 574 parent->child = tree->sibling;
594 575
595 DeleteTree(tree, FALSE); 576 DeleteTree(tree, FALSE);
596 } 577 }
597 578
598 579
599 /* ---------------------------------------------------------------------------- 580 /* ----------------------------------------------------------------------------
600 * 581 *
601 * DeleteTree() is the recursive function that supports Delete(). 582 * DeleteTree() is the recursive function that supports Delete().
602 * If 'contour' is True, then only the contours are recursively deleted. 583 * If 'contour' is True, then only the contours are recursively deleted.
603 * This flag should be True when you are regenerating a tree's layout 584 * This flag should be True when you are regenerating a tree's layout
604 * and still want to preserve the nodes. Since contours would be deleted 585 * and still want to preserve the nodes. Since contours would be deleted
605 * only due to a change in sibling or level distance, each node's border 586 * only due to a change in sibling or level distance, each node's border
606 * value is updated with the current value of TreeBorderSize; 587 * value is updated with the current value of TreeBorderSize;
607 * 588 *
608 * ---------------------------------------------------------------------------- 589 * ----------------------------------------------------------------------------
609 */ 590 */
610 591
611 DeleteTree(tree, contour) 592 void
612 Tree *tree; 593 DeleteTree(Tree *tree, int contour)
613 int contour;
614 { 594 {
615 Tree *child; 595 Tree *child;
616 596
617 if (tree->elision) { 597 if (tree->elision) {
618 RuboutLeaf(tree); 598 RuboutLeaf(tree);
628 DeleteTree(child, contour); 608 DeleteTree(child, contour);
629 } 609 }
630 else 610 else
631 RuboutLeaf(tree); 611 RuboutLeaf(tree);
632 612
633 if (contour) 613 if (contour)
634 tree->border = TreeBorderSize; 614 tree->border = TreeBorderSize;
635 else { 615 else {
636 free(tree->label.text); 616 free(tree->label.text);
637 free(tree); 617 free(tree);
638 NumNodes--; 618 NumNodes--;
639 } 619 }
640 } 620 }
641 621
642 622
643 /* ---------------------------------------------------------------------------- 623 /* ----------------------------------------------------------------------------
644 * 624 *
645 * ComputeTreeSize() 625 * ComputeTreeSize()
646 * This function should be called after tree layout. 626 * This function should be called after tree layout.
647 * 627 *
648 * ---------------------------------------------------------------------------- 628 * ----------------------------------------------------------------------------
649 */ 629 */
650 630
651 void 631 void
652 ComputeTreeSize(tree, width, height, x_offset, y_offset) 632 ComputeTreeSize(Tree *tree,
653 Tree *tree; 633 int *width, int *height,
654 int *width, *height; 634 int *x_offset, int *y_offset)
655 int *x_offset, *y_offset;
656 { 635 {
657 Polyline *contour, *tail; 636 Polyline *contour, *tail;
658 int upper_min_y = 0, lower_max_y = 0; 637 int upper_min_y = 0, lower_max_y = 0;
659 int upper_abs_y = 0, lower_abs_y = 0; 638 int upper_abs_y = 0, lower_abs_y = 0;
660 int x = 0; 639 int x = 0;
661 640
662 /* do upper contour */ 641 /* do upper contour */
663 contour = tree->contour.upper.head; 642 contour = tree->contour.upper.head;
664 tail = tree->contour.upper.tail; 643 tail = tree->contour.upper.tail;
665 while (contour) { 644 while (contour) {
666 if ((contour->dy + upper_abs_y) < upper_min_y) 645 if ((contour->dy + upper_abs_y) < upper_min_y)
667 upper_min_y = contour->dy + upper_abs_y; 646 upper_min_y = contour->dy + upper_abs_y;
668 upper_abs_y += contour->dy; 647 upper_abs_y += contour->dy;
669 if (contour == tail) 648 if (contour == tail)
670 contour = NULL; 649 contour = NULL;
671 else 650 else
694 if (y_offset) 673 if (y_offset)
695 *y_offset = - upper_min_y + tree->border; 674 *y_offset = - upper_min_y + tree->border;
696 } 675 }
697 676
698 /* ---------------------------------------------------------------------------- 677 /* ----------------------------------------------------------------------------
699 * 678 *
700 * PetrifyTree() 679 * PetrifyTree()
701 * 680 *
702 * ---------------------------------------------------------------------------- 681 * ----------------------------------------------------------------------------
703 */ 682 */
704 683
705 void 684 void
706 PetrifyTree(tree, x, y) 685 PetrifyTree(Tree *tree, int x, int y)
707 Tree *tree;
708 int x, y;
709 { 686 {
710 int width, height; 687 int width, height;
711 int x_offset, y_offset; 688 int x_offset, y_offset;
712 689
713 tree->old_pos = tree->pos; /* used by AnimateTree */ 690 tree->old_pos = tree->pos; /* used by AnimateTree */
714 691
715 /* fix position of each node */ 692 /* fix position of each node */
716 tree->pos.x = x + tree->offset.x; 693 tree->pos.x = x + tree->offset.x;
717 tree->pos.y = y + tree->offset.y; 694 tree->pos.y = y + tree->offset.y;
718 695
719 if (tree->child) { 696 if (tree->child) {
720 PetrifyTree(tree->child, tree->pos.x, tree->pos.y); 697 PetrifyTree(tree->child, tree->pos.x, tree->pos.y);
721 ComputeSubTreeExtent(tree); /* for benefit of interface picking */ 698 ComputeSubTreeExtent(tree); /* for benefit of interface picking */
722 } 699 }
723 if (tree->sibling) 700 if (tree->sibling)