cde/programs/dtinfo/dtinfo/src/Widgets/Tree.c

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