From CLR
(Entry<K,V> x)
| 1369 | |
| 1370 | /** From CLR **/ |
| 1371 | private void fixAfterDeletion(Entry<K,V> x) { |
| 1372 | while (x != root && colorOf(x) == BLACK) { |
| 1373 | if (x == leftOf(parentOf(x))) { |
| 1374 | Entry<K,V> sib = rightOf(parentOf(x)); |
| 1375 | |
| 1376 | if (colorOf(sib) == RED) { |
| 1377 | setColor(sib, BLACK); |
| 1378 | setColor(parentOf(x), RED); |
| 1379 | rotateLeft(parentOf(x)); |
| 1380 | sib = rightOf(parentOf(x)); |
| 1381 | } |
| 1382 | |
| 1383 | if (colorOf(leftOf(sib)) == BLACK && |
| 1384 | colorOf(rightOf(sib)) == BLACK) { |
| 1385 | setColor(sib, RED); |
| 1386 | x = parentOf(x); |
| 1387 | } else { |
| 1388 | if (colorOf(rightOf(sib)) == BLACK) { |
| 1389 | setColor(leftOf(sib), BLACK); |
| 1390 | setColor(sib, RED); |
| 1391 | rotateRight(sib); |
| 1392 | sib = rightOf(parentOf(x)); |
| 1393 | } |
| 1394 | setColor(sib, colorOf(parentOf(x))); |
| 1395 | setColor(parentOf(x), BLACK); |
| 1396 | setColor(rightOf(sib), BLACK); |
| 1397 | rotateLeft(parentOf(x)); |
| 1398 | x = root; |
| 1399 | } |
| 1400 | } else { // symmetric |
| 1401 | Entry<K,V> sib = leftOf(parentOf(x)); |
| 1402 | |
| 1403 | if (colorOf(sib) == RED) { |
| 1404 | setColor(sib, BLACK); |
| 1405 | setColor(parentOf(x), RED); |
| 1406 | rotateRight(parentOf(x)); |
| 1407 | sib = leftOf(parentOf(x)); |
| 1408 | } |
| 1409 | |
| 1410 | if (colorOf(rightOf(sib)) == BLACK && |
| 1411 | colorOf(leftOf(sib)) == BLACK) { |
| 1412 | setColor(sib, RED); |
| 1413 | x = parentOf(x); |
| 1414 | } else { |
| 1415 | if (colorOf(leftOf(sib)) == BLACK) { |
| 1416 | setColor(rightOf(sib), BLACK); |
| 1417 | setColor(sib, RED); |
| 1418 | rotateLeft(sib); |
| 1419 | sib = leftOf(parentOf(x)); |
| 1420 | } |
| 1421 | setColor(sib, colorOf(parentOf(x))); |
| 1422 | setColor(parentOf(x), BLACK); |
| 1423 | setColor(leftOf(sib), BLACK); |
| 1424 | rotateRight(parentOf(x)); |
| 1425 | x = root; |
| 1426 | } |
| 1427 | } |
| 1428 | } |
no test coverage detected