cgit.sxemacs.org Git - packages/blob - xemacs-packages/oo-browser/tree-x/draw.c

   1 /* ----------------------------------------------------------------------------
   2  * File    : draw.c
   3  * Purpose : drawing-specific routines for dynamic tree program
   4  * ----------------------------------------------------------------------------
   5  */
   6
   7 #include <stdlib.h>
   8 #include <X11/Intrinsic.h>
   9 #include <X11/StringDefs.h>
  10
  11 #include "dissolve.h"
  12 #include "defs.h"
  13 #include "tree.h"
  14 #include "dbl.h"
  15 #include "intf.h"
  16
  17 /* ------------------------------------------------------------------------- */
  18 /*                              Global Variables                             */
  19 /* ------------------------------------------------------------------------- */
  20
  21 Tree *TheTree;
  22
  23
  24 /* ------------------------------------------------------------------------- */
  25 /*                              Local Variables                              */
  26 /* ------------------------------------------------------------------------- */
  27
  28 static char AnimationMode = FALSE;
  29 static char strbuf[BUFSIZ];
  30 static int  AnimationStep = ANIMATION_STEP;
  31
  32
  33 /* ------------------------------------------------------------------------- */
  34 /*                                 Functions                                 */
  35 /* ------------------------------------------------------------------------- */
  36
  37
  38 /* ----------------------------------------------------------------------------
  39  *
  40  *   BeginFrame() provides an abstraction for double buffering. It should
  41  *   be called prior to creating a new frame of animation.
  42  *
  43  * ----------------------------------------------------------------------------
  44  */
  45
  46 void
  47 BeginFrame(void)
  48 {
  49   DBLbegin_frame(TreeDrawingAreaDB);
  50 }
  51
  52
  53 /* ----------------------------------------------------------------------------
  54  *
  55  *   EndFrame() provides an abstraction for double buffering. It should
  56  *   be called after creating a new frame of animation.
  57  *
  58  * ----------------------------------------------------------------------------
  59  */
  60
  61 void
  62 EndFrame(void)
  63 {
  64   /* Changed second parameter from 0 to 1 at Torgeir Veimo's suggestion
  65      on 9/21/1997.  -- Bob Weiner, BeOpen.com */
  66   DBLend_frame(TreeDrawingAreaDB, 1);
  67 }
  68
  69
  70 /* ----------------------------------------------------------------------------
  71  *
  72  *   GetDrawingSize() gets the size of the drawing area, and returns the
  73  *   dimensions in the arguments.
  74  *
  75  * ----------------------------------------------------------------------------
  76  */
  77
  78 static void
  79 GetDrawingSize(int *width, int *height)
  80 {
  81   Dimension w, h;
  82   Arg al [2];
  83
  84   XtSetArg (al [0], XtNwidth,  &w);
  85   XtSetArg (al [1], XtNheight, &h);
  86   XtGetValues(TreeDrawingArea, al, 2);
  87
  88   *width  = (int) w;
  89   *height = (int) h;
  90 }
  91
  92
  93 /* ----------------------------------------------------------------------------
  94  *
  95  *   SetDrawingSize() sets the size of the drawing area to the given
  96  *   dimensions.
  97  *
  98  * ----------------------------------------------------------------------------
  99  */
 100
 101 static void
 102 SetDrawingSize(int width, int height)
 103 {
 104   Arg al [2];
 105   XtSetArg (al [0], XtNwidth,   (Dimension) width);
 106   XtSetArg (al [1], XtNheight,  (Dimension) height);
 107   XtSetValues (TreeDrawingArea, al, 2);
 108
 109   XClearArea(TreeDrawingAreaDB->display,
 110              TreeDrawingAreaDB->window, 0, 0, 0, 0, FALSE);
 111 }
 112
 113
 114 /* ----------------------------------------------------------------------------
 115  *
 116  *   SetDrawingTree() is used to specify what tree is to be drawn in the
 117  *   drawing area.
 118  *
 119  * ----------------------------------------------------------------------------
 120  */
 121
 122 void
 123 SetDrawingTree(Tree *tree)
 124 {
 125   TheTree = tree;
 126 }
 127
 128
 129 /* ----------------------------------------------------------------------------
 130  *
 131  *   SetNodeLabel() sets the label text of the specified node and computes
 132  *   the bounding rectangle so that the layout can be determined. This
 133  *   function is called when new nodes are created. If TreeAlignNodes is
 134  *   True, the string is truncated so that the node's width is no longer
 135  *   than TreeParentDistance.
 136  *
 137  * ----------------------------------------------------------------------------
 138  */
 139
 140 void
 141 SetNodeLabel(Tree *node, char *label)
 142 {
 143   int         len;
 144   int         dummy;
 145   XCharStruct rtrn;
 146
 147   len = strlen(label);
 148   while (len > 1) {
 149     XTextExtents(TreeLabelFont, label, len, &dummy, &dummy, &dummy, &rtrn);
 150     node->width  = rtrn.lbearing + rtrn.rbearing + (LABEL_MAT_WIDTH * 2) + 1;
 151     node->height = rtrn.ascent + rtrn.descent + (LABEL_MAT_HEIGHT * 2) + 1;
 152     if (TreeAlignNodes) {
 153       if (node->width <= (2 * TreeParentDistance))
 154         break;
 155       else
 156         len--;
 157     }
 158     else
 159       break;
 160   }
 161
 162   node->label.text = label;
 163   node->label.len  = len;
 164   node->label.xoffset = LABEL_MAT_WIDTH + 1,
 165   node->label.yoffset = rtrn.ascent + LABEL_MAT_HEIGHT + 1;
 166 }
 167
 168
 169 /* ----------------------------------------------------------------------------
 170  *
 171  *   SetDrawColor() sets the drawing color of the TreeDrawingArea.
 172  *
 173  * ----------------------------------------------------------------------------
 174  */
 175
 176 void
 177 SetDrawColor(int color)
 178 {
 179   XSetForeground(TreeDrawingAreaDB->display, TreeDrawingAreaDB->gc,
 180                  TreeDrawingAreaDB->colors[color]);
 181 }
 182
 183 /* ----------------------------------------------------------------------------
 184  *
 185  *   SetLineWidth() sets the line width of lines drawn in the TreeDrawingArea.
 186  *
 187  * ----------------------------------------------------------------------------
 188  */
 189
 190 static void
 191 SetLineWidth(unsigned int width)
 192 {
 193   XSetLineAttributes(TreeDrawingAreaDB->display, TreeDrawingAreaDB->gc,
 194                      width, LineSolid, CapButt, JoinRound);
 195 }
 196
 197
 198 /* ----------------------------------------------------------------------------
 199  *
 200  *   SetContours() sets the visibility of three possible contour modes:
 201  *   the outside contour, all subtree contours, or selected contours.
 202  *
 203  * ----------------------------------------------------------------------------
 204  */
 205
 206 static void
 207 SetContours(ContourOption option)
 208 {
 209   if (option == NoContours) {
 210     switch (TreeShowContourOption) {
 211     case OutsideContour:
 212       DrawTreeContour(TheTree, New, BACKGROUND_COLOR, FALSE, FALSE, FALSE);
 213       break;
 214     case AllContours:
 215       DrawTreeContour(TheTree, New, BACKGROUND_COLOR, FALSE, FALSE, TRUE);
 216       break;
 217     case SelectedContours:
 218       DrawTreeContour(TheTree, New, BACKGROUND_COLOR, FALSE, TRUE, TRUE);
 219       break;
 220     default:
 221       ;
 222     }
 223     DrawTreeContour(TheTree, New, BACKGROUND_COLOR, FALSE, FALSE, TRUE);
 224   }
 225   else if (option == OutsideContour) {
 226     switch (TreeShowContourOption) {
 227     case AllContours:
 228       DrawTreeContour(TheTree, New, BACKGROUND_COLOR, FALSE, FALSE, TRUE);
 229       break;
 230     case SelectedContours:
 231       DrawTreeContour(TheTree, New, BACKGROUND_COLOR, FALSE, TRUE, TRUE);
 232       break;
 233     default:
 234       ;
 235     }
 236     DrawTreeContour(TheTree, New, CONTOUR_COLOR, FALSE, FALSE, FALSE);
 237   } else if (option == AllContours) {
 238     DrawTreeContour(TheTree, New, CONTOUR_COLOR, FALSE, FALSE, TRUE);
 239   } else if (option == SelectedContours) {
 240     switch (TreeShowContourOption) {
 241     case AllContours:
 242       DrawTreeContour(TheTree, New, BACKGROUND_COLOR, FALSE, FALSE, TRUE);
 243       break;
 244     case OutsideContour:
 245       DrawTreeContour(TheTree, New, BACKGROUND_COLOR, FALSE, FALSE, FALSE);
 246       break;
 247     default:
 248       DrawTreeContour(TheTree, New, BACKGROUND_COLOR, FALSE, FALSE, TRUE);
 249     }
 250     DrawTreeContour(TheTree, New, CONTOUR_COLOR, FALSE, TRUE, TRUE);
 251   }
 252   TreeShowContourOption = option;
 253 }
 254
 255
 256 /* ----------------------------------------------------------------------------
 257  *
 258  *   HiliteNode() is called by Unzip() to change the color of a node.
 259  *
 260  * ----------------------------------------------------------------------------
 261  */
 262
 263 void
 264 HiliteNode(Tree *tree, PosMode pos_mode)
 265 {
 266   SetDrawColor(HIGHLIGHT_COLOR);
 267   DrawNode(tree, pos_mode);
 268   SetDrawColor(TREE_COLOR);
 269 }
 270
 271
 272 /* ----------------------------------------------------------------------------
 273  *
 274  *   DrawNode() takes a node and draws the node in the specified widget
 275  *   at its (x,y) coordinate. (x, y) indicates the upper-left corner where
 276  *   the node is drawn. Also, a line is drawn from the center of the left
 277  *   edge to the center of the parent's right edge. 'draw_mode' specifies
 278  *   the drawing mode (whether or not the node is erased, rather than drawn).
 279  *   'pos_mode' determines whether or not to use the old position of the node.
 280  *   This flag is used in animating the movement of a node from its old
 281  *   position to its new position.
 282  *
 283  * ----------------------------------------------------------------------------
 284  */
 285
 286 void
 287 DrawNode(Tree *node, PosMode pos_mode)
 288 {
 289   Widget   w;
 290   GC       gc;
 291
 292   w  = TreeDrawingArea;
 293   gc = TreeDrawingAreaDB->gc;
 294
 295   if (pos_mode == Old) {
 296     XDrawString(XtDisplay(w), XtWindow(w), gc,
 297                 node->old_pos.x + node->label.xoffset,
 298                 node->old_pos.y + node->label.yoffset,
 299                 node->label.text, node->label.len);
 300     XDrawRectangle(XtDisplay(w), XtWindow(w), gc,
 301                    node->old_pos.x, node->old_pos.y,
 302                    node->width, node->height);
 303     if (node->parent)
 304       XDrawLine(XtDisplay(w), XtWindow(w), gc,
 305                 node->old_pos.x - 1,
 306                 node->old_pos.y + (node->height / 2),
 307                 node->parent->old_pos.x + node->parent->width + 1,
 308                 node->parent->old_pos.y + (node->parent->height / 2));
 309     if (node->elision) {
 310       XSetFillStyle(TreeDrawingAreaDB->display, TreeDrawingAreaDB->gc,
 311                     FillTiled);
 312       XFillRectangle(XtDisplay(w), XtWindow(w), gc,
 313                      node->old_pos.x + node->width - ELISION_WIDTH,
 314                      node->old_pos.y + 1, ELISION_WIDTH, node->height - 1);
 315       XSetFillStyle(TreeDrawingAreaDB->display, TreeDrawingAreaDB->gc,
 316                     FillSolid);
 317     }
 318   } else {
 319     XDrawString(XtDisplay(w), XtWindow(w), gc,
 320                 node->pos.x + node->label.xoffset,
 321                 node->pos.y + node->label.yoffset,
 322                 node->label.text, node->label.len);
 323
 324     XDrawRectangle(XtDisplay(w), XtWindow(w), gc,
 325                    node->pos.x, node->pos.y,
 326                    node->width, node->height);
 327     if (node->parent)
 328       XDrawLine(XtDisplay(w), XtWindow(w), gc,
 329                 node->pos.x - 1,
 330                 node->pos.y + (node->height / 2),
 331                 node->parent->pos.x + node->parent->width + 1,
 332                 node->parent->pos.y + (node->parent->height / 2));
 333     if (node->elision) {
 334       XSetFillStyle(TreeDrawingAreaDB->display, TreeDrawingAreaDB->gc,
 335                     FillTiled);
 336       XFillRectangle(XtDisplay(w), XtWindow(w), gc,
 337                      node->pos.x + node->width - ELISION_WIDTH,
 338                      node->pos.y + 1, ELISION_WIDTH, node->height - 1);
 339       XSetFillStyle(TreeDrawingAreaDB->display, TreeDrawingAreaDB->gc,
 340                     FillSolid);
 341     }
 342   }
 343 }
 344
 345
 346 /* ----------------------------------------------------------------------------
 347  *
 348  *   DrawTreeContour() draws the contour of the specified subtree. Bridges
 349  *   are not traversed, so the actual subtree contour is drawn, as opposed
 350  *   to the merged contour. 'color' specifies the drawing color. If 'detach'
 351  *   is True,  the lines attaching the subtree contour to the node are not
 352  *   drawn.  If 'select' is true, then only subtrees that are flagged as
 353  *   selected are shown. If 'recursive' is True, the entire tree is traversed.
 354  *
 355  * ----------------------------------------------------------------------------
 356  */
 357
 358 void
 359 DrawTreeContour(Tree *tree, PosMode pos_mode,
 360                 int color, int detach_p, int select_p, int recursive)
 361 {
 362   Widget w = TreeDrawingArea;
 363   Polyline *contour, *tail;
 364   Tree *child;
 365   int x, y, i;
 366
 367   if (tree == NULL)
 368     return;
 369
 370   if ((select_p && tree->show_contour) || !select_p) {
 371
 372     SetDrawColor(color);
 373     SetLineWidth(TreeContourWidth);
 374
 375     /* draw upper contour */
 376     contour = tree->contour.upper.head;
 377     tail    = tree->contour.upper.tail;
 378     if (pos_mode == Old) {
 379       x = tree->old_pos.x - tree->border;
 380       y = tree->old_pos.y - tree->border;
 381     }
 382     else {
 383       x = tree->pos.x - tree->border;
 384       y = tree->pos.y - tree->border;
 385     }
 386
 387     if (detach_p) {             /* skip over attaching lines */
 388       for (i = 0 ; i < 2 ; i++) {
 389         x += contour->dx;
 390         y += contour->dy;
 391         contour = contour->link;
 392       }
 393     }
 394
 395     while (contour) {
 396       XDrawLine(XtDisplay(w), XtWindow(w), TreeDrawingAreaDB->gc,
 397                 x, y, x + contour->dx, y + contour->dy);
 398       x += contour->dx;
 399       y += contour->dy;
 400       if (contour == tail)      /* make sure you don't follow bridges */
 401         contour = NULL;
 402       else
 403         contour = contour->link;
 404     }
 405
 406     /* draw lower contour */
 407     contour = tree->contour.lower.head;
 408     tail    = tree->contour.lower.tail;
 409     if (pos_mode == Old) {
 410       x = tree->old_pos.x - tree->border;
 411       y = tree->old_pos.y + tree->border + tree->height;
 412     } else {
 413       x = tree->pos.x - tree->border;
 414       y = tree->pos.y + tree->border + tree->height;
 415     }
 416
 417     if (detach_p) {             /* skip over attaching lines */
 418       for (i = 0 ; i < 2 ; i++) {
 419         x += contour->dx;
 420         y += contour->dy;
 421         contour = contour->link;
 422       }
 423     }
 424
 425     while (contour) {
 426       XDrawLine(XtDisplay(w), XtWindow(w), TreeDrawingAreaDB->gc,
 427                 x, y, x + contour->dx, y + contour->dy);
 428       x += contour->dx;
 429       y += contour->dy;
 430       if (contour == tail)      /* make sure you don't follow bridges */
 431         contour = NULL;
 432       else
 433         contour = contour->link;
 434     }
 435   }
 436
 437   if (recursive) {
 438     FOREACH_CHILD(child, tree)
 439       if (!child->elision)
 440         DrawTreeContour(child, pos_mode, color,
 441                         detach_p, select_p, recursive);
 442   }
 443
 444   SetDrawColor(TREE_COLOR);
 445   SetLineWidth(0);
 446 }
 447
 448
 449 /* ----------------------------------------------------------------------------
 450  *
 451  *   DrawTree() traverses the given tree, drawing the node and connecting
 452  *   segments. The tree contours are also drawn at each step, if enabled.
 453  *   'draw_mode' specifies the drawing mode in which the tree is drawn.
 454  *   'pos_mode' determines whether or not to use the old position of the node.
 455  *   This flag is used in animating the movement of a node from its old
 456  *   position to its new position. DrawNode() is called to draw an individual
 457  *   node.
 458  *
 459  * ----------------------------------------------------------------------------
 460  */
 461
 462 void
 463 DrawTree(Tree *tree, PosMode pos_mode)
 464 {
 465   if (tree == NULL)
 466     return;
 467
 468   DrawNode(tree, pos_mode);
 469
 470   /* do stuff that animates Unzip() */
 471   if (tree->split) {
 472     if (!AnimationMode ||
 473         (tree->pos.x == tree->old_pos.x &&
 474          tree->pos.y == tree->old_pos.y))
 475       DrawTreeContour(tree, pos_mode, SPLIT_COLOR, FALSE, FALSE, FALSE);
 476     else
 477       DrawTreeContour(tree, pos_mode, ACTION_COLOR, FALSE, FALSE, FALSE);
 478   }
 479   if (tree->on_path)
 480     HiliteNode(tree, pos_mode);
 481
 482   if (tree->child && !tree->elision)
 483     DrawTree(tree->child, pos_mode);
 484   if (tree->sibling)
 485     DrawTree(tree->sibling, pos_mode);
 486
 487   maybe_highlight_node(tree);
 488 }
 489
 490
 491 /* ----------------------------------------------------------------------------
 492  *
 493  *   ShiftTree() adjusts the positions of each node so that it moves from
 494  *   the "old" position towards the "new position". This is used by
 495  *   AnimateTree(). 'done' is set to FALSE if the tree is not in its
 496  *   final position; it is used to determine when to stop animating the tree.
 497  *
 498  * ----------------------------------------------------------------------------
 499  */
 500
 501 static void
 502 ShiftTree(Tree *tree, int *done)
 503 {
 504   Tree *child;
 505
 506   if (tree->old_pos.x != tree->pos.x ||
 507       tree->old_pos.y != tree->pos.y)
 508     {
 509       tree->old_pos.x = tree->pos.x;
 510       tree->old_pos.y = tree->pos.y;
 511     }
 512
 513   FOREACH_CHILD(child, tree)
 514     ShiftTree(child, done);
 515 }
 516
 517
 518 /* ----------------------------------------------------------------------------
 519  *
 520  *   AnimateTree() draws the given tree in a series of steps to give the
 521  *   effect of animation from the "old" layout to the "new" layout of the
 522  *   tree.
 523  *
 524  *   The algorithm used here is not efficient; the entire tree is drawn
 525  *   on each iteration of the animation sequence; it would be more efficient
 526  *   to only redraw what is necessary. However, the method used here takes
 527  *   advantage of existing code without modification.
 528  *
 529  * ----------------------------------------------------------------------------
 530  */
 531
 532 static void
 533 AnimateTree(Tree *tree)
 534 {
 535   int done = FALSE;
 536
 537   AnimationMode = FALSE;
 538   /* highlight which nodes have to move */
 539   BeginFrame();
 540     DrawTree(tree, Old);
 541   EndFrame();
 542   Pause();
 543   if (PauseAfterStep)
 544     AnimationStep = ANIMATION_STEP_STEP;
 545   while (!done) {
 546     done = TRUE;
 547     ShiftTree(tree, &done);
 548     BeginFrame();
 549       DrawTree(tree, Old);
 550     EndFrame();
 551     if (PauseAfterStep)
 552       Pause();
 553   }
 554   if (PauseAfterStep)
 555     AnimationStep = ANIMATION_STEP;
 556   AnimationMode = FALSE;
 557 }
 558
 559
 560 /* ----------------------------------------------------------------------------
 561  *
 562  *   AnimateZip() generates a sequence of frames that animates the Zip() step.
 563  *   It is similar in logical structure to Zip().
 564  *
 565  * ----------------------------------------------------------------------------
 566  */
 567
 568 static void
 569 AnimateZip(Tree *tree)
 570 {
 571   Tree *child;
 572
 573   /* show results of Join() step */
 574   if (tree->child) {
 575     BeginFrame();
 576       FOREACH_CHILD(child, tree)
 577         child->split = FALSE;
 578       DrawTree(TheTree, New);
 579       DrawTreeContour(tree, New, CONTOUR_COLOR, TRUE, FALSE, FALSE);
 580     EndFrame();
 581
 582     StatusMsg("Zip: merge and join contours", FALSE);
 583     Pause();
 584
 585     /* show results of AttachParent() step */
 586     BeginFrame();
 587       DrawTree(TheTree, New);
 588       DrawTreeContour(tree, New, CONTOUR_COLOR, FALSE, FALSE, FALSE);
 589     EndFrame();
 590
 591     StatusMsg("Zip: attach parents", FALSE);
 592     Pause();
 593   }
 594
 595   tree->on_path = FALSE;
 596
 597   if (tree->parent)
 598     AnimateZip(tree->parent);
 599   else {
 600     tree->on_path = FALSE;
 601     BeginFrame();
 602       DrawTree(TheTree, New);
 603       DrawTreeContour(TheTree, New, CONTOUR_COLOR, FALSE, FALSE, FALSE);
 604     EndFrame();
 605     StatusMsg("Zip: reassemble entire contour", FALSE);
 606     Pause();
 607   }
 608 }
 609
 610
 611 /* ----------------------------------------------------------------------------
 612  *
 613  *   CountNodes() returns the number of nodes in the specified tree.
 614  *   Nodes below a node that has been collapsed are ignored.
 615  *
 616  * ----------------------------------------------------------------------------
 617  */
 618
 619 static int
 620 CountNodes(Tree *tree)
 621 {
 622   int num_nodes = 1;            /* count root of subtree */
 623   Tree *child;
 624
 625   if (!tree->elision) {
 626     FOREACH_CHILD(child, tree)
 627       num_nodes += CountNodes(child);
 628   }
 629   return num_nodes;
 630 }
 631
 632
 633 /* ----------------------------------------------------------------------------
 634  *
 635  *   CollectNodeRectangles() is a recursive function used by
 636  *   GetSubTreeRectangles() to collect the rectangles of descendant nodes
 637  *   into the pre-allocated storage passed to this function.
 638  *
 639  * ----------------------------------------------------------------------------
 640  */
 641
 642 static void
 643 CollectNodeRectangles(Tree *node, XRectangle **rectangles, int fill)
 644 {
 645   Tree *child;
 646
 647   (*rectangles)->x = node->pos.x;
 648   (*rectangles)->y = node->pos.y;
 649   if (fill) {
 650     (*rectangles)->width = node->width + 1;
 651     (*rectangles)->height = node->height + 1;
 652   } else {
 653     (*rectangles)->width = node->width;
 654     (*rectangles)->height = node->height;
 655   }
 656   (*rectangles)++;
 657
 658   if (!node->elision)
 659     FOREACH_CHILD(child, node)
 660       CollectNodeRectangles(child, rectangles, fill);
 661 }
 662
 663
 664 /* ----------------------------------------------------------------------------
 665  *
 666  *   GetSubTreeRectangles() builds an array of XRectangles that contain
 667  *   all the node rectangles in the tree, except the root node itself.
 668  *   The array is returned in 'rectangles' and the number of rectangles
 669  *   is returned in 'nrectangles.' Storage for the rectangles is allocated
 670  *   in this function. This function is used by PickAction to determine
 671  *   what rectangles need to be dissolved away. 'fill', if True, specifies
 672  *   that the rectangles should be 1 pixel larger in each dimension to
 673  *   compensate for FillRectangle behavior.
 674  *
 675  * ----------------------------------------------------------------------------
 676  */
 677
 678 static void
 679 GetSubTreeRectangles(Tree *tree, XRectangle **rectangles,
 680                      int *nrectangles, int fill)
 681 {
 682   Tree *child;
 683   XRectangle *crect;            /* current rectangle */
 684
 685   *nrectangles = CountNodes(tree) - 1;        /* don't count root node */
 686   *rectangles = (XRectangle *) malloc(sizeof(XRectangle) * *nrectangles);
 687   ASSERT(*rectangles, "could not allocate memory for rectangles");
 688
 689   crect = *rectangles;
 690   if (!tree->elision)
 691     FOREACH_CHILD(child, tree)
 692       CollectNodeRectangles(child, &crect, fill);
 693 }
 694
 695
 696 /* ----------------------------------------------------------------------------
 697  *
 698  *   CollectNodeSegments() is a recursive function used by GetSubTreeSegments()
 699  *   to collect the line segments connecting nodes into the pre-allocated
 700  *   storage passed to this function.
 701  *
 702  * ----------------------------------------------------------------------------
 703  */
 704
 705 static void
 706 CollectNodeSegments(Tree *node, XSegment **segments)
 707 {
 708   Tree *child;
 709
 710   (*segments)->x1 = node->pos.x - 1;
 711   (*segments)->y1 = node->pos.y + (node->height / 2),
 712   (*segments)->x2 = node->parent->pos.x + node->parent->width + 1;
 713   (*segments)->y2 = node->parent->pos.y + (node->parent->height / 2);
 714   (*segments)++;
 715
 716   if (!node->elision)
 717     FOREACH_CHILD(child, node)
 718       CollectNodeSegments(child, segments);
 719 }
 720
 721
 722 /* ----------------------------------------------------------------------------
 723  *
 724  *   GetSubTreeSegments() builds an array of XSegments that contain
 725  *   all the line segments connecting the nodes in the tree. The array is
 726  *   returned in 'segments' and the number of segments is returned in
 727  *   'nsegments.' Storage for the segments is allocated in this function.
 728  *   This function is used by PickAction to determine what line segments
 729  *   rectangles need to be dissolved away.
 730  *
 731  * ----------------------------------------------------------------------------
 732  */
 733
 734 static void
 735 GetSubTreeSegments(Tree *tree, XSegment **segments, int *nsegments)
 736 {
 737   Tree *child;
 738   XSegment *cseg;               /* current segment */
 739
 740   *nsegments = CountNodes(tree) - 1;
 741   *segments = (XSegment *) malloc(sizeof(XSegment) * *nsegments);
 742   ASSERT(*segments, "could not allocate memory for segments");
 743
 744   cseg = *segments;
 745   if (!tree->elision)
 746     FOREACH_CHILD(child, tree)
 747       CollectNodeSegments(child, &cseg);
 748 }
 749
 750
 751 /* ----------------------------------------------------------------------------
 752  *
 753  *   ComputeSubTreeExtent() computes the extent of a subtree. This is
 754  *   easily computed based on the tree's contour, as in ComputeTreeSize().
 755  *   This extent is stored in the node, and used by SearchTree for
 756  *   pick-correlation.
 757  *
 758  *   This function assumes that the given tree has at least one child; do not
 759  *   pass a leaf node to this function.
 760  *
 761  * ----------------------------------------------------------------------------
 762  */
 763
 764 void
 765 ComputeSubTreeExtent(Tree *tree)
 766 {
 767   int width, height;
 768   int x_offset, y_offset;
 769
 770   ComputeTreeSize(tree, &width, &height, &x_offset, &y_offset);
 771   tree->subextent.pos.x  = tree->child->pos.x - tree->child->border;
 772   tree->subextent.pos.y  = tree->pos.y - y_offset;
 773   tree->subextent.width  = width - (tree->child->pos.x - tree->pos.x) - 1;
 774   tree->subextent.height = height - 1;
 775 }
 776
 777
 778 /* ----------------------------------------------------------------------------
 779  *
 780  *   SearchTree() determines if a node's rectangular region encloses the
 781  *   specified point in (x,y). Rather than using a brute-force search
 782  *   through all node rectangles of a given tree, the subtree extents
 783  *   are used in a recursive fashion to drive the search as long as the
 784  *   given point is enclosed in an extent. In the worst case, the search
 785  *   time would be on the order of a brute-force search, but with complex
 786  *   trees, this method reduces the number of visits.
 787  *
 788  *   The extent of a subtree is computed by ComputeSubTreeExtent() and is
 789  *   stored in each node of the tree.
 790  *
 791  * ----------------------------------------------------------------------------
 792  */
 793
 794 int
 795 SearchTree(Tree *tree, int x, int y, Tree **node)
 796 {
 797   Tree *child;
 798
 799   if (tree == NULL)
 800     return FALSE;
 801
 802   if (PT_IN_RECT(x, y, tree->pos.x, tree->pos.y,
 803                  tree->pos.x + tree->width,
 804                  tree->pos.y + tree->height)) {
 805     *node = tree;
 806     return TRUE;
 807   }
 808   if (tree->child && (PT_IN_EXTENT(x, y, tree->subextent)))
 809     FOREACH_CHILD(child, tree) {
 810       if (SearchTree(child, x, y, node))
 811         return TRUE;
 812     }
 813   return FALSE;
 814 }
 815
 816
 817 /* ----------------------------------------------------------------------------
 818  *
 819  *   ExposeHandler() handles expose events in the TreeDrawingArea. This
 820  *   function is not intelligent; it just redraws the entire contents.
 821  *
 822  * ----------------------------------------------------------------------------
 823  */
 824
 825 void
 826 ExposeHandler(Widget w, XtPointer closure,
 827               XEvent *event, Boolean *continue_to_dispatch)
 828 {
 829   if (event->xexpose.count == 0) {
 830     BeginFrame();
 831       SetContours(TreeShowContourOption);
 832       DrawTree(TheTree, New);
 833     EndFrame();
 834   }
 835 }
 836
 837
 838 /* ----------------------------------------------------------------------------
 839  *
 840  *   ExpandCollapseNode is called to expand or collapse a node in the tree.
 841  *
 842  * ----------------------------------------------------------------------------
 843  */
 844
 845 void
 846 ExpandCollapseNode(Tree *node)
 847 {
 848   int        width, height;
 849   int        old_width, old_height;
 850   int        x_offset, y_offset;
 851   XRectangle *rectangles;
 852   XSegment   *segments;
 853   int        nrectangles, nsegments;
 854   int        expand = FALSE;
 855   Widget     w = TreeDrawingArea;
 856
 857   StatusMsg("", TRUE);
 858
 859   /* hilite node so that we know where we are */
 860   /* DrawTree will hilite it as a side effect */
 861   if (TreeShowSteps)
 862     node->on_path = TRUE;
 863
 864   /* erase the contour before changing in the tree */
 865   if ((TreeShowContourOption != NoContours) || TreeShowSteps) {
 866     BeginFrame();
 867       DrawTree(TheTree, New);
 868     EndFrame();
 869   }
 870
 871   sprintf(strbuf, "Node `%s' selected for %s", node->label.text,
 872           node->elision ? "expansion" : "collapse");
 873   StatusMsg(strbuf, FALSE);
 874   Pause();
 875
 876   if (node->parent)
 877     Unzip(node->parent);
 878   else {
 879     StatusMsg("Show entire contour", FALSE);
 880     if (TreeShowSteps) {
 881       BeginFrame();
 882         DrawTreeContour(TheTree, New, CONTOUR_COLOR, FALSE, FALSE, FALSE);
 883         DrawTree(TheTree, New);
 884       EndFrame();
 885       Pause();
 886     }
 887   }
 888
 889   /* are we collapsing a subtree? */
 890   if (!node->elision) {
 891     StatusMsg("Collapse subtree", FALSE);
 892     GetSubTreeRectangles(node, &rectangles, &nrectangles, TRUE);
 893     GetSubTreeSegments(node, &segments, &nsegments);
 894     DissolveTree(XtDisplay(w), XtWindow(w),
 895                  rectangles, nrectangles,
 896                  segments, nsegments, TRUE);
 897     free(rectangles);
 898     free(segments);
 899     Pause();
 900
 901     StatusMsg("Replace subtree contour with leaf contour", FALSE);
 902     node->elision = TRUE;
 903     if (TreeShowSteps)
 904       node->split = TRUE;       /* turned off in AnimateZip */
 905     node->old_contour = node->contour;
 906     node->width += ELISION_WIDTH;
 907     LayoutLeaf(node);
 908     BeginFrame();
 909       SetContours(TreeShowContourOption);
 910       DrawTree(TheTree, New);
 911     EndFrame();
 912     Pause();
 913   } else {
 914     StatusMsg("Replace leaf contour with old subtree contour", FALSE);
 915     if (TreeShowSteps)
 916       node->split = TRUE;       /* turned off in AnimateZip */
 917     RuboutLeaf(node);
 918     node->contour = node->old_contour;
 919     expand = TRUE;
 920   }
 921
 922   if (node->parent)
 923     Zip(node->parent);
 924
 925   ComputeTreeSize(TheTree, &width, &height, &x_offset, &y_offset);
 926   PetrifyTree(TheTree, x_offset + MAT_SIZE, y_offset + MAT_SIZE);
 927   GetDrawingSize(&old_width, &old_height);
 928
 929   if (expand) {
 930     SetDrawingSize(width + (2 * MAT_SIZE), height + (2 * MAT_SIZE));
 931     BeginFrame();
 932       DrawTree(TheTree, Old);
 933     EndFrame();
 934     Pause();
 935     StatusMsg("Move tree to new configuration", FALSE);
 936     AnimateTree(TheTree);
 937   } else {
 938     /* we are shrinking or staying the same */
 939     StatusMsg("Move tree to new configuration", FALSE);
 940     AnimateTree(TheTree);
 941     SetDrawingSize(width + (2 * MAT_SIZE), height + (2 * MAT_SIZE));
 942   }
 943
 944   if (expand) {
 945     StatusMsg("Expand subtree", FALSE);
 946     node->elision = FALSE;
 947
 948     /* erase elision marker */
 949     XSetFunction(TreeDrawingAreaDB->display, TreeDrawingAreaDB->gc,
 950                  GXclear);
 951     XFillRectangle(XtDisplay(w), XtWindow(w), TreeDrawingAreaDB->gc,
 952                    node->pos.x + node->width - ELISION_WIDTH + 1,
 953                    node->pos.y, ELISION_WIDTH, node->height + 1);
 954     XSetFunction(TreeDrawingAreaDB->display, TreeDrawingAreaDB->gc,
 955                  GXcopy);
 956     node->width -= ELISION_WIDTH;
 957
 958     GetSubTreeRectangles(node, &rectangles, &nrectangles, FALSE);
 959     GetSubTreeSegments(node, &segments, &nsegments);
 960     /* dissolve the tree back in */
 961     DissolveTree(XtDisplay(w), XtWindow(w),
 962                  rectangles, nrectangles,
 963                  segments, nsegments, FALSE);
 964     free(rectangles);
 965     free(segments);
 966
 967     /* draw text of nodes */
 968     BeginFrame();
 969       SetContours(TreeShowContourOption);
 970       DrawTree(TheTree, New);
 971     EndFrame();
 972     Pause();
 973   }
 974
 975   if (TreeShowSteps) {
 976     node->on_path = FALSE;
 977     if (node->parent)
 978       AnimateZip(node->parent);
 979     else
 980       node->split = FALSE;
 981   }
 982
 983   /* BUG: the display isn't properly updated here! */
 984   /* There should probably be some code here that
 985      clears the tree below the node currently being
 986      collapsed or expanded. Hack added 20.03.95 (torgeir@ii.uib.no).
 987      I'll try to fix this later. */
 988
 989   XClearArea(TreeDisplay, XtWindow(TreeDrawingArea), 0, 0, 0, 0, FALSE);
 990
 991   BeginFrame();
 992     SetContours(TreeShowContourOption);
 993     DrawTree(TheTree, New);
 994   EndFrame();
 995
 996   StatusMsg("Ready", TRUE);
 997 }
 998
 999 /* ----------------------------------------------------------------------------
1000  *
1001  *   InsertNode() handles the task of inserting a new node in the tree,
1002  *   at the given position with respect to 'base_node'. When 'node_pos' is
1003  *   either Before or After, it is assumed that 'base_node' has a parent.
1004  *
1005  * ----------------------------------------------------------------------------
1006  */
1007
1008 void
1009 InsertNode(Tree *base_node, NodePosition node_pos, char *new_node_text)
1010 {
1011   Tree *new_node;
1012   Tree *parent;
1013   Tree *sibling = NULL;
1014   Tree *child;
1015
1016   int  width, height;
1017   int  x_offset, y_offset;
1018
1019   StatusMsg("", TRUE);
1020
1021   new_node = MakeNode();        /* should check for memory failure */
1022   SetNodeLabel(new_node, new_node_text);
1023   LayoutLeaf(new_node);
1024
1025   /* figure out parent & sibling */
1026   if (node_pos == Child) {
1027     parent = base_node;
1028     /* find last child, if one exists */
1029     FOREACH_CHILD(child, parent)
1030       sibling = child;
1031   } else if (node_pos == After) {
1032     parent = base_node->parent;
1033     sibling = base_node;
1034   } else if (node_pos == Before) {
1035     parent = base_node->parent;
1036     FOREACH_CHILD(child, parent)
1037       if (child->sibling == base_node) {
1038         sibling = child;
1039         break;
1040       }
1041   } else {
1042     parent = NULL;
1043     abort();
1044   }
1045
1046   if (TreeShowSteps)
1047     parent->on_path = TRUE;
1048
1049   if ((TreeShowContourOption != NoContours) ||
1050       TreeShowSteps) {
1051     BeginFrame();
1052       DrawTree(TheTree, New);
1053     EndFrame();
1054   }
1055
1056   sprintf(strbuf, "Inserting `%s' as child of node `%s'",
1057           new_node_text, parent->label.text);
1058   StatusMsg(strbuf, FALSE);
1059   Pause();
1060
1061   /* erase the contour before changing in the tree */
1062
1063   Insert(parent, new_node, sibling);
1064
1065   ComputeTreeSize(TheTree, &width, &height, &x_offset, &y_offset);
1066   PetrifyTree(TheTree, x_offset + MAT_SIZE, y_offset + MAT_SIZE);
1067
1068   if (sibling)
1069     new_node->old_pos = sibling->old_pos;
1070   else if (new_node->sibling)
1071     new_node->old_pos = new_node->sibling->old_pos;
1072   else {
1073     new_node->old_pos.x = new_node->pos.x;
1074     new_node->old_pos.y = parent->old_pos.y;
1075   }
1076
1077   if (TreeShowSteps)
1078     new_node->split = TRUE;
1079
1080   SetDrawingSize(width + (2 * MAT_SIZE), height + (2 * MAT_SIZE));
1081   BeginFrame();
1082     DrawTree(TheTree, Old);
1083   EndFrame();
1084   StatusMsg("Insert: add new node and contour", FALSE);
1085   Pause();
1086
1087   StatusMsg("Move tree to new configuration", FALSE);
1088   AnimateTree(TheTree);
1089
1090   if (TreeShowSteps) {
1091     if (parent)
1092       AnimateZip(parent);
1093   }
1094
1095   BeginFrame();
1096     SetContours(TreeShowContourOption);
1097     DrawTree(TheTree, New);
1098   EndFrame();
1099
1100   StatusMsg("Ready", TRUE);
1101 }
1102
1103 /* ----------------------------------------------------------------------------
1104  *
1105  *   DeleteNode() handles the task of deleting a given node in the tree.
1106  *
1107  * ----------------------------------------------------------------------------
1108  */
1109
1110 void
1111 DeleteNode(Tree *node)
1112 {
1113   Tree *parent;
1114
1115   XRectangle *rectangles;
1116   XSegment   *segments;
1117   int         nrectangles, nsegments;
1118   Widget      w = TreeDrawingArea;
1119   int  width, height;
1120   int  x_offset, y_offset;
1121
1122   StatusMsg("", TRUE);
1123
1124   if (TreeShowSteps)
1125     node->on_path = TRUE;
1126
1127   /* erase the contour before changing in the tree */
1128   if ((TreeShowContourOption != NoContours) ||
1129       TreeShowSteps) {
1130     BeginFrame();
1131       DrawTree(TheTree, New);
1132     EndFrame();
1133   }
1134
1135   sprintf(strbuf, "Node `%s' selected for deletion", node->label.text);
1136   StatusMsg(strbuf, FALSE);
1137   Pause();
1138
1139   parent = node->parent;
1140
1141   if (parent)
1142     Unzip(parent);
1143   else
1144     TheTree = NULL;             /* delete root of tree */
1145
1146   /* fade out deleted subtree */
1147   StatusMsg("Delete subtree", FALSE);
1148   GetSubTreeRectangles(node, &rectangles, &nrectangles, TRUE);
1149   GetSubTreeSegments(node, &segments, &nsegments);
1150   DissolveTree(XtDisplay(w), XtWindow(w),
1151                rectangles, nrectangles,
1152                segments, nsegments, TRUE);
1153   free(rectangles);
1154   free(segments);
1155
1156   Delete(node);
1157
1158   BeginFrame();
1159   if (TheTree)
1160     DrawTree(TheTree, New);
1161   EndFrame();
1162   Pause();
1163
1164   if (parent)
1165     Zip(parent);
1166
1167   if (TheTree) {
1168     ComputeTreeSize(TheTree, &width, &height, &x_offset, &y_offset);
1169     PetrifyTree(TheTree, x_offset + MAT_SIZE, y_offset + MAT_SIZE);
1170     StatusMsg("Move tree to new configuration", FALSE);
1171     AnimateTree(TheTree);
1172     SetDrawingSize(width + (2 * MAT_SIZE), height + (2 * MAT_SIZE));
1173     Pause();
1174
1175     if (TreeShowSteps) {
1176       if (parent)
1177         AnimateZip(parent);
1178     }
1179
1180     BeginFrame();
1181       SetContours(TreeShowContourOption);
1182       DrawTree(TheTree, New);
1183     EndFrame();
1184
1185   }
1186
1187   StatusMsg("Ready", TRUE);
1188 }
1189
1190
1191 /* ----------------------------------------------------------------------------
1192  *
1193  *   ResetLabels() is called when the TreeAlignNodes mode is changed.
1194  *   When TreeParentDistance changes, the node width changes, so this
1195  *   function forces each node's width to be recomputed.
1196  *
1197  * ----------------------------------------------------------------------------
1198  */
1199
1200 void
1201 ResetLabels(Tree *tree)
1202 {
1203   Tree *child;
1204
1205   SetNodeLabel(tree, tree->label.text);
1206   FOREACH_CHILD(child, tree)
1207     ResetLabels(child);
1208 }
1209
1210
1211 /* ----------------------------------------------------------------------------
1212  *
1213  *   SetupTree() handles the task of setting up the specified tree in
1214  *   the drawing area.
1215  *
1216  * ----------------------------------------------------------------------------
1217  */
1218
1219 void
1220 SetupTree(Tree *tree)
1221 {
1222   int width, height;
1223   int x_offset, y_offset;
1224
1225   LayoutTree(tree);
1226   ComputeTreeSize(tree, &width, &height, &x_offset, &y_offset);
1227   PetrifyTree(tree, x_offset + MAT_SIZE, y_offset + MAT_SIZE);
1228   SetDrawingTree(tree);
1229   SetDrawingSize(width + (2 * MAT_SIZE), height + (2 * MAT_SIZE));
1230   BeginFrame();
1231     SetContours(TreeShowContourOption);
1232     DrawTree(tree, New);
1233   EndFrame();
1234 }