1 /*
2 * $XConsortium: Tree.c,v 1.45 94/04/17 20:13:20 kaleb Exp $
3 *
4
5 Copyright (c) 1990, 1994 X Consortium
6
7 Permission is hereby granted, free of charge, to any person obtaining a copy
8 of this software and associated documentation files (the "Software"), to deal
9 in the Software without restriction, including without limitation the rights
10 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
11 copies of the Software, and to permit persons to whom the Software is
12 furnished to do so, subject to the following conditions:
13
14 The above copyright notice and this permission notice shall be included in
15 all copies or substantial portions of the Software.
16
17 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
18 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
20 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
21 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
22 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
23
24 Except as contained in this notice, the name of the X Consortium shall not be
25 used in advertising or otherwise to promote the sale, use or other dealings
26 in this Software without prior written authorization from the X Consortium.
27
28 * Copyright 1989 Prentice Hall
29 *
30 * Permission to use, copy, modify, and distribute this software for any
31 * purpose and without fee is hereby granted, provided that the above
32 * copyright notice appear in all copies and that both the copyright notice
33 * and this permission notice appear in supporting documentation.
34 *
35 * Prentice Hall and the authors disclaim all warranties with regard
36 * to this software, including all implied warranties of merchantability and
37 * fitness. In no event shall Prentice Hall or the authors be liable
38 * for any special, indirect or cosequential damages or any damages whatsoever
39 * resulting from loss of use, data or profits, whether in an action of
40 * contract, negligence or other tortious action, arising out of or in
41 * connection with the use or performance of this software.
42 *
43 * Authors: Jim Fulton, MIT X Consortium,
44 * based on a version by Douglas Young, Prentice Hall
45 *
46 * This widget is based on the Tree widget described on pages 397-419 of
47 * Douglas Young's book "The X Window System, Programming and Applications
48 * with Xt OSF/Motif Edition." The layout code has been rewritten to use
49 * additional blank space to make the structure of the graph easier to see
50 * as well as to support vertical trees.
51 */
52
53 #include <X11/IntrinsicP.h>
54 #include <X11/StringDefs.h>
55 #include "XawInit.h"
56 #include "Cardinals.h"
57 #include "TreeP.h"
58
59 #define IsHorizontal(tw) ((tw)->tree.gravity == WestGravity || \
60 (tw)->tree.gravity == EastGravity)
61
62
63 /* widget class method */
64 static void ClassInitialize();
65 static void Initialize();
66 static void ConstraintInitialize();
67 static void ConstraintDestroy();
68 static Boolean ConstraintSetValues();
69 static void Destroy();
70 static Boolean SetValues();
71 static XtGeometryResult GeometryManager();
72 static void ChangeManaged();
73 static void Redisplay();
74 static XtGeometryResult QueryGeometry();
75
76 /* utility routines */
77 static void insert_node();
78 static void delete_node();
79 static void layout_tree();
80
81
82 /*
83 * resources of the tree itself
84 */
85 static XtResource resources[] = {
86 { XtNautoReconfigure, XtCAutoReconfigure, XtRBoolean, sizeof (Boolean),
87 XtOffsetOf(TreeRec, tree.auto_reconfigure), XtRImmediate,
88 (XtPointer) FALSE },
89 { XtNhSpace, XtCHSpace, XtRDimension, sizeof (Dimension),
90 XtOffsetOf(TreeRec, tree.hpad), XtRImmediate, (XtPointer) 0 },
91 { XtNvSpace, XtCVSpace, XtRDimension, sizeof (Dimension),
92 XtOffsetOf(TreeRec, tree.vpad), XtRImmediate, (XtPointer) 0 },
93 { XtNforeground, XtCForeground, XtRPixel, sizeof (Pixel),
94 XtOffsetOf(TreeRec, tree.foreground), XtRString,
95 XtDefaultForeground},
96 { XtNlineWidth, XtCLineWidth, XtRDimension, sizeof (Dimension),
97 XtOffsetOf(TreeRec, tree.line_width), XtRImmediate, (XtPointer) 0 },
98 { XtNgravity, XtCGravity, XtRGravity, sizeof (XtGravity),
99 XtOffsetOf(TreeRec, tree.gravity), XtRImmediate,
100 (XtPointer) WestGravity },
101 };
102
103
104 /*
105 * resources that are attached to all children of the tree
106 */
107 static XtResource treeConstraintResources[] = {
108 { XtNtreeParent, XtCTreeParent, XtRWidget, sizeof (Widget),
109 XtOffsetOf(TreeConstraintsRec, tree.parent), XtRImmediate, NULL },
110 { XtNtreeGC, XtCTreeGC, XtRGC, sizeof(GC),
111 XtOffsetOf(TreeConstraintsRec, tree.gc), XtRImmediate, NULL },
112 };
113
114
115 TreeClassRec treeClassRec = {
116 {
117 /* core_class fields */
118 (WidgetClass) &constraintClassRec, /* superclass */
119 "Tree", /* class_name */
120 sizeof(TreeRec), /* widget_size */
121 ClassInitialize, /* class_init */
122 NULL, /* class_part_init */
123 FALSE, /* class_inited */
124 Initialize, /* initialize */
125 NULL, /* initialize_hook */
126 XtInheritRealize, /* realize */
127 NULL, /* actions */
128 0, /* num_actions */
129 resources, /* resources */
130 XtNumber(resources), /* num_resources */
131 NULLQUARK, /* xrm_class */
132 TRUE, /* compress_motion */
133 TRUE, /* compress_exposure */
134 TRUE, /* compress_enterleave*/
135 TRUE, /* visible_interest */
136 Destroy, /* destroy */
137 NULL, /* resize */
138 Redisplay, /* expose */
139 SetValues, /* set_values */
140 NULL, /* set_values_hook */
141 XtInheritSetValuesAlmost, /* set_values_almost */
142 NULL, /* get_values_hook */
143 NULL, /* accept_focus */
144 XtVersion, /* version */
145 NULL, /* callback_private */
146 NULL, /* tm_table */
147 QueryGeometry, /* query_geometry */
148 NULL, /* display_accelerator*/
149 NULL, /* extension */
150 },
151 {
152 /* composite_class fields */
153 GeometryManager, /* geometry_manager */
154 ChangeManaged, /* change_managed */
155 XtInheritInsertChild, /* insert_child */
156 XtInheritDeleteChild, /* delete_child */
157 NULL, /* extension */
158 },
159 {
160 /* constraint_class fields */
161 treeConstraintResources, /* subresources */
162 XtNumber(treeConstraintResources), /* subresource_count */
163 sizeof(TreeConstraintsRec), /* constraint_size */
164 ConstraintInitialize, /* initialize */
165 ConstraintDestroy, /* destroy */
166 ConstraintSetValues, /* set_values */
167 NULL, /* extension */
168 },
169 {
170 /* Tree class fields */
171 0, /* ignore */
172 }
173 };
174
175 WidgetClass treeWidgetClass = (WidgetClass) &treeClassRec;
176
177
178 /*****************************************************************************
179 * *
180 * tree utility routines *
181 * *
182 *****************************************************************************/
183
initialize_dimensions(listp,sizep,n)184 static void initialize_dimensions (listp, sizep, n)
185 Dimension **listp;
186 int *sizep;
187 int n;
188 {
189 int i;
190 Dimension *l;
191
192 if (!*listp) {
193 *listp = (Dimension *) XtCalloc ((unsigned int) n,
194 (unsigned int) sizeof(Dimension));
195 *sizep = ((*listp) ? n : 0);
196 return;
197 }
198 if (n > *sizep) {
199 *listp = (Dimension *) XtRealloc((char *) *listp,
200 (unsigned int) (n*sizeof(Dimension)));
201 if (!*listp) {
202 *sizep = 0;
203 return;
204 }
205 for (i = *sizep, l = (*listp) + i; i < n; i++, l++) *l = 0;
206 *sizep = n;
207 }
208 return;
209 }
210
get_tree_gc(w)211 static GC get_tree_gc (w)
212 TreeWidget w;
213 {
214 XtGCMask valuemask = GCBackground | GCForeground;
215 XGCValues values;
216
217 values.background = w->core.background_pixel;
218 values.foreground = w->tree.foreground;
219 if (w->tree.line_width != 0) {
220 valuemask |= GCLineWidth;
221 values.line_width = w->tree.line_width;
222 }
223
224 return XtGetGC ((Widget) w, valuemask, &values);
225 }
226
insert_node(parent,node)227 static void insert_node (parent, node)
228 Widget parent, node;
229 {
230 TreeConstraints pc;
231 TreeConstraints nc = TREE_CONSTRAINT(node);
232 int nindex;
233
234 nc->tree.parent = parent;
235
236 if (parent == NULL) return;
237
238 /*
239 * If there isn't more room in the children array,
240 * allocate additional space.
241 */
242 pc = TREE_CONSTRAINT(parent);
243 nindex = pc->tree.n_children;
244
245 if (pc->tree.n_children == pc->tree.max_children) {
246 pc->tree.max_children += (pc->tree.max_children / 2) + 2;
247 pc->tree.children = (WidgetList) XtRealloc ((char *)pc->tree.children,
248 (unsigned int)
249 ((pc->tree.max_children) *
250 sizeof(Widget)));
251 }
252
253 /*
254 * Add the sub_node in the next available slot and
255 * increment the counter.
256 */
257 pc->tree.children[nindex] = node;
258 pc->tree.n_children++;
259 }
260
delete_node(parent,node)261 static void delete_node (parent, node)
262 Widget parent, node;
263 {
264 TreeConstraints pc;
265 int pos, i;
266
267 /*
268 * Make sure the parent exists.
269 */
270 if (!parent) return;
271
272 pc = TREE_CONSTRAINT(parent);
273
274 /*
275 * Find the sub_node on its parent's list.
276 */
277 for (pos = 0; pos < pc->tree.n_children; pos++)
278 if (pc->tree.children[pos] == node) break;
279
280 if (pos == pc->tree.n_children) return;
281
282 /*
283 * Decrement the number of children
284 */
285 pc->tree.n_children--;
286
287 /*
288 * Fill in the gap left by the sub_node.
289 * Zero the last slot for good luck.
290 */
291 for (i = pos; i < pc->tree.n_children; i++)
292 pc->tree.children[i] = pc->tree.children[i+1];
293
294 pc->tree.children[pc->tree.n_children]=0;
295 }
296
check_gravity(tw,grav)297 static void check_gravity (tw, grav)
298 TreeWidget tw;
299 XtGravity grav;
300 {
301 switch (tw->tree.gravity) {
302 case WestGravity: case NorthGravity: case EastGravity: case SouthGravity:
303 break;
304 default:
305 tw->tree.gravity = grav;
306 break;
307 }
308 }
309
310
311 /*****************************************************************************
312 * *
313 * tree class methods *
314 * *
315 *****************************************************************************/
316
ClassInitialize()317 static void ClassInitialize ()
318 {
319 XawInitializeWidgetSet();
320 XtAddConverter (XtRString, XtRGravity, XmuCvtStringToGravity,
321 (XtConvertArgList) NULL, (Cardinal) 0);
322 }
323
324
325 /*ARGSUSED*/
Initialize(grequest,gnew,args,num_args)326 static void Initialize (grequest, gnew, args, num_args)
327 Widget grequest, gnew;
328 ArgList args;
329 Cardinal *num_args;
330 {
331 TreeWidget request = (TreeWidget) grequest, new = (TreeWidget) gnew;
332 Arg arglist[2];
333
334 /*
335 * Make sure the widget's width and height are
336 * greater than zero.
337 */
338 if (request->core.width <= 0) new->core.width = 5;
339 if (request->core.height <= 0) new->core.height = 5;
340
341 /*
342 * Set the padding according to the orientation
343 */
344 if (request->tree.hpad == 0 && request->tree.vpad == 0) {
345 if (IsHorizontal (request)) {
346 new->tree.hpad = TREE_HORIZONTAL_DEFAULT_SPACING;
347 new->tree.vpad = TREE_VERTICAL_DEFAULT_SPACING;
348 } else {
349 new->tree.hpad = TREE_VERTICAL_DEFAULT_SPACING;
350 new->tree.vpad = TREE_HORIZONTAL_DEFAULT_SPACING;
351 }
352 }
353
354 /*
355 * Create a graphics context for the connecting lines.
356 */
357 new->tree.gc = get_tree_gc (new);
358
359 /*
360 * Create the hidden root widget.
361 */
362 new->tree.tree_root = (Widget) NULL;
363 XtSetArg(arglist[0], XtNwidth, 1);
364 XtSetArg(arglist[1], XtNheight, 1);
365 new->tree.tree_root = XtCreateWidget ("root", widgetClass, gnew,
366 arglist,TWO);
367
368 /*
369 * Allocate the array used to hold the widest values per depth
370 */
371 new->tree.largest = NULL;
372 new->tree.n_largest = 0;
373 initialize_dimensions (&new->tree.largest, &new->tree.n_largest,
374 TREE_INITIAL_DEPTH);
375
376 /*
377 * make sure that our gravity is one of the acceptable values
378 */
379 check_gravity (new, WestGravity);
380 }
381
382
383 /* ARGSUSED */
ConstraintInitialize(request,new,args,num_args)384 static void ConstraintInitialize (request, new, args, num_args)
385 Widget request, new;
386 ArgList args;
387 Cardinal *num_args;
388 {
389 TreeConstraints tc = TREE_CONSTRAINT(new);
390 TreeWidget tw = (TreeWidget) new->core.parent;
391
392 /*
393 * Initialize the widget to have no sub-nodes.
394 */
395 tc->tree.n_children = 0;
396 tc->tree.max_children = 0;
397 tc->tree.children = (Widget *) NULL;
398 tc->tree.x = tc->tree.y = 0;
399 tc->tree.bbsubwidth = 0;
400 tc->tree.bbsubheight = 0;
401
402
403 /*
404 * If this widget has a super-node, add it to that
405 * widget' sub-nodes list. Otherwise make it a sub-node of
406 * the tree_root widget.
407 */
408 if (tc->tree.parent)
409 insert_node (tc->tree.parent, new);
410 else if (tw->tree.tree_root)
411 insert_node (tw->tree.tree_root, new);
412 }
413
414
415 /* ARGSUSED */
SetValues(gcurrent,grequest,gnew,args,num_args)416 static Boolean SetValues (gcurrent, grequest, gnew, args, num_args)
417 Widget gcurrent, grequest, gnew;
418 ArgList args;
419 Cardinal *num_args;
420 {
421 TreeWidget current = (TreeWidget) gcurrent, new = (TreeWidget) gnew;
422 Boolean redraw = FALSE;
423
424 /*
425 * If the foreground color has changed, redo the GC's
426 * and indicate a redraw.
427 */
428 if (new->tree.foreground != current->tree.foreground ||
429 new->core.background_pixel != current->core.background_pixel ||
430 new->tree.line_width != current->tree.line_width) {
431 XtReleaseGC (gnew, new->tree.gc);
432 new->tree.gc = get_tree_gc (new);
433 redraw = TRUE;
434 }
435
436 /*
437 * If the minimum spacing has changed, recalculate the
438 * tree layout. layout_tree() does a redraw, so we don't
439 * need SetValues to do another one.
440 */
441 if (new->tree.gravity != current->tree.gravity) {
442 check_gravity (new, current->tree.gravity);
443 }
444
445 if (IsHorizontal(new) != IsHorizontal(current)) {
446 if (new->tree.vpad == current->tree.vpad &&
447 new->tree.hpad == current->tree.hpad) {
448 new->tree.vpad = current->tree.hpad;
449 new->tree.hpad = current->tree.vpad;
450 }
451 }
452
453 if (new->tree.vpad != current->tree.vpad ||
454 new->tree.hpad != current->tree.hpad ||
455 new->tree.gravity != current->tree.gravity) {
456 layout_tree (new, TRUE);
457 redraw = FALSE;
458 }
459 return redraw;
460 }
461
462
463 /* ARGSUSED */
ConstraintSetValues(current,request,new,args,num_args)464 static Boolean ConstraintSetValues (current, request, new, args, num_args)
465 Widget current, request, new;
466 ArgList args;
467 Cardinal *num_args;
468 {
469 TreeConstraints newc = TREE_CONSTRAINT(new);
470 TreeConstraints curc = TREE_CONSTRAINT(current);
471 TreeWidget tw = (TreeWidget) new->core.parent;
472
473 /*
474 * If the parent field has changed, remove the widget
475 * from the old widget's children list and add it to the
476 * new one.
477 */
478 if (curc->tree.parent != newc->tree.parent){
479 if (curc->tree.parent)
480 delete_node (curc->tree.parent, new);
481 if (newc->tree.parent)
482 insert_node(newc->tree.parent, new);
483
484 /*
485 * If the Tree widget has been realized,
486 * compute new layout.
487 */
488 if (XtIsRealized((Widget)tw))
489 layout_tree (tw, FALSE);
490 }
491 return False;
492 }
493
494
ConstraintDestroy(w)495 static void ConstraintDestroy (w)
496 Widget w;
497 {
498 TreeConstraints tc = TREE_CONSTRAINT(w);
499 TreeWidget tw = (TreeWidget) XtParent(w);
500 int i;
501
502 /*
503 * Remove the widget from its parent's sub-nodes list and
504 * make all this widget's sub-nodes sub-nodes of the parent.
505 */
506
507 if (tw->tree.tree_root == w) {
508 if (tc->tree.n_children > 0)
509 tw->tree.tree_root = tc->tree.children[0];
510 else
511 tw->tree.tree_root = NULL;
512 }
513
514 delete_node (tc->tree.parent, (Widget) w);
515 for (i = 0; i< tc->tree.n_children; i++)
516 insert_node (tc->tree.parent, tc->tree.children[i]);
517
518 layout_tree ((TreeWidget) (w->core.parent), FALSE);
519 }
520
521 /* ARGSUSED */
GeometryManager(w,request,reply)522 static XtGeometryResult GeometryManager (w, request, reply)
523 Widget w;
524 XtWidgetGeometry *request;
525 XtWidgetGeometry *reply;
526 {
527
528 TreeWidget tw = (TreeWidget) w->core.parent;
529
530 /*
531 * No position changes allowed!.
532 */
533 if ((request->request_mode & CWX && request->x!=w->core.x)
534 ||(request->request_mode & CWY && request->y!=w->core.y))
535 return (XtGeometryNo);
536
537 /*
538 * Allow all resize requests.
539 */
540
541 if (request->request_mode & CWWidth)
542 w->core.width = request->width;
543 if (request->request_mode & CWHeight)
544 w->core.height = request->height;
545 if (request->request_mode & CWBorderWidth)
546 w->core.border_width = request->border_width;
547
548 if (tw->tree.auto_reconfigure) layout_tree (tw, FALSE);
549 return (XtGeometryYes);
550 }
551
ChangeManaged(gw)552 static void ChangeManaged (gw)
553 Widget gw;
554 {
555 layout_tree ((TreeWidget) gw, FALSE);
556 }
557
558
Destroy(gw)559 static void Destroy (gw)
560 Widget gw;
561 {
562 TreeWidget w = (TreeWidget) gw;
563
564 XtReleaseGC (gw, w->tree.gc);
565 if (w->tree.largest) XtFree ((char *) w->tree.largest);
566 }
567
568
569 /* ARGSUSED */
Redisplay(gw,event,region)570 static void Redisplay (gw, event, region)
571 Widget gw;
572 XEvent *event;
573 Region region;
574 {
575 TreeWidget tw = (TreeWidget) gw;
576
577 /*
578 * If the Tree widget is visible, visit each managed child.
579 */
580 if (tw->core.visible) {
581 int i, j;
582 Display *dpy = XtDisplay (tw);
583 Window w = XtWindow (tw);
584
585 for (i = 0; i < tw->composite.num_children; i++) {
586 Widget child = tw->composite.children[i];
587 TreeConstraints tc = TREE_CONSTRAINT(child);
588
589 /*
590 * Don't draw lines from the fake tree_root.
591 */
592 if (child != tw->tree.tree_root && tc->tree.n_children) {
593 int srcx = child->core.x + child->core.border_width;
594 int srcy = child->core.y + child->core.border_width;
595
596 switch (tw->tree.gravity) {
597 case WestGravity:
598 srcx += child->core.width + child->core.border_width;
599 /* fall through */
600 case EastGravity:
601 srcy += child->core.height / 2;
602 break;
603
604 case NorthGravity:
605 srcy += child->core.height + child->core.border_width;
606 /* fall through */
607 case SouthGravity:
608 srcx += child->core.width / 2;
609 break;
610 }
611
612 for (j = 0; j < tc->tree.n_children; j++) {
613 Widget k = tc->tree.children[j];
614 GC gc = (tc->tree.gc ? tc->tree.gc : tw->tree.gc);
615
616 switch (tw->tree.gravity) {
617 case WestGravity:
618 /*
619 * right center to left center
620 */
621 XDrawLine (dpy, w, gc, srcx, srcy,
622 (int) k->core.x,
623 (k->core.y + ((int) k->core.border_width) +
624 ((int) k->core.height) / 2));
625 break;
626
627 case NorthGravity:
628 /*
629 * bottom center to top center
630 */
631 XDrawLine (dpy, w, gc, srcx, srcy,
632 (k->core.x + ((int) k->core.border_width) +
633 ((int) k->core.width) / 2),
634 (int) k->core.y);
635 break;
636
637 case EastGravity:
638 /*
639 * left center to right center
640 */
641 XDrawLine (dpy, w, gc, srcx, srcy,
642 (k->core.x +
643 (((int) k->core.border_width) << 1) +
644 (int) k->core.width),
645 (k->core.y + ((int) k->core.border_width) +
646 ((int) k->core.height) / 2));
647 break;
648
649 case SouthGravity:
650 /*
651 * top center to bottom center
652 */
653 XDrawLine (dpy, w, gc, srcx, srcy,
654 (k->core.x + ((int) k->core.border_width) +
655 ((int) k->core.width) / 2),
656 (k->core.y +
657 (((int) k->core.border_width) << 1) +
658 (int) k->core.height));
659 break;
660 }
661 }
662 }
663 }
664 }
665 }
666
QueryGeometry(w,intended,preferred)667 static XtGeometryResult QueryGeometry (w, intended, preferred)
668 Widget w;
669 XtWidgetGeometry *intended, *preferred;
670 {
671 TreeWidget tw = (TreeWidget) w;
672
673 preferred->request_mode = (CWWidth | CWHeight);
674 preferred->width = tw->tree.maxwidth;
675 preferred->height = tw->tree.maxheight;
676
677 if (((intended->request_mode & (CWWidth | CWHeight)) ==
678 (CWWidth | CWHeight)) &&
679 intended->width == preferred->width &&
680 intended->height == preferred->height)
681 return XtGeometryYes;
682 else if (preferred->width == w->core.width &&
683 preferred->height == w->core.height)
684 return XtGeometryNo;
685 else
686 return XtGeometryAlmost;
687 }
688
689
690 /*****************************************************************************
691 * *
692 * tree layout algorithm *
693 * *
694 * Each node in the tree is "shrink-wrapped" with a minimal bounding *
695 * rectangle, laid next to its siblings (with a small about of padding in *
696 * between) and then wrapped with their parent. Parents are centered about *
697 * their children (or vice versa if the parent is larger than the children). *
698 * *
699 *****************************************************************************/
700
compute_bounding_box_subtree(tree,w,depth)701 static void compute_bounding_box_subtree (tree, w, depth)
702 TreeWidget tree;
703 Widget w;
704 int depth;
705 {
706 TreeConstraints tc = TREE_CONSTRAINT(w); /* info attached to all kids */
707 int i;
708 Bool horiz = IsHorizontal (tree);
709 Dimension newwidth, newheight;
710 Dimension bw2 = w->core.border_width * 2;
711
712 /*
713 * Set the max-size per level.
714 */
715 if (depth >= tree->tree.n_largest) {
716 initialize_dimensions (&tree->tree.largest,
717 &tree->tree.n_largest, depth + 1);
718 }
719 newwidth = ((horiz ? w->core.width : w->core.height) + bw2);
720 if (tree->tree.largest[depth] < newwidth)
721 tree->tree.largest[depth] = newwidth;
722
723
724 /*
725 * initialize
726 */
727 tc->tree.bbwidth = w->core.width + bw2;
728 tc->tree.bbheight = w->core.height + bw2;
729
730 if (tc->tree.n_children == 0) return;
731
732 /*
733 * Figure the size of the opposite dimension (vertical if tree is
734 * horizontal, else vice versa). The other dimension will be set
735 * in the second pass once we know the maximum dimensions.
736 */
737 newwidth = 0;
738 newheight = 0;
739 for (i = 0; i < tc->tree.n_children; i++) {
740 Widget child = tc->tree.children[i];
741 TreeConstraints cc = TREE_CONSTRAINT(child);
742
743 compute_bounding_box_subtree (tree, child, depth + 1);
744
745 if (horiz) {
746 if (newwidth < cc->tree.bbwidth) newwidth = cc->tree.bbwidth;
747 newheight += tree->tree.vpad + cc->tree.bbheight;
748 } else {
749 if (newheight < cc->tree.bbheight) newheight = cc->tree.bbheight;
750 newwidth += tree->tree.hpad + cc->tree.bbwidth;
751 }
752 }
753
754
755 tc->tree.bbsubwidth = newwidth;
756 tc->tree.bbsubheight = newheight;
757
758 /*
759 * Now fit parent onto side (or top) of bounding box and correct for
760 * extra padding. Be careful of unsigned arithmetic.
761 */
762 if (horiz) {
763 tc->tree.bbwidth += tree->tree.hpad + newwidth;
764 newheight -= tree->tree.vpad;
765 if (newheight > tc->tree.bbheight) tc->tree.bbheight = newheight;
766 } else {
767 tc->tree.bbheight += tree->tree.vpad + newheight;
768 newwidth -= tree->tree.hpad;
769 if (newwidth > tc->tree.bbwidth) tc->tree.bbwidth = newwidth;
770 }
771 }
772
773
set_positions(tw,w,level)774 static void set_positions (tw, w, level)
775 TreeWidget tw;
776 Widget w;
777 int level;
778 {
779 int i;
780
781 if (w) {
782 TreeConstraints tc = TREE_CONSTRAINT(w);
783
784 if (level > 0) {
785 /*
786 * mirror if necessary
787 */
788 switch (tw->tree.gravity) {
789 case EastGravity:
790 tc->tree.x = (((Position) tw->tree.maxwidth) -
791 ((Position) w->core.width) - tc->tree.x);
792 break;
793
794 case SouthGravity:
795 tc->tree.y = (((Position) tw->tree.maxheight) -
796 ((Position) w->core.height) - tc->tree.y);
797 break;
798 }
799
800 /*
801 * Move the widget into position.
802 */
803 XtMoveWidget (w, tc->tree.x, tc->tree.y);
804 }
805
806 /*
807 * Set the positions of all children.
808 */
809 for (i = 0; i < tc->tree.n_children; i++)
810 set_positions (tw, tc->tree.children[i], level + 1);
811 }
812 }
813
814
arrange_subtree(tree,w,depth,x,y)815 static void arrange_subtree (tree, w, depth, x, y)
816 TreeWidget tree;
817 Widget w;
818 int depth;
819 Position x, y;
820 {
821 TreeConstraints tc = TREE_CONSTRAINT(w); /* info attached to all kids */
822 TreeConstraints firstcc, lastcc;
823 int i;
824 int newx, newy;
825 Bool horiz = IsHorizontal (tree);
826 Widget child = NULL;
827 Dimension tmp;
828 Dimension bw2 = w->core.border_width * 2;
829 Bool relayout = True;
830
831
832 /*
833 * If no children, then just lay out where requested.
834 */
835 tc->tree.x = x;
836 tc->tree.y = y;
837
838 if (horiz) {
839 int myh = (w->core.height + bw2);
840
841 if (myh > (int)tc->tree.bbsubheight) {
842 y += (myh - (int)tc->tree.bbsubheight) / 2;
843 relayout = False;
844 }
845 } else {
846 int myw = (w->core.width + bw2);
847
848 if (myw > (int)tc->tree.bbsubwidth) {
849 x += (myw - (int)tc->tree.bbsubwidth) / 2;
850 relayout = False;
851 }
852 }
853
854 if ((tmp = ((Dimension) x) + tc->tree.bbwidth) > tree->tree.maxwidth)
855 tree->tree.maxwidth = tmp;
856 if ((tmp = ((Dimension) y) + tc->tree.bbheight) > tree->tree.maxheight)
857 tree->tree.maxheight = tmp;
858
859 if (tc->tree.n_children == 0) return;
860
861
862 /*
863 * Have children, so walk down tree laying out children, then laying
864 * out parents.
865 */
866 if (horiz) {
867 newx = x + tree->tree.largest[depth];
868 if (depth > 0) newx += tree->tree.hpad;
869 newy = y;
870 } else {
871 newx = x;
872 newy = y + tree->tree.largest[depth];
873 if (depth > 0) newy += tree->tree.vpad;
874 }
875
876 for (i = 0; i < tc->tree.n_children; i++) {
877 TreeConstraints cc;
878
879 child = tc->tree.children[i]; /* last value is used outside loop */
880 cc = TREE_CONSTRAINT(child);
881
882 arrange_subtree (tree, child, depth + 1, newx, newy);
883 if (horiz) {
884 newy += tree->tree.vpad + cc->tree.bbheight;
885 } else {
886 newx += tree->tree.hpad + cc->tree.bbwidth;
887 }
888 }
889
890 /*
891 * now layout parent between first and last children
892 */
893 if (relayout) {
894 Position adjusted;
895 firstcc = TREE_CONSTRAINT (tc->tree.children[0]);
896 lastcc = TREE_CONSTRAINT (child);
897
898 /* Adjustments are disallowed if they result in a position above
899 * or to the left of the originally requested position, because
900 * this could collide with the position of the previous sibling.
901 */
902 if (horiz) {
903 tc->tree.x = x;
904 adjusted = firstcc->tree.y +
905 ((lastcc->tree.y + (Position) child->core.height +
906 (Position) child->core.border_width * 2 -
907 firstcc->tree.y - (Position) w->core.height -
908 (Position) w->core.border_width * 2 + 1) / 2);
909 if (adjusted > tc->tree.y) tc->tree.y = adjusted;
910 } else {
911 adjusted = firstcc->tree.x +
912 ((lastcc->tree.x + (Position) child->core.width +
913 (Position) child->core.border_width * 2 -
914 firstcc->tree.x - (Position) w->core.width -
915 (Position) w->core.border_width * 2 + 1) / 2);
916 if (adjusted > tc->tree.x) tc->tree.x = adjusted;
917 tc->tree.y = y;
918 }
919 }
920 }
921
set_tree_size(tw,insetvalues,width,height)922 static void set_tree_size (tw, insetvalues, width, height)
923 TreeWidget tw;
924 Boolean insetvalues;
925 Dimension width, height;
926 {
927 if (insetvalues) {
928 tw->core.width = width;
929 tw->core.height = height;
930 } else {
931 Dimension replyWidth = 0, replyHeight = 0;
932 XtGeometryResult result = XtMakeResizeRequest ((Widget) tw,
933 width, height,
934 &replyWidth,
935 &replyHeight);
936 /*
937 * Accept any compromise.
938 */
939 if (result == XtGeometryAlmost)
940 XtMakeResizeRequest ((Widget) tw, replyWidth, replyHeight,
941 (Dimension *) NULL, (Dimension *) NULL);
942 }
943 return;
944 }
945
layout_tree(tw,insetvalues)946 static void layout_tree (tw, insetvalues)
947 TreeWidget tw;
948 Boolean insetvalues;
949 {
950 int i;
951 Dimension *dp;
952
953 /*
954 * Do a depth-first search computing the width and height of the bounding
955 * box for the tree at that position (and below). Then, walk again using
956 * this information to layout the children at each level.
957 */
958
959 if (tw->tree.tree_root == NULL)
960 return;
961
962 tw->tree.maxwidth = tw->tree.maxheight = 0;
963 for (i = 0, dp = tw->tree.largest; i < tw->tree.n_largest; i++, dp++)
964 *dp = 0;
965 initialize_dimensions (&tw->tree.largest, &tw->tree.n_largest,
966 tw->tree.n_largest);
967 compute_bounding_box_subtree (tw, tw->tree.tree_root, 0);
968
969 /*
970 * Second pass to do final layout. Each child's bounding box is stacked
971 * on top of (if horizontal, else next to) on top of its siblings. The
972 * parent is centered between the first and last children.
973 */
974 arrange_subtree (tw, tw->tree.tree_root, 0, 0, 0);
975
976 /*
977 * Move each widget into place.
978 */
979 set_tree_size (tw, insetvalues, tw->tree.maxwidth, tw->tree.maxheight);
980 set_positions (tw, tw->tree.tree_root, 0);
981
982 /*
983 * And redisplay.
984 */
985 if (XtIsRealized ((Widget) tw)) {
986 XClearArea (XtDisplay(tw), XtWindow((Widget)tw), 0, 0, 0, 0, True);
987 }
988 }
989
990
991
992 /*****************************************************************************
993 * *
994 * Public Routines *
995 * *
996 *****************************************************************************/
997
998 void
999 #if NeedFunctionPrototypes
XawTreeForceLayout(Widget tree)1000 XawTreeForceLayout (Widget tree)
1001 #else
1002 XawTreeForceLayout (tree)
1003 Widget tree;
1004 #endif
1005 {
1006 layout_tree ((TreeWidget) tree, FALSE);
1007 }
1008
1009