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