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