1// This may look like C code, but it is really -*- C++ -*- 2/* 3Copyright (C) 1988 Free Software Foundation 4 written by Doug Lea (dl@rocky.oswego.edu) 5 6This file is part of GNU CC. 7 8GNU CC is distributed in the hope that it will be useful, 9but WITHOUT ANY WARRANTY. No author or distributor 10accepts responsibility to anyone for the consequences of using it 11or for whether it serves any particular purpose or works at all, 12unless he says so in writing. Refer to the GNU CC General Public 13License for full details. 14 15Everyone is granted permission to copy, modify and redistribute 16GNU CC, but only under the conditions described in the 17GNU CC General Public License. A copy of this license is 18supposed to have been given to you along with GNU CC so you 19can know your rights and responsibilities. It should be in a 20file named COPYING. Among other things, the copyright notice 21and this notice must be preserved on all copies. 22*/ 23 24#ifdef __GNUG__ 25#pragma implementation 26#endif 27#include <stream.h> 28#include <assert.h> 29#include "<T>.AVLSet.h" 30 31 32/* 33 constants & inlines for maintaining balance & thread status in tree nodes 34*/ 35 36#define AVLBALANCEMASK 3 37#define AVLBALANCED 0 38#define AVLLEFTHEAVY 1 39#define AVLRIGHTHEAVY 2 40 41#define LTHREADBIT 4 42#define RTHREADBIT 8 43 44 45static inline int bf(<T>AVLNode* t) 46{ 47 return t->stat & AVLBALANCEMASK; 48} 49 50static inline void set_bf(<T>AVLNode* t, int b) 51{ 52 t->stat = (t->stat & ~AVLBALANCEMASK) | (b & AVLBALANCEMASK); 53} 54 55 56static inline int rthread(<T>AVLNode* t) 57{ 58 return t->stat & RTHREADBIT; 59} 60 61static inline void set_rthread(<T>AVLNode* t, int b) 62{ 63 if (b) 64 t->stat |= RTHREADBIT; 65 else 66 t->stat &= ~RTHREADBIT; 67} 68 69static inline int lthread(<T>AVLNode* t) 70{ 71 return t->stat & LTHREADBIT; 72} 73 74static inline void set_lthread(<T>AVLNode* t, int b) 75{ 76 if (b) 77 t->stat |= LTHREADBIT; 78 else 79 t->stat &= ~LTHREADBIT; 80} 81 82/* 83 traversal primitives 84*/ 85 86 87<T>AVLNode* <T>AVLSet::leftmost() 88{ 89 <T>AVLNode* t = root; 90 if (t != 0) while (t->lt != 0) t = t->lt; 91 return t; 92} 93 94<T>AVLNode* <T>AVLSet::rightmost() 95{ 96 <T>AVLNode* t = root; 97 if (t != 0) while (t->rt != 0) t = t->rt; 98 return t; 99} 100 101<T>AVLNode* <T>AVLSet::succ(<T>AVLNode* t) 102{ 103 <T>AVLNode* r = t->rt; 104 if (!rthread(t)) while (!lthread(r)) r = r->lt; 105 return r; 106} 107 108<T>AVLNode* <T>AVLSet::pred(<T>AVLNode* t) 109{ 110 <T>AVLNode* l = t->lt; 111 if (!lthread(t)) while (!rthread(l)) l = l->rt; 112 return l; 113} 114 115 116Pix <T>AVLSet::seek(<T&> key) 117{ 118 <T>AVLNode* t = root; 119 if (t == 0) 120 return 0; 121 for (;;) 122 { 123 int cmp = <T>CMP(key, t->item); 124 if (cmp == 0) 125 return Pix(t); 126 else if (cmp < 0) 127 { 128 if (lthread(t)) 129 return 0; 130 else 131 t = t->lt; 132 } 133 else if (rthread(t)) 134 return 0; 135 else 136 t = t->rt; 137 } 138} 139 140 141/* 142 The combination of threads and AVL bits make adding & deleting 143 interesting, but very awkward. 144 145 We use the following statics to avoid passing them around recursively 146*/ 147 148static int _need_rebalancing; // to send back balance info from rec. calls 149static <T>* _target_item; // add/del_item target 150static <T>AVLNode* _found_node; // returned added/deleted node 151static int _already_found; // for deletion subcases 152 153static <T>AVLNode** _hold_nodes; // used for rebuilding trees 154static int _max_hold_index; // # elements-1 in _hold_nodes 155 156 157void <T>AVLSet:: _add(<T>AVLNode*& t) 158{ 159 int cmp = <T>CMP(*_target_item, t->item); 160 if (cmp == 0) 161 { 162 _found_node = t; 163 return; 164 } 165 else if (cmp < 0) 166 { 167 if (lthread(t)) 168 { 169 ++count; 170 _found_node = new <T>AVLNode(*_target_item); 171 set_lthread(_found_node, 1); 172 set_rthread(_found_node, 1); 173 _found_node->lt = t->lt; 174 _found_node->rt = t; 175 t->lt = _found_node; 176 set_lthread(t, 0); 177 _need_rebalancing = 1; 178 } 179 else 180 _add(t->lt); 181 if (_need_rebalancing) 182 { 183 switch(bf(t)) 184 { 185 case AVLRIGHTHEAVY: 186 set_bf(t, AVLBALANCED); 187 _need_rebalancing = 0; 188 return; 189 case AVLBALANCED: 190 set_bf(t, AVLLEFTHEAVY); 191 return; 192 case AVLLEFTHEAVY: 193 <T>AVLNode* l = t->lt; 194 if (bf(l) == AVLLEFTHEAVY) 195 { 196 if (rthread(l)) 197 t->lt = l; 198 else 199 t->lt = l->rt; 200 set_lthread(t, rthread(l)); 201 l->rt = t; 202 set_rthread(l, 0); 203 set_bf(t, AVLBALANCED); 204 set_bf(l, AVLBALANCED); 205 t = l; 206 _need_rebalancing = 0; 207 } 208 else 209 { 210 <T>AVLNode* r = l->rt; 211 set_rthread(l, lthread(r)); 212 if (lthread(r)) 213 l->rt = r; 214 else 215 l->rt = r->lt; 216 r->lt = l; 217 set_lthread(r, 0); 218 set_lthread(t, rthread(r)); 219 if (rthread(r)) 220 t->lt = r; 221 else 222 t->lt = r->rt; 223 r->rt = t; 224 set_rthread(r, 0); 225 if (bf(r) == AVLLEFTHEAVY) 226 set_bf(t, AVLRIGHTHEAVY); 227 else 228 set_bf(t, AVLBALANCED); 229 if (bf(r) == AVLRIGHTHEAVY) 230 set_bf(l, AVLLEFTHEAVY); 231 else 232 set_bf(l, AVLBALANCED); 233 set_bf(r, AVLBALANCED); 234 t = r; 235 _need_rebalancing = 0; 236 return; 237 } 238 } 239 } 240 } 241 else 242 { 243 if (rthread(t)) 244 { 245 ++count; 246 _found_node = new <T>AVLNode(*_target_item); 247 set_rthread(t, 0); 248 set_lthread(_found_node, 1); 249 set_rthread(_found_node, 1); 250 _found_node->lt = t; 251 _found_node->rt = t->rt; 252 t->rt = _found_node; 253 _need_rebalancing = 1; 254 } 255 else 256 _add(t->rt); 257 if (_need_rebalancing) 258 { 259 switch(bf(t)) 260 { 261 case AVLLEFTHEAVY: 262 set_bf(t, AVLBALANCED); 263 _need_rebalancing = 0; 264 return; 265 case AVLBALANCED: 266 set_bf(t, AVLRIGHTHEAVY); 267 return; 268 case AVLRIGHTHEAVY: 269 <T>AVLNode* r = t->rt; 270 if (bf(r) == AVLRIGHTHEAVY) 271 { 272 if (lthread(r)) 273 t->rt = r; 274 else 275 t->rt = r->lt; 276 set_rthread(t, lthread(r)); 277 r->lt = t; 278 set_lthread(r, 0); 279 set_bf(t, AVLBALANCED); 280 set_bf(r, AVLBALANCED); 281 t = r; 282 _need_rebalancing = 0; 283 } 284 else 285 { 286 <T>AVLNode* l = r->lt; 287 set_lthread(r, rthread(l)); 288 if (rthread(l)) 289 r->lt = l; 290 else 291 r->lt = l->rt; 292 l->rt = r; 293 set_rthread(l, 0); 294 set_rthread(t, lthread(l)); 295 if (lthread(l)) 296 t->rt = l; 297 else 298 t->rt = l->lt; 299 l->lt = t; 300 set_lthread(l, 0); 301 if (bf(l) == AVLRIGHTHEAVY) 302 set_bf(t, AVLLEFTHEAVY); 303 else 304 set_bf(t, AVLBALANCED); 305 if (bf(l) == AVLLEFTHEAVY) 306 set_bf(r, AVLRIGHTHEAVY); 307 else 308 set_bf(r, AVLBALANCED); 309 set_bf(l, AVLBALANCED); 310 t = l; 311 _need_rebalancing = 0; 312 return; 313 } 314 } 315 } 316 } 317} 318 319 320Pix <T>AVLSet::add(<T&> item) 321{ 322 if (root == 0) 323 { 324 ++count; 325 root = new <T>AVLNode(item); 326 set_rthread(root, 1); 327 set_lthread(root, 1); 328 return Pix(root); 329 } 330 else 331 { 332 _target_item = &item; 333 _need_rebalancing = 0; 334 _add(root); 335 return Pix(_found_node); 336 } 337} 338 339 340void <T>AVLSet::_del(<T>AVLNode* par, <T>AVLNode*& t) 341{ 342 int comp; 343 if (_already_found) 344 { 345 if (rthread(t)) 346 comp = 0; 347 else 348 comp = 1; 349 } 350 else 351 comp = <T>CMP(*_target_item, t->item); 352 if (comp == 0) 353 { 354 if (lthread(t) && rthread(t)) 355 { 356 _found_node = t; 357 if (t == par->lt) 358 { 359 set_lthread(par, 1); 360 par->lt = t->lt; 361 } 362 else 363 { 364 set_rthread(par, 1); 365 par->rt = t->rt; 366 } 367 _need_rebalancing = 1; 368 return; 369 } 370 else if (lthread(t)) 371 { 372 _found_node = t; 373 <T>AVLNode* s = succ(t); 374 if (s != 0 && lthread(s)) 375 s->lt = t->lt; 376 t = t->rt; 377 _need_rebalancing = 1; 378 return; 379 } 380 else if (rthread(t)) 381 { 382 _found_node = t; 383 <T>AVLNode* p = pred(t); 384 if (p != 0 && rthread(p)) 385 p->rt = t->rt; 386 t = t->lt; 387 _need_rebalancing = 1; 388 return; 389 } 390 else // replace item & find someone deletable 391 { 392 <T>AVLNode* p = pred(t); 393 t->item = p->item; 394 _already_found = 1; 395 comp = -1; // fall through below to left 396 } 397 } 398 399 if (comp < 0) 400 { 401 if (lthread(t)) 402 return; 403 _del(t, t->lt); 404 if (!_need_rebalancing) 405 return; 406 switch (bf(t)) 407 { 408 case AVLLEFTHEAVY: 409 set_bf(t, AVLBALANCED); 410 return; 411 case AVLBALANCED: 412 set_bf(t, AVLRIGHTHEAVY); 413 _need_rebalancing = 0; 414 return; 415 case AVLRIGHTHEAVY: 416 <T>AVLNode* r = t->rt; 417 switch (bf(r)) 418 { 419 case AVLBALANCED: 420 if (lthread(r)) 421 t->rt = r; 422 else 423 t->rt = r->lt; 424 set_rthread(t, lthread(r)); 425 r->lt = t; 426 set_lthread(r, 0); 427 set_bf(t, AVLRIGHTHEAVY); 428 set_bf(r, AVLLEFTHEAVY); 429 _need_rebalancing = 0; 430 t = r; 431 return; 432 case AVLRIGHTHEAVY: 433 if (lthread(r)) 434 t->rt = r; 435 else 436 t->rt = r->lt; 437 set_rthread(t, lthread(r)); 438 r->lt = t; 439 set_lthread(r, 0); 440 set_bf(t, AVLBALANCED); 441 set_bf(r, AVLBALANCED); 442 t = r; 443 return; 444 case AVLLEFTHEAVY: 445 <T>AVLNode* l = r->lt; 446 set_lthread(r, rthread(l)); 447 if (rthread(l)) 448 r->lt = l; 449 else 450 r->lt = l->rt; 451 l->rt = r; 452 set_rthread(l, 0); 453 set_rthread(t, lthread(l)); 454 if (lthread(l)) 455 t->rt = l; 456 else 457 t->rt = l->lt; 458 l->lt = t; 459 set_lthread(l, 0); 460 if (bf(l) == AVLRIGHTHEAVY) 461 set_bf(t, AVLLEFTHEAVY); 462 else 463 set_bf(t, AVLBALANCED); 464 if (bf(l) == AVLLEFTHEAVY) 465 set_bf(r, AVLRIGHTHEAVY); 466 else 467 set_bf(r, AVLBALANCED); 468 set_bf(l, AVLBALANCED); 469 t = l; 470 return; 471 } 472 } 473 } 474 else 475 { 476 if (rthread(t)) 477 return; 478 _del(t, t->rt); 479 if (!_need_rebalancing) 480 return; 481 switch (bf(t)) 482 { 483 case AVLRIGHTHEAVY: 484 set_bf(t, AVLBALANCED); 485 return; 486 case AVLBALANCED: 487 set_bf(t, AVLLEFTHEAVY); 488 _need_rebalancing = 0; 489 return; 490 case AVLLEFTHEAVY: 491 <T>AVLNode* l = t->lt; 492 switch (bf(l)) 493 { 494 case AVLBALANCED: 495 if (rthread(l)) 496 t->lt = l; 497 else 498 t->lt = l->rt; 499 set_lthread(t, rthread(l)); 500 l->rt = t; 501 set_rthread(l, 0); 502 set_bf(t, AVLLEFTHEAVY); 503 set_bf(l, AVLRIGHTHEAVY); 504 _need_rebalancing = 0; 505 t = l; 506 return; 507 case AVLLEFTHEAVY: 508 if (rthread(l)) 509 t->lt = l; 510 else 511 t->lt = l->rt; 512 set_lthread(t, rthread(l)); 513 l->rt = t; 514 set_rthread(l, 0); 515 set_bf(t, AVLBALANCED); 516 set_bf(l, AVLBALANCED); 517 t = l; 518 return; 519 case AVLRIGHTHEAVY: 520 <T>AVLNode* r = l->rt; 521 set_rthread(l, lthread(r)); 522 if (lthread(r)) 523 l->rt = r; 524 else 525 l->rt = r->lt; 526 r->lt = l; 527 set_lthread(r, 0); 528 set_lthread(t, rthread(r)); 529 if (rthread(r)) 530 t->lt = r; 531 else 532 t->lt = r->rt; 533 r->rt = t; 534 set_rthread(r, 0); 535 if (bf(r) == AVLLEFTHEAVY) 536 set_bf(t, AVLRIGHTHEAVY); 537 else 538 set_bf(t, AVLBALANCED); 539 if (bf(r) == AVLRIGHTHEAVY) 540 set_bf(l, AVLLEFTHEAVY); 541 else 542 set_bf(l, AVLBALANCED); 543 set_bf(r, AVLBALANCED); 544 t = r; 545 return; 546 } 547 } 548 } 549} 550 551 552 553void <T>AVLSet::del(<T&> item) 554{ 555 if (root == 0) return; 556 _need_rebalancing = 0; 557 _already_found = 0; 558 _found_node = 0; 559 _target_item = &item; 560 _del(root, root); 561 if (_found_node) 562 { 563 delete(_found_node); 564 if (--count == 0) 565 root = 0; 566 } 567} 568 569// build an ordered array of pointers to tree nodes back into a tree 570// we know that at least one element exists 571 572static <T>AVLNode* _do_treeify(int lo, int hi, int& h) 573{ 574 int lh, rh; 575 int mid = (lo + hi) / 2; 576 <T>AVLNode* t = _hold_nodes[mid]; 577 if (lo > mid - 1) 578 { 579 set_lthread(t, 1); 580 if (mid == 0) 581 t->lt = 0; 582 else 583 t->lt = _hold_nodes[mid-1]; 584 lh = 0; 585 } 586 else 587 { 588 set_lthread(t, 0); 589 t->lt = _do_treeify(lo, mid-1, lh); 590 } 591 if (hi < mid + 1) 592 { 593 set_rthread(t, 1); 594 if (mid == _max_hold_index) 595 t->rt = 0; 596 else 597 t->rt = _hold_nodes[mid+1]; 598 rh = 0; 599 } 600 else 601 { 602 set_rthread(t, 0); 603 t->rt = _do_treeify(mid+1, hi, rh); 604 } 605 if (lh == rh) 606 { 607 set_bf(t, AVLBALANCED); 608 h = lh + 1; 609 } 610 else if (lh == rh - 1) 611 { 612 set_bf(t, AVLRIGHTHEAVY); 613 h = rh + 1; 614 } 615 else if (rh == lh - 1) 616 { 617 set_bf(t, AVLLEFTHEAVY); 618 h = lh + 1; 619 } 620 else // can't happen 621 abort(); 622 623 return t; 624} 625 626static <T>AVLNode* _treeify(int n) 627{ 628 <T>AVLNode* t; 629 if (n == 0) 630 t = 0; 631 else 632 { 633 int b; 634 _max_hold_index = n-1; 635 t = _do_treeify(0, _max_hold_index, b); 636 } 637 delete _hold_nodes; 638 return t; 639} 640 641 642void <T>AVLSet::_kill(<T>AVLNode* t) 643{ 644 if (t != 0) 645 { 646 if (!lthread(t)) _kill(t->lt); 647 if (!rthread(t)) _kill(t->rt); 648 delete t; 649 } 650} 651 652 653<T>AVLSet::<T>AVLSet(<T>AVLSet& b) 654{ 655 if ((count = b.count) == 0) 656 { 657 root = 0; 658 } 659 else 660 { 661 _hold_nodes = new <T>AVLNodePtr [count]; 662 <T>AVLNode* t = b.leftmost(); 663 int i = 0; 664 while (t != 0) 665 { 666 _hold_nodes[i++] = new <T>AVLNode(t->item); 667 t = b.succ(t); 668 } 669 root = _treeify(count); 670 } 671} 672 673 674int <T>AVLSet::operator == (<T>AVLSet& y) 675{ 676 if (count != y.count) 677 return 0; 678 else 679 { 680 <T>AVLNode* t = leftmost(); 681 <T>AVLNode* u = y.leftmost(); 682 for (;;) 683 { 684 if (t == 0) 685 return 1; 686 else if (!(<T>EQ(t->item, u->item))) 687 return 0; 688 else 689 { 690 t = succ(t); 691 u = y.succ(u); 692 } 693 } 694 } 695} 696 697int <T>AVLSet::operator <= (<T>AVLSet& y) 698{ 699 if (count > y.count) 700 return 0; 701 else 702 { 703 <T>AVLNode* t = leftmost(); 704 <T>AVLNode* u = y.leftmost(); 705 for (;;) 706 { 707 if (t == 0) 708 return 1; 709 else if (u == 0) 710 return 0; 711 int cmp = <T>CMP(t->item, u->item); 712 if (cmp == 0) 713 { 714 t = succ(t); 715 u = y.succ(u); 716 } 717 else if (cmp < 0) 718 return 0; 719 else 720 u = y.succ(u); 721 } 722 } 723} 724 725void <T>AVLSet::operator |=(<T>AVLSet& y) 726{ 727 <T>AVLNode* t = leftmost(); 728 <T>AVLNode* u = y.leftmost(); 729 int rsize = count + y.count; 730 _hold_nodes = new <T>AVLNodePtr [rsize]; 731 int k = 0; 732 for (;;) 733 { 734 if (t == 0) 735 { 736 while (u != 0) 737 { 738 _hold_nodes[k++] = new <T>AVLNode(u->item); 739 u = y.succ(u); 740 } 741 break; 742 } 743 else if (u == 0) 744 { 745 while (t != 0) 746 { 747 _hold_nodes[k++] = t; 748 t = succ(t); 749 } 750 break; 751 } 752 int cmp = <T>CMP(t->item, u->item); 753 if (cmp == 0) 754 { 755 _hold_nodes[k++] = t; 756 t = succ(t); 757 u = y.succ(u); 758 } 759 else if (cmp < 0) 760 { 761 _hold_nodes[k++] = t; 762 t = succ(t); 763 } 764 else 765 { 766 _hold_nodes[k++] = new <T>AVLNode(u->item); 767 u = y.succ(u); 768 } 769 } 770 root = _treeify(k); 771 count = k; 772} 773 774void <T>AVLSet::operator &= (<T>AVLSet& y) 775{ 776 <T>AVLNode* t = leftmost(); 777 <T>AVLNode* u = y.leftmost(); 778 int rsize = (count < y.count)? count : y.count; 779 _hold_nodes = new <T>AVLNodePtr [rsize]; 780 int k = 0; 781 for (;;) 782 { 783 if (t == 0) 784 break; 785 if (u == 0) 786 { 787 while (t != 0) 788 { 789 <T>AVLNode* tmp = succ(t); 790 delete t; 791 t = tmp; 792 } 793 break; 794 } 795 int cmp = <T>CMP(t->item, u->item); 796 if (cmp == 0) 797 { 798 _hold_nodes[k++] = t; 799 t = succ(t); 800 u = y.succ(u); 801 } 802 else if (cmp < 0) 803 { 804 <T>AVLNode* tmp = succ(t); 805 delete t; 806 t = tmp; 807 } 808 else 809 u = y.succ(u); 810 } 811 root = _treeify(k); 812 count = k; 813} 814 815 816void <T>AVLSet::operator -=(<T>AVLSet& y) 817{ 818 <T>AVLNode* t = leftmost(); 819 <T>AVLNode* u = y.leftmost(); 820 int rsize = count; 821 _hold_nodes = new <T>AVLNodePtr [rsize]; 822 int k = 0; 823 for (;;) 824 { 825 if (t == 0) 826 break; 827 else if (u == 0) 828 { 829 while (t != 0) 830 { 831 _hold_nodes[k++] = t; 832 t = succ(t); 833 } 834 break; 835 } 836 int cmp = <T>CMP(t->item, u->item); 837 if (cmp == 0) 838 { 839 <T>AVLNode* tmp = succ(t); 840 delete t; 841 t = tmp; 842 u = y.succ(u); 843 } 844 else if (cmp < 0) 845 { 846 _hold_nodes[k++] = t; 847 t = succ(t); 848 } 849 else 850 u = y.succ(u); 851 } 852 root = _treeify(k); 853 count = k; 854} 855 856int <T>AVLSet::owns(Pix i) 857{ 858 if (i == 0) return 0; 859 for (<T>AVLNode* t = leftmost(); t != 0; t = succ(t)) 860 if (Pix(t) == i) return 1; 861 return 0; 862} 863 864int <T>AVLSet::OK() 865{ 866 int v = 1; 867 if (root == 0) 868 v = count == 0; 869 else 870 { 871 int n = 1; 872 <T>AVLNode* trail = leftmost(); 873 <T>AVLNode* t = succ(trail); 874 while (t != 0) 875 { 876 ++n; 877 v &= <T>CMP(trail->item, t->item) < 0; 878 trail = t; 879 t = succ(t); 880 } 881 v &= n == count; 882 } 883 if (!v) error("invariant failure"); 884 return v; 885} 886