Tree.c revision 7a84e134 
1/*
2 * $Xorg: Tree.c,v 1.4 2001/02/09 02:03:47 xorgcvs Exp $
3 *
4
5Copyright 1990, 1994, 1998  The Open Group
6
7Permission to use, copy, modify, distribute, and sell this software and its
8documentation for any purpose is hereby granted without fee, provided that
9the above copyright notice appear in all copies and that both that
10copyright notice and this permission notice appear in supporting
11documentation.
12
13The above copyright notice and this permission notice shall be included in
14all copies or substantial portions of the Software.
15
16THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
19OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
20AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
21CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
22
23Except as contained in this notice, the name of The Open Group shall not be
24used in advertising or otherwise to promote the sale, use or other dealings
25in this Software without prior written authorization from The Open Group.
26
27 * Copyright 1989 Prentice Hall
28 *
29 * Permission to use, copy, modify, and distribute this software for any
30 * purpose and without fee is hereby granted, provided that the above
31 * copyright notice appear in all copies and that both the copyright notice
32 * and this permission notice appear in supporting documentation.
33 *
34 * Prentice Hall and the authors disclaim all warranties with regard
35 * to this software, including all implied warranties of merchantability and
36 * fitness.  In no event shall Prentice Hall or the authors be liable
37 * for any special, indirect or cosequential damages or any damages whatsoever
38 * resulting from loss of use, data or profits, whether in an action of
39 * contract, negligence or other tortious action, arising out of or in
40 * connection with the use or performance of this software.
41 *
42 * Authors:  Jim Fulton, MIT X Consortium,
43 *           based on a version by Douglas Young, Prentice Hall
44 *
45 * This widget is based on the Tree widget described on pages 397-419 of
46 * Douglas Young's book "The X Window System, Programming and Applications
47 * with Xt OSF/Motif Edition."  The layout code has been rewritten to use
48 * additional blank space to make the structure of the graph easier to see
49 * as well as to support vertical trees.
50 */
51/* $XFree86: xc/lib/Xaw/Tree.c,v 1.9 2001/01/17 19:42:35 dawes Exp $ */
52
53#ifdef HAVE_CONFIG_H
54#include <config.h>
55#endif
56#include <X11/IntrinsicP.h>
57#include <X11/StringDefs.h>
58#include <X11/Xaw/XawInit.h>
59#include <X11/Xaw/Cardinals.h>
60#include <X11/Xaw/TreeP.h>
61#include "Private.h"
62
63#define IsHorizontal(tw) ((tw)->tree.gravity == WestGravity || \
64			  (tw)->tree.gravity == EastGravity)
65
66/*
67 * Class Methods
68 */
69static void XawTreeChangeManaged(Widget);
70static void XawTreeClassInitialize(void);
71static void XawTreeConstraintDestroy(Widget);
72static void XawTreeConstraintInitialize(Widget, Widget, ArgList, Cardinal*);
73static Boolean XawTreeConstraintSetValues(Widget, Widget, Widget,
74					  ArgList, Cardinal*);
75static void XawTreeDestroy(Widget);
76static XtGeometryResult XawTreeGeometryManager(Widget, XtWidgetGeometry*,
77					       XtWidgetGeometry*);
78static void XawTreeInitialize(Widget, Widget, ArgList, Cardinal*);
79static XtGeometryResult XawTreeQueryGeometry(Widget, XtWidgetGeometry*,
80					     XtWidgetGeometry*);
81static void XawTreeRedisplay(Widget, XEvent*, Region);
82static Boolean XawTreeSetValues(Widget, Widget, Widget, ArgList, Cardinal*);
83
84/*
85 * Prototypes
86 */
87static void arrange_subtree(TreeWidget, Widget, int, int, int);
88static void check_gravity(TreeWidget, XtGravity);
89static void compute_bounding_box_subtree(TreeWidget, Widget, int);
90static void delete_node(Widget, Widget);
91static GC get_tree_gc(TreeWidget);
92static void initialize_dimensions(Dimension**, int*, int);
93static void insert_node(Widget, Widget);
94static void layout_tree(TreeWidget, Bool);
95static void set_positions(TreeWidget, Widget, int);
96static void set_tree_size(TreeWidget, Bool, unsigned int, unsigned int);
97
98/*
99 * Initialization
100 */
101
102/*
103 * resources of the tree itself
104 */
105static XtResource resources[] = {
106    { XtNautoReconfigure, XtCAutoReconfigure, XtRBoolean, sizeof (Boolean),
107	XtOffsetOf(TreeRec, tree.auto_reconfigure), XtRImmediate,
108	(XtPointer) FALSE },
109    { XtNhSpace, XtCHSpace, XtRDimension, sizeof (Dimension),
110	XtOffsetOf(TreeRec, tree.hpad), XtRImmediate, (XtPointer) 0 },
111    { XtNvSpace, XtCVSpace, XtRDimension, sizeof (Dimension),
112	XtOffsetOf(TreeRec, tree.vpad), XtRImmediate, (XtPointer) 0 },
113    { XtNforeground, XtCForeground, XtRPixel, sizeof (Pixel),
114	XtOffsetOf(TreeRec, tree.foreground), XtRString,
115	XtDefaultForeground},
116    { XtNlineWidth, XtCLineWidth, XtRDimension, sizeof (Dimension),
117	XtOffsetOf(TreeRec, tree.line_width), XtRImmediate, (XtPointer) 0 },
118    { XtNgravity, XtCGravity, XtRGravity, sizeof (XtGravity),
119	XtOffsetOf(TreeRec, tree.gravity), XtRImmediate,
120	(XtPointer) WestGravity },
121#ifndef OLDXAW
122    { XawNdisplayList, XawCDisplayList, XawRDisplayList, sizeof(XawDisplayList*),
123	XtOffsetOf(TreeRec, tree.display_list), XtRImmediate,
124	NULL },
125#endif
126};
127
128
129/*
130 * resources that are attached to all children of the tree
131 */
132static XtResource treeConstraintResources[] = {
133    { XtNtreeParent, XtCTreeParent, XtRWidget, sizeof (Widget),
134	XtOffsetOf(TreeConstraintsRec, tree.parent), XtRImmediate, NULL },
135    { XtNtreeGC, XtCTreeGC, XtRGC, sizeof(GC),
136	XtOffsetOf(TreeConstraintsRec, tree.gc), XtRImmediate, NULL },
137};
138
139
140TreeClassRec treeClassRec = {
141  {
142					/* core_class fields  */
143    (WidgetClass) &constraintClassRec,	/* superclass         */
144    "Tree",				/* class_name         */
145    sizeof(TreeRec),			/* widget_size        */
146    XawTreeClassInitialize,		/* class_init         */
147    NULL,				/* class_part_init    */
148    FALSE,				/* class_inited       */
149    XawTreeInitialize,			/* initialize         */
150    NULL,				/* initialize_hook    */
151    XtInheritRealize,			/* realize            */
152    NULL,				/* actions            */
153    0,					/* num_actions        */
154    resources,				/* resources          */
155    XtNumber(resources),		/* num_resources      */
156    NULLQUARK,				/* xrm_class          */
157    TRUE,				/* compress_motion    */
158    TRUE,				/* compress_exposure  */
159    TRUE,				/* compress_enterleave*/
160    TRUE,				/* visible_interest   */
161    XawTreeDestroy,			/* destroy            */
162    NULL,				/* resize             */
163    XawTreeRedisplay,			/* expose             */
164    XawTreeSetValues,			/* set_values         */
165    NULL,				/* set_values_hook    */
166    XtInheritSetValuesAlmost,		/* set_values_almost  */
167    NULL,				/* get_values_hook    */
168    NULL,				/* accept_focus       */
169    XtVersion,				/* version            */
170    NULL,				/* callback_private   */
171    NULL,				/* tm_table           */
172    XawTreeQueryGeometry,		/* query_geometry     */
173    NULL,				/* display_accelerator*/
174    NULL,				/* extension          */
175  },
176  {
177					/* composite_class fields */
178    XawTreeGeometryManager,		/* geometry_manager    */
179    XawTreeChangeManaged,		/* change_managed      */
180    XtInheritInsertChild,		/* insert_child        */
181    XtInheritDeleteChild,		/* delete_child        */
182    NULL,				/* extension           */
183  },
184  {
185					/* constraint_class fields */
186   treeConstraintResources,		/* subresources        */
187   XtNumber(treeConstraintResources),	/* subresource_count   */
188   sizeof(TreeConstraintsRec),		/* constraint_size     */
189   XawTreeConstraintInitialize,		/* initialize          */
190   XawTreeConstraintDestroy,		/* destroy             */
191   XawTreeConstraintSetValues,		/* set_values          */
192   NULL,				/* extension           */
193   },
194  {
195					/* Tree class fields */
196    0,					/* ignore              */
197  }
198};
199
200WidgetClass treeWidgetClass = (WidgetClass) &treeClassRec;
201
202
203/*****************************************************************************
204 *                                                                           *
205 *			     tree utility routines                           *
206 *                                                                           *
207 *****************************************************************************/
208
209static void
210initialize_dimensions(Dimension **listp, int *sizep, int n)
211{
212    int i;
213    Dimension *l;
214
215    if (!*listp) {
216	*listp = (Dimension *) XtCalloc ((unsigned int) n,
217					 (unsigned int) sizeof(Dimension));
218	*sizep = ((*listp) ? n : 0);
219	return;
220    }
221    if (n > *sizep) {
222	*listp = (Dimension *) XtRealloc((char *) *listp,
223					 (unsigned int) (n*sizeof(Dimension)));
224	if (!*listp) {
225	    *sizep = 0;
226	    return;
227	}
228	for (i = *sizep, l = (*listp) + i; i < n; i++, l++) *l = 0;
229	*sizep = n;
230    }
231    return;
232}
233
234static GC
235get_tree_gc(TreeWidget w)
236{
237    XtGCMask valuemask = GCBackground | GCForeground;
238    XGCValues values;
239
240    values.background = w->core.background_pixel;
241    values.foreground = w->tree.foreground;
242    if (w->tree.line_width != 0) {
243	valuemask |= GCLineWidth;
244	values.line_width = w->tree.line_width;
245    }
246
247    return XtGetGC ((Widget) w, valuemask, &values);
248}
249
250static void
251insert_node(Widget parent, Widget node)
252{
253    TreeConstraints pc;
254    TreeConstraints nc = TREE_CONSTRAINT(node);
255    int nindex;
256
257    nc->tree.parent = parent;
258
259    if (parent == NULL) return;
260
261    /*
262     * If there isn't more room in the children array,
263     * allocate additional space.
264     */
265    pc = TREE_CONSTRAINT(parent);
266    nindex = pc->tree.n_children;
267
268    if (pc->tree.n_children == pc->tree.max_children) {
269	pc->tree.max_children += (pc->tree.max_children / 2) + 2;
270	pc->tree.children = (WidgetList) XtRealloc ((char *)pc->tree.children,
271						    (unsigned int)
272						    ((pc->tree.max_children) *
273						    sizeof(Widget)));
274    }
275
276    /*
277     * Add the sub_node in the next available slot and
278     * increment the counter.
279     */
280    pc->tree.children[nindex] = node;
281    pc->tree.n_children++;
282}
283
284static void
285delete_node(Widget parent, Widget node)
286{
287    TreeConstraints pc;
288    int pos, 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]=0;
318}
319
320static void
321check_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
339static void
340XawTreeClassInitialize(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*/
350static void
351XawTreeInitialize(Widget grequest, Widget gnew,
352		  ArgList args, Cardinal *num_args)
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 */
407static void
408XawTreeConstraintInitialize(Widget request, Widget cnew,
409			    ArgList args, Cardinal *num_args)
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 */
438static Boolean
439XawTreeSetValues(Widget gcurrent, Widget grequest, Widget gnew,
440		 ArgList args, Cardinal *num_args)
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 */
485static Boolean
486XawTreeConstraintSetValues(Widget current, Widget request, Widget cnew,
487			   ArgList args, Cardinal *num_args)
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
515static void
516XawTreeConstraintDestroy(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 */
542static XtGeometryResult
543XawTreeGeometryManager(Widget w, XtWidgetGeometry *request,
544		       XtWidgetGeometry *reply)
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
571static void
572XawTreeChangeManaged(Widget gw)
573{
574    layout_tree ((TreeWidget) gw, FALSE);
575}
576
577
578static void
579XawTreeDestroy(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 */
589static void
590XawTreeRedisplay(Widget gw, XEvent *event, Region region)
591{
592    TreeWidget tw = (TreeWidget) gw;
593
594#ifndef OLDXAW
595    if (tw->tree.display_list)
596	XawRunDisplayList(gw, tw->tree.display_list, event, region);
597#endif
598
599    /*
600     * If the Tree widget is visible, visit each managed child.
601     */
602    if (tw->core.visible) {
603	Cardinal i;
604	int j;
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
690static XtGeometryResult
691XawTreeQueryGeometry(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
724static void
725compute_bounding_box_subtree(TreeWidget tree, Widget w, int depth)
726{
727    TreeConstraints tc = TREE_CONSTRAINT(w);  /* info attached to all kids */
728    int i;
729    Bool horiz = IsHorizontal (tree);
730    Dimension newwidth, newheight;
731    Dimension bw2 = w->core.border_width * 2;
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 = ((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 = w->core.width + bw2;
749    tc->tree.bbheight = 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 += tree->tree.vpad + cc->tree.bbheight;
769	} else {
770	    if (newheight < cc->tree.bbheight) newheight = cc->tree.bbheight;
771	    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 += tree->tree.hpad + newwidth;
785	newheight -= tree->tree.vpad;
786	if (newheight > tc->tree.bbheight) tc->tree.bbheight = newheight;
787    } else {
788	tc->tree.bbheight += tree->tree.vpad + newheight;
789	newwidth -= tree->tree.hpad;
790	if (newwidth > tc->tree.bbwidth) tc->tree.bbwidth = newwidth;
791    }
792}
793
794
795static void
796set_positions(TreeWidget tw, Widget w, int level)
797{
798    int i;
799
800    if (w) {
801	TreeConstraints tc = TREE_CONSTRAINT(w);
802
803	if (level > 0) {
804	    /*
805	     * mirror if necessary
806	     */
807	    switch (tw->tree.gravity) {
808	      case EastGravity:
809		tc->tree.x = (((Position) tw->tree.maxwidth) -
810			      ((Position) w->core.width) - tc->tree.x);
811		break;
812
813	      case SouthGravity:
814		tc->tree.y = (((Position) tw->tree.maxheight) -
815			      ((Position) w->core.height) - tc->tree.y);
816		break;
817	    }
818
819	    /*
820	     * Move the widget into position.
821	     */
822	    XtMoveWidget (w, tc->tree.x, tc->tree.y);
823	}
824
825	/*
826	 * Set the positions of all children.
827	 */
828	for (i = 0; i < tc->tree.n_children; i++)
829	  set_positions (tw, tc->tree.children[i], level + 1);
830    }
831}
832
833
834static void
835arrange_subtree(TreeWidget tree, Widget w, int depth, int x, int y)
836{
837    TreeConstraints tc = TREE_CONSTRAINT(w);  /* info attached to all kids */
838    TreeConstraints firstcc, lastcc;
839    int i;
840    int newx, newy;
841    Bool horiz = IsHorizontal (tree);
842    Widget child = NULL;
843    Dimension tmp;
844    Dimension bw2 = w->core.border_width * 2;
845    Bool relayout = True;
846
847
848    /*
849     * If no children, then just lay out where requested.
850     */
851    tc->tree.x = x;
852    tc->tree.y = y;
853
854    if (horiz) {
855	int myh = (w->core.height + bw2);
856
857	if (myh > (int)tc->tree.bbsubheight) {
858	    y += (myh - (int)tc->tree.bbsubheight) / 2;
859	    relayout = False;
860	}
861    } else {
862	int myw = (w->core.width + bw2);
863
864	if (myw > (int)tc->tree.bbsubwidth) {
865	    x += (myw - (int)tc->tree.bbsubwidth) / 2;
866	    relayout = False;
867	}
868    }
869
870    if ((tmp = ((Dimension) x) + tc->tree.bbwidth) > tree->tree.maxwidth)
871      tree->tree.maxwidth = tmp;
872    if ((tmp = ((Dimension) y) + tc->tree.bbheight) > tree->tree.maxheight)
873      tree->tree.maxheight = tmp;
874
875    if (tc->tree.n_children == 0) return;
876
877
878    /*
879     * Have children, so walk down tree laying out children, then laying
880     * out parents.
881     */
882    if (horiz) {
883	newx = x + tree->tree.largest[depth];
884	if (depth > 0) newx += tree->tree.hpad;
885	newy = y;
886    } else {
887	newx = x;
888	newy = y + tree->tree.largest[depth];
889	if (depth > 0) newy += tree->tree.vpad;
890    }
891
892    for (i = 0; i < tc->tree.n_children; i++) {
893	TreeConstraints cc;
894
895	child = tc->tree.children[i];	/* last value is used outside loop */
896	cc = TREE_CONSTRAINT(child);
897
898	arrange_subtree (tree, child, depth + 1, newx, newy);
899	if (horiz) {
900	    newy += tree->tree.vpad + cc->tree.bbheight;
901	} else {
902	    newx += tree->tree.hpad + cc->tree.bbwidth;
903	}
904    }
905
906    /*
907     * now layout parent between first and last children
908     */
909    if (relayout) {
910	Position adjusted;
911	firstcc = TREE_CONSTRAINT (tc->tree.children[0]);
912	lastcc = TREE_CONSTRAINT (child);
913
914	/* Adjustments are disallowed if they result in a position above
915         * or to the left of the originally requested position, because
916	 * this could collide with the position of the previous sibling.
917	 */
918	if (horiz) {
919	    tc->tree.x = x;
920	    adjusted = firstcc->tree.y +
921	      ((lastcc->tree.y + (Position) child->core.height +
922		(Position) child->core.border_width * 2 -
923		firstcc->tree.y - (Position) w->core.height -
924		(Position) w->core.border_width * 2 + 1) / 2);
925	    if (adjusted > tc->tree.y) tc->tree.y = adjusted;
926	} else {
927	    adjusted = firstcc->tree.x +
928	      ((lastcc->tree.x + (Position) child->core.width +
929		(Position) child->core.border_width * 2 -
930		firstcc->tree.x - (Position) w->core.width -
931		(Position) w->core.border_width * 2 + 1) / 2);
932	    if (adjusted > tc->tree.x) tc->tree.x = adjusted;
933	    tc->tree.y = y;
934	}
935    }
936}
937
938static void
939set_tree_size(TreeWidget tw, Bool insetvalues,
940	      unsigned int width, unsigned int height)
941{
942    if (insetvalues) {
943	tw->core.width = width;
944	tw->core.height = height;
945    } else {
946	Dimension replyWidth = 0, replyHeight = 0;
947	XtGeometryResult result = XtMakeResizeRequest ((Widget) tw,
948						       width, height,
949						       &replyWidth,
950						       &replyHeight);
951	/*
952	 * Accept any compromise.
953	 */
954	if (result == XtGeometryAlmost)
955	  XtMakeResizeRequest ((Widget) tw, replyWidth, replyHeight,
956			       (Dimension *) NULL, (Dimension *) NULL);
957    }
958    return;
959}
960
961static void
962layout_tree(TreeWidget tw, Bool insetvalues)
963{
964    int i;
965    Dimension *dp;
966
967    /*
968     * Do a depth-first search computing the width and height of the bounding
969     * box for the tree at that position (and below).  Then, walk again using
970     * this information to layout the children at each level.
971     */
972
973    if (tw->tree.tree_root == NULL)
974	return;
975
976    tw->tree.maxwidth = tw->tree.maxheight = 0;
977    for (i = 0, dp = tw->tree.largest; i < tw->tree.n_largest; i++, dp++)
978      *dp = 0;
979    initialize_dimensions (&tw->tree.largest, &tw->tree.n_largest,
980			   tw->tree.n_largest);
981    compute_bounding_box_subtree (tw, tw->tree.tree_root, 0);
982
983   /*
984    * Second pass to do final layout.  Each child's bounding box is stacked
985    * on top of (if horizontal, else next to) on top of its siblings.  The
986    * parent is centered between the first and last children.
987    */
988    arrange_subtree (tw, tw->tree.tree_root, 0, 0, 0);
989
990    /*
991     * Move each widget into place.
992     */
993    set_tree_size (tw, insetvalues, tw->tree.maxwidth, tw->tree.maxheight);
994    set_positions (tw, tw->tree.tree_root, 0);
995
996    /*
997     * And redisplay.
998     */
999    if (XtIsRealized ((Widget) tw)) {
1000	XClearArea (XtDisplay(tw), XtWindow((Widget)tw), 0, 0, 0, 0, True);
1001    }
1002}
1003
1004
1005
1006/*****************************************************************************
1007 *                                                                           *
1008 * 				Public Routines                              *
1009 *                                                                           *
1010 *****************************************************************************/
1011
1012void
1013XawTreeForceLayout(Widget tree)
1014{
1015    layout_tree ((TreeWidget) tree, FALSE);
1016}
1017
1018