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