Test B+ tree operations when splitting nodes
| 90 | |
| 91 | |
| 92 | class TestSetItemSplitting: |
| 93 | """Test B+ tree operations when splitting nodes""" |
| 94 | |
| 95 | def test_overflow(self): |
| 96 | tree = BPlusTreeMap(capacity=4) |
| 97 | # With capacity=4, need 5 items to force a split |
| 98 | tree[1] = "one" |
| 99 | tree[2] = "two" |
| 100 | tree[3] = "three" |
| 101 | tree[4] = "four" |
| 102 | tree[5] = "five" |
| 103 | |
| 104 | assert check_invariants(tree) |
| 105 | assert len(tree) == 5 |
| 106 | assert tree[1] == "one" |
| 107 | assert tree[2] == "two" |
| 108 | assert tree[3] == "three" |
| 109 | assert tree[4] == "four" |
| 110 | assert tree[5] == "five" |
| 111 | |
| 112 | assert not tree.root.is_leaf() |
| 113 | |
| 114 | def test_split_then_add(self): |
| 115 | tree = BPlusTreeMap(capacity=4) |
| 116 | # With capacity=4, need more items to force multiple splits |
| 117 | tree[1] = "one" |
| 118 | tree[2] = "two" |
| 119 | tree[3] = "three" |
| 120 | tree[4] = "four" |
| 121 | tree[5] = "five" |
| 122 | tree[6] = "six" |
| 123 | tree[7] = "seven" |
| 124 | tree[8] = "eight" |
| 125 | |
| 126 | # Check correctness via invariants instead of exact structure |
| 127 | assert check_invariants(tree) |
| 128 | assert len(tree) == 8 |
| 129 | assert tree[1] == "one" |
| 130 | assert tree[2] == "two" |
| 131 | assert tree[3] == "three" |
| 132 | assert tree[4] == "four" |
| 133 | assert tree[5] == "five" |
| 134 | assert tree[6] == "six" |
| 135 | assert tree[7] == "seven" |
| 136 | assert tree[8] == "eight" |
| 137 | |
| 138 | # The simpler implementation may create more leaves, but that's OK |
| 139 | # as long as invariants hold |
| 140 | assert ( |
| 141 | tree.leaf_count() >= 2 |
| 142 | ) # At minimum need 2 leaves for 8 items with capacity 4 |
| 143 | |
| 144 | def test_many_insertions_maintain_invariants(self): |
| 145 | """Test that invariants hold after many insertions""" |
| 146 | tree = BPlusTreeMap(capacity=6) |
| 147 | |
| 148 | # Insert many items |
| 149 | for i in range(20): |
nothing calls this directly
no outgoing calls
no test coverage detected