swap two nodes (except for their content), taking care of special cases where one is the other's parent ... hey, it happens. @param x one node @param y another node @param index _KEY or _VALUE
(Node x, Node y, int index)
| 1074 | * @param index _KEY or _VALUE |
| 1075 | */ |
| 1076 | private void swapPosition(Node x, Node y, int index) |
| 1077 | { |
| 1078 | |
| 1079 | // Save initial values. |
| 1080 | Node x_old_parent = x.getParent(index); |
| 1081 | Node x_old_left_child = x.getLeft(index); |
| 1082 | Node x_old_right_child = x.getRight(index); |
| 1083 | Node y_old_parent = y.getParent(index); |
| 1084 | Node y_old_left_child = y.getLeft(index); |
| 1085 | Node y_old_right_child = y.getRight(index); |
| 1086 | boolean x_was_left_child = |
| 1087 | (x.getParent(index) != null) |
| 1088 | && (x == x.getParent(index).getLeft(index)); |
| 1089 | boolean y_was_left_child = |
| 1090 | (y.getParent(index) != null) |
| 1091 | && (y == y.getParent(index).getLeft(index)); |
| 1092 | |
| 1093 | // Swap, handling special cases of one being the other's parent. |
| 1094 | if (x == y_old_parent) |
| 1095 | { // x was y's parent |
| 1096 | x.setParent(y, index); |
| 1097 | if (y_was_left_child) |
| 1098 | { |
| 1099 | y.setLeft(x, index); |
| 1100 | y.setRight(x_old_right_child, index); |
| 1101 | } |
| 1102 | else |
| 1103 | { |
| 1104 | y.setRight(x, index); |
| 1105 | y.setLeft(x_old_left_child, index); |
| 1106 | } |
| 1107 | } |
| 1108 | else |
| 1109 | { |
| 1110 | x.setParent(y_old_parent, index); |
| 1111 | if (y_old_parent != null) |
| 1112 | { |
| 1113 | if (y_was_left_child) |
| 1114 | { |
| 1115 | y_old_parent.setLeft(x, index); |
| 1116 | } |
| 1117 | else |
| 1118 | { |
| 1119 | y_old_parent.setRight(x, index); |
| 1120 | } |
| 1121 | } |
| 1122 | y.setLeft(x_old_left_child, index); |
| 1123 | y.setRight(x_old_right_child, index); |
| 1124 | } |
| 1125 | if (y == x_old_parent) |
| 1126 | { // y was x's parent |
| 1127 | y.setParent(x, index); |
| 1128 | if (x_was_left_child) |
| 1129 | { |
| 1130 | x.setLeft(y, index); |
| 1131 | x.setRight(y_old_right_child, index); |
| 1132 | } |
| 1133 | else |
no test coverage detected