Debian Codegraph @

src/Tree.c

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