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

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