| 1 | 1 | class Zipper: |
| 2 | def __init__(self, tree, path=[]): |
| 3 | # Edge Case: Handle when tree is None |
| 4 | if tree is None: |
| 5 | raise ValueError("Tree cannot be None") |
| 6 | self.tree = tree |
| 7 | self.path = path # path is a list of (parent_tree, is_left_child) tuples |
| 8 | |
| 2 | 9 | # Tree is a dict with keys "value" (int), "left" (dict or None), "right" (dict or None) |
| 3 | 10 | @staticmethod |
| 4 | 11 | def from_tree(tree: dict) -> "Zipper": |
| 5 | | pass |
| 12 | # Edge Case: Handle when tree is None |
| 13 | if tree is None: |
| 14 | return None |
| 15 | return Zipper(tree, []) |
| 6 | 16 | |
| 7 | 17 | def value(self) -> int: |
| 8 | | pass |
| 18 | # Edge Case: Handle when current node is None (should not happen with valid zippers) |
| 19 | if not self.tree: |
| 20 | raise ValueError("Current node is None") |
| 21 | return self.tree["value"] |
| 9 | 22 | |
| 10 | 23 | def set_value(self, value: int) -> "Zipper": |
| 11 | | pass |
| 24 | # Edge Case: Handle when value is None |
| 25 | if value is None: |
| 26 | raise ValueError("Value cannot be None") |
| 27 | |
| 28 | # Get the root tree and copy the entire tree structure |
| 29 | root_zipper = self._get_root() |
| 30 | new_root_tree = self._copy_tree(root_zipper.tree) |
| 31 | |
| 32 | # Navigate to the equivalent position in the new tree |
| 33 | current = new_root_tree |
| 34 | new_path = [] |
| 35 | for parent, is_left in self.path: |
| 36 | # Add current node and direction to path |
| 37 | new_path.append((current, is_left)) |
| 38 | # Navigate to next node |
| 39 | if is_left: |
| 40 | current = current["left"] |
| 41 | else: |
| 42 | current = current["right"] |
| 43 | |
| 44 | # Update the value at the focus |
| 45 | current["value"] = value |
| 46 | |
| 47 | return Zipper(current, new_path) |
| 12 | 48 | |
| 13 | 49 | def left(self) -> "Zipper | None": |
| 14 | | pass |
| 50 | # Edge Case: Handle when current node has no left child |
| 51 | if not self.tree or not self.tree["left"]: |
| 52 | return None |
| 53 | new_path = self.path + [(self.tree, True)] |
| 54 | return Zipper(self.tree["left"], new_path) |
| 15 | 55 | |
| 16 | 56 | def set_left(self, tree: dict | None) -> "Zipper": |
| 17 | | pass |
| 57 | # Get the root tree and copy the entire tree structure |
| 58 | root_zipper = self._get_root() |
| 59 | new_root_tree = self._copy_tree(root_zipper.tree) |
| 60 | |
| 61 | # Navigate to the equivalent position in the new tree |
| 62 | current = new_root_tree |
| 63 | new_path = [] |
| 64 | for parent, is_left in self.path: |
| 65 | # Add current node and direction to path |
| 66 | new_path.append((current, is_left)) |
| 67 | # Navigate to next node |
| 68 | if is_left: |
| 69 | current = current["left"] |
| 70 | else: |
| 71 | current = current["right"] |
| 72 | |
| 73 | # Update the left child at the focus |
| 74 | current["left"] = tree |
| 75 | |
| 76 | return Zipper(current, new_path) |
| 18 | 77 | |
| 19 | 78 | def right(self) -> "Zipper | None": |
| 20 | | pass |
| 79 | # Edge Case: Handle when current node has no right child |
| 80 | if not self.tree or not self.tree["right"]: |
| 81 | return None |
| 82 | new_path = self.path + [(self.tree, False)] |
| 83 | return Zipper(self.tree["right"], new_path) |
| 21 | 84 | |
| 22 | 85 | def set_right(self, tree: dict | None) -> "Zipper": |
| 23 | | pass |
| 86 | # Get the root tree and copy the entire tree structure |
| 87 | root_zipper = self._get_root() |
| 88 | new_root_tree = self._copy_tree(root_zipper.tree) |
| 89 | |
| 90 | # Navigate to the equivalent position in the new tree |
| 91 | current = new_root_tree |
| 92 | new_path = [] |
| 93 | for parent, is_left in self.path: |
| 94 | # Add current node and direction to path |
| 95 | new_path.append((current, is_left)) |
| 96 | # Navigate to next node |
| 97 | if is_left: |
| 98 | current = current["left"] |
| 99 | else: |
| 100 | current = current["right"] |
| 101 | |
| 102 | # Update the right child at the focus |
| 103 | current["right"] = tree |
| 104 | |
| 105 | return Zipper(current, new_path) |
| 24 | 106 | |
| 25 | 107 | def up(self) -> "Zipper | None": |
| 26 | | pass |
| 108 | # Edge Case: Handle when we're at the root (no parent) |
| 109 | if not self.path: |
| 110 | return None |
| 111 | |
| 112 | # Get the parent and whether we were in the left subtree |
| 113 | parent_tree, is_left_child = self.path[-1] |
| 114 | new_path = self.path[:-1] |
| 115 | |
| 116 | return Zipper(parent_tree, new_path) |
| 117 | |
| 118 | def prev(self) -> "Zipper | None": |
| 119 | """Move to the previous sibling (left sibling)""" |
| 120 | # Edge Case: Handle when we're at the root (no parent) |
| 121 | if not self.path: |
| 122 | return None |
| 123 | |
| 124 | # Get the parent |
| 125 | parent_tree, is_left_child = self.path[-1] |
| 126 | |
| 127 | # If we are the right child, our previous sibling is the left child |
| 128 | if not is_left_child: # We are the right child |
| 129 | if parent_tree["left"] is not None: |
| 130 | # Build path to left child |
| 131 | new_path = self.path[:-1] + [(parent_tree, True)] |
| 132 | return Zipper(parent_tree["left"], new_path) |
| 133 | |
| 134 | # No previous sibling |
| 135 | return None |
| 136 | |
| 137 | def next(self) -> "Zipper | None": |
| 138 | """Move to the next sibling (right sibling)""" |
| 139 | # Edge Case: Handle when we're at the root (no parent) |
| 140 | if not self.path: |
| 141 | return None |
| 142 | |
| 143 | # Get the parent |
| 144 | parent_tree, is_left_child = self.path[-1] |
| 145 | |
| 146 | # If we are the left child, our next sibling is the right child |
| 147 | if is_left_child: # We are the left child |
| 148 | if parent_tree["right"] is not None: |
| 149 | # Build path to right child |
| 150 | new_path = self.path[:-1] + [(parent_tree, False)] |
| 151 | return Zipper(parent_tree["right"], new_path) |
| 152 | |
| 153 | # No next sibling |
| 154 | return None |
| 155 | |
| 156 | def insert_before(self, tree: dict) -> "Zipper": |
| 157 | """Insert a new subtree before the focus node (as left sibling)""" |
| 158 | # Edge Case: Handle when we're at the root (no parent) |
| 159 | if not self.path: |
| 160 | raise ValueError("Cannot insert before root") |
| 161 | |
| 162 | # Get the root tree and copy the entire tree structure |
| 163 | root_zipper = self._get_root() |
| 164 | new_root_tree = self._copy_tree(root_zipper.tree) |
| 165 | |
| 166 | # Navigate to the equivalent position in the new tree |
| 167 | current = new_root_tree |
| 168 | new_path = [] |
| 169 | for parent, is_left in self.path: |
| 170 | # Add current node and direction to path |
| 171 | new_path.append((current, is_left)) |
| 172 | # Navigate to next node |
| 173 | if is_left: |
| 174 | current = current["left"] |
| 175 | else: |
| 176 | current = current["right"] |
| 177 | |
| 178 | # Get the parent in the new tree |
| 179 | if not new_path: |
| 180 | raise ValueError("Cannot insert before root") |
| 181 | |
| 182 | parent_node, is_left_child = new_path[-1] |
| 183 | |
| 184 | # Insert as left sibling (left child of parent) |
| 185 | # If we are the right child, insert as left child of parent |
| 186 | if not is_left_child: # We are the right child |
| 187 | parent_node["left"] = tree |
| 188 | else: |
| 189 | # If we are the left child, we can't insert "before" in the traditional sense |
| 190 | # We'll insert the new tree as the left child of parent, and make the current |
| 191 | # node the right child of the new tree |
| 192 | old_left = parent_node["left"] |
| 193 | new_tree_node = { |
| 194 | "value": tree["value"], |
| 195 | "left": tree.get("left"), |
| 196 | "right": old_left |
| 197 | } |
| 198 | parent_node["left"] = new_tree_node |
| 199 | # Update current to point to the new node |
| 200 | current = new_tree_node |
| 201 | |
| 202 | return Zipper(current, new_path) |
| 203 | |
| 204 | def insert_after(self, tree: dict) -> "Zipper": |
| 205 | """Insert a new subtree after the focus node (as right sibling)""" |
| 206 | # Edge Case: Handle when we're at the root (no parent) |
| 207 | if not self.path: |
| 208 | raise ValueError("Cannot insert after root") |
| 209 | |
| 210 | # Get the root tree and copy the entire tree structure |
| 211 | root_zipper = self._get_root() |
| 212 | new_root_tree = self._copy_tree(root_zipper.tree) |
| 213 | |
| 214 | # Navigate to the equivalent position in the new tree |
| 215 | current = new_root_tree |
| 216 | new_path = [] |
| 217 | for parent, is_left in self.path: |
| 218 | # Add current node and direction to path |
| 219 | new_path.append((current, is_left)) |
| 220 | # Navigate to next node |
| 221 | if is_left: |
| 222 | current = current["left"] |
| 223 | else: |
| 224 | current = current["right"] |
| 225 | |
| 226 | # Get the parent in the new tree |
| 227 | if not new_path: |
| 228 | raise ValueError("Cannot insert after root") |
| 229 | |
| 230 | parent_node, is_left_child = new_path[-1] |
| 231 | |
| 232 | # Insert as right sibling (right child of parent) |
| 233 | # If we are the left child, insert as right child of parent |
| 234 | if is_left_child: # We are the left child |
| 235 | parent_node["right"] = tree |
| 236 | else: |
| 237 | # If we are the right child, we can't insert "after" in the traditional sense |
| 238 | # We'll insert the new tree as the right child of parent, and make the current |
| 239 | # node the left child of the new tree |
| 240 | old_right = parent_node["right"] |
| 241 | new_tree_node = { |
| 242 | "value": tree["value"], |
| 243 | "left": old_right, |
| 244 | "right": tree.get("right") |
| 245 | } |
| 246 | parent_node["right"] = new_tree_node |
| 247 | # Update current to point to the new node |
| 248 | current = new_tree_node |
| 249 | |
| 250 | return Zipper(current, new_path) |
| 251 | |
| 252 | def delete(self) -> "Zipper | None": |
| 253 | """Remove the focus node and move focus to next > prev > parent""" |
| 254 | # Edge Case: Handle when we're at the root (no parent) |
| 255 | if not self.path: |
| 256 | raise ValueError("Cannot delete root") |
| 257 | |
| 258 | # Try to move focus in order: next > prev > parent |
| 259 | next_focus = self.next() |
| 260 | if next_focus is not None: |
| 261 | new_focus_path = next_focus.path |
| 262 | new_focus_tree = next_focus.tree |
| 263 | else: |
| 264 | prev_focus = self.prev() |
| 265 | if prev_focus is not None: |
| 266 | new_focus_path = prev_focus.path |
| 267 | new_focus_tree = prev_focus.tree |
| 268 | else: |
| 269 | parent_focus = self.up() |
| 270 | if parent_focus is not None: |
| 271 | new_focus_path = parent_focus.path |
| 272 | new_focus_tree = parent_focus.tree |
| 273 | else: |
| 274 | # This shouldn't happen if we have a path but no parent |
| 275 | return None |
| 276 | |
| 277 | # Get the root tree and copy the entire tree structure |
| 278 | root_zipper = self._get_root() |
| 279 | new_root_tree = self._copy_tree(root_zipper.tree) |
| 280 | |
| 281 | # Navigate to the equivalent position in the new tree and remove it |
| 282 | current = new_root_tree |
| 283 | path_to_current = [] |
| 284 | for parent, is_left in self.path: |
| 285 | path_to_current.append((current, is_left)) |
| 286 | if is_left: |
| 287 | current = current["left"] |
| 288 | else: |
| 289 | current = current["right"] |
| 290 | |
| 291 | # Get the parent in the new tree and remove the current node |
| 292 | if path_to_current: |
| 293 | parent_node, is_left_child = path_to_current[-1] |
| 294 | if is_left_child: |
| 295 | parent_node["left"] = None |
| 296 | else: |
| 297 | parent_node["right"] = None |
| 298 | |
| 299 | # Create new focus zipper based on the modified tree |
| 300 | # Navigate to the new focus position in the modified tree |
| 301 | new_focus_current = new_root_tree |
| 302 | new_focus_full_path = [] |
| 303 | for parent, is_left in new_focus_path: |
| 304 | new_focus_full_path.append((new_focus_current, is_left)) |
| 305 | if is_left: |
| 306 | new_focus_current = new_focus_current["left"] |
| 307 | else: |
| 308 | new_focus_current = new_focus_current["right"] |
| 309 | |
| 310 | return Zipper(new_focus_tree, new_focus_full_path) |
| 27 | 311 | |
| 28 | 312 | def to_tree(self) -> dict: |
| 29 | | pass |
| 313 | # Get the root zipper to access the full tree |
| 314 | root_zipper = self._get_root() |
| 315 | # Return a copy of the full tree |
| 316 | return self._copy_tree(root_zipper.tree) |
| 317 | |
| 318 | def _get_root(self): |
| 319 | """Helper method to get the root zipper""" |
| 320 | current = self |
| 321 | while current.path: |
| 322 | current = current.up() |
| 323 | return current |
| 324 | |
| 325 | def _rebuild_path(self, new_tree): |
| 326 | """Helper method to rebuild path with references to nodes in new tree""" |
| 327 | if not self.path: |
| 328 | return [] |
| 329 | |
| 330 | new_path = [] |
| 331 | current = new_tree |
| 332 | |
| 333 | # Navigate through the path to rebuild it with new tree references |
| 334 | for parent, is_left in self.path: |
| 335 | new_path.append((current, is_left)) |
| 336 | if is_left: |
| 337 | current = current["left"] |
| 338 | else: |
| 339 | current = current["right"] |
| 340 | |
| 341 | # The last element in path should point to the parent of current focus |
| 342 | # So we need to remove the last step to get the correct path |
| 343 | return new_path[:-1] if new_path else [] |
| 344 | |
| 345 | def _copy_tree(self, tree): |
| 346 | """Helper method to create a deep copy of a tree""" |
| 347 | # Edge Case: Handle when tree is None |
| 348 | if tree is None: |
| 349 | return None |
| 350 | |
| 351 | # Edge Case: Handle when tree doesn't have required keys |
| 352 | if "value" not in tree: |
| 353 | raise ValueError("Tree must have a 'value' key") |
| 354 | |
| 355 | copied_tree = { |
| 356 | "value": tree["value"], |
| 357 | "left": self._copy_tree(tree.get("left")), |
| 358 | "right": self._copy_tree(tree.get("right")) |
| 359 | } |
| 360 | return copied_tree |
| 361 | |
| 362 | # Handled Edge Cases: tree is None, current node is None, value is None, current node has no left child, current node has no right child, we're at the root (no parent), tree doesn't have required keys |