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