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