src/Tree.c

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