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

   1 /* ----------------------------------------------------------------------------
   2  * File    : tree.c
   3  * Purpose : dynamic tree program based on Sven Moen's algorithm
   4  * ----------------------------------------------------------------------------
   5  */
   6
   7 #include "defs.h"
   8 #include "tree.h"
   9 #include "dbl.h"
  10 #include "intf.h"
  11 #include <string.h>
  12 #include <stdlib.h>
  13
  14 /* ------------------------------------------------------------------------- */
  15 /*                              Global Variables                             */
  16 /* ------------------------------------------------------------------------- */
  17
  18 static int NumLines = 0;
  19 static int NumNodes = 0;
  20
  21
  22 /* ----------------------------------------------------------------------------
  23  *
  24  *   MakeLine() allocates the memory required for a Polyline and
  25  *   initializes the fields of a Polyline to the arguments. The
  26  *   newly-allocated Polyline is returned by the function.
  27  *
  28  * ----------------------------------------------------------------------------
  29  */
  30
  31 Polyline*
  32 MakeLine(short dx, short dy, Polyline *line)
  33 {
  34    Polyline *new_line = (Polyline *) malloc(sizeof(Polyline));
  35
  36    NASSERT(new_line, "could not allocate memory for polyline");
  37    NumLines++;
  38
  39    new_line->dx = dx;
  40    new_line->dy = dy;
  41    new_line->link = line;
  42
  43    return new_line;
  44 }
  45
  46 /* ----------------------------------------------------------------------------
  47  *
  48  *   MakeNode() allocates the memory required for a tree node, and
  49  *   zeros out all the fields in the Node. It returns a pointer to the
  50  *   tree node upon success, and NULL upon failure.
  51  *
  52  * ----------------------------------------------------------------------------
  53  */
  54
  55 Tree*
  56 MakeNode(void)
  57 {
  58    Tree *node = (Tree *) malloc(sizeof(Tree));
  59
  60    NASSERT(node, "could not allocate memory for node");
  61    NumNodes++;
  62
  63    if (node == NULL)
  64       return NULL;
  65    else {
  66      memset((char *) node, 0, sizeof(Tree));
  67      return node;
  68    }
  69 }
  70
  71 /* ----------------------------------------------------------------------------
  72  *
  73  *   MakeBridge()
  74  *
  75  * ----------------------------------------------------------------------------
  76  */
  77
  78 static Polyline*
  79 MakeBridge(Polyline *line1, int x1, int y1, Polyline *line2, int x2, int y2)
  80 {
  81    int dx, dy, s;
  82    Polyline *r;
  83
  84    dx = x2 + line2->dx - x1;
  85    if (line2->dx == 0)
  86       dy = line2->dy;
  87    else {
  88       s = dx * line2->dy;
  89       dy = s / line2->dx;
  90    }
  91    r = MakeLine(dx, dy, line2->link);
  92    line1->link = MakeLine(0, y2 + line2->dy - dy - y1, r);
  93
  94    return r;
  95 }
  96
  97 /* ----------------------------------------------------------------------------
  98  *
  99  *   Offset() computes the necessary offset that prevents two line segments
 100  *   from intersecting each other. This is the "heart" of the merge step
 101  *   that computes how two subtree contours should be separated.
 102  *
 103  *   The code is taken directly from Sven Moen's paper, with changes in
 104  *   some variable names to give more meaning:
 105  *
 106  *   - px,py indicate the x- and y-coordinates of the point on the longer
 107  *     segment if the previous Offset() call had two unequal segments
 108  *
 109  *   - lx,ly indicate the dx and dy values of the "lower" line segment
 110  *
 111  *   - ux,uy indicate the dx and dy values of the "upper" line segment
 112  *
 113  * ----------------------------------------------------------------------------
 114  */
 115
 116 static int
 117 Offset(int px, int py, int lx, int ly, int ux, int uy)
 118 {
 119    int d, s, t;
 120
 121    if (ux <= px || px+lx <= 0)
 122       return 0;
 123
 124    t = ux*ly - lx*uy;
 125
 126    if (t > 0) {
 127       if (px < 0) {
 128          s = px*ly;
 129          d = s/lx - py;
 130       }
 131       else if (px > 0) {
 132          s = px*uy;
 133          d = s/ux - py;
 134       }
 135       else {
 136          d = -py;
 137       }
 138    }
 139    else {
 140       if (ux < px+lx) {
 141          s = (ux-px) * ly;
 142          d = uy - (py + s/lx);
 143       }
 144       else if (ux > px+lx) {
 145          s = (lx+px) * uy;
 146          d = s/ux - (py+ly);
 147       }
 148       else {
 149          d = uy - (py+ly);
 150       }
 151    }
 152
 153    return MAX(0, d);
 154 }
 155
 156 /* ----------------------------------------------------------------------------
 157  *
 158  *   Merge()
 159  *
 160  * ----------------------------------------------------------------------------
 161  */
 162
 163 static int
 164 Merge(Polygon *c1, Polygon *c2)
 165 {
 166    int x, y, total, d;
 167    Polyline *lower, *upper, *bridge;
 168
 169    x = y = total = 0;
 170
 171    /*  compare lower part of upper child's contour
 172     *  with upper part of lower child's contour
 173     */
 174    upper = c1->lower.head;
 175    lower = c2->upper.head;
 176
 177    while (lower && upper) {
 178       d = Offset(x, y, lower->dx, lower->dy, upper->dx, upper->dy);
 179       y += d;
 180       total += d;
 181
 182       if (x + lower->dx <= upper->dx) {
 183          x += lower->dx;
 184          y += lower->dy;
 185          lower = lower->link;
 186       }
 187       else {
 188          x -= upper->dx;
 189          y -= upper->dy;
 190          upper = upper->link;
 191       }
 192    }
 193
 194    if (lower) {
 195       bridge = MakeBridge(c1->upper.tail, 0, 0, lower, x, y);
 196       c1->upper.tail = (bridge->link) ? c2->upper.tail : bridge;
 197       c1->lower.tail = c2->lower.tail;
 198    }
 199    else {
 200       bridge = MakeBridge(c2->lower.tail, x, y, upper, 0, 0);
 201       if (!bridge->link)
 202          c1->lower.tail = bridge;
 203    }
 204    c1->lower.head = c2->lower.head;
 205
 206    return total;
 207 }
 208
 209 /* ----------------------------------------------------------------------------
 210  *
 211  *   DetachParent() reverses the effects of AttachParent by removing
 212  *   the four line segments that connect the subtree contour to the
 213  *   node specified by 'tree'.
 214  *
 215  * ----------------------------------------------------------------------------
 216  */
 217
 218 static void
 219 DetachParent(Tree *tree)
 220 {
 221    free(tree->contour.upper.head->link);
 222    free(tree->contour.upper.head);
 223    tree->contour.upper.head = NULL;
 224    tree->contour.upper.tail = NULL;
 225
 226    free(tree->contour.lower.head->link);
 227    free(tree->contour.lower.head);
 228    tree->contour.lower.head = NULL;
 229    tree->contour.lower.tail = NULL;
 230
 231    NumLines -= 4;
 232 }
 233
 234 /* ----------------------------------------------------------------------------
 235  *
 236  *   AttachParent()
 237  *   This function also establishes the position of the first child
 238  *   The code follows Sven Moen's version, with slight modification to
 239  *   support varying borders at different levels.
 240  *
 241  * ----------------------------------------------------------------------------
 242  */
 243
 244 static void
 245 AttachParent(Tree *tree, int h)
 246 {
 247    int x, y1, y2;
 248
 249    if (TreeAlignNodes)
 250       x = tree->border + (TreeParentDistance * 2) +
 251          (TreeParentDistance - tree->width);
 252    else
 253       x = tree->border + TreeParentDistance;
 254    y2 = (h - tree->height)/2 - tree->border;
 255    y1 = y2 + tree->height + (2 * tree->border) - h;
 256    tree->child->offset.x = x + tree->width;
 257    tree->child->offset.y = y1;
 258    tree->contour.upper.head = MakeLine(tree->width, 0,
 259                                        MakeLine(x, y1,
 260                                                 tree->contour.upper.head));
 261    tree->contour.lower.head = MakeLine(tree->width, 0,
 262                                        MakeLine(x, y2,
 263                                                 tree->contour.lower.head));
 264 }
 265
 266 /* ----------------------------------------------------------------------------
 267  *
 268  *   Split()
 269  *   The tree passed to Split() must have at least 1 child, because
 270  *   it doesn't make sense to split a leaf (there are no bridges)
 271  *
 272  * ----------------------------------------------------------------------------
 273  */
 274
 275 static void
 276 Split(Tree *tree)
 277 {
 278    Tree *child;
 279    Polyline *link;
 280
 281    FOREACH_CHILD(child, tree) {
 282       if ((link = child->contour.upper.tail->link)) {
 283          free(link->link);
 284          free(link);
 285          child->contour.upper.tail->link = NULL;
 286          NumLines -= 2;
 287       }
 288       if ((link = child->contour.lower.tail->link)) {
 289          free(link->link);
 290          free(link);
 291          NumLines -= 2;
 292          child->contour.lower.tail->link = NULL;
 293       }
 294    }
 295 }
 296
 297 /* ----------------------------------------------------------------------------
 298  *
 299  *   Join() merges all subtree contours of the given tree and returns the
 300  *   height of the entire tree contour.
 301  *
 302  * ----------------------------------------------------------------------------
 303  */
 304
 305 static int
 306 Join(Tree *tree)
 307 {
 308    Tree *child;
 309    int d, h, sum;
 310
 311    /*   to start, set the parent's contour and height
 312     *   to contour and height of first child
 313     */
 314    child = tree->child;
 315    tree->contour = child->contour;
 316    sum = h = child->height + (2 * child->border);
 317
 318    /* extend contour to include contours of all children of parent */
 319    for (child = child->sibling ; child ; child = child->sibling) {
 320       d = Merge(&tree->contour, &child->contour);
 321       child->offset.y = d + h;
 322       child->offset.x = 0;
 323       h = child->height + (2 * child->border);
 324       /* keep cumulative heights of subtree contours */
 325       sum += d + h;
 326    }
 327    return sum;
 328 }
 329
 330 /* ----------------------------------------------------------------------------
 331  *
 332  *   RuboutLeaf() accepts a single node (leaf) and removes its contour.
 333  *   The memory associated with the contour is deallocated.
 334  *
 335  * ----------------------------------------------------------------------------
 336  */
 337
 338 void
 339 RuboutLeaf(Tree *tree)
 340 {
 341    free(tree->contour.upper.head);
 342    free(tree->contour.lower.tail);
 343    free(tree->contour.lower.head);
 344    tree->contour.upper.head = NULL;
 345    tree->contour.upper.tail = NULL;
 346    tree->contour.lower.head = NULL;
 347    tree->contour.lower.tail = NULL;
 348    NumLines -= 3;
 349 }
 350
 351 /* ----------------------------------------------------------------------------
 352  *
 353  *   LayoutLeaf() accepts a single node (leaf) and forms its contour. This
 354  *   function assumes that the width, height, and border fields of the
 355  *   node have been assigned meaningful values.
 356  *
 357  * ----------------------------------------------------------------------------
 358  */
 359
 360 void
 361 LayoutLeaf(Tree *tree)
 362 {
 363    tree->node_height = 0;
 364    tree->border = TreeBorderSize;
 365
 366    tree->contour.upper.tail = MakeLine(tree->width + 2 * tree->border, 0,
 367                                        NULL);
 368    tree->contour.upper.head = tree->contour.upper.tail;
 369
 370    tree->contour.lower.tail = MakeLine(0, -tree->height - 2 * tree->border,
 371                                        NULL);
 372    tree->contour.lower.head = MakeLine(tree->width + 2 * tree->border, 0,
 373                                        tree->contour.lower.tail);
 374
 375 }
 376
 377 /* ----------------------------------------------------------------------------
 378  *
 379  *   LayoutTree() traverses the given tree (in depth-first order), and forms
 380  *   subtree or leaf contours at each node as needed. Each node's contour is
 381  *   stored in its "contour" field. Elision is also supported by generating
 382  *   the contour for both the expanded and collapsed node. This routine
 383  *   also computes the tree height of each node in the tree, so that variable
 384  *   density layout can be demonstrated.
 385  *
 386  * ----------------------------------------------------------------------------
 387  */
 388
 389 void
 390 LayoutTree(Tree *tree)
 391 {
 392    Tree *child;
 393    int   height = 0;
 394
 395    FOREACH_CHILD(child, tree) {
 396       LayoutTree(child);
 397
 398       if (child->elision) {     /* support elision */
 399          child->old_contour = child->contour;
 400          LayoutLeaf(child);
 401       }
 402
 403    }
 404
 405    if (tree->child) {
 406
 407       FOREACH_CHILD(child, tree)
 408          height = MAX(child->node_height, height);
 409       tree->node_height = height + 1;
 410
 411       if (TreeLayoutDensity == Fixed)
 412          tree->border = TreeBorderSize;
 413       else
 414          tree->border =
 415             (int) (TreeBorderSize * (tree->node_height * DENSITY_FACTOR));
 416
 417       AttachParent(tree, Join(tree));
 418    }
 419    else
 420       LayoutLeaf(tree);
 421 }
 422
 423 /* ------------------------------------------------------------------------- */
 424
 425 void
 426 Unzip(Tree *tree)
 427 {
 428    Tree *child;
 429
 430 #ifdef INTF
 431    if (TreeShowSteps) {
 432       HiliteNode(tree, New);
 433       tree->on_path = TRUE;
 434       StatusMsg("Unzip: follow parent links up to root", 0);
 435       Pause();
 436    }
 437 #endif
 438
 439    if (tree->parent)
 440       Unzip(tree->parent);
 441
 442    if (tree->child) {
 443
 444 #ifdef INTF
 445       /*   draw entire contour; do it only for root, because the last
 446        *   frame drawn in this function will have already drawn the
 447        *   contour for the most recently split subtree.
 448        */
 449       if (TreeShowSteps) {
 450          if (tree->parent == NULL) {
 451             BeginFrame();
 452               DrawTreeContour(tree, New, CONTOUR_COLOR, FALSE, FALSE, FALSE);
 453               DrawTree(TheTree, New);
 454             EndFrame();
 455             StatusMsg("Unzip: disassemble entire contour", 0);
 456             Pause();
 457          }
 458       }
 459 #endif
 460
 461 #ifdef INTF
 462       /* draw contour as it would appear after DetachParent() */
 463       if (TreeShowSteps) {
 464          BeginFrame();
 465 #if 0 /* mrb */
 466            DrawTreeContour(tree, New, CONTOUR_COLOR, TRUE,
 467                            FALSE, FALSE, FALSE);
 468 #endif
 469            DrawTreeContour(tree, New, CONTOUR_COLOR, TRUE,
 470                            FALSE, FALSE);
 471            DrawTree(TheTree, New);
 472          EndFrame();
 473          StatusMsg("Unzip: detach parent", 0);
 474          Pause();
 475       }
 476 #endif
 477
 478       DetachParent(tree);
 479       Split(tree);
 480
 481 #ifdef INTF
 482       if (TreeShowSteps) {
 483          BeginFrame();
 484            /* mark other subtree contours as split, and */
 485            /* draw only the contour on path in full     */
 486            FOREACH_CHILD(child, tree) {
 487               if (!child->on_path)
 488                  child->split = TRUE;
 489               else
 490                  DrawTreeContour(child, New, CONTOUR_COLOR,
 491                                  FALSE, FALSE, FALSE);
 492            }
 493            DrawTree(TheTree, New);
 494          EndFrame();
 495          StatusMsg("Unzip: split tree", 0);
 496          Pause();
 497       }
 498 #endif
 499
 500    }
 501    else
 502       RuboutLeaf(tree);         /* leaf node */
 503 }
 504
 505 /* ------------------------------------------------------------------------- */
 506
 507 void
 508 Zip(Tree *tree)
 509 {
 510    if (tree->child)
 511       AttachParent(tree, Join(tree));
 512    else
 513       LayoutLeaf(tree);
 514
 515    if (tree->parent)
 516       Zip(tree->parent);
 517 }
 518
 519 /* ----------------------------------------------------------------------------
 520  *
 521  *   Insert() adds the specified child to parent, just after the specified
 522  *   sibling. If 'sibling' is Null, the child is added as the first child.
 523  *
 524  * ----------------------------------------------------------------------------
 525  */
 526
 527 void
 528 Insert(Tree *parent, Tree *child, Tree *sibling)
 529 {
 530    Unzip(parent);
 531    child->parent = parent;
 532    if (sibling) {
 533       child->sibling = sibling->sibling;
 534       sibling->sibling = child;
 535    }
 536    else {
 537       child->sibling = parent->child;
 538       parent->child = child;
 539    }
 540    Zip(parent);
 541 }
 542
 543
 544
 545
 546 /* ----------------------------------------------------------------------------
 547  *
 548  *   Delete() traverses the specified tree and frees all storage
 549  *   allocated to the subtree, including contours and bridges.
 550  *   If the tree had a preceding sibling, the preceding sibling is
 551  *   modified to point to the tree's succeeding sibling, if any.
 552  *
 553  * ----------------------------------------------------------------------------
 554  */
 555
 556 void
 557 Delete(Tree *tree)
 558 {
 559    Tree *sibling = NULL;
 560    Tree *parent, *child;
 561
 562    /* find sibling */
 563    parent = tree->parent;
 564    if (parent) {
 565       FOREACH_CHILD(child, parent)
 566          if (child->sibling == tree) {
 567             sibling = child;
 568             break;
 569          }
 570    }
 571    if (sibling)
 572       sibling->sibling = tree->sibling;
 573    else if (parent)
 574       parent->child = tree->sibling;
 575
 576    DeleteTree(tree, FALSE);
 577 }
 578
 579
 580 /* ----------------------------------------------------------------------------
 581  *
 582  *   DeleteTree() is the recursive function that supports Delete().
 583  *   If 'contour' is True, then only the contours are recursively deleted.
 584  *   This flag should be True when you are regenerating a tree's layout
 585  *   and still want to preserve the nodes. Since contours would be deleted
 586  *   only due to a change in sibling or level distance, each node's border
 587  *   value is updated with the current value of TreeBorderSize;
 588  *
 589  * ----------------------------------------------------------------------------
 590  */
 591
 592 void
 593 DeleteTree(Tree *tree, int contour)
 594 {
 595    Tree *child;
 596
 597    if (tree->elision) {
 598       RuboutLeaf(tree);
 599       tree->contour = tree->old_contour;
 600       tree->old_contour.upper.head = NULL;    /* flag to note 'NULL' contour */
 601    }
 602
 603    if (!IS_LEAF(tree)) {
 604       DetachParent(tree);
 605       Split(tree);
 606
 607 #if 0
 608       /* This macro makes a child->sibling reference
 609          after the child has been deleted, so don't
 610          use it.  - kkm@kis.ru, 4/9/1998  */
 611       FOREACH_CHILD(child,tree)
 612          DeleteTree(child, contour);
 613 #else
 614       child = tree->child;
 615       while (child)
 616         {
 617           Tree* next = child->sibling;
 618           DeleteTree (child, contour);
 619           child = next;
 620         }
 621 #endif
 622    }
 623    else
 624       RuboutLeaf(tree);
 625
 626    if (contour)
 627       tree->border = TreeBorderSize;
 628    else {
 629       free(tree->label.text);
 630       free(tree);
 631       NumNodes--;
 632    }
 633 }
 634
 635
 636 /* ----------------------------------------------------------------------------
 637  *
 638  *   ComputeTreeSize()
 639  *   This function should be called after tree layout.
 640  *
 641  * ----------------------------------------------------------------------------
 642  */
 643
 644 void
 645 ComputeTreeSize(Tree *tree,
 646                 int *width, int *height,
 647                 int *x_offset, int *y_offset)
 648 {
 649    Polyline *contour, *tail;
 650    int upper_min_y = 0, lower_max_y = 0;
 651    int upper_abs_y = 0, lower_abs_y = 0;
 652    int x = 0;
 653
 654    /* do upper contour */
 655    contour = tree->contour.upper.head;
 656    tail    = tree->contour.upper.tail;
 657    while (contour) {
 658       if ((contour->dy + upper_abs_y) < upper_min_y)
 659          upper_min_y = contour->dy + upper_abs_y;
 660       upper_abs_y += contour->dy;
 661       if (contour == tail)
 662          contour = NULL;
 663       else
 664          contour = contour->link;
 665    }
 666
 667    /* do lower contour */
 668    contour = tree->contour.lower.head;
 669    tail    = tree->contour.lower.tail;
 670    while (contour) {
 671       if ((contour->dy + lower_abs_y) > lower_max_y)
 672          lower_max_y = contour->dy + lower_abs_y;
 673       lower_abs_y += contour->dy;
 674       x += contour->dx;
 675       if (contour == tail)
 676          contour = NULL;
 677       else
 678          contour = contour->link;
 679    }
 680
 681    *width = x + 1;
 682    *height = lower_max_y - upper_min_y +
 683              (tree->height + (2 * tree->border)) + 1;
 684    if (x_offset)
 685       *x_offset = tree->border;
 686    if (y_offset)
 687       *y_offset = - upper_min_y + tree->border;
 688 }
 689
 690 /* ----------------------------------------------------------------------------
 691  *
 692  *   PetrifyTree()
 693  *
 694  * ----------------------------------------------------------------------------
 695  */
 696
 697 void
 698 PetrifyTree(Tree *tree, int x, int y)
 699 {
 700    tree->old_pos = tree->pos;   /* used by AnimateTree */
 701
 702    /* fix position of each node */
 703    tree->pos.x = x + tree->offset.x;
 704    tree->pos.y = y + tree->offset.y;
 705
 706    if (tree->child) {
 707       PetrifyTree(tree->child, tree->pos.x, tree->pos.y);
 708       ComputeSubTreeExtent(tree); /* for benefit of interface picking */
 709    }
 710    if (tree->sibling)
 711       PetrifyTree(tree->sibling, tree->pos.x, tree->pos.y);
 712 }