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