Leaf node using Python array module for more efficient int storage.
| 14 | |
| 15 | |
| 16 | class IntArrayLeafNode: |
| 17 | """Leaf node using Python array module for more efficient int storage.""" |
| 18 | |
| 19 | def __init__(self, capacity: int = 128): |
| 20 | self.capacity = capacity |
| 21 | self.num_keys = 0 |
| 22 | # Single array: first half keys, second half values |
| 23 | # Using array module for more efficient int storage |
| 24 | self.data = array("q", [0] * (capacity * 2)) # 'q' = signed long long |
| 25 | self.next = None |
| 26 | |
| 27 | def find_position(self, key: int) -> int: |
| 28 | """Binary search for key position.""" |
| 29 | left, right = 0, self.num_keys |
| 30 | while left < right: |
| 31 | mid = (left + right) // 2 |
| 32 | if self.data[mid] < key: |
| 33 | left = mid + 1 |
| 34 | else: |
| 35 | right = mid |
| 36 | return left |
| 37 | |
| 38 | def insert(self, key: int, value: int) -> bool: |
| 39 | """Insert key-value pair. Returns True if successful.""" |
| 40 | pos = self.find_position(key) |
| 41 | |
| 42 | # Check if key exists |
| 43 | if pos < self.num_keys and self.data[pos] == key: |
| 44 | self.data[self.capacity + pos] = value |
| 45 | return True |
| 46 | |
| 47 | # Check capacity |
| 48 | if self.num_keys >= self.capacity: |
| 49 | return False |
| 50 | |
| 51 | # Shift elements using array slicing (more efficient) |
| 52 | if pos < self.num_keys: |
| 53 | # Shift keys |
| 54 | self.data[pos + 1 : self.num_keys + 1] = self.data[pos : self.num_keys] |
| 55 | # Shift values |
| 56 | self.data[ |
| 57 | self.capacity + pos + 1 : self.capacity + self.num_keys + 1 |
| 58 | ] = self.data[self.capacity + pos : self.capacity + self.num_keys] |
| 59 | |
| 60 | # Insert |
| 61 | self.data[pos] = key |
| 62 | self.data[self.capacity + pos] = value |
| 63 | self.num_keys += 1 |
| 64 | return True |
| 65 | |
| 66 | def lookup(self, key: int) -> int: |
| 67 | """Lookup value for key. Returns -1 if not found.""" |
| 68 | pos = self.find_position(key) |
| 69 | if pos < self.num_keys and self.data[pos] == key: |
| 70 | return self.data[self.capacity + pos] |
| 71 | return -1 |
| 72 | |
| 73 |
no outgoing calls