Mercurial > hg > xemacs-beta

comparison lisp/oobr/tree-x/tree.c @ 0:376386a54a3c r19-14

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Import from CVS: tag r19-14
author cvs
date Mon, 13 Aug 2007 08:45:50 +0200
parents
children
comparison
equal deleted inserted replaced
-1:000000000000 0:376386a54a3c
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 }