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