src/libavoid/region.cpp

   1 /*
   2  * vim: ts=4 sw=4 et tw=0 wm=0
   3  *
   4  * libavoid - Fast, Incremental, Object-avoiding Line Router
   5  * Copyright (C) 2004-2006  Michael Wybrow <mjwybrow@users.sourceforge.net>
   6  *
   7  * This library is free software; you can redistribute it and/or
   8  * modify it under the terms of the GNU Lesser General Public
   9  * License as published by the Free Software Foundation; either
  10  * version 2.1 of the License, or (at your option) any later version.
  11  *
  12  * This library is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15  * Lesser General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU Lesser General Public
  18  * License along with this library; if not, write to the Free Software
  19  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  20  *
  21 */
  22
  23 #include <stdio.h>
  24 #include <cstdlib>
  25 #include <algorithm>
  26 #include <cassert>
  27 #include <cmath>
  28
  29 #include "libavoid/shape.h"
  30 #include "libavoid/region.h"
  31
  32
  33 namespace Avoid {
  34
  35 Region *centerRegion = NULL;
  36
  37 static const BBox screenBBox =
  38         {Point(-INFINITY, -INFINITY), Point(INFINITY, INFINITY)};
  39
  40
  41 Region::Region()
  42     : _bbox(screenBBox)
  43     , _left(NULL), _right(NULL), _up(NULL), _down(NULL)
  44 {
  45     _blocks.clear();
  46 }
  47
  48
  49 Region::Region(double x1, double y1, double x2, double y2)
  50     : _left(NULL), _right(NULL), _up(NULL), _down(NULL)
  51 {
  52     _bbox.a.x = x1;
  53     _bbox.a.y = y1;
  54     _bbox.b.x = x2;
  55     _bbox.b.y = y2;
  56
  57     _blocks.clear();
  58 }
  59
  60
  61 static const unsigned int R_INSIDE = 0;
  62 static const unsigned int R_LEFT   = 1;
  63 static const unsigned int R_LEDGE  = 2;
  64 static const unsigned int R_RIGHT  = 4;
  65 static const unsigned int R_REDGE  = 8;
  66 static const unsigned int R_ABOVE  = 16;
  67 static const unsigned int R_TEDGE  = 32;
  68 static const unsigned int R_BELOW  = 64;
  69 static const unsigned int R_BEDGE  = 128;
  70
  71 static const unsigned int R_NONE   = R_INSIDE;
  72 static const unsigned int R_UP     = R_ABOVE;
  73 static const unsigned int R_DOWN   = R_BELOW;
  74 static const unsigned int R_HORI   = R_LEFT | R_RIGHT;
  75 static const unsigned int R_VERT   = R_UP | R_DOWN;
  76
  77
  78 static void printBBox(const char *label, const BBox &bbox)
  79 {
  80     if (label)
  81     {
  82         printf("%s: ", label);
  83     }
  84     printf("(%.2f, %.2f)-(%.2f, %.2f)\n", bbox.a.x, bbox.a.y,
  85             bbox.b.x, bbox.b.y);
  86 }
  87
  88
  89 bool Region::overlapCheck(BBox& bbox, unsigned int& p)
  90 {
  91     p = R_INSIDE;
  92     Point& a = bbox.a;
  93     Point& b = bbox.b;
  94     Point& r = _bbox.a;
  95     Point& s = _bbox.b;
  96
  97     if (s.x <= a.x)
  98     {
  99         // Wholly right.
 100         p = R_RIGHT;
 101         return false;
 102     }
 103     else if (r.x >= b.x)
 104     {
 105         // Wholly left.
 106         p = R_LEFT;
 107         return false;
 108     }
 109
 110     if (s.y <= a.y)
 111     {
 112         // Wholly below.
 113         p = R_BELOW;
 114         return false;
 115     }
 116     else if (r.y >= b.y)
 117     {
 118         // Wholly above.
 119         p = R_ABOVE;
 120         return false;
 121     }
 122
 123     if (a.y == r.y)
 124     {
 125         // Shared top edge.
 126         p |= R_TEDGE;
 127     }
 128     else if (a.y < r.y)
 129     {
 130         // Need to split above.
 131         p |= R_ABOVE;
 132     }
 133
 134     if (b.y == s.y)
 135     {
 136         // Shared bottom edge.
 137         p |= R_BEDGE;
 138     }
 139     else if (b.y > s.y)
 140     {
 141         // Need to split below.
 142         p |= R_BELOW;
 143     }
 144
 145     if (a.x == r.x)
 146     {
 147         // Shared left edge.
 148         p |= R_LEDGE;
 149     }
 150     else if (a.x < r.x)
 151     {
 152         // Need to split left.
 153         p |= R_LEFT;
 154     }
 155
 156     if (b.x == s.x)
 157     {
 158         // Shared right edge.
 159         p |= R_REDGE;
 160     }
 161     else if (b.x > s.x)
 162     {
 163         // Need to split right.
 164         p |= R_RIGHT;
 165     }
 166
 167     return true;
 168 }
 169
 170
 171 void Region::getBBox(BBox& bb)
 172 {
 173     bb.a = _bbox.a;
 174     bb.b = _bbox.b;
 175 }
 176
 177
 178 Region *Region::up(void)
 179 {
 180     return _up;
 181 }
 182
 183
 184 Region *Region::down(void)
 185 {
 186     return _down;
 187 }
 188
 189
 190 Region *Region::left(void)
 191 {
 192     return _left;
 193 }
 194
 195
 196 Region *Region::right(void)
 197 {
 198     return _right;
 199 }
 200
 201
 202 bool Region::isBlock(void)
 203 {
 204     return !(_blocks.empty());
 205 }
 206
 207
 208 void Region::initialSplit(BBox& bbox, unsigned int pos, unsigned int& shapeId)
 209 {
 210     Point& n1 = bbox.a;
 211     Point& n2 = bbox.b;
 212     Region *newR = this;
 213     Region *left, *right, *top, *bottom;
 214
 215     if (pos == R_INSIDE)
 216     {
 217         split(n2.y, R_HORI);
 218         split(n2.x, R_VERT);
 219         newR = split(n1.y, R_HORI);
 220         newR = newR->split(n1.x, R_VERT);
 221
 222         printf("%p - list %d add %d\n", newR,
 223                 (int) newR->_blocks.size(), shapeId);
 224         newR->_blocks.push_back((int) shapeId);
 225         newR->_blocks.sort();
 226         newR->_blocks.unique();
 227     }
 228     else
 229     {
 230         Region *tar = NULL;
 231         tar = newR->findRegion(n1.x, R_VERT);
 232         if (pos & R_LEFT)
 233         {
 234             if (n1.x == tar->_bbox.a.x)
 235             {
 236                 newR = tar->_right;
 237             }
 238             else if (n1.x == tar->_bbox.b.x)
 239             {
 240                 newR = tar;
 241             }
 242             else
 243             {
 244                 newR = tar->split(n1.x, R_VERT);
 245             }
 246         }
 247         else if (!(pos & R_LEDGE))
 248         {
 249             newR = tar->split(n1.x, R_VERT);
 250         }
 251         left = newR;
 252
 253         tar = left->findRegion(n1.y, R_HORI);
 254         if (pos & R_ABOVE)
 255         {
 256             if (n1.y == tar->_bbox.a.y)
 257             {
 258                 newR = tar->_down;
 259             }
 260             else if (n1.y == tar->_bbox.b.y)
 261             {
 262                 newR = tar;
 263             }
 264             else
 265             {
 266                 newR = tar->split(n1.y, R_HORI);
 267             }
 268         }
 269         else if (!(pos & R_TEDGE))
 270         {
 271             newR = tar->split(n1.y, R_HORI);
 272         }
 273         top = newR;
 274
 275         right = newR;
 276         tar = newR->findRegion(n2.x, R_VERT);
 277         if (pos & R_RIGHT)
 278         {
 279
 280             if (n2.x == tar->_bbox.a.x)
 281             {
 282                 right = tar->_left;
 283             }
 284             else if (n2.x == tar->_bbox.b.x)
 285             {
 286                 right = tar;
 287             }
 288             else
 289             {
 290                 tar->split(n2.x, R_VERT);
 291                 right = tar;
 292             }
 293         }
 294         else if (!(pos & R_REDGE))
 295         {
 296             tar->split(n2.x, R_VERT);
 297             right = tar;
 298         }
 299
 300         bottom = right;
 301         tar = right->findRegion(n2.y, R_HORI);
 302         if (pos & R_BELOW)
 303         {
 304             if (n2.y == tar->_bbox.a.y)
 305             {
 306                 bottom = tar->_up;
 307             }
 308             else if (n2.y == tar->_bbox.b.y)
 309             {
 310                 bottom = tar;
 311             }
 312             else
 313             {
 314                 tar->split(n2.y, R_HORI);
 315                 bottom = tar;
 316             }
 317         }
 318         else if (!(pos & R_BEDGE))
 319         {
 320             tar->split(n2.y, R_HORI);
 321             bottom = tar;
 322         }
 323
 324         // top is actually top-left, and bottom is bottom-right.
 325         Region *curr = top, *cptr = NULL;
 326         while (curr->_bbox.b.y <= bottom->_bbox.b.y)
 327         {
 328             cptr = curr;
 329             while (cptr->_bbox.b.x <= bottom->_bbox.b.x)
 330             {
 331                 printf("%p - list %d add %d\n", cptr,
 332                         (int) cptr->_blocks.size(), shapeId);
 333                 cptr->_blocks.push_back((int) shapeId);
 334                 cptr->_blocks.sort();
 335                 cptr->_blocks.unique();
 336
 337                 cptr = cptr->_right;
 338             }
 339
 340             curr = curr->_down;
 341         }
 342     }
 343 }
 344
 345
 346 // Returns the region containing the value 'pos' in the direction 'dir'.
 347 // Thus, if looking for the x value 55, you would pass R_VERT as 'dir'.
 348 // 'forMerge' specifies that the left or top block of a pair of regions
 349 // with the split value of 'pos' should be returned.
 350 Region *Region::findRegion(double pos, unsigned int dir, const bool forMerge)
 351 {
 352     Region *curr = this;
 353
 354     if (dir & R_VERT)
 355     {
 356         while (pos > curr->_bbox.b.x)
 357         {
 358             curr = curr->_right;
 359         }
 360         while (pos < curr->_bbox.a.x)
 361         {
 362             curr = curr->_left;
 363         }
 364         if (forMerge)
 365         {
 366             if (pos == curr->_bbox.a.x)
 367             {
 368                 curr = curr->_left;
 369             }
 370             if (pos != curr->_bbox.b.x)
 371             {
 372                 // 'pos' is not on the boundary.
 373                 return NULL;
 374             }
 375         }
 376     }
 377     else if (dir & R_HORI)
 378     {
 379         while (pos > curr->_bbox.b.y)
 380         {
 381             curr = curr->_down;
 382         }
 383         while (pos < curr->_bbox.a.y)
 384         {
 385             curr = curr->_up;
 386         }
 387         if (forMerge)
 388         {
 389             if (pos == curr->_bbox.a.y)
 390             {
 391                 curr = curr->_up;
 392             }
 393             if (pos != curr->_bbox.b.y)
 394             {
 395                 // 'pos' is not on the boundary.
 396                 return NULL;
 397             }
 398         }
 399     }
 400     return curr;
 401 }
 402
 403
 404 Region *Region::split(double pos, unsigned int dir)
 405 {
 406     Region *newR = NULL;
 407     bool first = true;
 408
 409     if (dir & R_VERT)
 410     {
 411         newR = splitDir(pos, R_UP, first);
 412         if (_down) _down->splitDir(pos, R_DOWN);
 413     }
 414     else if (dir & R_HORI)
 415     {
 416         newR = splitDir(pos, R_RIGHT, first);
 417         if (_left)  _left->splitDir(pos, R_LEFT);
 418     }
 419     return newR;
 420 }
 421
 422
 423 void Region::merge(unsigned int dir)
 424 {
 425     bool first = true;
 426
 427     if (dir & R_VERT)
 428     {
 429         mergeDir(R_UP, first);
 430         if (_down) _down->mergeDir(R_DOWN);
 431     }
 432     else if (dir & R_HORI)
 433     {
 434         mergeDir(R_RIGHT, first);
 435         if (_left)  _left->mergeDir(R_LEFT);
 436     }
 437 }
 438
 439
 440 void Region::mergeRegion(Region *src)
 441 {
 442     assert(src != NULL);
 443
 444     if (src == _left)
 445     {
 446         pairHor(src->_left, this);
 447         _bbox.a.x = src->_bbox.a.x;
 448     }
 449     else if (src == _right)
 450     {
 451         pairHor(this, src->_right);
 452         _bbox.b.x = src->_bbox.b.x;
 453     }
 454     else if (src == _up)
 455     {
 456         pairVer(src->_up, this);
 457         _bbox.a.y = src->_bbox.a.y;
 458     }
 459     else if (src == _down)
 460     {
 461         pairVer(this, src->_down);
 462         _bbox.b.y = src->_bbox.b.y;
 463     }
 464     else
 465     {
 466         fprintf(stderr, "Error: Avoid::Region::merge(): "
 467                 "Argument not adjoining region.\n");
 468         abort();
 469     }
 470     mergeAttributes(src);
 471     printf("DEL %p\n", src);
 472     delete src;
 473 }
 474
 475
 476 Region *Region::splitDir(double pos, unsigned int dir, bool first)
 477 {
 478     Point& o1 = _bbox.a;
 479     Point& o2 = _bbox.b;
 480
 481     Region *newR = NULL;
 482
 483     if (dir & R_VERT)
 484     {
 485         assert(pos > _bbox.a.x);
 486         assert(pos < _bbox.b.x);
 487
 488         // Vertical recursion:
 489
 490         // Create new block.
 491         Region *r  = new Region(pos, o1.y, o2.x, o2.y);
 492         printf("NEW %p\n", r);
 493         r->copyAttributes(this);
 494
 495         Region *o_up    = _up;
 496         Region *o_down  = _down;
 497
 498         // Resize old block.
 499         o2.x = pos;
 500
 501         pairHor(r, _right);
 502         pairHor(this, r);
 503
 504         if (dir & R_UP)
 505         {
 506             if (!first)  pairVer(r, _down->_right);
 507
 508             if (o_up)    o_up->splitDir(pos, R_UP);
 509         }
 510         else if (dir & R_DOWN)
 511         {
 512             if (!first)  pairVer(_up->_right, r);
 513
 514             if (o_down)  o_down->splitDir(pos, R_DOWN);
 515         }
 516         newR = r;
 517     }
 518     else if (dir & R_HORI)
 519     {
 520         // Vertical recursion:
 521
 522         // Create new block.
 523         Region *b  = new Region(o1.x, pos, o2.x, o2.y);
 524         printf("NEW %p\n", b);
 525         b->copyAttributes(this);
 526
 527         Region *o_left  = _left;
 528         Region *o_right = _right;
 529
 530         // Resize old block.
 531         o2.y = pos;
 532
 533         pairVer(b, _down);
 534         pairVer(this, b);
 535
 536         if (dir & R_LEFT)
 537         {
 538             if (!first)  pairHor(b, _right->_down);
 539
 540             if (o_left)  o_left->splitDir(pos, R_LEFT);
 541         }
 542         else if (dir & R_RIGHT)
 543         {
 544             if (!first)  pairHor(_left->_down, b);
 545
 546             if (o_right) o_right->splitDir(pos, R_RIGHT);
 547         }
 548         newR = b;
 549     }
 550     return newR;
 551 }
 552
 553
 554 void Region::mergeDir(unsigned int dir, bool first)
 555 {
 556     if (dir & R_VERT)
 557     {
 558         assert(_right != NULL);
 559
 560         mergeRegion(_right);
 561
 562         if (dir & R_UP)
 563         {
 564             if (_up)    _up->mergeDir(dir, R_UP);
 565         }
 566         else if (dir & R_DOWN)
 567         {
 568             if (_down)  _down->mergeDir(dir, R_DOWN);
 569         }
 570     }
 571     else if (dir & R_HORI)
 572     {
 573         assert(_down != NULL);
 574
 575         mergeRegion(_down);
 576
 577         if (dir & R_LEFT)
 578         {
 579             if (_left)  _left->mergeDir(dir, R_LEFT);
 580         }
 581         else if (dir & R_RIGHT)
 582         {
 583             if (_right) _right->mergeDir(dir, R_RIGHT);
 584         }
 585     }
 586 }
 587
 588
 589 void Region::copyAttributes(Region *src)
 590 {
 591     _blocks = src->_blocks;
 592 }
 593
 594
 595 void Region::mergeAttributes(Region *src)
 596 {
 597     _blocks.merge(src->_blocks);
 598     _blocks.sort();
 599     _blocks.unique();
 600 }
 601
 602
 603 //---------------------------
 604 // Static member functions:
 605
 606
 607 void Region::pairHor(Region *l, Region *r)
 608 {
 609     if (l)  l->_right = r;
 610     if (r)  r->_left  = l;
 611 }
 612
 613
 614 void Region::pairVer(Region *a, Region *b)
 615 {
 616     if (a)  a->_down = b;
 617     if (b)  b->_up   = a;
 618 }
 619
 620
 621 void Region::addShape(ShapeRef *shape)
 622 {
 623     if (!centerRegion)
 624     {
 625         // Add new default region.
 626         centerRegion = new Region();
 627         printf("NEW %p\n", centerRegion);
 628     }
 629     BBox bbox;
 630     // Get bounding box for added shape.
 631     shape->boundingBox(bbox);
 632     printBBox("Add", bbox);
 633
 634     unsigned int shapeId = shape->id();
 635
 636     // Find starting point for overlap
 637     Region *curr = centerRegion;
 638     unsigned int pos = R_INSIDE;
 639     while (!(curr->overlapCheck(bbox, pos)))
 640     {
 641         if (pos & R_LEFT)
 642         {
 643             curr = curr->_left;
 644         }
 645         else if (pos & R_RIGHT)
 646         {
 647             curr = curr->_right;
 648         }
 649         else if (pos & R_ABOVE)
 650         {
 651             curr = curr->_up;
 652         }
 653         else if (pos & R_BELOW)
 654         {
 655             curr = curr->_down;
 656         }
 657     }
 658
 659     curr->initialSplit(bbox, pos, shapeId);
 660     centerRegion = curr;
 661 }
 662
 663
 664 void Region::removeShape(ShapeRef *shape)
 665 {
 666     const bool forMerge = true;
 667
 668     BBox bbox;
 669     // Get bounding box for added shape.
 670     shape->boundingBox(bbox);
 671     printBBox("Remove", bbox);
 672
 673     unsigned int shapeId = shape->id();
 674
 675     Region *aboveTop = centerRegion->findRegion(bbox.a.y, R_HORI, forMerge);
 676     Region *aboveBottom = aboveTop->findRegion(bbox.b.y, R_HORI, forMerge);
 677     Region *leftOfLeft = aboveBottom->findRegion(bbox.a.x, R_VERT, forMerge);
 678     Region *leftOfRight = leftOfLeft->findRegion(bbox.b.x, R_VERT, forMerge);
 679
 680     assert(aboveTop    != NULL);
 681     assert(aboveBottom != NULL);
 682     assert(leftOfLeft  != NULL);
 683     assert(leftOfRight != NULL);
 684
 685     // Find Top Left.
 686     Region *topLeft = leftOfLeft->_right;
 687     while (topLeft->_bbox.a.y != aboveTop->_bbox.b.y)
 688     {
 689         topLeft = topLeft->_up;
 690     }
 691
 692     // Find Bottom Right.
 693     Region *botRight = leftOfRight;
 694     while (botRight->_bbox.b.y != aboveBottom->_bbox.b.y)
 695     {
 696         botRight = botRight->_down;
 697     }
 698
 699     // Clear blocking flag.
 700     Region *curr = topLeft, *cptr = NULL;
 701     while (curr->_bbox.b.y <= botRight->_bbox.b.y)
 702     {
 703         cptr = curr;
 704         while (cptr->_bbox.b.x <= botRight->_bbox.b.x)
 705         {
 706             ShapeList& blocks = cptr->_blocks;
 707
 708             assert(std::find(blocks.begin(), blocks.end(), (int) shapeId) !=
 709                     blocks.end());
 710             printf("%p - list %d remove %d\n", cptr,
 711                     (int) blocks.size(), shapeId);
 712             cptr->_blocks.remove((int) shapeId);
 713
 714             cptr = cptr->_right;
 715         }
 716
 717         curr = curr->_down;
 718     }
 719
 720     // These two are safe since they don't invalidate the pointers
 721     // to the regions that are inside the shape.
 722     if (aboveBottom->safeToMerge(R_HORI))
 723     {
 724         aboveBottom->merge(R_HORI);
 725     }
 726     if (leftOfRight->safeToMerge(R_VERT))
 727     {
 728         leftOfRight->merge(R_VERT);
 729     }
 730
 731     // Be a bit more careful with these.
 732     double leftX = leftOfLeft->_bbox.b.x;
 733     if (aboveTop->safeToMerge(R_HORI))
 734     {
 735         aboveTop->merge(R_HORI);
 736     }
 737     // leftOfLeft may have been freed, so look for the new block at
 738     // that position.
 739     leftOfLeft = aboveTop->findRegion(leftX, R_VERT, forMerge);
 740     assert(leftOfLeft);
 741     if (leftOfLeft->safeToMerge(R_VERT))
 742     {
 743         leftOfLeft->merge(R_VERT);
 744     }
 745 }
 746
 747
 748 bool Region::safeToMerge(unsigned int dir)
 749 {
 750     bool unsafe = false;
 751
 752     if (dir == R_HORI)
 753     {
 754         printf("safeToMerge? y = %.3f... ", _bbox.b.y);
 755         unsafe |= unsafeToMerge(R_RIGHT);
 756         if (_left)  unsafe |= _left->unsafeToMerge(R_LEFT);
 757     }
 758     else if (dir == R_VERT)
 759     {
 760         printf("safeToMerge? x = %.3f... ", _bbox.b.x);
 761         unsafe |= unsafeToMerge(R_DOWN);
 762         if (_up)  unsafe |= _up->unsafeToMerge(R_UP);
 763     }
 764     printf("%s.\n", (unsafe) ? "no" : "yes");
 765
 766     return !unsafe;
 767 }
 768
 769
 770 bool Region::unsafeToMerge(unsigned int dir)
 771 {
 772     bool unsafe = false;
 773
 774     if (dir & R_HORI)
 775     {
 776         // If they are not the same on both sides then we can merge.
 777         if (_blocks != _down->_blocks)
 778         {
 779             printf("\n  _blocks:\n    ");
 780             for (ShapeList::iterator i = _blocks.begin(); i != _blocks.end();
 781                     ++i)
 782             {
 783                 printf("%d ", *i);
 784             }
 785             printf("\n  _down->_blocks:\n    ");
 786             for (ShapeList::iterator i = _down->_blocks.begin();
 787                     i != _down->_blocks.end(); ++i)
 788             {
 789                 printf("%d ", *i);
 790             }
 791             unsafe |= true;
 792             printf("\n");
 793         }
 794
 795         if ((dir == R_LEFT) && _left)
 796         {
 797             unsafe |= _left->unsafeToMerge(dir);
 798         }
 799         else if ((dir == R_RIGHT) && _right)
 800         {
 801             unsafe |= _right->unsafeToMerge(dir);
 802         }
 803     }
 804     else if (dir & R_VERT)
 805     {
 806         if (_blocks !=  _right->_blocks)
 807         {
 808             printf("\n  _blocks:\n    ");
 809             for (ShapeList::iterator i = _blocks.begin(); i != _blocks.end();
 810                     ++i)
 811             {
 812                 printf("%d ", *i);
 813             }
 814             printf("\n  _right->_blocks:\n    ");
 815             for (ShapeList::iterator i = _right->_blocks.begin();
 816                     i != _right->_blocks.end(); ++i)
 817             {
 818                 printf("%d ", *i);
 819             }
 820             unsafe |= true;
 821             printf("\n");
 822         }
 823
 824         if ((dir == R_UP) && _up)
 825         {
 826             unsafe |= _up->unsafeToMerge(dir);
 827         }
 828         else if ((dir == R_DOWN) && _down)
 829         {
 830             unsafe |= _down->unsafeToMerge(dir);
 831         }
 832     }
 833     return unsafe;
 834
 835 }
 836
 837
 838 Region *Region::getTopLeftRegion(void)
 839 {
 840     Region *curr = centerRegion;
 841
 842     while (curr && (curr->_up || curr->_left))
 843     {
 844         if (curr->_up)
 845         {
 846             curr = curr->_up;
 847         }
 848         else
 849         {
 850             curr = curr->_left;
 851         }
 852     }
 853     return curr;
 854 }
 855
 856
 857 }
 858