1 //===----------------------------------------------------------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is dual licensed under the MIT and the University of Illinois Open 6 // Source Licenses. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 10 // Not a portable test 11 12 // Returns __tree_next(__z) 13 // template <class _NodePtr> 14 // void 15 // __tree_remove(_NodePtr __root, _NodePtr __z) 16 17 #include <__tree> 18 #include <cassert> 19 20 struct Node 21 { 22 Node* __left_; 23 Node* __right_; 24 Node* __parent_; 25 bool __is_black_; 26 27 Node* __parent_unsafe() const { return __parent_; } 28 void __set_parent(Node* x) { __parent_ = x;} 29 30 Node() : __left_(), __right_(), __parent_(), __is_black_() {} 31 }; 32 33 void 34 test1() 35 { 36 { 37 // Left 38 // Case 1 -> Case 2 -> x is red turned to black 39 Node root; 40 Node b; 41 Node c; 42 Node d; 43 Node e; 44 Node y; 45 46 root.__left_ = &b; 47 48 b.__parent_ = &root; 49 b.__left_ = &y; 50 b.__right_ = &d; 51 b.__is_black_ = true; 52 53 y.__parent_ = &b; 54 y.__left_ = 0; 55 y.__right_ = 0; 56 y.__is_black_ = true; 57 58 d.__parent_ = &b; 59 d.__left_ = &c; 60 d.__right_ = &e; 61 d.__is_black_ = false; 62 63 c.__parent_ = &d; 64 c.__left_ = 0; 65 c.__right_ = 0; 66 c.__is_black_ = true; 67 68 e.__parent_ = &d; 69 e.__left_ = 0; 70 e.__right_ = 0; 71 e.__is_black_ = true; 72 73 std::__tree_remove(root.__left_, &y); 74 assert(std::__tree_invariant(root.__left_)); 75 76 assert(root.__parent_ == 0); 77 assert(root.__left_ == &d); 78 assert(root.__right_ == 0); 79 assert(root.__is_black_ == false); 80 81 assert(d.__parent_ == &root); 82 assert(d.__left_ == &b); 83 assert(d.__right_ == &e); 84 assert(d.__is_black_ == true); 85 86 assert(b.__parent_ == &d); 87 assert(b.__left_ == 0); 88 assert(b.__right_ == &c); 89 assert(b.__is_black_ == true); 90 91 assert(c.__parent_ == &b); 92 assert(c.__left_ == 0); 93 assert(c.__right_ == 0); 94 assert(c.__is_black_ == false); 95 96 assert(e.__parent_ == &d); 97 assert(e.__left_ == 0); 98 assert(e.__right_ == 0); 99 assert(e.__is_black_ == true); 100 } 101 { 102 // Right 103 // Case 1 -> Case 2 -> x is red turned to black 104 Node root; 105 Node b; 106 Node c; 107 Node d; 108 Node e; 109 Node y; 110 111 root.__left_ = &b; 112 113 b.__parent_ = &root; 114 b.__right_ = &y; 115 b.__left_ = &d; 116 b.__is_black_ = true; 117 118 y.__parent_ = &b; 119 y.__right_ = 0; 120 y.__left_ = 0; 121 y.__is_black_ = true; 122 123 d.__parent_ = &b; 124 d.__right_ = &c; 125 d.__left_ = &e; 126 d.__is_black_ = false; 127 128 c.__parent_ = &d; 129 c.__right_ = 0; 130 c.__left_ = 0; 131 c.__is_black_ = true; 132 133 e.__parent_ = &d; 134 e.__right_ = 0; 135 e.__left_ = 0; 136 e.__is_black_ = true; 137 138 std::__tree_remove(root.__left_, &y); 139 assert(std::__tree_invariant(root.__left_)); 140 141 assert(root.__parent_ == 0); 142 assert(root.__left_ == &d); 143 assert(root.__right_ == 0); 144 assert(root.__is_black_ == false); 145 146 assert(d.__parent_ == &root); 147 assert(d.__right_ == &b); 148 assert(d.__left_ == &e); 149 assert(d.__is_black_ == true); 150 151 assert(b.__parent_ == &d); 152 assert(b.__right_ == 0); 153 assert(b.__left_ == &c); 154 assert(b.__is_black_ == true); 155 156 assert(c.__parent_ == &b); 157 assert(c.__right_ == 0); 158 assert(c.__left_ == 0); 159 assert(c.__is_black_ == false); 160 161 assert(e.__parent_ == &d); 162 assert(e.__right_ == 0); 163 assert(e.__left_ == 0); 164 assert(e.__is_black_ == true); 165 } 166 { 167 // Left 168 // Case 1 -> Case 3 -> Case 4 169 Node root; 170 Node b; 171 Node c; 172 Node d; 173 Node e; 174 Node f; 175 Node y; 176 177 root.__left_ = &b; 178 179 b.__parent_ = &root; 180 b.__left_ = &y; 181 b.__right_ = &d; 182 b.__is_black_ = true; 183 184 y.__parent_ = &b; 185 y.__left_ = 0; 186 y.__right_ = 0; 187 y.__is_black_ = true; 188 189 d.__parent_ = &b; 190 d.__left_ = &c; 191 d.__right_ = &e; 192 d.__is_black_ = false; 193 194 c.__parent_ = &d; 195 c.__left_ = &f; 196 c.__right_ = 0; 197 c.__is_black_ = true; 198 199 e.__parent_ = &d; 200 e.__left_ = 0; 201 e.__right_ = 0; 202 e.__is_black_ = true; 203 204 f.__parent_ = &c; 205 f.__left_ = 0; 206 f.__right_ = 0; 207 f.__is_black_ = false; 208 209 std::__tree_remove(root.__left_, &y); 210 assert(std::__tree_invariant(root.__left_)); 211 212 assert(root.__parent_ == 0); 213 assert(root.__left_ == &d); 214 assert(root.__right_ == 0); 215 assert(root.__is_black_ == false); 216 217 assert(d.__parent_ == &root); 218 assert(d.__left_ == &f); 219 assert(d.__right_ == &e); 220 assert(d.__is_black_ == true); 221 222 assert(f.__parent_ == &d); 223 assert(f.__left_ == &b); 224 assert(f.__right_ == &c); 225 assert(f.__is_black_ == false); 226 227 assert(b.__parent_ == &f); 228 assert(b.__left_ == 0); 229 assert(b.__right_ == 0); 230 assert(b.__is_black_ == true); 231 232 assert(c.__parent_ == &f); 233 assert(c.__left_ == 0); 234 assert(c.__right_ == 0); 235 assert(c.__is_black_ == true); 236 237 assert(e.__parent_ == &d); 238 assert(e.__left_ == 0); 239 assert(e.__right_ == 0); 240 assert(e.__is_black_ == true); 241 } 242 { 243 // Right 244 // Case 1 -> Case 3 -> Case 4 245 Node root; 246 Node b; 247 Node c; 248 Node d; 249 Node e; 250 Node f; 251 Node y; 252 253 root.__left_ = &b; 254 255 b.__parent_ = &root; 256 b.__right_ = &y; 257 b.__left_ = &d; 258 b.__is_black_ = true; 259 260 y.__parent_ = &b; 261 y.__right_ = 0; 262 y.__left_ = 0; 263 y.__is_black_ = true; 264 265 d.__parent_ = &b; 266 d.__right_ = &c; 267 d.__left_ = &e; 268 d.__is_black_ = false; 269 270 c.__parent_ = &d; 271 c.__right_ = &f; 272 c.__left_ = 0; 273 c.__is_black_ = true; 274 275 e.__parent_ = &d; 276 e.__right_ = 0; 277 e.__left_ = 0; 278 e.__is_black_ = true; 279 280 f.__parent_ = &c; 281 f.__right_ = 0; 282 f.__left_ = 0; 283 f.__is_black_ = false; 284 285 std::__tree_remove(root.__left_, &y); 286 assert(std::__tree_invariant(root.__left_)); 287 288 assert(root.__parent_ == 0); 289 assert(root.__left_ == &d); 290 assert(root.__right_ == 0); 291 assert(root.__is_black_ == false); 292 293 assert(d.__parent_ == &root); 294 assert(d.__right_ == &f); 295 assert(d.__left_ == &e); 296 assert(d.__is_black_ == true); 297 298 assert(f.__parent_ == &d); 299 assert(f.__right_ == &b); 300 assert(f.__left_ == &c); 301 assert(f.__is_black_ == false); 302 303 assert(b.__parent_ == &f); 304 assert(b.__right_ == 0); 305 assert(b.__left_ == 0); 306 assert(b.__is_black_ == true); 307 308 assert(c.__parent_ == &f); 309 assert(c.__right_ == 0); 310 assert(c.__left_ == 0); 311 assert(c.__is_black_ == true); 312 313 assert(e.__parent_ == &d); 314 assert(e.__right_ == 0); 315 assert(e.__left_ == 0); 316 assert(e.__is_black_ == true); 317 } 318 } 319 320 void 321 test2() 322 { 323 { 324 Node root; 325 Node a; 326 Node b; 327 Node c; 328 329 root.__left_ = &b; 330 331 b.__parent_ = &root; 332 b.__left_ = &a; 333 b.__right_ = &c; 334 b.__is_black_ = true; 335 336 a.__parent_ = &b; 337 a.__left_ = 0; 338 a.__right_ = 0; 339 a.__is_black_ = true; 340 341 c.__parent_ = &b; 342 c.__left_ = 0; 343 c.__right_ = 0; 344 c.__is_black_ = true; 345 346 std::__tree_remove(root.__left_, &a); 347 348 assert(std::__tree_invariant(root.__left_)); 349 350 assert(root.__parent_ == 0); 351 assert(root.__left_ == &b); 352 assert(root.__right_ == 0); 353 assert(root.__is_black_ == false); 354 355 assert(b.__parent_ == &root); 356 assert(b.__left_ == 0); 357 assert(b.__right_ == &c); 358 assert(b.__is_black_ == true); 359 360 assert(c.__parent_ == &b); 361 assert(c.__left_ == 0); 362 assert(c.__right_ == 0); 363 assert(c.__is_black_ == false); 364 365 std::__tree_remove(root.__left_, &b); 366 367 assert(std::__tree_invariant(root.__left_)); 368 369 assert(root.__parent_ == 0); 370 assert(root.__left_ == &c); 371 assert(root.__right_ == 0); 372 assert(root.__is_black_ == false); 373 374 assert(c.__parent_ == &root); 375 assert(c.__left_ == 0); 376 assert(c.__right_ == 0); 377 assert(c.__is_black_ == true); 378 379 std::__tree_remove(root.__left_, &c); 380 381 assert(std::__tree_invariant(root.__left_)); 382 383 assert(root.__parent_ == 0); 384 assert(root.__left_ == 0); 385 assert(root.__right_ == 0); 386 assert(root.__is_black_ == false); 387 } 388 { 389 Node root; 390 Node a; 391 Node b; 392 Node c; 393 394 root.__left_ = &b; 395 396 b.__parent_ = &root; 397 b.__left_ = &a; 398 b.__right_ = &c; 399 b.__is_black_ = true; 400 401 a.__parent_ = &b; 402 a.__left_ = 0; 403 a.__right_ = 0; 404 a.__is_black_ = false; 405 406 c.__parent_ = &b; 407 c.__left_ = 0; 408 c.__right_ = 0; 409 c.__is_black_ = false; 410 411 std::__tree_remove(root.__left_, &a); 412 413 assert(std::__tree_invariant(root.__left_)); 414 415 assert(root.__parent_ == 0); 416 assert(root.__left_ == &b); 417 assert(root.__right_ == 0); 418 assert(root.__is_black_ == false); 419 420 assert(b.__parent_ == &root); 421 assert(b.__left_ == 0); 422 assert(b.__right_ == &c); 423 assert(b.__is_black_ == true); 424 425 assert(c.__parent_ == &b); 426 assert(c.__left_ == 0); 427 assert(c.__right_ == 0); 428 assert(c.__is_black_ == false); 429 430 std::__tree_remove(root.__left_, &b); 431 432 assert(std::__tree_invariant(root.__left_)); 433 434 assert(root.__parent_ == 0); 435 assert(root.__left_ == &c); 436 assert(root.__right_ == 0); 437 assert(root.__is_black_ == false); 438 439 assert(c.__parent_ == &root); 440 assert(c.__left_ == 0); 441 assert(c.__right_ == 0); 442 assert(c.__is_black_ == true); 443 444 std::__tree_remove(root.__left_, &c); 445 446 assert(std::__tree_invariant(root.__left_)); 447 448 assert(root.__parent_ == 0); 449 assert(root.__left_ == 0); 450 assert(root.__right_ == 0); 451 assert(root.__is_black_ == false); 452 } 453 { 454 Node root; 455 Node a; 456 Node b; 457 Node c; 458 459 root.__left_ = &b; 460 461 b.__parent_ = &root; 462 b.__left_ = &a; 463 b.__right_ = &c; 464 b.__is_black_ = true; 465 466 a.__parent_ = &b; 467 a.__left_ = 0; 468 a.__right_ = 0; 469 a.__is_black_ = true; 470 471 c.__parent_ = &b; 472 c.__left_ = 0; 473 c.__right_ = 0; 474 c.__is_black_ = true; 475 476 std::__tree_remove(root.__left_, &a); 477 478 assert(std::__tree_invariant(root.__left_)); 479 480 assert(root.__parent_ == 0); 481 assert(root.__left_ == &b); 482 assert(root.__right_ == 0); 483 assert(root.__is_black_ == false); 484 485 assert(b.__parent_ == &root); 486 assert(b.__left_ == 0); 487 assert(b.__right_ == &c); 488 assert(b.__is_black_ == true); 489 490 assert(c.__parent_ == &b); 491 assert(c.__left_ == 0); 492 assert(c.__right_ == 0); 493 assert(c.__is_black_ == false); 494 495 std::__tree_remove(root.__left_, &c); 496 497 assert(std::__tree_invariant(root.__left_)); 498 499 assert(root.__parent_ == 0); 500 assert(root.__left_ == &b); 501 assert(root.__right_ == 0); 502 assert(root.__is_black_ == false); 503 504 assert(b.__parent_ == &root); 505 assert(b.__left_ == 0); 506 assert(b.__right_ == 0); 507 assert(b.__is_black_ == true); 508 509 std::__tree_remove(root.__left_, &b); 510 511 assert(std::__tree_invariant(root.__left_)); 512 513 assert(root.__parent_ == 0); 514 assert(root.__left_ == 0); 515 assert(root.__right_ == 0); 516 assert(root.__is_black_ == false); 517 } 518 { 519 Node root; 520 Node a; 521 Node b; 522 Node c; 523 524 root.__left_ = &b; 525 526 b.__parent_ = &root; 527 b.__left_ = &a; 528 b.__right_ = &c; 529 b.__is_black_ = true; 530 531 a.__parent_ = &b; 532 a.__left_ = 0; 533 a.__right_ = 0; 534 a.__is_black_ = false; 535 536 c.__parent_ = &b; 537 c.__left_ = 0; 538 c.__right_ = 0; 539 c.__is_black_ = false; 540 541 std::__tree_remove(root.__left_, &a); 542 543 assert(std::__tree_invariant(root.__left_)); 544 545 assert(root.__parent_ == 0); 546 assert(root.__left_ == &b); 547 assert(root.__right_ == 0); 548 assert(root.__is_black_ == false); 549 550 assert(b.__parent_ == &root); 551 assert(b.__left_ == 0); 552 assert(b.__right_ == &c); 553 assert(b.__is_black_ == true); 554 555 assert(c.__parent_ == &b); 556 assert(c.__left_ == 0); 557 assert(c.__right_ == 0); 558 assert(c.__is_black_ == false); 559 560 std::__tree_remove(root.__left_, &c); 561 562 assert(std::__tree_invariant(root.__left_)); 563 564 assert(root.__parent_ == 0); 565 assert(root.__left_ == &b); 566 assert(root.__right_ == 0); 567 assert(root.__is_black_ == false); 568 569 assert(b.__parent_ == &root); 570 assert(b.__left_ == 0); 571 assert(b.__right_ == 0); 572 assert(b.__is_black_ == true); 573 574 std::__tree_remove(root.__left_, &b); 575 576 assert(std::__tree_invariant(root.__left_)); 577 578 assert(root.__parent_ == 0); 579 assert(root.__left_ == 0); 580 assert(root.__right_ == 0); 581 assert(root.__is_black_ == false); 582 } 583 { 584 Node root; 585 Node a; 586 Node b; 587 Node c; 588 589 root.__left_ = &b; 590 591 b.__parent_ = &root; 592 b.__left_ = &a; 593 b.__right_ = &c; 594 b.__is_black_ = true; 595 596 a.__parent_ = &b; 597 a.__left_ = 0; 598 a.__right_ = 0; 599 a.__is_black_ = true; 600 601 c.__parent_ = &b; 602 c.__left_ = 0; 603 c.__right_ = 0; 604 c.__is_black_ = true; 605 606 std::__tree_remove(root.__left_, &b); 607 608 assert(std::__tree_invariant(root.__left_)); 609 610 assert(root.__parent_ == 0); 611 assert(root.__left_ == &c); 612 assert(root.__right_ == 0); 613 assert(root.__is_black_ == false); 614 615 assert(a.__parent_ == &c); 616 assert(a.__left_ == 0); 617 assert(a.__right_ == 0); 618 assert(a.__is_black_ == false); 619 620 assert(c.__parent_ == &root); 621 assert(c.__left_ == &a); 622 assert(c.__right_ == 0); 623 assert(c.__is_black_ == true); 624 625 std::__tree_remove(root.__left_, &a); 626 627 assert(std::__tree_invariant(root.__left_)); 628 629 assert(root.__parent_ == 0); 630 assert(root.__left_ == &c); 631 assert(root.__right_ == 0); 632 assert(root.__is_black_ == false); 633 634 assert(c.__parent_ == &root); 635 assert(c.__left_ == 0); 636 assert(c.__right_ == 0); 637 assert(c.__is_black_ == true); 638 639 std::__tree_remove(root.__left_, &c); 640 641 assert(std::__tree_invariant(root.__left_)); 642 643 assert(root.__parent_ == 0); 644 assert(root.__left_ == 0); 645 assert(root.__right_ == 0); 646 assert(root.__is_black_ == false); 647 } 648 { 649 Node root; 650 Node a; 651 Node b; 652 Node c; 653 654 root.__left_ = &b; 655 656 b.__parent_ = &root; 657 b.__left_ = &a; 658 b.__right_ = &c; 659 b.__is_black_ = true; 660 661 a.__parent_ = &b; 662 a.__left_ = 0; 663 a.__right_ = 0; 664 a.__is_black_ = false; 665 666 c.__parent_ = &b; 667 c.__left_ = 0; 668 c.__right_ = 0; 669 c.__is_black_ = false; 670 671 std::__tree_remove(root.__left_, &b); 672 673 assert(std::__tree_invariant(root.__left_)); 674 675 assert(root.__parent_ == 0); 676 assert(root.__left_ == &c); 677 assert(root.__right_ == 0); 678 assert(root.__is_black_ == false); 679 680 assert(a.__parent_ == &c); 681 assert(a.__left_ == 0); 682 assert(a.__right_ == 0); 683 assert(a.__is_black_ == false); 684 685 assert(c.__parent_ == &root); 686 assert(c.__left_ == &a); 687 assert(c.__right_ == 0); 688 assert(c.__is_black_ == true); 689 690 std::__tree_remove(root.__left_, &a); 691 692 assert(std::__tree_invariant(root.__left_)); 693 694 assert(root.__parent_ == 0); 695 assert(root.__left_ == &c); 696 assert(root.__right_ == 0); 697 assert(root.__is_black_ == false); 698 699 assert(c.__parent_ == &root); 700 assert(c.__left_ == 0); 701 assert(c.__right_ == 0); 702 assert(c.__is_black_ == true); 703 704 std::__tree_remove(root.__left_, &c); 705 706 assert(std::__tree_invariant(root.__left_)); 707 708 assert(root.__parent_ == 0); 709 assert(root.__left_ == 0); 710 assert(root.__right_ == 0); 711 assert(root.__is_black_ == false); 712 } 713 { 714 Node root; 715 Node a; 716 Node b; 717 Node c; 718 719 root.__left_ = &b; 720 721 b.__parent_ = &root; 722 b.__left_ = &a; 723 b.__right_ = &c; 724 b.__is_black_ = true; 725 726 a.__parent_ = &b; 727 a.__left_ = 0; 728 a.__right_ = 0; 729 a.__is_black_ = true; 730 731 c.__parent_ = &b; 732 c.__left_ = 0; 733 c.__right_ = 0; 734 c.__is_black_ = true; 735 736 std::__tree_remove(root.__left_, &b); 737 738 assert(std::__tree_invariant(root.__left_)); 739 740 assert(root.__parent_ == 0); 741 assert(root.__left_ == &c); 742 assert(root.__right_ == 0); 743 assert(root.__is_black_ == false); 744 745 assert(a.__parent_ == &c); 746 assert(a.__left_ == 0); 747 assert(a.__right_ == 0); 748 assert(a.__is_black_ == false); 749 750 assert(c.__parent_ == &root); 751 assert(c.__left_ == &a); 752 assert(c.__right_ == 0); 753 assert(c.__is_black_ == true); 754 755 std::__tree_remove(root.__left_, &c); 756 757 assert(std::__tree_invariant(root.__left_)); 758 759 assert(root.__parent_ == 0); 760 assert(root.__left_ == &a); 761 assert(root.__right_ == 0); 762 assert(root.__is_black_ == false); 763 764 assert(a.__parent_ == &root); 765 assert(a.__left_ == 0); 766 assert(a.__right_ == 0); 767 assert(a.__is_black_ == true); 768 769 std::__tree_remove(root.__left_, &a); 770 771 assert(std::__tree_invariant(root.__left_)); 772 773 assert(root.__parent_ == 0); 774 assert(root.__left_ == 0); 775 assert(root.__right_ == 0); 776 assert(root.__is_black_ == false); 777 } 778 { 779 Node root; 780 Node a; 781 Node b; 782 Node c; 783 784 root.__left_ = &b; 785 786 b.__parent_ = &root; 787 b.__left_ = &a; 788 b.__right_ = &c; 789 b.__is_black_ = true; 790 791 a.__parent_ = &b; 792 a.__left_ = 0; 793 a.__right_ = 0; 794 a.__is_black_ = false; 795 796 c.__parent_ = &b; 797 c.__left_ = 0; 798 c.__right_ = 0; 799 c.__is_black_ = false; 800 801 std::__tree_remove(root.__left_, &b); 802 803 assert(std::__tree_invariant(root.__left_)); 804 805 assert(root.__parent_ == 0); 806 assert(root.__left_ == &c); 807 assert(root.__right_ == 0); 808 assert(root.__is_black_ == false); 809 810 assert(a.__parent_ == &c); 811 assert(a.__left_ == 0); 812 assert(a.__right_ == 0); 813 assert(a.__is_black_ == false); 814 815 assert(c.__parent_ == &root); 816 assert(c.__left_ == &a); 817 assert(c.__right_ == 0); 818 assert(c.__is_black_ == true); 819 820 std::__tree_remove(root.__left_, &c); 821 822 assert(std::__tree_invariant(root.__left_)); 823 824 assert(root.__parent_ == 0); 825 assert(root.__left_ == &a); 826 assert(root.__right_ == 0); 827 assert(root.__is_black_ == false); 828 829 assert(a.__parent_ == &root); 830 assert(a.__left_ == 0); 831 assert(a.__right_ == 0); 832 assert(a.__is_black_ == true); 833 834 std::__tree_remove(root.__left_, &a); 835 836 assert(std::__tree_invariant(root.__left_)); 837 838 assert(root.__parent_ == 0); 839 assert(root.__left_ == 0); 840 assert(root.__right_ == 0); 841 assert(root.__is_black_ == false); 842 } 843 { 844 Node root; 845 Node a; 846 Node b; 847 Node c; 848 849 root.__left_ = &b; 850 851 b.__parent_ = &root; 852 b.__left_ = &a; 853 b.__right_ = &c; 854 b.__is_black_ = true; 855 856 a.__parent_ = &b; 857 a.__left_ = 0; 858 a.__right_ = 0; 859 a.__is_black_ = true; 860 861 c.__parent_ = &b; 862 c.__left_ = 0; 863 c.__right_ = 0; 864 c.__is_black_ = true; 865 866 std::__tree_remove(root.__left_, &c); 867 868 assert(std::__tree_invariant(root.__left_)); 869 870 assert(root.__parent_ == 0); 871 assert(root.__left_ == &b); 872 assert(root.__right_ == 0); 873 assert(root.__is_black_ == false); 874 875 assert(a.__parent_ == &b); 876 assert(a.__left_ == 0); 877 assert(a.__right_ == 0); 878 assert(a.__is_black_ == false); 879 880 assert(b.__parent_ == &root); 881 assert(b.__left_ == &a); 882 assert(b.__right_ == 0); 883 assert(b.__is_black_ == true); 884 885 std::__tree_remove(root.__left_, &b); 886 887 assert(std::__tree_invariant(root.__left_)); 888 889 assert(root.__parent_ == 0); 890 assert(root.__left_ == &a); 891 assert(root.__right_ == 0); 892 assert(root.__is_black_ == false); 893 894 assert(a.__parent_ == &root); 895 assert(a.__left_ == 0); 896 assert(a.__right_ == 0); 897 assert(a.__is_black_ == true); 898 899 std::__tree_remove(root.__left_, &a); 900 901 assert(std::__tree_invariant(root.__left_)); 902 903 assert(root.__parent_ == 0); 904 assert(root.__left_ == 0); 905 assert(root.__right_ == 0); 906 assert(root.__is_black_ == false); 907 } 908 { 909 Node root; 910 Node a; 911 Node b; 912 Node c; 913 914 root.__left_ = &b; 915 916 b.__parent_ = &root; 917 b.__left_ = &a; 918 b.__right_ = &c; 919 b.__is_black_ = true; 920 921 a.__parent_ = &b; 922 a.__left_ = 0; 923 a.__right_ = 0; 924 a.__is_black_ = false; 925 926 c.__parent_ = &b; 927 c.__left_ = 0; 928 c.__right_ = 0; 929 c.__is_black_ = false; 930 931 std::__tree_remove(root.__left_, &c); 932 933 assert(std::__tree_invariant(root.__left_)); 934 935 assert(root.__parent_ == 0); 936 assert(root.__left_ == &b); 937 assert(root.__right_ == 0); 938 assert(root.__is_black_ == false); 939 940 assert(a.__parent_ == &b); 941 assert(a.__left_ == 0); 942 assert(a.__right_ == 0); 943 assert(a.__is_black_ == false); 944 945 assert(b.__parent_ == &root); 946 assert(b.__left_ == &a); 947 assert(b.__right_ == 0); 948 assert(b.__is_black_ == true); 949 950 std::__tree_remove(root.__left_, &b); 951 952 assert(std::__tree_invariant(root.__left_)); 953 954 assert(root.__parent_ == 0); 955 assert(root.__left_ == &a); 956 assert(root.__right_ == 0); 957 assert(root.__is_black_ == false); 958 959 assert(a.__parent_ == &root); 960 assert(a.__left_ == 0); 961 assert(a.__right_ == 0); 962 assert(a.__is_black_ == true); 963 964 std::__tree_remove(root.__left_, &a); 965 966 assert(std::__tree_invariant(root.__left_)); 967 968 assert(root.__parent_ == 0); 969 assert(root.__left_ == 0); 970 assert(root.__right_ == 0); 971 assert(root.__is_black_ == false); 972 } 973 { 974 Node root; 975 Node a; 976 Node b; 977 Node c; 978 979 root.__left_ = &b; 980 981 b.__parent_ = &root; 982 b.__left_ = &a; 983 b.__right_ = &c; 984 b.__is_black_ = true; 985 986 a.__parent_ = &b; 987 a.__left_ = 0; 988 a.__right_ = 0; 989 a.__is_black_ = true; 990 991 c.__parent_ = &b; 992 c.__left_ = 0; 993 c.__right_ = 0; 994 c.__is_black_ = true; 995 996 std::__tree_remove(root.__left_, &c); 997 998 assert(std::__tree_invariant(root.__left_)); 999 1000 assert(root.__parent_ == 0); 1001 assert(root.__left_ == &b); 1002 assert(root.__right_ == 0); 1003 assert(root.__is_black_ == false); 1004 1005 assert(a.__parent_ == &b); 1006 assert(a.__left_ == 0); 1007 assert(a.__right_ == 0); 1008 assert(a.__is_black_ == false); 1009 1010 assert(b.__parent_ == &root); 1011 assert(b.__left_ == &a); 1012 assert(b.__right_ == 0); 1013 assert(b.__is_black_ == true); 1014 1015 std::__tree_remove(root.__left_, &a); 1016 1017 assert(std::__tree_invariant(root.__left_)); 1018 1019 assert(root.__parent_ == 0); 1020 assert(root.__left_ == &b); 1021 assert(root.__right_ == 0); 1022 assert(root.__is_black_ == false); 1023 1024 assert(b.__parent_ == &root); 1025 assert(b.__left_ == 0); 1026 assert(b.__right_ == 0); 1027 assert(b.__is_black_ == true); 1028 1029 std::__tree_remove(root.__left_, &b); 1030 1031 assert(std::__tree_invariant(root.__left_)); 1032 1033 assert(root.__parent_ == 0); 1034 assert(root.__left_ == 0); 1035 assert(root.__right_ == 0); 1036 assert(root.__is_black_ == false); 1037 } 1038 { 1039 Node root; 1040 Node a; 1041 Node b; 1042 Node c; 1043 1044 root.__left_ = &b; 1045 1046 b.__parent_ = &root; 1047 b.__left_ = &a; 1048 b.__right_ = &c; 1049 b.__is_black_ = true; 1050 1051 a.__parent_ = &b; 1052 a.__left_ = 0; 1053 a.__right_ = 0; 1054 a.__is_black_ = false; 1055 1056 c.__parent_ = &b; 1057 c.__left_ = 0; 1058 c.__right_ = 0; 1059 c.__is_black_ = false; 1060 1061 std::__tree_remove(root.__left_, &c); 1062 1063 assert(std::__tree_invariant(root.__left_)); 1064 1065 assert(root.__parent_ == 0); 1066 assert(root.__left_ == &b); 1067 assert(root.__right_ == 0); 1068 assert(root.__is_black_ == false); 1069 1070 assert(a.__parent_ == &b); 1071 assert(a.__left_ == 0); 1072 assert(a.__right_ == 0); 1073 assert(a.__is_black_ == false); 1074 1075 assert(b.__parent_ == &root); 1076 assert(b.__left_ == &a); 1077 assert(b.__right_ == 0); 1078 assert(b.__is_black_ == true); 1079 1080 std::__tree_remove(root.__left_, &a); 1081 1082 assert(std::__tree_invariant(root.__left_)); 1083 1084 assert(root.__parent_ == 0); 1085 assert(root.__left_ == &b); 1086 assert(root.__right_ == 0); 1087 assert(root.__is_black_ == false); 1088 1089 assert(b.__parent_ == &root); 1090 assert(b.__left_ == 0); 1091 assert(b.__right_ == 0); 1092 assert(b.__is_black_ == true); 1093 1094 std::__tree_remove(root.__left_, &b); 1095 1096 assert(std::__tree_invariant(root.__left_)); 1097 1098 assert(root.__parent_ == 0); 1099 assert(root.__left_ == 0); 1100 assert(root.__right_ == 0); 1101 assert(root.__is_black_ == false); 1102 } 1103 } 1104 1105 void 1106 test3() 1107 { 1108 Node root; 1109 Node a; 1110 Node b; 1111 Node c; 1112 Node d; 1113 Node e; 1114 Node f; 1115 Node g; 1116 Node h; 1117 1118 root.__left_ = &e; 1119 1120 e.__parent_ = &root; 1121 e.__left_ = &c; 1122 e.__right_ = &g; 1123 e.__is_black_ = true; 1124 1125 c.__parent_ = &e; 1126 c.__left_ = &b; 1127 c.__right_ = &d; 1128 c.__is_black_ = false; 1129 1130 g.__parent_ = &e; 1131 g.__left_ = &f; 1132 g.__right_ = &h; 1133 g.__is_black_ = false; 1134 1135 b.__parent_ = &c; 1136 b.__left_ = &a; 1137 b.__right_ = 0; 1138 b.__is_black_ = true; 1139 1140 d.__parent_ = &c; 1141 d.__left_ = 0; 1142 d.__right_ = 0; 1143 d.__is_black_ = true; 1144 1145 f.__parent_ = &g; 1146 f.__left_ = 0; 1147 f.__right_ = 0; 1148 f.__is_black_ = true; 1149 1150 h.__parent_ = &g; 1151 h.__left_ = 0; 1152 h.__right_ = 0; 1153 h.__is_black_ = true; 1154 1155 a.__parent_ = &b; 1156 a.__left_ = 0; 1157 a.__right_ = 0; 1158 a.__is_black_ = false; 1159 1160 assert(std::__tree_invariant(root.__left_)); 1161 1162 std::__tree_remove(root.__left_, &h); 1163 1164 assert(std::__tree_invariant(root.__left_)); 1165 1166 assert(root.__parent_ == 0); 1167 assert(root.__left_ == &e); 1168 assert(root.__right_ == 0); 1169 assert(root.__is_black_ == false); 1170 1171 assert(e.__parent_ == &root); 1172 assert(e.__left_ == &c); 1173 assert(e.__right_ == &g); 1174 assert(e.__is_black_ == true); 1175 1176 assert(c.__parent_ == &e); 1177 assert(c.__left_ == &b); 1178 assert(c.__right_ == &d); 1179 assert(c.__is_black_ == false); 1180 1181 assert(g.__parent_ == &e); 1182 assert(g.__left_ == &f); 1183 assert(g.__right_ == 0); 1184 assert(g.__is_black_ == true); 1185 1186 assert(b.__parent_ == &c); 1187 assert(b.__left_ == &a); 1188 assert(b.__right_ == 0); 1189 assert(b.__is_black_ == true); 1190 1191 assert(a.__parent_ == &b); 1192 assert(a.__left_ == 0); 1193 assert(a.__right_ == 0); 1194 assert(a.__is_black_ == false); 1195 1196 assert(d.__parent_ == &c); 1197 assert(d.__left_ == 0); 1198 assert(d.__right_ == 0); 1199 assert(d.__is_black_ == true); 1200 1201 assert(f.__parent_ == &g); 1202 assert(f.__left_ == 0); 1203 assert(f.__right_ == 0); 1204 assert(f.__is_black_ == false); 1205 1206 std::__tree_remove(root.__left_, &g); 1207 1208 assert(std::__tree_invariant(root.__left_)); 1209 1210 assert(root.__parent_ == 0); 1211 assert(root.__left_ == &e); 1212 assert(root.__right_ == 0); 1213 assert(root.__is_black_ == false); 1214 1215 assert(e.__parent_ == &root); 1216 assert(e.__left_ == &c); 1217 assert(e.__right_ == &f); 1218 assert(e.__is_black_ == true); 1219 1220 assert(c.__parent_ == &e); 1221 assert(c.__left_ == &b); 1222 assert(c.__right_ == &d); 1223 assert(c.__is_black_ == false); 1224 1225 assert(b.__parent_ == &c); 1226 assert(b.__left_ == &a); 1227 assert(b.__right_ == 0); 1228 assert(b.__is_black_ == true); 1229 1230 assert(a.__parent_ == &b); 1231 assert(a.__left_ == 0); 1232 assert(a.__right_ == 0); 1233 assert(a.__is_black_ == false); 1234 1235 assert(d.__parent_ == &c); 1236 assert(d.__left_ == 0); 1237 assert(d.__right_ == 0); 1238 assert(d.__is_black_ == true); 1239 1240 assert(f.__parent_ == &e); 1241 assert(f.__left_ == 0); 1242 assert(f.__right_ == 0); 1243 assert(f.__is_black_ == true); 1244 1245 std::__tree_remove(root.__left_, &f); 1246 1247 assert(std::__tree_invariant(root.__left_)); 1248 1249 assert(root.__parent_ == 0); 1250 assert(root.__left_ == &c); 1251 assert(root.__right_ == 0); 1252 assert(root.__is_black_ == false); 1253 1254 assert(c.__parent_ == &root); 1255 assert(c.__left_ == &b); 1256 assert(c.__right_ == &e); 1257 assert(c.__is_black_ == true); 1258 1259 assert(b.__parent_ == &c); 1260 assert(b.__left_ == &a); 1261 assert(b.__right_ == 0); 1262 assert(b.__is_black_ == true); 1263 1264 assert(e.__parent_ == &c); 1265 assert(e.__left_ == &d); 1266 assert(e.__right_ == 0); 1267 assert(e.__is_black_ == true); 1268 1269 assert(a.__parent_ == &b); 1270 assert(a.__left_ == 0); 1271 assert(a.__right_ == 0); 1272 assert(a.__is_black_ == false); 1273 1274 assert(d.__parent_ == &e); 1275 assert(d.__left_ == 0); 1276 assert(d.__right_ == 0); 1277 assert(d.__is_black_ == false); 1278 1279 std::__tree_remove(root.__left_, &e); 1280 1281 assert(std::__tree_invariant(root.__left_)); 1282 1283 assert(root.__parent_ == 0); 1284 assert(root.__left_ == &c); 1285 assert(root.__right_ == 0); 1286 assert(root.__is_black_ == false); 1287 1288 assert(c.__parent_ == &root); 1289 assert(c.__left_ == &b); 1290 assert(c.__right_ == &d); 1291 assert(c.__is_black_ == true); 1292 1293 assert(b.__parent_ == &c); 1294 assert(b.__left_ == &a); 1295 assert(b.__right_ == 0); 1296 assert(b.__is_black_ == true); 1297 1298 assert(a.__parent_ == &b); 1299 assert(a.__left_ == 0); 1300 assert(a.__right_ == 0); 1301 assert(a.__is_black_ == false); 1302 1303 assert(d.__parent_ == &c); 1304 assert(d.__left_ == 0); 1305 assert(d.__right_ == 0); 1306 assert(d.__is_black_ == true); 1307 1308 std::__tree_remove(root.__left_, &d); 1309 1310 assert(std::__tree_invariant(root.__left_)); 1311 1312 assert(root.__parent_ == 0); 1313 assert(root.__left_ == &b); 1314 assert(root.__right_ == 0); 1315 assert(root.__is_black_ == false); 1316 1317 assert(b.__parent_ == &root); 1318 assert(b.__left_ == &a); 1319 assert(b.__right_ == &c); 1320 assert(b.__is_black_ == true); 1321 1322 assert(a.__parent_ == &b); 1323 assert(a.__left_ == 0); 1324 assert(a.__right_ == 0); 1325 assert(a.__is_black_ == true); 1326 1327 assert(c.__parent_ == &b); 1328 assert(c.__left_ == 0); 1329 assert(c.__right_ == 0); 1330 assert(c.__is_black_ == true); 1331 1332 std::__tree_remove(root.__left_, &c); 1333 1334 assert(std::__tree_invariant(root.__left_)); 1335 1336 assert(root.__parent_ == 0); 1337 assert(root.__left_ == &b); 1338 assert(root.__right_ == 0); 1339 assert(root.__is_black_ == false); 1340 1341 assert(b.__parent_ == &root); 1342 assert(b.__left_ == &a); 1343 assert(b.__right_ == 0); 1344 assert(b.__is_black_ == true); 1345 1346 assert(a.__parent_ == &b); 1347 assert(a.__left_ == 0); 1348 assert(a.__right_ == 0); 1349 assert(a.__is_black_ == false); 1350 1351 std::__tree_remove(root.__left_, &b); 1352 1353 assert(std::__tree_invariant(root.__left_)); 1354 1355 assert(root.__parent_ == 0); 1356 assert(root.__left_ == &a); 1357 assert(root.__right_ == 0); 1358 assert(root.__is_black_ == false); 1359 1360 assert(a.__parent_ == &root); 1361 assert(a.__left_ == 0); 1362 assert(a.__right_ == 0); 1363 assert(a.__is_black_ == true); 1364 1365 std::__tree_remove(root.__left_, &a); 1366 1367 assert(std::__tree_invariant(root.__left_)); 1368 1369 assert(root.__parent_ == 0); 1370 assert(root.__left_ == 0); 1371 assert(root.__right_ == 0); 1372 assert(root.__is_black_ == false); 1373 } 1374 1375 void 1376 test4() 1377 { 1378 Node root; 1379 Node a; 1380 Node b; 1381 Node c; 1382 Node d; 1383 Node e; 1384 Node f; 1385 Node g; 1386 Node h; 1387 1388 root.__left_ = &d; 1389 1390 d.__parent_ = &root; 1391 d.__left_ = &b; 1392 d.__right_ = &f; 1393 d.__is_black_ = true; 1394 1395 b.__parent_ = &d; 1396 b.__left_ = &a; 1397 b.__right_ = &c; 1398 b.__is_black_ = false; 1399 1400 f.__parent_ = &d; 1401 f.__left_ = &e; 1402 f.__right_ = &g; 1403 f.__is_black_ = false; 1404 1405 a.__parent_ = &b; 1406 a.__left_ = 0; 1407 a.__right_ = 0; 1408 a.__is_black_ = true; 1409 1410 c.__parent_ = &b; 1411 c.__left_ = 0; 1412 c.__right_ = 0; 1413 c.__is_black_ = true; 1414 1415 e.__parent_ = &f; 1416 e.__left_ = 0; 1417 e.__right_ = 0; 1418 e.__is_black_ = true; 1419 1420 g.__parent_ = &f; 1421 g.__left_ = 0; 1422 g.__right_ = &h; 1423 g.__is_black_ = true; 1424 1425 h.__parent_ = &g; 1426 h.__left_ = 0; 1427 h.__right_ = 0; 1428 h.__is_black_ = false; 1429 1430 assert(std::__tree_invariant(root.__left_)); 1431 1432 std::__tree_remove(root.__left_, &a); 1433 1434 assert(std::__tree_invariant(root.__left_)); 1435 1436 assert(root.__parent_ == 0); 1437 assert(root.__left_ == &d); 1438 assert(root.__right_ == 0); 1439 assert(root.__is_black_ == false); 1440 1441 assert(d.__parent_ == &root); 1442 assert(d.__left_ == &b); 1443 assert(d.__right_ == &f); 1444 assert(d.__is_black_ == true); 1445 1446 assert(b.__parent_ == &d); 1447 assert(b.__left_ == 0); 1448 assert(b.__right_ == &c); 1449 assert(b.__is_black_ == true); 1450 1451 assert(f.__parent_ == &d); 1452 assert(f.__left_ == &e); 1453 assert(f.__right_ == &g); 1454 assert(f.__is_black_ == false); 1455 1456 assert(c.__parent_ == &b); 1457 assert(c.__left_ == 0); 1458 assert(c.__right_ == 0); 1459 assert(c.__is_black_ == false); 1460 1461 assert(e.__parent_ == &f); 1462 assert(e.__left_ == 0); 1463 assert(e.__right_ == 0); 1464 assert(e.__is_black_ == true); 1465 1466 assert(g.__parent_ == &f); 1467 assert(g.__left_ == 0); 1468 assert(g.__right_ == &h); 1469 assert(g.__is_black_ == true); 1470 1471 assert(h.__parent_ == &g); 1472 assert(h.__left_ == 0); 1473 assert(h.__right_ == 0); 1474 assert(h.__is_black_ == false); 1475 1476 std::__tree_remove(root.__left_, &b); 1477 1478 assert(std::__tree_invariant(root.__left_)); 1479 1480 assert(root.__parent_ == 0); 1481 assert(root.__left_ == &d); 1482 assert(root.__right_ == 0); 1483 assert(root.__is_black_ == false); 1484 1485 assert(d.__parent_ == &root); 1486 assert(d.__left_ == &c); 1487 assert(d.__right_ == &f); 1488 assert(d.__is_black_ == true); 1489 1490 assert(c.__parent_ == &d); 1491 assert(c.__left_ == 0); 1492 assert(c.__right_ == 0); 1493 assert(c.__is_black_ == true); 1494 1495 assert(f.__parent_ == &d); 1496 assert(f.__left_ == &e); 1497 assert(f.__right_ == &g); 1498 assert(f.__is_black_ == false); 1499 1500 assert(e.__parent_ == &f); 1501 assert(e.__left_ == 0); 1502 assert(e.__right_ == 0); 1503 assert(e.__is_black_ == true); 1504 1505 assert(g.__parent_ == &f); 1506 assert(g.__left_ == 0); 1507 assert(g.__right_ == &h); 1508 assert(g.__is_black_ == true); 1509 1510 assert(h.__parent_ == &g); 1511 assert(h.__left_ == 0); 1512 assert(h.__right_ == 0); 1513 assert(h.__is_black_ == false); 1514 1515 std::__tree_remove(root.__left_, &c); 1516 1517 assert(std::__tree_invariant(root.__left_)); 1518 1519 assert(root.__parent_ == 0); 1520 assert(root.__left_ == &f); 1521 assert(root.__right_ == 0); 1522 assert(root.__is_black_ == false); 1523 1524 assert(f.__parent_ == &root); 1525 assert(f.__left_ == &d); 1526 assert(f.__right_ == &g); 1527 assert(f.__is_black_ == true); 1528 1529 assert(d.__parent_ == &f); 1530 assert(d.__left_ == 0); 1531 assert(d.__right_ == &e); 1532 assert(d.__is_black_ == true); 1533 1534 assert(g.__parent_ == &f); 1535 assert(g.__left_ == 0); 1536 assert(g.__right_ == &h); 1537 assert(g.__is_black_ == true); 1538 1539 assert(e.__parent_ == &d); 1540 assert(e.__left_ == 0); 1541 assert(e.__right_ == 0); 1542 assert(e.__is_black_ == false); 1543 1544 assert(h.__parent_ == &g); 1545 assert(h.__left_ == 0); 1546 assert(h.__right_ == 0); 1547 assert(h.__is_black_ == false); 1548 1549 std::__tree_remove(root.__left_, &d); 1550 1551 assert(std::__tree_invariant(root.__left_)); 1552 1553 assert(root.__parent_ == 0); 1554 assert(root.__left_ == &f); 1555 assert(root.__right_ == 0); 1556 assert(root.__is_black_ == false); 1557 1558 assert(f.__parent_ == &root); 1559 assert(f.__left_ == &e); 1560 assert(f.__right_ == &g); 1561 assert(f.__is_black_ == true); 1562 1563 assert(e.__parent_ == &f); 1564 assert(e.__left_ == 0); 1565 assert(e.__right_ == 0); 1566 assert(e.__is_black_ == true); 1567 1568 assert(g.__parent_ == &f); 1569 assert(g.__left_ == 0); 1570 assert(g.__right_ == &h); 1571 assert(g.__is_black_ == true); 1572 1573 assert(h.__parent_ == &g); 1574 assert(h.__left_ == 0); 1575 assert(h.__right_ == 0); 1576 assert(h.__is_black_ == false); 1577 1578 std::__tree_remove(root.__left_, &e); 1579 1580 assert(std::__tree_invariant(root.__left_)); 1581 1582 assert(root.__parent_ == 0); 1583 assert(root.__left_ == &g); 1584 assert(root.__right_ == 0); 1585 assert(root.__is_black_ == false); 1586 1587 assert(g.__parent_ == &root); 1588 assert(g.__left_ == &f); 1589 assert(g.__right_ == &h); 1590 assert(g.__is_black_ == true); 1591 1592 assert(f.__parent_ == &g); 1593 assert(f.__left_ == 0); 1594 assert(f.__right_ == 0); 1595 assert(f.__is_black_ == true); 1596 1597 assert(h.__parent_ == &g); 1598 assert(h.__left_ == 0); 1599 assert(h.__right_ == 0); 1600 assert(h.__is_black_ == true); 1601 1602 std::__tree_remove(root.__left_, &f); 1603 1604 assert(std::__tree_invariant(root.__left_)); 1605 1606 assert(root.__parent_ == 0); 1607 assert(root.__left_ == &g); 1608 assert(root.__right_ == 0); 1609 assert(root.__is_black_ == false); 1610 1611 assert(g.__parent_ == &root); 1612 assert(g.__left_ == 0); 1613 assert(g.__right_ == &h); 1614 assert(g.__is_black_ == true); 1615 1616 assert(h.__parent_ == &g); 1617 assert(h.__left_ == 0); 1618 assert(h.__right_ == 0); 1619 assert(h.__is_black_ == false); 1620 1621 std::__tree_remove(root.__left_, &g); 1622 1623 assert(std::__tree_invariant(root.__left_)); 1624 1625 assert(root.__parent_ == 0); 1626 assert(root.__left_ == &h); 1627 assert(root.__right_ == 0); 1628 assert(root.__is_black_ == false); 1629 1630 assert(h.__parent_ == &root); 1631 assert(h.__left_ == 0); 1632 assert(h.__right_ == 0); 1633 assert(h.__is_black_ == true); 1634 1635 std::__tree_remove(root.__left_, &h); 1636 1637 assert(std::__tree_invariant(root.__left_)); 1638 1639 assert(root.__parent_ == 0); 1640 assert(root.__left_ == 0); 1641 assert(root.__right_ == 0); 1642 assert(root.__is_black_ == false); 1643 } 1644 1645 int main() 1646 { 1647 test1(); 1648 test2(); 1649 test3(); 1650 test4(); 1651 } 1652