| 1205 | |
| 1206 | #[test] |
| 1207 | fn remove_level1() { |
| 1208 | let f = &mut MapForest::<u32, f32>::new(); |
| 1209 | let mut m = two_leaf(f); |
| 1210 | |
| 1211 | // Verify geometry. |
| 1212 | m.verify(f, &()); |
| 1213 | assert_eq!(m.tpath(10, f, &()), "node2[0]--node0[0]"); |
| 1214 | assert_eq!(m.tpath(40, f, &()), "node2[0]--node0[3]"); |
| 1215 | assert_eq!(m.tpath(49, f, &()), "node2[0]--node0[4]"); |
| 1216 | assert_eq!(m.tpath(50, f, &()), "node2[1]--node1[0]"); |
| 1217 | assert_eq!(m.tpath(80, f, &()), "node2[1]--node1[3]"); |
| 1218 | |
| 1219 | // Remove the front entry from a node that stays healthy. |
| 1220 | assert_eq!(m.insert(55, 5.5, f, &()), None); |
| 1221 | assert_eq!(m.remove(50, f, &()), Some(5.0)); |
| 1222 | m.verify(f, &()); |
| 1223 | assert_eq!(m.tpath(49, f, &()), "node2[0]--node0[4]"); |
| 1224 | assert_eq!(m.tpath(50, f, &()), "node2[0]--node0[4]"); |
| 1225 | assert_eq!(m.tpath(55, f, &()), "node2[1]--node1[0]"); |
| 1226 | |
| 1227 | // Remove the front entry from the first leaf node: No critical key to update. |
| 1228 | assert_eq!(m.insert(15, 1.5, f, &()), None); |
| 1229 | assert_eq!(m.remove(10, f, &()), Some(1.0)); |
| 1230 | m.verify(f, &()); |
| 1231 | |
| 1232 | // [ 15 20 30 40 ] [ 55 60 70 80 ] |
| 1233 | |
| 1234 | // Remove the front entry from a right-most node that underflows. |
| 1235 | // No rebalancing for the right-most node. Still need critical key update. |
| 1236 | assert_eq!(m.remove(55, f, &()), Some(5.5)); |
| 1237 | m.verify(f, &()); |
| 1238 | assert_eq!(m.tpath(55, f, &()), "node2[0]--node0[4]"); |
| 1239 | assert_eq!(m.tpath(60, f, &()), "node2[1]--node1[0]"); |
| 1240 | |
| 1241 | // [ 15 20 30 40 ] [ 60 70 80 ] |
| 1242 | |
| 1243 | // Replenish the right leaf. |
| 1244 | assert_eq!(m.insert(90, 9.0, f, &()), None); |
| 1245 | assert_eq!(m.insert(100, 10.0, f, &()), None); |
| 1246 | m.verify(f, &()); |
| 1247 | assert_eq!(m.tpath(55, f, &()), "node2[0]--node0[4]"); |
| 1248 | assert_eq!(m.tpath(60, f, &()), "node2[1]--node1[0]"); |
| 1249 | |
| 1250 | // [ 15 20 30 40 ] [ 60 70 80 90 100 ] |
| 1251 | |
| 1252 | // Removing one entry from the left leaf should trigger a rebalancing from the right |
| 1253 | // sibling. |
| 1254 | assert_eq!(m.remove(20, f, &()), Some(2.0)); |
| 1255 | m.verify(f, &()); |
| 1256 | |
| 1257 | // [ 15 30 40 60 ] [ 70 80 90 100 ] |
| 1258 | // Check that the critical key was updated correctly. |
| 1259 | assert_eq!(m.tpath(50, f, &()), "node2[0]--node0[3]"); |
| 1260 | assert_eq!(m.tpath(60, f, &()), "node2[0]--node0[3]"); |
| 1261 | assert_eq!(m.tpath(70, f, &()), "node2[1]--node1[0]"); |
| 1262 | |
| 1263 | // Remove front entry from the left-most leaf node, underflowing. |
| 1264 | // This should cause two leaf nodes to be merged and the root node to go away. |