Verify that B+ tree matches reference implementation
(self)
| 132 | return get_depth(self.btree.root) |
| 133 | |
| 134 | def verify_consistency(self) -> bool: |
| 135 | """Verify that B+ tree matches reference implementation""" |
| 136 | try: |
| 137 | # Check lengths match |
| 138 | if len(self.btree) != len(self.reference): |
| 139 | print( |
| 140 | f"Length mismatch: btree={len(self.btree)}, reference={len(self.reference)}" |
| 141 | ) |
| 142 | return False |
| 143 | |
| 144 | # Check all keys in reference exist in btree with same values |
| 145 | for key, expected_value in self.reference.items(): |
| 146 | try: |
| 147 | actual_value = self.btree[key] |
| 148 | if actual_value != expected_value: |
| 149 | print( |
| 150 | f"Value mismatch for key {key}: btree={actual_value}, reference={expected_value}" |
| 151 | ) |
| 152 | return False |
| 153 | except KeyError: |
| 154 | print(f"Key {key} missing from btree but exists in reference") |
| 155 | return False |
| 156 | |
| 157 | # Check no extra keys in btree |
| 158 | for leaf in self._get_all_btree_keys(): |
| 159 | if leaf not in self.reference: |
| 160 | print(f"Extra key {leaf} in btree but not in reference") |
| 161 | return False |
| 162 | |
| 163 | # Check B+ tree invariants |
| 164 | if not check_invariants(self.btree): |
| 165 | print("B+ tree invariants violated") |
| 166 | return False |
| 167 | |
| 168 | return True |
| 169 | |
| 170 | except Exception as e: |
| 171 | print(f"Error during consistency check: {e}") |
| 172 | return False |
| 173 | |
| 174 | def _get_all_btree_keys(self) -> List[Any]: |
| 175 | """Extract all keys from B+ tree by traversing leaves""" |
no test coverage detected