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