components/x11/libXaw5/src/Tree.c

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