| 1065 | |
| 1066 | #[test] |
| 1067 | fn split_level1_leaf() { |
| 1068 | // Various ways of splitting a full leaf node at level 1. |
| 1069 | let f = &mut MapForest::<u32, f32>::new(); |
| 1070 | |
| 1071 | // Return a map whose root node is a full inner node, and the leaf nodes are all full |
| 1072 | // containing: |
| 1073 | // |
| 1074 | // 110, 120, ..., 170 |
| 1075 | // 210, 220, ..., 270 |
| 1076 | // ... |
| 1077 | // 810, 820, ..., 870 |
| 1078 | fn full(f: &mut MapForest<u32, f32>) -> Map<u32, f32> { |
| 1079 | let mut m = Map::new(); |
| 1080 | |
| 1081 | // Start by inserting elements in order. |
| 1082 | // This should leave 8 leaf nodes with 4 elements in each. |
| 1083 | for row in 1..9 { |
| 1084 | for col in 1..5 { |
| 1085 | m.insert(row * 100 + col * 10, row as f32 + col as f32 * 0.1, f, &()); |
| 1086 | } |
| 1087 | } |
| 1088 | |
| 1089 | // Then top up the leaf nodes without splitting them. |
| 1090 | for row in 1..9 { |
| 1091 | for col in 5..8 { |
| 1092 | m.insert(row * 100 + col * 10, row as f32 + col as f32 * 0.1, f, &()); |
| 1093 | } |
| 1094 | } |
| 1095 | |
| 1096 | m |
| 1097 | } |
| 1098 | |
| 1099 | let mut m = full(f); |
| 1100 | // Verify geometry. Get get node2 as the root and leaves node0, 1, 3, ... |
| 1101 | m.verify(f, &()); |
| 1102 | assert_eq!(m.tpath(110, f, &()), "node2[0]--node0[0]"); |
| 1103 | assert_eq!(m.tpath(140, f, &()), "node2[0]--node0[3]"); |
| 1104 | assert_eq!(m.tpath(210, f, &()), "node2[1]--node1[0]"); |
| 1105 | assert_eq!(m.tpath(270, f, &()), "node2[1]--node1[6]"); |
| 1106 | assert_eq!(m.tpath(310, f, &()), "node2[2]--node3[0]"); |
| 1107 | assert_eq!(m.tpath(810, f, &()), "node2[7]--node8[0]"); |
| 1108 | assert_eq!(m.tpath(870, f, &()), "node2[7]--node8[6]"); |
| 1109 | |
| 1110 | { |
| 1111 | let mut c = m.cursor_mut(f, &()); |
| 1112 | assert_eq!(c.goto_first(), Some(1.1)); |
| 1113 | assert_eq!(c.key(), Some(110)); |
| 1114 | } |
| 1115 | |
| 1116 | // Front of first leaf. |
| 1117 | m.insert(0, 4.2, f, &()); |
| 1118 | m.verify(f, &()); |
| 1119 | assert_eq!(m.get(0, f, &()), Some(4.2)); |
| 1120 | |
| 1121 | // First leaf split 4-4 after appending to LHS. |
| 1122 | f.clear(); |
| 1123 | m = full(f); |
| 1124 | m.insert(135, 4.2, f, &()); |