| 1 | 1 | class Zipper: |
| 2 | | # Tree is a dict with keys "value" (int), "left" (dict or None), "right" (dict or None) |
| 2 | """ |
| 3 | A zipper for navigating and manipulating a binary tree. |
| 4 | |
| 5 | A zipper contains a data structure and a pointer (focus) into that data structure. |
| 6 | It supports moving through the tree and modifying it in a functional way. |
| 7 | |
| 8 | Attributes: |
| 9 | _focus (dict): The current node that is focused. |
| 10 | _path (list): A list of tuples representing the path from root to focus. |
| 11 | Each tuple contains (parent_node, direction) where direction is 'left' or 'right'. |
| 12 | _root (dict): Reference to the root of the tree for to_tree operation. |
| 13 | """ |
| 14 | |
| 15 | def __init__(self, focus, path=None, root=None): |
| 16 | """ |
| 17 | Initialize a Zipper. |
| 18 | |
| 19 | Args: |
| 20 | focus (dict): The node that is currently focused. |
| 21 | path (list): Path from root to focus. |
| 22 | root (dict): Reference to the root node. |
| 23 | """ |
| 24 | self._focus = focus |
| 25 | self._path = path if path is not None else [] |
| 26 | self._root = root if root is not None else focus |
| 27 | |
| 3 | 28 | @staticmethod |
| 4 | 29 | def from_tree(tree: dict) -> "Zipper": |
| 5 | | pass |
| 6 | | |
| 30 | """ |
| 31 | Create a zipper from a binary tree. |
| 32 | |
| 33 | Args: |
| 34 | tree (dict): A binary tree represented as a dict with keys "value", "left", and "right". |
| 35 | |
| 36 | Returns: |
| 37 | Zipper: A new zipper with focus on the root node. |
| 38 | |
| 39 | Edge Cases: |
| 40 | - Empty tree (None): Returns None. |
| 41 | """ |
| 42 | # Edge Case: Empty tree |
| 43 | if tree is None: |
| 44 | return None |
| 45 | return Zipper(tree) |
| 46 | |
| 7 | 47 | def value(self) -> int: |
| 8 | | pass |
| 9 | | |
| 48 | """ |
| 49 | Get the value of the focus node. |
| 50 | |
| 51 | Returns: |
| 52 | int: The value of the focus node. |
| 53 | |
| 54 | Edge Cases: |
| 55 | - Focus is None: This shouldn't happen with a properly constructed zipper. |
| 56 | """ |
| 57 | # Edge Case: Focus is None (shouldn't happen in normal operation) |
| 58 | if self._focus is None: |
| 59 | raise ValueError("Focus is None") |
| 60 | return self._focus["value"] |
| 61 | |
| 10 | 62 | def set_value(self, value: int) -> "Zipper": |
| 11 | | pass |
| 12 | | |
| 63 | """ |
| 64 | Set the value of the focus node and return a new zipper. |
| 65 | |
| 66 | Args: |
| 67 | value (int): The new value for the focus node. |
| 68 | |
| 69 | Returns: |
| 70 | Zipper: A new zipper with updated focus node value. |
| 71 | |
| 72 | Edge Cases: |
| 73 | - Focus is None: Returns a new zipper with the same state. |
| 74 | """ |
| 75 | # Edge Case: Focus is None |
| 76 | if self._focus is None: |
| 77 | return Zipper(self._focus, self._path, self._root) |
| 78 | |
| 79 | new_focus = { |
| 80 | "value": value, |
| 81 | "left": self._focus["left"], |
| 82 | "right": self._focus["right"] |
| 83 | } |
| 84 | |
| 85 | # Reconstruct the tree with the new focus |
| 86 | new_root = self._reconstruct_tree(new_focus) |
| 87 | |
| 88 | # Create a new path to the focus with updated focus node |
| 89 | new_path = [] |
| 90 | current = new_root |
| 91 | for parent, direction in self._path: |
| 92 | new_path.append((current, direction)) |
| 93 | current = current[direction] |
| 94 | |
| 95 | return Zipper(new_focus, new_path, new_root) |
| 96 | |
| 13 | 97 | def left(self) -> "Zipper | None": |
| 14 | | pass |
| 15 | | |
| 98 | """ |
| 99 | Move the focus to the left child and return a new zipper. |
| 100 | |
| 101 | Returns: |
| 102 | Zipper | None: A new zipper with focus on the left child, or None if no left child. |
| 103 | |
| 104 | Edge Cases: |
| 105 | - Focus is None: Returns None. |
| 106 | - No left child: Returns None. |
| 107 | """ |
| 108 | # Edge Case: Focus is None |
| 109 | if self._focus is None: |
| 110 | return None |
| 111 | |
| 112 | # Edge Case: No left child |
| 113 | if self._focus["left"] is None: |
| 114 | return None |
| 115 | |
| 116 | new_path = self._path + [(self._focus, "left")] |
| 117 | return Zipper(self._focus["left"], new_path, self._root) |
| 118 | |
| 16 | 119 | def set_left(self, tree: dict | None) -> "Zipper": |
| 17 | | pass |
| 18 | | |
| 120 | """ |
| 121 | Set the left child of the focus node and return a new zipper. |
| 122 | |
| 123 | Args: |
| 124 | tree (dict | None): The new left subtree. |
| 125 | |
| 126 | Returns: |
| 127 | Zipper: A new zipper with updated left child. |
| 128 | |
| 129 | Edge Cases: |
| 130 | - Focus is None: Returns a new zipper with the same state. |
| 131 | """ |
| 132 | # Edge Case: Focus is None |
| 133 | if self._focus is None: |
| 134 | return Zipper(self._focus, self._path, self._root) |
| 135 | |
| 136 | new_focus = { |
| 137 | "value": self._focus["value"], |
| 138 | "left": tree, |
| 139 | "right": self._focus["right"] |
| 140 | } |
| 141 | |
| 142 | # Reconstruct the tree with the new focus |
| 143 | new_root = self._reconstruct_tree(new_focus) |
| 144 | |
| 145 | # Create a new path to the focus with updated focus node |
| 146 | new_path = [] |
| 147 | current = new_root |
| 148 | for parent, direction in self._path: |
| 149 | new_path.append((current, direction)) |
| 150 | current = current[direction] |
| 151 | |
| 152 | return Zipper(new_focus, new_path, new_root) |
| 153 | |
| 19 | 154 | def right(self) -> "Zipper | None": |
| 20 | | pass |
| 21 | | |
| 155 | """ |
| 156 | Move the focus to the right child and return a new zipper. |
| 157 | |
| 158 | Returns: |
| 159 | Zipper | None: A new zipper with focus on the right child, or None if no right child. |
| 160 | |
| 161 | Edge Cases: |
| 162 | - Focus is None: Returns None. |
| 163 | - No right child: Returns None. |
| 164 | """ |
| 165 | # Edge Case: Focus is None |
| 166 | if self._focus is None: |
| 167 | return None |
| 168 | |
| 169 | # Edge Case: No right child |
| 170 | if self._focus["right"] is None: |
| 171 | return None |
| 172 | |
| 173 | new_path = self._path + [(self._focus, "right")] |
| 174 | return Zipper(self._focus["right"], new_path, self._root) |
| 175 | |
| 22 | 176 | def set_right(self, tree: dict | None) -> "Zipper": |
| 23 | | pass |
| 24 | | |
| 177 | """ |
| 178 | Set the right child of the focus node and return a new zipper. |
| 179 | |
| 180 | Args: |
| 181 | tree (dict | None): The new right subtree. |
| 182 | |
| 183 | Returns: |
| 184 | Zipper: A new zipper with updated right child. |
| 185 | |
| 186 | Edge Cases: |
| 187 | - Focus is None: Returns a new zipper with the same state. |
| 188 | """ |
| 189 | # Edge Case: Focus is None |
| 190 | if self._focus is None: |
| 191 | return Zipper(self._focus, self._path, self._root) |
| 192 | |
| 193 | new_focus = { |
| 194 | "value": self._focus["value"], |
| 195 | "left": self._focus["left"], |
| 196 | "right": tree |
| 197 | } |
| 198 | |
| 199 | # Reconstruct the tree with the new focus |
| 200 | new_root = self._reconstruct_tree(new_focus) |
| 201 | |
| 202 | # Create a new path to the focus with updated focus node |
| 203 | new_path = [] |
| 204 | current = new_root |
| 205 | for parent, direction in self._path: |
| 206 | new_path.append((current, direction)) |
| 207 | current = current[direction] |
| 208 | |
| 209 | return Zipper(new_focus, new_path, new_root) |
| 210 | |
| 25 | 211 | def up(self) -> "Zipper | None": |
| 26 | | pass |
| 27 | | |
| 212 | """ |
| 213 | Move the focus to the parent node and return a new zipper. |
| 214 | |
| 215 | Returns: |
| 216 | Zipper | None: A new zipper with focus on the parent, or None if at root. |
| 217 | |
| 218 | Edge Cases: |
| 219 | - Focus is None: Returns None. |
| 220 | - Already at root (empty path): Returns None. |
| 221 | """ |
| 222 | # Edge Case: Focus is None |
| 223 | if self._focus is None: |
| 224 | return None |
| 225 | |
| 226 | # Edge Case: Already at root |
| 227 | if not self._path: |
| 228 | return None |
| 229 | |
| 230 | # Move up one level in the path |
| 231 | parent, direction = self._path[-1] |
| 232 | new_path = self._path[:-1] |
| 233 | |
| 234 | return Zipper(parent, new_path, self._root) |
| 235 | |
| 28 | 236 | def to_tree(self) -> dict: |
| 29 | | pass |
| 237 | """ |
| 238 | Get the complete tree from the zipper. |
| 239 | |
| 240 | Returns: |
| 241 | dict: The complete binary tree. |
| 242 | |
| 243 | Edge Cases: |
| 244 | - Root is None: Returns None. |
| 245 | """ |
| 246 | # Edge Case: Root is None |
| 247 | if self._root is None: |
| 248 | return None |
| 249 | return self._root |
| 250 | |
| 251 | def prev(self) -> "Zipper | None": |
| 252 | """ |
| 253 | Move the focus to the previous sibling (left sibling) and return a new zipper. |
| 254 | In a binary tree, this means moving from a right child to its left sibling. |
| 255 | |
| 256 | Returns: |
| 257 | Zipper | None: A new zipper with focus on the previous sibling, or None if no previous sibling. |
| 258 | """ |
| 259 | # Edge Case: Focus is None or at root (no parent) |
| 260 | if self._focus is None or not self._path: |
| 261 | return None |
| 262 | |
| 263 | parent, direction = self._path[-1] |
| 264 | |
| 265 | # If current node is the right child, move to the left child of the same parent |
| 266 | if direction == "right" and parent["left"] is not None: |
| 267 | new_path = self._path[:-1] + [(parent, "left")] |
| 268 | return Zipper(parent["left"], new_path, self._root) |
| 269 | |
| 270 | # No previous sibling |
| 271 | return None |
| 272 | |
| 273 | def next(self) -> "Zipper | None": |
| 274 | """ |
| 275 | Move the focus to the next sibling (right sibling) and return a new zipper. |
| 276 | In a binary tree, this means moving from a left child to its right sibling. |
| 277 | |
| 278 | Returns: |
| 279 | Zipper | None: A new zipper with focus on the next sibling, or None if no next sibling. |
| 280 | """ |
| 281 | # Edge Case: Focus is None or at root (no parent) |
| 282 | if self._focus is None or not self._path: |
| 283 | return None |
| 284 | |
| 285 | parent, direction = self._path[-1] |
| 286 | |
| 287 | # If current node is the left child, move to the right child of the same parent |
| 288 | if direction == "left" and parent["right"] is not None: |
| 289 | new_path = self._path[:-1] + [(parent, "right")] |
| 290 | return Zipper(parent["right"], new_path, self._root) |
| 291 | |
| 292 | # No next sibling |
| 293 | return None |
| 294 | |
| 295 | def insert_before(self, tree: dict | None) -> "Zipper": |
| 296 | """ |
| 297 | Insert a new subtree before the focus node. |
| 298 | In a binary tree, this means: |
| 299 | - If focus is a right child, set the left child of the parent to the new tree |
| 300 | - If focus is a left child, we cannot insert "before" it in a binary tree structure, |
| 301 | so we'll insert as the left child of the focus node itself |
| 302 | |
| 303 | Args: |
| 304 | tree (dict | None): The new subtree to insert. |
| 305 | |
| 306 | Returns: |
| 307 | Zipper: A new zipper with the inserted subtree. |
| 308 | """ |
| 309 | # Edge Case: Focus is None or at root |
| 310 | if self._focus is None or not self._path: |
| 311 | # If at root, insert as left child of the focus node |
| 312 | return self.set_left(tree) |
| 313 | |
| 314 | parent, direction = self._path[-1] |
| 315 | |
| 316 | # Create a new parent with the inserted tree |
| 317 | new_parent = { |
| 318 | "value": parent["value"], |
| 319 | "left": parent["left"], |
| 320 | "right": parent["right"] |
| 321 | } |
| 322 | |
| 323 | if direction == "right": |
| 324 | # Insert before a right child by setting parent's left child |
| 325 | new_parent["left"] = tree |
| 326 | new_focus = self._focus |
| 327 | else: |
| 328 | # Insert before a left child by setting focus's left child |
| 329 | new_focus = { |
| 330 | "value": self._focus["value"], |
| 331 | "left": tree, |
| 332 | "right": self._focus["right"] |
| 333 | } |
| 334 | |
| 335 | # Reconstruct the tree |
| 336 | new_root = self._reconstruct_tree(new_focus if direction == "left" else new_parent) |
| 337 | |
| 338 | # Create a new path |
| 339 | new_path = [] |
| 340 | current = new_root |
| 341 | for p, d in self._path: |
| 342 | # Update the parent in the path if it was modified |
| 343 | if direction == "right" and p is parent: |
| 344 | new_path.append((new_parent, d)) |
| 345 | current = new_parent |
| 346 | else: |
| 347 | new_path.append((current, d)) |
| 348 | current = current[d] |
| 349 | |
| 350 | # Focus should be the same node but in the new tree |
| 351 | final_focus = new_root |
| 352 | for _, d in self._path: |
| 353 | final_focus = final_focus[d] |
| 354 | |
| 355 | return Zipper(final_focus, new_path, new_root) |
| 356 | |
| 357 | def insert_after(self, tree: dict | None) -> "Zipper": |
| 358 | """ |
| 359 | Insert a new subtree after the focus node. |
| 360 | In a binary tree, this means: |
| 361 | - If focus is a left child, set the right child of the parent to the new tree |
| 362 | - If focus is a right child, we cannot insert "after" it in a binary tree structure, |
| 363 | so we'll insert as the right child of the focus node itself |
| 364 | |
| 365 | Args: |
| 366 | tree (dict | None): The new subtree to insert. |
| 367 | |
| 368 | Returns: |
| 369 | Zipper: A new zipper with the inserted subtree. |
| 370 | """ |
| 371 | # Edge Case: Focus is None or at root |
| 372 | if self._focus is None or not self._path: |
| 373 | # If at root, insert as right child of the focus node |
| 374 | return self.set_right(tree) |
| 375 | |
| 376 | parent, direction = self._path[-1] |
| 377 | |
| 378 | # Create a new parent with the inserted tree |
| 379 | new_parent = { |
| 380 | "value": parent["value"], |
| 381 | "left": parent["left"], |
| 382 | "right": parent["right"] |
| 383 | } |
| 384 | |
| 385 | if direction == "left": |
| 386 | # Insert after a left child by setting parent's right child |
| 387 | new_parent["right"] = tree |
| 388 | new_focus = self._focus |
| 389 | else: |
| 390 | # Insert after a right child by setting focus's right child |
| 391 | new_focus = { |
| 392 | "value": self._focus["value"], |
| 393 | "left": self._focus["left"], |
| 394 | "right": tree |
| 395 | } |
| 396 | |
| 397 | # Reconstruct the tree |
| 398 | new_root = self._reconstruct_tree(new_focus if direction == "right" else new_parent) |
| 399 | |
| 400 | # Create a new path |
| 401 | new_path = [] |
| 402 | current = new_root |
| 403 | for p, d in self._path: |
| 404 | # Update the parent in the path if it was modified |
| 405 | if direction == "left" and p is parent: |
| 406 | new_path.append((new_parent, d)) |
| 407 | current = new_parent |
| 408 | else: |
| 409 | new_path.append((current, d)) |
| 410 | current = current[d] |
| 411 | |
| 412 | # Focus should be the same node but in the new tree |
| 413 | final_focus = new_root |
| 414 | for _, d in self._path: |
| 415 | final_focus = final_focus[d] |
| 416 | |
| 417 | return Zipper(final_focus, new_path, new_root) |
| 418 | |
| 419 | def delete(self) -> "Zipper | None": |
| 420 | """ |
| 421 | Remove the focus node and all subtrees. |
| 422 | Focus moves to the next node if possible, otherwise to the prev node if possible, |
| 423 | otherwise to the parent node. |
| 424 | |
| 425 | Returns: |
| 426 | Zipper | None: A new zipper with focus moved according to the priority, |
| 427 | or None if the tree becomes empty. |
| 428 | """ |
| 429 | # Edge Case: Focus is None or at root with no children |
| 430 | if self._focus is None: |
| 431 | return None |
| 432 | |
| 433 | if not self._path: # At root |
| 434 | # Try next priority: left child, then right child |
| 435 | if self._focus["left"] is not None: |
| 436 | return Zipper(self._focus["left"], [], self._focus["left"]) |
| 437 | elif self._focus["right"] is not None: |
| 438 | return Zipper(self._focus["right"], [], self._focus["right"]) |
| 439 | else: |
| 440 | # Tree becomes empty |
| 441 | return None |
| 442 | |
| 443 | # Get parent and direction |
| 444 | parent, direction = self._path[-1] |
| 445 | |
| 446 | # Create a new parent without the focus node |
| 447 | new_parent = { |
| 448 | "value": parent["value"], |
| 449 | "left": parent["left"], |
| 450 | "right": parent["right"] |
| 451 | } |
| 452 | new_parent[direction] = None |
| 453 | |
| 454 | # Reconstruct the tree |
| 455 | new_root = self._reconstruct_tree(new_parent) |
| 456 | |
| 457 | # Determine where to move focus based on priority |
| 458 | # 1. Try next (right sibling if focus was left child) |
| 459 | if direction == "left" and parent["right"] is not None: |
| 460 | new_path = self._path[:-1] + [(new_parent, "right")] |
| 461 | return Zipper(parent["right"], new_path, new_root) |
| 462 | |
| 463 | # 2. Try prev (left sibling if focus was right child) |
| 464 | elif direction == "right" and parent["left"] is not None: |
| 465 | new_path = self._path[:-1] + [(new_parent, "left")] |
| 466 | return Zipper(parent["left"], new_path, new_root) |
| 467 | |
| 468 | # 3. Move to parent |
| 469 | if len(self._path) > 1: |
| 470 | # Reconstruct path to parent |
| 471 | new_path = self._path[:-1] |
| 472 | final_parent, _ = new_path[-1] |
| 473 | return Zipper(final_parent, new_path[:-1], new_root) |
| 474 | else: |
| 475 | # Parent is root |
| 476 | return Zipper(new_root, [], new_root) |
| 477 | |
| 478 | def _reconstruct_tree(self, new_focus): |
| 479 | """ |
| 480 | Reconstruct the tree with a new focus node. |
| 481 | |
| 482 | Args: |
| 483 | new_focus (dict): The new focus node. |
| 484 | |
| 485 | Returns: |
| 486 | dict: The reconstructed tree. |
| 487 | """ |
| 488 | # If we're at the root, the new_focus is the new root |
| 489 | if not self._path: |
| 490 | return new_focus |
| 491 | |
| 492 | # Build from the bottom up |
| 493 | current = new_focus |
| 494 | # Go through the path in reverse to rebuild the tree |
| 495 | for parent, direction in reversed(self._path): |
| 496 | updated_parent = { |
| 497 | "value": parent["value"], |
| 498 | "left": parent["left"], |
| 499 | "right": parent["right"] |
| 500 | } |
| 501 | updated_parent[direction] = current |
| 502 | current = updated_parent |
| 503 | |
| 504 | return current |
| 505 | |
| 506 | # Handled Edge Cases: Empty tree, Focus is None, No left child, No right child, Already at root |