Gitiles
Code Review Sign In
gerrit-public.fairphone.software / platform / external / libcxx / 1d4a1edbc7e4461b59239e1b8297e9dd395a6322 / . / test / std / containers / associative / tree_balance_after_insert.pass.cpp
blob: b0a3e74cab0afb267a88d9dee7b5801cad30be17 [file] [log] [blame]
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]1//===----------------------------------------------------------------------===//
2//
Howard Hinnantf5256e12010-05-11 21:36:01 +0000[diff] [blame]3// The LLVM Compiler Infrastructure
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]4//
Howard Hinnantb64f8b02010-11-16 22:09:02 +0000[diff] [blame]5// This file is dual licensed under the MIT and the University of Illinois Open
6// Source Licenses. See LICENSE.TXT for details.
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]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() : __left_(), __right_(), __parent_(), __is_black_() {}
28};
29
30void
31test1()
32{
33 {
34 Node root;
35 Node a;
36 Node b;
37 Node c;
38 Node d;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]39
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]40 root.__left_ = &c;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]41
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]42 c.__parent_ = &root;
43 c.__left_ = &b;
44 c.__right_ = &d;
45 c.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]46
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]47 b.__parent_ = &c;
48 b.__left_ = &a;
49 b.__right_ = 0;
50 b.__is_black_ = false;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]51
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]52 d.__parent_ = &c;
53 d.__left_ = 0;
54 d.__right_ = 0;
55 d.__is_black_ = false;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]56
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]57 a.__parent_ = &b;
58 a.__left_ = 0;
59 a.__right_ = 0;
60 a.__is_black_ = false;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]61
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]62 std::__tree_balance_after_insert(root.__left_, &a);
63
64 assert(std::__tree_invariant(root.__left_));
65
66 assert(root.__left_ == &c);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]67
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]68 assert(c.__parent_ == &root);
69 assert(c.__left_ == &b);
70 assert(c.__right_ == &d);
71 assert(c.__is_black_ == true);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]72
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]73 assert(b.__parent_ == &c);
74 assert(b.__left_ == &a);
75 assert(b.__right_ == 0);
76 assert(b.__is_black_ == true);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]77
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]78 assert(d.__parent_ == &c);
79 assert(d.__left_ == 0);
80 assert(d.__right_ == 0);
81 assert(d.__is_black_ == true);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]82
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]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;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]94
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]95 root.__left_ = &c;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]96
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]97 c.__parent_ = &root;
98 c.__left_ = &b;
99 c.__right_ = &d;
100 c.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]101
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]102 b.__parent_ = &c;
103 b.__left_ = 0;
104 b.__right_ = &a;
105 b.__is_black_ = false;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]106
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]107 d.__parent_ = &c;
108 d.__left_ = 0;
109 d.__right_ = 0;
110 d.__is_black_ = false;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]111
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]112 a.__parent_ = &b;
113 a.__left_ = 0;
114 a.__right_ = 0;
115 a.__is_black_ = false;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]116
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]117 std::__tree_balance_after_insert(root.__left_, &a);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]118
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]119 assert(std::__tree_invariant(root.__left_));
120
121 assert(root.__left_ == &c);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]122
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]123 assert(c.__parent_ == &root);
124 assert(c.__left_ == &b);
125 assert(c.__right_ == &d);
126 assert(c.__is_black_ == true);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]127
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]128 assert(b.__parent_ == &c);
129 assert(b.__left_ == 0);
130 assert(b.__right_ == &a);
131 assert(b.__is_black_ == true);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]132
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]133 assert(d.__parent_ == &c);
134 assert(d.__left_ == 0);
135 assert(d.__right_ == 0);
136 assert(d.__is_black_ == true);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]137
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]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;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]149
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]150 root.__left_ = &c;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]151
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]152 c.__parent_ = &root;
153 c.__left_ = &b;
154 c.__right_ = &d;
155 c.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]156
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]157 b.__parent_ = &c;
158 b.__left_ = 0;
159 b.__right_ = 0;
160 b.__is_black_ = false;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]161
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]162 d.__parent_ = &c;
163 d.__left_ = &a;
164 d.__right_ = 0;
165 d.__is_black_ = false;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]166
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]167 a.__parent_ = &d;
168 a.__left_ = 0;
169 a.__right_ = 0;
170 a.__is_black_ = false;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]171
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]172 std::__tree_balance_after_insert(root.__left_, &a);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]173
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]174 assert(std::__tree_invariant(root.__left_));
175
176 assert(root.__left_ == &c);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]177
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]178 assert(c.__parent_ == &root);
179 assert(c.__left_ == &b);
180 assert(c.__right_ == &d);
181 assert(c.__is_black_ == true);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]182
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]183 assert(b.__parent_ == &c);
184 assert(b.__left_ == 0);
185 assert(b.__right_ == 0);
186 assert(b.__is_black_ == true);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]187
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]188 assert(d.__parent_ == &c);
189 assert(d.__left_ == &a);
190 assert(d.__right_ == 0);
191 assert(d.__is_black_ == true);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]192
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]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;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]204
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]205 root.__left_ = &c;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]206
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]207 c.__parent_ = &root;
208 c.__left_ = &b;
209 c.__right_ = &d;
210 c.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]211
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]212 b.__parent_ = &c;
213 b.__left_ = 0;
214 b.__right_ = 0;
215 b.__is_black_ = false;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]216
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]217 d.__parent_ = &c;
218 d.__left_ = 0;
219 d.__right_ = &a;
220 d.__is_black_ = false;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]221
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]222 a.__parent_ = &d;
223 a.__left_ = 0;
224 a.__right_ = 0;
225 a.__is_black_ = false;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]226
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]227 std::__tree_balance_after_insert(root.__left_, &a);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]228
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]229 assert(std::__tree_invariant(root.__left_));
230
231 assert(root.__left_ == &c);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]232
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]233 assert(c.__parent_ == &root);
234 assert(c.__left_ == &b);
235 assert(c.__right_ == &d);
236 assert(c.__is_black_ == true);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]237
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]238 assert(b.__parent_ == &c);
239 assert(b.__left_ == 0);
240 assert(b.__right_ == 0);
241 assert(b.__is_black_ == true);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]242
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]243 assert(d.__parent_ == &c);
244 assert(d.__left_ == 0);
245 assert(d.__right_ == &a);
246 assert(d.__is_black_ == true);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]247
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]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;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]264
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]265 root.__left_ = &c;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]266
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]267 c.__parent_ = &root;
268 c.__left_ = &b;
269 c.__right_ = &d;
270 c.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]271
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]272 b.__parent_ = &c;
273 b.__left_ = &a;
274 b.__right_ = &g;
275 b.__is_black_ = false;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]276
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]277 d.__parent_ = &c;
278 d.__left_ = &h;
279 d.__right_ = &i;
280 d.__is_black_ = false;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]281
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]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;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]289
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]290 f.__parent_ = &a;
291 f.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]292
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]293 g.__parent_ = &b;
294 g.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]295
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]296 h.__parent_ = &d;
297 h.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]298
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]299 i.__parent_ = &d;
300 i.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]301
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]302 std::__tree_balance_after_insert(root.__left_, &a);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]303
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]304 assert(std::__tree_invariant(root.__left_));
305
306 assert(root.__left_ == &c);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]307
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]308 assert(c.__parent_ == &root);
309 assert(c.__left_ == &b);
310 assert(c.__right_ == &d);
311 assert(c.__is_black_ == true);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]312
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]313 assert(b.__parent_ == &c);
314 assert(b.__left_ == &a);
315 assert(b.__right_ == &g);
316 assert(b.__is_black_ == true);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]317
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]318 assert(d.__parent_ == &c);
319 assert(d.__left_ == &h);
320 assert(d.__right_ == &i);
321 assert(d.__is_black_ == true);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]322
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]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;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]339
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]340 root.__left_ = &c;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]341
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]342 c.__parent_ = &root;
343 c.__left_ = &b;
344 c.__right_ = &d;
345 c.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]346
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]347 b.__parent_ = &c;
348 b.__left_ = &g;
349 b.__right_ = &a;
350 b.__is_black_ = false;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]351
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]352 d.__parent_ = &c;
353 d.__left_ = &h;
354 d.__right_ = &i;
355 d.__is_black_ = false;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]356
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]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;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]364
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]365 f.__parent_ = &a;
366 f.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]367
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]368 g.__parent_ = &b;
369 g.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]370
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]371 h.__parent_ = &d;
372 h.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]373
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]374 i.__parent_ = &d;
375 i.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]376
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]377 std::__tree_balance_after_insert(root.__left_, &a);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]378
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]379 assert(std::__tree_invariant(root.__left_));
380
381 assert(root.__left_ == &c);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]382
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]383 assert(c.__parent_ == &root);
384 assert(c.__left_ == &b);
385 assert(c.__right_ == &d);
386 assert(c.__is_black_ == true);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]387
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]388 assert(b.__parent_ == &c);
389 assert(b.__left_ == &g);
390 assert(b.__right_ == &a);
391 assert(b.__is_black_ == true);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]392
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]393 assert(d.__parent_ == &c);
394 assert(d.__left_ == &h);
395 assert(d.__right_ == &i);
396 assert(d.__is_black_ == true);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]397
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]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;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]414
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]415 root.__left_ = &c;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]416
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]417 c.__parent_ = &root;
418 c.__left_ = &b;
419 c.__right_ = &d;
420 c.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]421
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]422 b.__parent_ = &c;
423 b.__left_ = &g;
424 b.__right_ = &h;
425 b.__is_black_ = false;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]426
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]427 d.__parent_ = &c;
428 d.__left_ = &a;
429 d.__right_ = &i;
430 d.__is_black_ = false;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]431
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]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;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]439
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]440 f.__parent_ = &a;
441 f.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]442
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]443 g.__parent_ = &b;
444 g.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]445
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]446 h.__parent_ = &b;
447 h.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]448
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]449 i.__parent_ = &d;
450 i.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]451
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]452 std::__tree_balance_after_insert(root.__left_, &a);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]453
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]454 assert(std::__tree_invariant(root.__left_));
455
456 assert(root.__left_ == &c);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]457
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]458 assert(c.__parent_ == &root);
459 assert(c.__left_ == &b);
460 assert(c.__right_ == &d);
461 assert(c.__is_black_ == true);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]462
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]463 assert(b.__parent_ == &c);
464 assert(b.__left_ == &g);
465 assert(b.__right_ == &h);
466 assert(b.__is_black_ == true);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]467
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]468 assert(d.__parent_ == &c);
469 assert(d.__left_ == &a);
470 assert(d.__right_ == &i);
471 assert(d.__is_black_ == true);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]472
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]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;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]489
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]490 root.__left_ = &c;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]491
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]492 c.__parent_ = &root;
493 c.__left_ = &b;
494 c.__right_ = &d;
495 c.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]496
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]497 b.__parent_ = &c;
498 b.__left_ = &g;
499 b.__right_ = &h;
500 b.__is_black_ = false;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]501
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]502 d.__parent_ = &c;
503 d.__left_ = &i;
504 d.__right_ = &a;
505 d.__is_black_ = false;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]506
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]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;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]514
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]515 f.__parent_ = &a;
516 f.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]517
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]518 g.__parent_ = &b;
519 g.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]520
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]521 h.__parent_ = &b;
522 h.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]523
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]524 i.__parent_ = &d;
525 i.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]526
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]527 std::__tree_balance_after_insert(root.__left_, &a);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]528
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]529 assert(std::__tree_invariant(root.__left_));
530
531 assert(root.__left_ == &c);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]532
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]533 assert(c.__parent_ == &root);
534 assert(c.__left_ == &b);
535 assert(c.__right_ == &d);
536 assert(c.__is_black_ == true);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]537
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]538 assert(b.__parent_ == &c);
539 assert(b.__left_ == &g);
540 assert(b.__right_ == &h);
541 assert(b.__is_black_ == true);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]542
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]543 assert(d.__parent_ == &c);
544 assert(d.__left_ == &i);
545 assert(d.__right_ == &a);
546 assert(d.__is_black_ == true);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]547
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]548 assert(a.__parent_ == &d);
549 assert(a.__left_ == &e);
550 assert(a.__right_ == &f);
551 assert(a.__is_black_ == false);
552 }
553}
554
555void
556test2()
557{
558 {
559 Node root;
560 Node a;
561 Node b;
562 Node c;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]563
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]564 root.__left_ = &c;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]565
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]566 c.__parent_ = &root;
567 c.__left_ = &a;
568 c.__right_ = 0;
569 c.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]570
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]571 a.__parent_ = &c;
572 a.__left_ = 0;
573 a.__right_ = &b;
574 a.__is_black_ = false;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]575
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]576 b.__parent_ = &a;
577 b.__left_ = 0;
578 b.__right_ = 0;
579 b.__is_black_ = false;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]580
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]581 std::__tree_balance_after_insert(root.__left_, &b);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]582
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]583 assert(std::__tree_invariant(root.__left_));
584
585 assert(root.__left_ == &b);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]586
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]587 assert(c.__parent_ == &b);
588 assert(c.__left_ == 0);
589 assert(c.__right_ == 0);
590 assert(c.__is_black_ == false);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]591
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]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;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]607
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]608 root.__left_ = &a;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]609
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]610 a.__parent_ = &root;
611 a.__left_ = 0;
612 a.__right_ = &c;
613 a.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]614
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]615 c.__parent_ = &a;
616 c.__left_ = &b;
617 c.__right_ = 0;
618 c.__is_black_ = false;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]619
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]620 b.__parent_ = &c;
621 b.__left_ = 0;
622 b.__right_ = 0;
623 b.__is_black_ = false;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]624
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]625 std::__tree_balance_after_insert(root.__left_, &b);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]626
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]627 assert(std::__tree_invariant(root.__left_));
628
629 assert(root.__left_ == &b);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]630
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]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);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]640
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]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;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]655
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]656 root.__left_ = &c;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]657
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]658 c.__parent_ = &root;
659 c.__left_ = &a;
660 c.__right_ = &g;
661 c.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]662
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]663 a.__parent_ = &c;
664 a.__left_ = &d;
665 a.__right_ = &b;
666 a.__is_black_ = false;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]667
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]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;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]675
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]676 e.__parent_ = &b;
677 e.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]678
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]679 f.__parent_ = &b;
680 f.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]681
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]682 g.__parent_ = &c;
683 g.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]684
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]685 std::__tree_balance_after_insert(root.__left_, &b);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]686
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]687 assert(std::__tree_invariant(root.__left_));
688
689 assert(root.__left_ == &b);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]690
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]691 assert(c.__parent_ == &b);
692 assert(c.__left_ == &f);
693 assert(c.__right_ == &g);
694 assert(c.__is_black_ == false);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]695
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]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;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]727
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]728 root.__left_ = &a;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]729
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]730 a.__parent_ = &root;
731 a.__left_ = &d;
732 a.__right_ = &c;
733 a.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]734
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]735 c.__parent_ = &a;
736 c.__left_ = &b;
737 c.__right_ = &g;
738 c.__is_black_ = false;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]739
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]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;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]747
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]748 e.__parent_ = &b;
749 e.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]750
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]751 f.__parent_ = &b;
752 f.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]753
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]754 g.__parent_ = &c;
755 g.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]756
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]757 std::__tree_balance_after_insert(root.__left_, &b);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]758
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]759 assert(std::__tree_invariant(root.__left_));
760
761 assert(root.__left_ == &b);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]762
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]763 assert(c.__parent_ == &b);
764 assert(c.__left_ == &f);
765 assert(c.__right_ == &g);
766 assert(c.__is_black_ == false);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]767
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]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
792void
793test3()
794{
795 {
796 Node root;
797 Node a;
798 Node b;
799 Node c;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]800
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]801 root.__left_ = &c;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]802
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]803 c.__parent_ = &root;
804 c.__left_ = &b;
805 c.__right_ = 0;
806 c.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]807
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]808 b.__parent_ = &c;
809 b.__left_ = &a;
810 b.__right_ = 0;
811 b.__is_black_ = false;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]812
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]813 a.__parent_ = &b;
814 a.__left_ = 0;
815 a.__right_ = 0;
816 a.__is_black_ = false;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]817
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]818 std::__tree_balance_after_insert(root.__left_, &a);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]819
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]820 assert(std::__tree_invariant(root.__left_));
821
822 assert(root.__left_ == &b);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]823
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]824 assert(c.__parent_ == &b);
825 assert(c.__left_ == 0);
826 assert(c.__right_ == 0);
827 assert(c.__is_black_ == false);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]828
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]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;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]844
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]845 root.__left_ = &a;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]846
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]847 a.__parent_ = &root;
848 a.__left_ = 0;
849 a.__right_ = &b;
850 a.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]851
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]852 b.__parent_ = &a;
853 b.__left_ = 0;
854 b.__right_ = &c;
855 b.__is_black_ = false;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]856
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]857 c.__parent_ = &b;
858 c.__left_ = 0;
859 c.__right_ = 0;
860 c.__is_black_ = false;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]861
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]862 std::__tree_balance_after_insert(root.__left_, &c);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]863
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]864 assert(std::__tree_invariant(root.__left_));
865
866 assert(root.__left_ == &b);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]867
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]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);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]877
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]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;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]892
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]893 root.__left_ = &c;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]894
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]895 c.__parent_ = &root;
896 c.__left_ = &b;
897 c.__right_ = &g;
898 c.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]899
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]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;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]909
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]910 d.__parent_ = &a;
911 d.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]912
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]913 e.__parent_ = &a;
914 e.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]915
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]916 f.__parent_ = &b;
917 f.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]918
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]919 g.__parent_ = &c;
920 g.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]921
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]922 std::__tree_balance_after_insert(root.__left_, &a);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]923
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]924 assert(std::__tree_invariant(root.__left_));
925
926 assert(root.__left_ == &b);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]927
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]928 assert(c.__parent_ == &b);
929 assert(c.__left_ == &f);
930 assert(c.__right_ == &g);
931 assert(c.__is_black_ == false);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]932
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]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;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]964
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]965 root.__left_ = &a;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]966
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]967 a.__parent_ = &root;
968 a.__left_ = &d;
969 a.__right_ = &b;
970 a.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]971
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]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;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]981
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]982 d.__parent_ = &a;
983 d.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]984
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]985 e.__parent_ = &b;
986 e.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]987
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]988 f.__parent_ = &c;
989 f.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]990
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]991 g.__parent_ = &c;
992 g.__is_black_ = true;
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]993
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]994 std::__tree_balance_after_insert(root.__left_, &c);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]995
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]996 assert(std::__tree_invariant(root.__left_));
997
998 assert(root.__left_ == &b);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]999
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]1000 assert(c.__parent_ == &b);
1001 assert(c.__left_ == &f);
1002 assert(c.__right_ == &g);
1003 assert(c.__is_black_ == false);
Howard Hinnant6046ace2010-08-22 00:15:28 +0000[diff] [blame]1004
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000[diff] [blame]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
1029void
1030test4()
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
1319void
1320test5()
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
1609int main()
1610{
1611 test1();
1612 test2();
1613 test3();
1614 test4();
1615 test5();
1616}