earlybrowserreborn - Blame information for rev 1

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