Class TestStressEdgeCases

python/tests/test_stress_edge_cases.py:19–222

Stress tests for edge cases that could break B+ tree invariants

class TestStressEdgeCases:
    """Stress tests for edge cases that could break B+ tree invariants"""

    def test_minimum_capacity_heavy_deletion(self):
        """Test minimum capacity (4) with heavy deletion patterns"""
        tree = BPlusTreeMap(capacity=4)

        # Build a substantial tree
        keys = list(range(100))
        for key in keys:
            tree[key] = f"value_{key}"

        assert check_invariants(tree), "Tree should be valid after insertions"

        # Delete in patterns that stress rebalancing
        # Pattern 1: Delete every 3rd key
        for i in range(0, 100, 3):
            if i in tree:
                del tree[i]
                assert check_invariants(tree), f"Invariants broken after deleting {i}"

        # Pattern 2: Delete consecutive ranges
        for start in range(10, 90, 20):
            for i in range(start, min(start + 5, 100)):
                if i in tree:
                    del tree[i]
                    assert check_invariants(
                        tree
                    ), f"Invariants broken after deleting {i}"

    def test_alternating_insert_delete_stress(self):
        """Test alternating insert/delete operations that could cause instability"""
        tree = BPlusTreeMap(capacity=8)

        # Start with some data
        for i in range(50):
            tree[i] = f"initial_{i}"

        assert check_invariants(tree), "Initial tree should be valid"

        # Alternating pattern that stresses the tree
        for round_num in range(10):
            # Insert a batch
            for i in range(100 + round_num * 20, 120 + round_num * 20):
                tree[i] = f"round_{round_num}_{i}"
                assert check_invariants(tree), f"Insert {i} broke invariants"

            # Delete a batch from different area
            for i in range(round_num * 5, round_num * 5 + 10):
                if i in tree:
                    del tree[i]
                    assert check_invariants(tree), f"Delete {i} broke invariants"

    def test_large_capacity_edge_cases(self):
        """Test very large capacity to stress single-level tree edge cases"""
        tree = BPlusTreeMap(capacity=1024)

        # Fill up close to capacity