Pre-populate the tree with a specified number of elements to create complex structure
(self, count: int)
| 72 | self.stats[op_type] = self.stats.get(op_type, 0) + 1 |
| 73 | |
| 74 | def _prepopulate_tree(self, count: int) -> None: |
| 75 | """Pre-populate the tree with a specified number of elements to create complex structure""" |
| 76 | print(f"Pre-populating tree with {count} elements...") |
| 77 | |
| 78 | # Use a different random state for prepopulation to ensure variety |
| 79 | prepop_state = random.getstate() |
| 80 | random.seed(self.seed + 12345) # Offset seed for prepopulation |
| 81 | |
| 82 | try: |
| 83 | # Insert keys in a pattern that creates a well-distributed tree |
| 84 | keys_to_insert = set() |
| 85 | |
| 86 | # Generate unique keys |
| 87 | while len(keys_to_insert) < count: |
| 88 | # Use a mix of patterns to ensure good tree structure |
| 89 | if len(keys_to_insert) < count // 2: |
| 90 | # First half: sequential with gaps |
| 91 | key = len(keys_to_insert) * 3 + random.randint(1, 2) |
| 92 | else: |
| 93 | # Second half: random distribution |
| 94 | key = random.randint(1, count * 10) |
| 95 | keys_to_insert.add(key) |
| 96 | |
| 97 | # Insert all keys |
| 98 | for key in sorted(keys_to_insert): |
| 99 | value = f"prepop_value_{key}" |
| 100 | self.btree[key] = value |
| 101 | self.reference[key] = value |
| 102 | |
| 103 | # Verify prepopulation worked correctly |
| 104 | if not self.verify_consistency(): |
| 105 | raise ValueError("Prepopulation failed consistency check") |
| 106 | |
| 107 | # Log prepopulation details |
| 108 | initial_nodes = self.btree._count_total_nodes() |
| 109 | initial_leaves = self.btree.leaf_count() |
| 110 | |
| 111 | print(f" ✅ Prepopulated with {len(self.reference)} keys") |
| 112 | print( |
| 113 | f" 📊 Tree structure: {initial_nodes} total nodes, {initial_leaves} leaves" |
| 114 | ) |
| 115 | print(f" 🏗️ Tree depth: {self._calculate_tree_depth()}") |
| 116 | print(f" ✅ Invariants verified") |
| 117 | |
| 118 | finally: |
| 119 | # Restore original random state |
| 120 | random.setstate(prepop_state) |
| 121 | |
| 122 | def _calculate_tree_depth(self) -> int: |
| 123 | """Calculate the depth of the tree""" |
no test coverage detected