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