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