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