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