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