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