Mercurial > hg > xemacs-beta

comparison pkg-src/tree-x/draw.c @ 163:0132846995bd r20-3b8

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Import from CVS: tag r20-3b8
author cvs
date Mon, 13 Aug 2007 09:43:35 +0200
parents
children 85ec50267440
comparison
equal deleted inserted replaced
162:4de2936b4e77 163:0132846995bd
1 /* ----------------------------------------------------------------------------
2 * File : draw.c
3 * Purpose : drawing-specific routines for dynamic tree program
4 * ----------------------------------------------------------------------------
5 */
6
7 #include <X11/Intrinsic.h>
8 #include <X11/StringDefs.h>
9
10 #include "defs.h"
11 #include "tree.h"
12 #include "dbl.h"
13 #include "intf.h"
14
15 /* ------------------------------------------------------------------------- */
16 /* Global Variables */
17 /* ------------------------------------------------------------------------- */
18
19 Tree *TheTree;
20
21
22 /* ------------------------------------------------------------------------- */
23 /* Local Variables */
24 /* ------------------------------------------------------------------------- */
25
26 static char AnimationMode = FALSE;
27 static char strbuf[BUFSIZ];
28 static int AnimationStep = ANIMATION_STEP;
29
30 /* ------------------------------------------------------------------------- */
31 /* Forward Function Declarations */
32 /* ------------------------------------------------------------------------- */
33
34 void DrawNode();
35 void DrawTreeContour();
36
37
38 /* ------------------------------------------------------------------------- */
39 /* Functions */
40 /* ------------------------------------------------------------------------- */
41
42
43 /* ----------------------------------------------------------------------------
44 *
45 * BeginFrame() provides an abstraction for double buffering. It should
46 * be called prior to creating a new frame of animation.
47 *
48 * ----------------------------------------------------------------------------
49 */
50
51 void
52 BeginFrame()
53 {
54 DBLbegin_frame(TreeDrawingAreaDB);
55 }
56
57
58 /* ----------------------------------------------------------------------------
59 *
60 * EndFrame() provides an abstraction for double buffering. It should
61 * be called after creating a new frame of animation.
62 *
63 * ----------------------------------------------------------------------------
64 */
65
66 void
67 EndFrame()
68 {
69 DBLend_frame(TreeDrawingAreaDB, 0);
70 }
71
72
73 /* ----------------------------------------------------------------------------
74 *
75 * GetDrawingSize() gets the size of the drawing area, and returns the
76 * dimensions in the arguments.
77 *
78 * ----------------------------------------------------------------------------
79 */
80
81 void
82 GetDrawingSize(width, height)
83 int *width, *height;
84 {
85 Dimension w, h;
86
87 XtVaGetValues(TreeDrawingArea,
88 XtNwidth, &w,
89 XtNheight, &h,
90 NULL);
91
92 *width = (int) w;
93 *height = (int) h;
94 }
95
96
97 /* ----------------------------------------------------------------------------
98 *
99 * SetDrawingSize() sets the size of the drawing area to the given
100 * dimensions.
101 *
102 * ----------------------------------------------------------------------------
103 */
104
105 void
106 SetDrawingSize(width, height)
107 int width, height;
108 {
109 XtVaSetValues(TreeDrawingArea,
110 XtNwidth, (Dimension) width,
111 XtNheight, (Dimension) height,
112 NULL);
113 }
114
115
116 /* ----------------------------------------------------------------------------
117 *
118 * SetDrawingTree() is used to specify what tree is to be drawn in the
119 * drawing area.
120 *
121 * ----------------------------------------------------------------------------
122 */
123
124 void
125 SetDrawingTree(tree)
126 Tree *tree;
127 {
128 TheTree = tree;
129 }
130
131
132 /* ----------------------------------------------------------------------------
133 *
134 * SetNodeLabel() sets the label text of the specified node and computes
135 * the bounding rectangle so that the layout can be determined. This
136 * function is called when new nodes are created. If TreeAlignNodes is
137 * True, the string is truncated so that the node's width is no longer
138 * than TreeParentDistance.
139 *
140 * ----------------------------------------------------------------------------
141 */
142
143 void
144 SetNodeLabel(node, label)
145 Tree *node;
146 char *label;
147 {
148 int len;
149 int dummy;
150 XCharStruct rtrn;
151
152 len = strlen(label);
153 while (len > 1) {
154 XTextExtents(TreeLabelFont, label, len, &dummy, &dummy, &dummy, &rtrn);
155 node->width = rtrn.lbearing + rtrn.rbearing + (LABEL_MAT_WIDTH * 2) + 1;
156 node->height = rtrn.ascent + rtrn.descent + (LABEL_MAT_HEIGHT * 2) + 1;
157 if (TreeAlignNodes) {
158 if (node->width <= (2 * TreeParentDistance))
159 break;
160 else
161 len--;
162 }
163 else
164 break;
165 }
166
167 node->label.text = label;
168 node->label.len = len;
169 node->label.xoffset = LABEL_MAT_WIDTH + 1,
170 node->label.yoffset = rtrn.ascent + LABEL_MAT_HEIGHT + 1;
171 }
172
173
174 /* ----------------------------------------------------------------------------
175 *
176 * SetDrawColor() sets the drawing color of the TreeDrawingArea.
177 *
178 * ----------------------------------------------------------------------------
179 */
180
181 void
182 SetDrawColor(color)
183 int color;
184 {
185 XSetForeground(TreeDrawingAreaDB->display, TreeDrawingAreaDB->gc,
186 TreeDrawingAreaDB->colors[color]);
187 }
188
189 /* ----------------------------------------------------------------------------
190 *
191 * SetLineWidth() sets the line width of lines drawn in the TreeDrawingArea.
192 *
193 * ----------------------------------------------------------------------------
194 */
195
196 void
197 SetLineWidth(width)
198 unsigned int width;
199 {
200 XSetLineAttributes(TreeDrawingAreaDB->display, TreeDrawingAreaDB->gc,
201 width, LineSolid, CapButt, JoinRound);
202 }
203
204
205 /* ----------------------------------------------------------------------------
206 *
207 * SetContours() sets the visibility of three possible contour modes:
208 * the outside contour, all subtree contours, or selected contours.
209 *
210 * ----------------------------------------------------------------------------
211 */
212
213 void
214 SetContours(option)
215 ContourOption option;
216 {
217 if (option == NoContours) {
218 switch (TreeShowContourOption) {
219 case OutsideContour:
220 DrawTreeContour(TheTree, New, BACKGROUND_COLOR, FALSE, FALSE, FALSE);
221 break;
222 case AllContours:
223 DrawTreeContour(TheTree, New, BACKGROUND_COLOR, FALSE, FALSE, TRUE);
224 break;
225 case SelectedContours:
226 DrawTreeContour(TheTree, New, BACKGROUND_COLOR, FALSE, TRUE, TRUE);
227 break;
228 default:
229 ;
230 }
231 DrawTreeContour(TheTree, New, BACKGROUND_COLOR, FALSE, FALSE, TRUE);
232 }
233 else if (option == OutsideContour) {
234 switch (TreeShowContourOption) {
235 case AllContours:
236 DrawTreeContour(TheTree, New, BACKGROUND_COLOR, FALSE, FALSE, TRUE);
237 break;
238 case SelectedContours:
239 DrawTreeContour(TheTree, New, BACKGROUND_COLOR, FALSE, TRUE, TRUE);
240 break;
241 default:
242 ;
243 }
244 DrawTreeContour(TheTree, New, CONTOUR_COLOR, FALSE, FALSE, FALSE);
245 } else if (option == AllContours) {
246 DrawTreeContour(TheTree, New, CONTOUR_COLOR, FALSE, FALSE, TRUE);
247 } else if (option == SelectedContours) {
248 switch (TreeShowContourOption) {
249 case AllContours:
250 DrawTreeContour(TheTree, New, BACKGROUND_COLOR, FALSE, FALSE, TRUE);
251 break;
252 case OutsideContour:
253 DrawTreeContour(TheTree, New, BACKGROUND_COLOR, FALSE, FALSE, FALSE);
254 break;
255 default:
256 DrawTreeContour(TheTree, New, BACKGROUND_COLOR, FALSE, FALSE, TRUE);
257 }
258 DrawTreeContour(TheTree, New, CONTOUR_COLOR, FALSE, TRUE, TRUE);
259 }
260 TreeShowContourOption = option;
261 }
262
263
264 /* ----------------------------------------------------------------------------
265 *
266 * HiliteNode() is called by Unzip() to change the color of a node.
267 *
268 * ----------------------------------------------------------------------------
269 */
270
271 void
272 HiliteNode(tree, pos_mode)
273 Tree *tree;
274 {
275 SetDrawColor(HIGHLIGHT_COLOR);
276 DrawNode(tree, pos_mode);
277 SetDrawColor(TREE_COLOR);
278 }
279
280
281 /* ----------------------------------------------------------------------------
282 *
283 * DrawNode() takes a node and draws the node in the specified widget
284 * at its (x,y) coordinate. (x, y) indicates the upper-left corner where
285 * the node is drawn. Also, a line is drawn from the center of the left
286 * edge to the center of the parent's right edge. 'draw_mode' specifies
287 * the drawing mode (whether or not the node is erased, rather than drawn).
288 * 'pos_mode' determines whether or not to use the old position of the node.
289 * This flag is used in animating the movement of a node from its old
290 * position to its new position.
291 *
292 * ----------------------------------------------------------------------------
293 */
294
295 void
296 DrawNode(node, pos_mode)
297 Tree *node;
298 PosMode pos_mode;
299 {
300 Widget w;
301 GC gc;
302
303 w = TreeDrawingArea;
304 gc = TreeDrawingAreaDB->gc;
305
306 if (pos_mode == Old) {
307 XDrawString(XtDisplay(w), XtWindow(w), gc,
308 node->old_pos.x + node->label.xoffset,
309 node->old_pos.y + node->label.yoffset,
310 node->label.text, node->label.len);
311 XDrawRectangle(XtDisplay(w), XtWindow(w), gc,
312 node->old_pos.x, node->old_pos.y,
313 node->width, node->height);
314 if (node->parent)
315 XDrawLine(XtDisplay(w), XtWindow(w), gc,
316 node->old_pos.x - 1,
317 node->old_pos.y + (node->height / 2),
318 node->parent->old_pos.x + node->parent->width + 1,
319 node->parent->old_pos.y + (node->parent->height / 2));
320 if (node->elision) {
321 XSetFillStyle(TreeDrawingAreaDB->display, TreeDrawingAreaDB->gc,
322 FillTiled);
323 XFillRectangle(XtDisplay(w), XtWindow(w), gc,
324 node->old_pos.x + node->width - ELISION_WIDTH,
325 node->old_pos.y + 1, ELISION_WIDTH, node->height - 1);
326 XSetFillStyle(TreeDrawingAreaDB->display, TreeDrawingAreaDB->gc,
327 FillSolid);
328 }
329 } else {
330 XDrawString(XtDisplay(w), XtWindow(w), gc,
331 node->pos.x + node->label.xoffset,
332 node->pos.y + node->label.yoffset,
333 node->label.text, node->label.len);
334
335 XDrawRectangle(XtDisplay(w), XtWindow(w), gc,
336 node->pos.x, node->pos.y,
337 node->width, node->height);
338 if (node->parent)
339 XDrawLine(XtDisplay(w), XtWindow(w), gc,
340 node->pos.x - 1,
341 node->pos.y + (node->height / 2),
342 node->parent->pos.x + node->parent->width + 1,
343 node->parent->pos.y + (node->parent->height / 2));
344 if (node->elision) {
345 XSetFillStyle(TreeDrawingAreaDB->display, TreeDrawingAreaDB->gc,
346 FillTiled);
347 XFillRectangle(XtDisplay(w), XtWindow(w), gc,
348 node->pos.x + node->width - ELISION_WIDTH,
349 node->pos.y + 1, ELISION_WIDTH, node->height - 1);
350 XSetFillStyle(TreeDrawingAreaDB->display, TreeDrawingAreaDB->gc,
351 FillSolid);
352 }
353 }
354 }
355
356
357 /* ----------------------------------------------------------------------------
358 *
359 * DrawTreeContour() draws the contour of the specified subtree. Bridges
360 * are not traversed, so the actual subtree contour is drawn, as opposed
361 * to the merged contour. 'color' specifies the drawing color. If 'detach'
362 * is True, the lines attaching the subtree contour to the node are not
363 * drawn. If 'select' is true, then only subtrees that are flagged as
364 * selected are shown. If 'recursive' is True, the entire tree is traversed.
365 *
366 * ----------------------------------------------------------------------------
367 */
368
369 void
370 DrawTreeContour(tree, pos_mode, color, detach, select, recursive)
371 Tree *tree;
372 PosMode pos_mode;
373 int color;
374 int detach;
375 int select;
376 int recursive;
377 {
378 Widget w = TreeDrawingArea;
379 Polyline *contour, *tail;
380 Tree *child;
381 int x, y, i;
382
383 if (tree == NULL)
384 return;
385
386 if ((select && tree->show_contour) || !select) {
387
388 SetDrawColor(color);
389 SetLineWidth(TreeContourWidth);
390
391 /* draw upper contour */
392 contour = tree->contour.upper.head;
393 tail = tree->contour.upper.tail;
394 if (pos_mode == Old) {
395 x = tree->old_pos.x - tree->border;
396 y = tree->old_pos.y - tree->border;
397 }
398 else {
399 x = tree->pos.x - tree->border;
400 y = tree->pos.y - tree->border;
401 }
402
403 if (detach) { /* skip over attaching lines */
404 for (i = 0 ; i < 2 ; i++) {
405 x += contour->dx;
406 y += contour->dy;
407 contour = contour->link;
408 }
409 }
410
411 while (contour) {
412 XDrawLine(XtDisplay(w), XtWindow(w), TreeDrawingAreaDB->gc,
413 x, y, x + contour->dx, y + contour->dy);
414 x += contour->dx;
415 y += contour->dy;
416 if (contour == tail) /* make sure you don't follow bridges */
417 contour = NULL;
418 else
419 contour = contour->link;
420 }
421
422 /* draw lower contour */
423 contour = tree->contour.lower.head;
424 tail = tree->contour.lower.tail;
425 if (pos_mode == Old) {
426 x = tree->old_pos.x - tree->border;
427 y = tree->old_pos.y + tree->border + tree->height;
428 } else {
429 x = tree->pos.x - tree->border;
430 y = tree->pos.y + tree->border + tree->height;
431 }
432
433 if (detach) { /* skip over attaching lines */
434 for (i = 0 ; i < 2 ; i++) {
435 x += contour->dx;
436 y += contour->dy;
437 contour = contour->link;
438 }
439 }
440
441 while (contour) {
442 XDrawLine(XtDisplay(w), XtWindow(w), TreeDrawingAreaDB->gc,
443 x, y, x + contour->dx, y + contour->dy);
444 x += contour->dx;
445 y += contour->dy;
446 if (contour == tail) /* make sure you don't follow bridges */
447 contour = NULL;
448 else
449 contour = contour->link;
450 }
451 }
452
453 if (recursive) {
454 FOREACH_CHILD(child, tree)
455 if (!child->elision)
456 DrawTreeContour(child, pos_mode, color,
457 detach, select, recursive);
458 }
459
460 SetDrawColor(TREE_COLOR);
461 SetLineWidth(0);
462 }
463
464
465 /* ----------------------------------------------------------------------------
466 *
467 * DrawTree() traverses the given tree, drawing the node and connecting
468 * segments. The tree contours are also drawn at each step, if enabled.
469 * 'draw_mode' specifies the drawing mode in which the tree is drawn.
470 * 'pos_mode' determines whether or not to use the old position of the node.
471 * This flag is used in animating the movement of a node from its old
472 * position to its new position. DrawNode() is called to draw an individual
473 * node.
474 *
475 * ----------------------------------------------------------------------------
476 */
477
478 void
479 DrawTree(tree, pos_mode)
480 Tree *tree;
481 PosMode pos_mode;
482 {
483 if (tree == NULL)
484 return;
485
486 DrawNode(tree, pos_mode);
487
488 /* do stuff that animates Unzip() */
489 if (tree->split) {
490 if (!AnimationMode ||
491 (tree->pos.x == tree->old_pos.x &&
492 tree->pos.y == tree->old_pos.y))
493 DrawTreeContour(tree, pos_mode, SPLIT_COLOR, FALSE, FALSE, FALSE);
494 else
495 DrawTreeContour(tree, pos_mode, ACTION_COLOR, FALSE, FALSE, FALSE);
496 }
497 if (tree->on_path)
498 HiliteNode(tree, pos_mode);
499
500 if (tree->child && !tree->elision)
501 DrawTree(tree->child, pos_mode);
502 if (tree->sibling)
503 DrawTree(tree->sibling, pos_mode);
504 }
505
506
507 /* ----------------------------------------------------------------------------
508 *
509 * ShiftTree() adjusts the positions of each node so that it moves from
510 * the "old" position towards the "new position". This is used by
511 * AnimateTree(). 'done' is set to FALSE if the tree is not in its
512 * final position; it is used to determine when to stop animating the tree.
513 *
514 * ----------------------------------------------------------------------------
515 */
516
517 void
518 ShiftTree(tree, done)
519 Tree *tree;
520 int *done;
521 {
522 Tree *child;
523
524 if (tree->old_pos.x != tree->pos.x ||
525 tree->old_pos.y != tree->pos.y)
526 {
527 tree->old_pos.x = tree->pos.x;
528 tree->old_pos.y = tree->pos.y;
529 }
530
531 FOREACH_CHILD(child, tree)
532 ShiftTree(child, done);
533 }
534
535
536 /* ----------------------------------------------------------------------------
537 *
538 * AnimateTree() draws the given tree in a series of steps to give the
539 * effect of animation from the "old" layout to the "new" layout of the
540 * tree.
541 *
542 * The algorithm used here is not efficient; the entire tree is drawn
543 * on each iteration of the animation sequence; it would be more efficient
544 * to only redraw what is necessary. However, the method used here takes
545 * advantage of existing code without modification.
546 *
547 * ----------------------------------------------------------------------------
548 */
549
550 void
551 AnimateTree(tree)
552 Tree *tree;
553 {
554 int done = FALSE;
555
556 AnimationMode = FALSE;
557 /* highlight which nodes have to move */
558 BeginFrame();
559 DrawTree(tree, Old);
560 EndFrame();
561 Pause();
562 if (PauseAfterStep)
563 AnimationStep = ANIMATION_STEP_STEP;
564 while (!done) {
565 done = TRUE;
566 ShiftTree(tree, &done);
567 BeginFrame();
568 DrawTree(tree, Old);
569 EndFrame();
570 if (PauseAfterStep)
571 Pause();
572 }
573 if (PauseAfterStep)
574 AnimationStep = ANIMATION_STEP;
575 AnimationMode = FALSE;
576 }
577
578
579 /* ----------------------------------------------------------------------------
580 *
581 * AnimateZip() generates a sequence of frames that animates the Zip() step.
582 * It is similar in logical structure to Zip().
583 *
584 * ----------------------------------------------------------------------------
585 */
586
587 void
588 AnimateZip(tree)
589 Tree *tree;
590 {
591 Tree *child;
592
593 /* show results of Join() step */
594 if (tree->child) {
595 BeginFrame();
596 FOREACH_CHILD(child, tree)
597 child->split = FALSE;
598 DrawTree(TheTree, New);
599 DrawTreeContour(tree, New, CONTOUR_COLOR, TRUE, FALSE, FALSE);
600 EndFrame();
601
602 StatusMsg("Zip: merge and join contours", FALSE);
603 Pause();
604
605 /* show results of AttachParent() step */
606 BeginFrame();
607 DrawTree(TheTree, New);
608 DrawTreeContour(tree, New, CONTOUR_COLOR, FALSE, FALSE, FALSE);
609 EndFrame();
610
611 StatusMsg("Zip: attach parents", FALSE);
612 Pause();
613 }
614
615 tree->on_path = FALSE;
616
617 if (tree->parent)
618 AnimateZip(tree->parent);
619 else {
620 tree->on_path = FALSE;
621 BeginFrame();
622 DrawTree(TheTree, New);
623 DrawTreeContour(TheTree, New, CONTOUR_COLOR, FALSE, FALSE, FALSE);
624 EndFrame();
625 StatusMsg("Zip: reassemble entire contour", FALSE);
626 Pause();
627 }
628 }
629
630
631 /* ----------------------------------------------------------------------------
632 *
633 * CountNodes() returns the number of nodes in the specified tree.
634 * Nodes below a node that has been collapsed are ignored.
635 *
636 * ----------------------------------------------------------------------------
637 */
638
639 int
640 CountNodes(tree)
641 Tree *tree;
642 {
643 int num_nodes = 1; /* count root of subtree */
644 Tree *child;
645
646 if (!tree->elision) {
647 FOREACH_CHILD(child, tree)
648 num_nodes += CountNodes(child);
649 }
650 return (num_nodes);
651 }
652
653
654 /* ----------------------------------------------------------------------------
655 *
656 * CollectNodeRectangles() is a recursive function used by
657 * GetSubTreeRectangles() to collect the rectangles of descendant nodes
658 * into the pre-allocated storage passed to this function.
659 *
660 * ----------------------------------------------------------------------------
661 */
662
663 void
664 CollectNodeRectangles(node, rectangles, fill)
665 Tree *node;
666 XRectangle **rectangles;
667 int fill;
668 {
669 Tree *child;
670
671 (*rectangles)->x = node->pos.x;
672 (*rectangles)->y = node->pos.y;
673 if (fill) {
674 (*rectangles)->width = node->width + 1;
675 (*rectangles)->height = node->height + 1;
676 } else {
677 (*rectangles)->width = node->width;
678 (*rectangles)->height = node->height;
679 }
680 (*rectangles)++;
681
682 if (!node->elision)
683 FOREACH_CHILD(child, node)
684 CollectNodeRectangles(child, rectangles, fill);
685 }
686
687
688 /* ----------------------------------------------------------------------------
689 *
690 * GetSubTreeRectangles() builds an array of XRectangles that contain
691 * all the node rectangles in the tree, except the root node itself.
692 * The array is returned in 'rectangles' and the number of rectangles
693 * is returned in 'nrectangles.' Storage for the rectangles is allocated
694 * in this function. This function is used by PickAction to determine
695 * what rectangles need to be dissolved away. 'fill', if True, specifies
696 * that the rectangles should be 1 pixel larger in each dimension to
697 * compensate for FillRectangle behavior.
698 *
699 * ----------------------------------------------------------------------------
700 */
701
702 void
703 GetSubTreeRectangles(tree, rectangles, nrectangles, fill)
704 Tree *tree;
705 XRectangle **rectangles;
706 int *nrectangles, fill;
707 {
708 Tree *child;
709 XRectangle *crect; /* current rectangle */
710
711 *nrectangles = CountNodes(tree) - 1; /* don't count root node */
712 *rectangles = (XRectangle *) malloc(sizeof(XRectangle) * *nrectangles);
713 ASSERT(*rectangles, "could not allocate memory for rectangles");
714
715 crect = *rectangles;
716 if (!tree->elision)
717 FOREACH_CHILD(child, tree)
718 CollectNodeRectangles(child, &crect, fill);
719 }
720
721
722 /* ----------------------------------------------------------------------------
723 *
724 * CollectNodeSegments() is a recursive function used by GetSubTreeSegments()
725 * to collect the line segments connecting nodes into the pre-allocated
726 * storage passed to this function.
727 *
728 * ----------------------------------------------------------------------------
729 */
730
731 void
732 CollectNodeSegments(node, segments)
733 Tree *node;
734 XSegment **segments;
735 {
736 Tree *child;
737
738 (*segments)->x1 = node->pos.x - 1;
739 (*segments)->y1 = node->pos.y + (node->height / 2),
740 (*segments)->x2 = node->parent->pos.x + node->parent->width + 1;
741 (*segments)->y2 = node->parent->pos.y + (node->parent->height / 2);
742 (*segments)++;
743
744 if (!node->elision)
745 FOREACH_CHILD(child, node)
746 CollectNodeSegments(child, segments);
747 }
748
749
750 /* ----------------------------------------------------------------------------
751 *
752 * GetSubTreeSegments() builds an array of XSegments that contain
753 * all the line segments connecting the nodes in the tree. The array is
754 * returned in 'segments' and the number of segments is returned in
755 * 'nsegments.' Storage for the segments is allocated in this function.
756 * This function is used by PickAction to determine what line segments
757 * rectangles need to be dissolved away.
758 *
759 * ----------------------------------------------------------------------------
760 */
761
762 void
763 GetSubTreeSegments(tree, segments, nsegments)
764 Tree *tree;
765 XSegment **segments;
766 int *nsegments;
767 {
768 Tree *child;
769 XSegment *cseg; /* current segment */
770
771 *nsegments = CountNodes(tree) - 1;
772 *segments = (XSegment *) malloc(sizeof(XSegment) * *nsegments);
773 ASSERT(*segments, "could not allocate memory for segments");
774
775 cseg = *segments;
776 if (!tree->elision)
777 FOREACH_CHILD(child, tree)
778 CollectNodeSegments(child, &cseg);
779 }
780
781
782 /* ----------------------------------------------------------------------------
783 *
784 * ComputeSubTreeExtent() computes the extent of a subtree. This is
785 * easily computed based on the tree's contour, as in ComputeTreeSize().
786 * This extent is stored in the node, and used by SearchTree for
787 * pick-correlation.
788 *
789 * This function assumes that the given tree has at least one child; do not
790 * pass a leaf node to this function.
791 *
792 * ----------------------------------------------------------------------------
793 */
794
795 void
796 ComputeSubTreeExtent(tree)
797 Tree *tree;
798 {
799 int width, height;
800 int x_offset, y_offset;
801
802 ComputeTreeSize(tree, &width, &height, &x_offset, &y_offset);
803 tree->subextent.pos.x = tree->child->pos.x - tree->child->border;
804 tree->subextent.pos.y = tree->pos.y - y_offset;
805 tree->subextent.width = width - (tree->child->pos.x - tree->pos.x) - 1;
806 tree->subextent.height = height - 1;
807 }
808
809
810 /* ----------------------------------------------------------------------------
811 *
812 * SearchTree() determines if a node's rectangular region encloses the
813 * specified point in (x,y). Rather than using a brute-force search
814 * through all node rectangles of a given tree, the subtree extents
815 * are used in a recursive fashion to drive the search as long as the
816 * given point is enclosed in an extent. In the worst case, the search
817 * time would be on the order of a brute-force search, but with complex
818 * trees, this method reduces the number of visits.
819 *
820 * The extent of a subtree is computed by ComputeSubTreeExtent() and is
821 * stored in each node of the tree.
822 *
823 * ----------------------------------------------------------------------------
824 */
825
826 int
827 SearchTree(tree, x, y, node)
828 Tree *tree, **node;
829 int x, y;
830 {
831 Tree *child;
832
833 if (tree == NULL)
834 return (FALSE);
835
836 if (PT_IN_RECT(x, y, tree->pos.x, tree->pos.y,
837 tree->pos.x + tree->width,
838 tree->pos.y + tree->height)) {
839 *node = tree;
840 return (TRUE);
841 }
842 if (tree->child && (PT_IN_EXTENT(x, y, tree->subextent)))
843 FOREACH_CHILD(child, tree) {
844 if (SearchTree(child, x, y, node))
845 return (TRUE);
846 }
847 return (FALSE);
848 }
849
850
851 /* ----------------------------------------------------------------------------
852 *
853 * ExposeHandler() handles expose events in the TreeDrawingArea. This
854 * function is not intelligent; it just redraws the entire contents.
855 *
856 * ----------------------------------------------------------------------------
857 */
858
859 void
860 ExposeHandler(w, client_data, event)
861 Widget w;
862 caddr_t client_data;
863 XExposeEvent *event;
864 {
865
866 if (event->count == 0) {
867 BeginFrame();
868 SetContours(TreeShowContourOption);
869 DrawTree(TheTree, New);
870 EndFrame();
871 }
872 }
873
874
875 /* ----------------------------------------------------------------------------
876 *
877 * ExpandCollapseNode is called to expand or collapse a node in the tree.
878 *
879 * ----------------------------------------------------------------------------
880 */
881
882 void
883 ExpandCollapseNode(node)
884 Tree *node;
885 {
886 int width, height;
887 int old_width, old_height;
888 int x_offset, y_offset;
889 XRectangle *rectangles;
890 XSegment *segments;
891 int nrectangles, nsegments;
892 int expand = FALSE;
893 Widget w = TreeDrawingArea;
894
895 StatusMsg("", TRUE);
896
897 /* hilite node so that we know where we are */
898 /* DrawTree will hilite it as a side effect */
899 if (TreeShowSteps)
900 node->on_path = TRUE;
901
902 /* erase the contour before changing in the tree */
903 if ((TreeShowContourOption != NoContours) || TreeShowSteps) {
904 BeginFrame();
905 DrawTree(TheTree, New);
906 EndFrame();
907 }
908
909 sprintf(strbuf, "Node `%s' selected for %s", node->label.text,
910 node->elision ? "expansion" : "collapse");
911 StatusMsg(strbuf, FALSE);
912 Pause();
913
914 if (node->parent)
915 Unzip(node->parent);
916 else {
917 StatusMsg("Show entire contour", FALSE);
918 if (TreeShowSteps) {
919 BeginFrame();
920 DrawTreeContour(TheTree, New, CONTOUR_COLOR, FALSE, FALSE, FALSE);
921 DrawTree(TheTree, New);
922 EndFrame();
923 Pause();
924 }
925 }
926
927 /* are we collapsing a subtree? */
928 if (!node->elision) {
929 StatusMsg("Collapse subtree", FALSE);
930 GetSubTreeRectangles(node, &rectangles, &nrectangles, TRUE);
931 GetSubTreeSegments(node, &segments, &nsegments);
932 DissolveTree(XtDisplay(w), XtWindow(w),
933 rectangles, nrectangles,
934 segments, nsegments, TRUE);
935 free(rectangles);
936 free(segments);
937 Pause();
938
939 StatusMsg("Replace subtree contour with leaf contour", FALSE);
940 node->elision = TRUE;
941 if (TreeShowSteps)
942 node->split = TRUE; /* turned off in AnimateZip */
943 node->old_contour = node->contour;
944 node->width += ELISION_WIDTH;
945 LayoutLeaf(node);
946 BeginFrame();
947 SetContours(TreeShowContourOption);
948 DrawTree(TheTree, New);
949 EndFrame();
950 Pause();
951 } else {
952 StatusMsg("Replace leaf contour with old subtree contour", FALSE);
953 if (TreeShowSteps)
954 node->split = TRUE; /* turned off in AnimateZip */
955 RuboutLeaf(node);
956 node->contour = node->old_contour;
957 expand = TRUE;
958 }
959
960 if (node->parent)
961 Zip(node->parent);
962
963 ComputeTreeSize(TheTree, &width, &height, &x_offset, &y_offset);
964 PetrifyTree(TheTree, x_offset + MAT_SIZE, y_offset + MAT_SIZE);
965 GetDrawingSize(&old_width, &old_height);
966
967 if (expand) {
968 SetDrawingSize(width + (2 * MAT_SIZE), height + (2 * MAT_SIZE));
969 BeginFrame();
970 DrawTree(TheTree, Old);
971 EndFrame();
972 Pause();
973 StatusMsg("Move tree to new configuration", FALSE);
974 AnimateTree(TheTree);
975 } else {
976 /* we are shrinking or staying the same */
977 StatusMsg("Move tree to new configuration", FALSE);
978 AnimateTree(TheTree);
979 SetDrawingSize(width + (2 * MAT_SIZE), height + (2 * MAT_SIZE));
980 }
981
982 if (expand) {
983 StatusMsg("Expand subtree", FALSE);
984 node->elision = FALSE;
985
986 /* erase elision marker */
987 XSetFunction(TreeDrawingAreaDB->display, TreeDrawingAreaDB->gc,
988 GXclear);
989 XFillRectangle(XtDisplay(w), XtWindow(w), TreeDrawingAreaDB->gc,
990 node->pos.x + node->width - ELISION_WIDTH + 1,
991 node->pos.y, ELISION_WIDTH, node->height + 1);
992 XSetFunction(TreeDrawingAreaDB->display, TreeDrawingAreaDB->gc,
993 GXcopy);
994 node->width -= ELISION_WIDTH;
995
996 GetSubTreeRectangles(node, &rectangles, &nrectangles, FALSE);
997 GetSubTreeSegments(node, &segments, &nsegments);
998 /* dissolve the tree back in */
999 DissolveTree(XtDisplay(w), XtWindow(w),
1000 rectangles, nrectangles,
1001 segments, nsegments, FALSE);
1002 free(rectangles);
1003 free(segments);
1004
1005 /* draw text of nodes */
1006 BeginFrame();
1007 SetContours(TreeShowContourOption);
1008 DrawTree(TheTree, New);
1009 EndFrame();
1010 Pause();
1011 }
1012
1013 if (TreeShowSteps) {
1014 node->on_path = FALSE;
1015 if (node->parent)
1016 AnimateZip(node->parent);
1017 else
1018 node->split = FALSE;
1019 }
1020
1021 /* BUG: the display isn't properly updated here! */
1022 /* There should probably be some code here that
1023 clears the tree below the node currently being
1024 collapsed or expanded. Hack added 20.03.95 (torgeir@ii.uib.no).
1025 I'll try to fix this later. */
1026
1027 XClearArea(TreeDisplay, XtWindow(TreeDrawingArea), 0, 0, 0, 0, FALSE);
1028
1029 BeginFrame();
1030 SetContours(TreeShowContourOption);
1031 DrawTree(TheTree, New);
1032 EndFrame();
1033
1034 StatusMsg("Ready", TRUE);
1035 }
1036
1037 /* ----------------------------------------------------------------------------
1038 *
1039 * InsertNode() handles the task of inserting a new node in the tree,
1040 * at the given position with respect to 'base_node'. When 'node_pos' is
1041 * either Before or After, it is assumed that 'base_node' has a parent.
1042 *
1043 * ----------------------------------------------------------------------------
1044 */
1045
1046 void
1047 InsertNode(base_node, node_pos, new_node_text)
1048 Tree *base_node;
1049 NodePosition node_pos;
1050 char *new_node_text;
1051 {
1052 Tree *new_node;
1053 Tree *parent;
1054 Tree *sibling = NULL;
1055 Tree *child;
1056
1057 int width, height;
1058 int x_offset, y_offset;
1059
1060 StatusMsg("", TRUE);
1061
1062 new_node = MakeNode(); /* should check for memory failure */
1063 SetNodeLabel(new_node, new_node_text);
1064 LayoutLeaf(new_node);
1065
1066 /* figure out parent & sibling */
1067 if (node_pos == Child) {
1068 parent = base_node;
1069 /* find last child, if one exists */
1070 FOREACH_CHILD(child, parent)
1071 sibling = child;
1072 } else if (node_pos == After) {
1073 parent = base_node->parent;
1074 sibling = base_node;
1075 } else if (node_pos == Before) {
1076 parent = base_node->parent;
1077 FOREACH_CHILD(child, parent)
1078 if (child->sibling == base_node) {
1079 sibling = child;
1080 break;
1081 }
1082 }
1083
1084 if (TreeShowSteps)
1085 parent->on_path = TRUE;
1086
1087 if ((TreeShowContourOption != NoContours) ||
1088 TreeShowSteps) {
1089 BeginFrame();
1090 DrawTree(TheTree, New);
1091 EndFrame();
1092 }
1093
1094 sprintf(strbuf, "Inserting `%s' as child of node `%s'",
1095 new_node_text, parent->label.text);
1096 StatusMsg(strbuf, FALSE);
1097 Pause();
1098
1099 /* erase the contour before changing in the tree */
1100
1101 Insert(parent, new_node, sibling);
1102
1103 ComputeTreeSize(TheTree, &width, &height, &x_offset, &y_offset);
1104 PetrifyTree(TheTree, x_offset + MAT_SIZE, y_offset + MAT_SIZE);
1105
1106 if (sibling)
1107 new_node->old_pos = sibling->old_pos;
1108 else if (new_node->sibling)
1109 new_node->old_pos = new_node->sibling->old_pos;
1110 else {
1111 new_node->old_pos.x = new_node->pos.x;
1112 new_node->old_pos.y = parent->old_pos.y;
1113 }
1114
1115 if (TreeShowSteps)
1116 new_node->split = TRUE;
1117
1118 SetDrawingSize(width + (2 * MAT_SIZE), height + (2 * MAT_SIZE));
1119 BeginFrame();
1120 DrawTree(TheTree, Old);
1121 EndFrame();
1122 StatusMsg("Insert: add new node and contour", FALSE);
1123 Pause();
1124
1125 StatusMsg("Move tree to new configuration", FALSE);
1126 AnimateTree(TheTree);
1127
1128 if (TreeShowSteps) {
1129 if (parent)
1130 AnimateZip(parent);
1131 }
1132
1133 BeginFrame();
1134 SetContours(TreeShowContourOption);
1135 DrawTree(TheTree, New);
1136 EndFrame();
1137
1138 StatusMsg("Ready", TRUE);
1139 }
1140
1141 /* ----------------------------------------------------------------------------
1142 *
1143 * DeleteNode() handles the task of deleting a given node in the tree.
1144 *
1145 * ----------------------------------------------------------------------------
1146 */
1147
1148 void
1149 DeleteNode(node)
1150 Tree *node;
1151 {
1152 Tree *parent;
1153
1154 XRectangle *rectangles;
1155 XSegment *segments;
1156 int nrectangles, nsegments;
1157 Widget w = TreeDrawingArea;
1158 int width, height;
1159 int x_offset, y_offset;
1160
1161 StatusMsg("", TRUE);
1162
1163 if (TreeShowSteps)
1164 node->on_path = TRUE;
1165
1166 /* erase the contour before changing in the tree */
1167 if ((TreeShowContourOption != NoContours) ||
1168 TreeShowSteps) {
1169 BeginFrame();
1170 DrawTree(TheTree, New);
1171 EndFrame();
1172 }
1173
1174 sprintf(strbuf, "Node `%s' selected for deletion", node->label.text);
1175 StatusMsg(strbuf, FALSE);
1176 Pause();
1177
1178 parent = node->parent;
1179
1180 if (parent)
1181 Unzip(parent);
1182 else
1183 TheTree = NULL; /* delete root of tree */
1184
1185 /* fade out deleted subtree */
1186 StatusMsg("Delete subtree", FALSE);
1187 GetSubTreeRectangles(node, &rectangles, &nrectangles, TRUE);
1188 GetSubTreeSegments(node, &segments, &nsegments);
1189 DissolveTree(XtDisplay(w), XtWindow(w),
1190 rectangles, nrectangles,
1191 segments, nsegments, TRUE);
1192 free(rectangles);
1193 free(segments);
1194
1195 Delete(node);
1196
1197 BeginFrame();
1198 if (TheTree)
1199 DrawTree(TheTree, New);
1200 EndFrame();
1201 Pause();
1202
1203 if (parent)
1204 Zip(parent);
1205
1206 if (TheTree) {
1207 ComputeTreeSize(TheTree, &width, &height, &x_offset, &y_offset);
1208 PetrifyTree(TheTree, x_offset + MAT_SIZE, y_offset + MAT_SIZE);
1209 StatusMsg("Move tree to new configuration", FALSE);
1210 AnimateTree(TheTree);
1211 SetDrawingSize(width + (2 * MAT_SIZE), height + (2 * MAT_SIZE));
1212 Pause();
1213
1214 if (TreeShowSteps) {
1215 if (parent)
1216 AnimateZip(parent);
1217 }
1218
1219 BeginFrame();
1220 SetContours(TreeShowContourOption);
1221 DrawTree(TheTree, New);
1222 EndFrame();
1223
1224 }
1225
1226 StatusMsg("Ready", TRUE);
1227 }
1228
1229
1230 /* ----------------------------------------------------------------------------
1231 *
1232 * ResetLabels() is called when the TreeAlignNodes mode is changed.
1233 * When TreeParentDistance changes, the node width changes, so this
1234 * function forces each node's width to be recomputed.
1235 *
1236 * ----------------------------------------------------------------------------
1237 */
1238
1239 ResetLabels(tree)
1240 Tree *tree;
1241 {
1242 Tree *child;
1243
1244 SetNodeLabel(tree, tree->label.text);
1245 FOREACH_CHILD(child, tree)
1246 ResetLabels(child);
1247 }
1248
1249
1250 /* ----------------------------------------------------------------------------
1251 *
1252 * SetupTree() handles the task of setting up the specified tree in
1253 * the drawing area.
1254 *
1255 * ----------------------------------------------------------------------------
1256 */
1257
1258 void
1259 SetupTree(tree)
1260 Tree *tree;
1261 {
1262 int width, height;
1263 int x_offset, y_offset;
1264
1265 LayoutTree(tree);
1266 ComputeTreeSize(tree, &width, &height, &x_offset, &y_offset);
1267 PetrifyTree(tree, x_offset + MAT_SIZE, y_offset + MAT_SIZE);
1268 SetDrawingTree(tree);
1269 SetDrawingSize(width + (2 * MAT_SIZE), height + (2 * MAT_SIZE));
1270 BeginFrame();
1271 SetContours(TreeShowContourOption);
1272 DrawTree(tree, New);
1273 EndFrame();
1274 }
1275
1276
1277
1278
1279
1280