Tree.c revision efbcb2bf 
1/*
2
3Copyright 1990, 1994, 1998  The Open Group
4
5Permission to use, copy, modify, distribute, and sell this software and its
6documentation for any purpose is hereby granted without fee, provided that
7the above copyright notice appear in all copies and that both that
8copyright notice and this permission notice appear in supporting
9documentation.
10
11The above copyright notice and this permission notice shall be included in
12all copies or substantial portions of the Software.
13
14THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
17OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
18AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
19CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
20
21Except as contained in this notice, the name of The Open Group shall not be
22used in advertising or otherwise to promote the sale, use or other dealings
23in 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 */
66static void XawTreeChangeManaged(Widget);
67static void XawTreeClassInitialize(void);
68static void XawTreeConstraintDestroy(Widget);
69static void XawTreeConstraintInitialize(Widget, Widget, ArgList, Cardinal*);
70static Boolean XawTreeConstraintSetValues(Widget, Widget, Widget,
71					  ArgList, Cardinal*);
72static void XawTreeDestroy(Widget);
73static XtGeometryResult XawTreeGeometryManager(Widget, XtWidgetGeometry*,
74					       XtWidgetGeometry*);
75static void XawTreeInitialize(Widget, Widget, ArgList, Cardinal*);
76static XtGeometryResult XawTreeQueryGeometry(Widget, XtWidgetGeometry*,
77					     XtWidgetGeometry*);
78static void XawTreeRedisplay(Widget, XEvent*, Region);
79static Boolean XawTreeSetValues(Widget, Widget, Widget, ArgList, Cardinal*);
80
81/*
82 * Prototypes
83 */
84static void arrange_subtree(TreeWidget, Widget, int, int, int);
85static void check_gravity(TreeWidget, XtGravity);
86static void compute_bounding_box_subtree(TreeWidget, Widget, int);
87static void delete_node(Widget, Widget);
88static GC get_tree_gc(TreeWidget);
89static void initialize_dimensions(Dimension**, int*, int);
90static void insert_node(Widget, Widget);
91static void layout_tree(TreeWidget, Bool);
92static void set_positions(TreeWidget, Widget, int);
93static void set_tree_size(TreeWidget, Bool, unsigned int, unsigned int);
94
95/*
96 * Initialization
97 */
98
99/*
100 * resources of the tree itself
101 */
102static 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 */
129static 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
137TreeClassRec 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
197WidgetClass treeWidgetClass = (WidgetClass) &treeClassRec;
198
199
200/*****************************************************************************
201 *                                                                           *
202 *			     tree utility routines                           *
203 *                                                                           *
204 *****************************************************************************/
205
206static void
207initialize_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
233static GC
234get_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
249static void
250insert_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
283static void
284delete_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
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 _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 */
407static void
408XawTreeConstraintInitialize(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 */
438static Boolean
439XawTreeSetValues(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 */
485static Boolean
486XawTreeConstraintSetValues(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
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 _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
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 _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
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    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
795static void
796set_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
833static void
834arrange_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
935static void
936set_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
959static void
960layout_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
1010void
1011XawTreeForceLayout(Widget tree)
1012{
1013    layout_tree ((TreeWidget) tree, FALSE);
1014}
1015
1016