| 1 | 1 | class Zipper: |
| 2 | def __init__(self, tree, breadcrumbs=None): |
| 3 | self.tree = tree |
| 4 | self.breadcrumbs = breadcrumbs or [] |
| 5 | |
| 2 | 6 | @staticmethod |
| 3 | 7 | def from_tree(tree): |
| 4 | | pass |
| 8 | """Create a zipper from a tree, focused on the root.""" |
| 9 | return Zipper(tree) |
| 5 | 10 | |
| 6 | 11 | def value(self): |
| 7 | | pass |
| 12 | """Get the value of the focus node.""" |
| 13 | # Edge Case: Empty tree or missing value |
| 14 | if not self.tree or 'value' not in self.tree: |
| 15 | return None |
| 16 | return self.tree['value'] |
| 8 | 17 | |
| 9 | | def set_value(self): |
| 10 | | pass |
| 18 | def set_value(self, value): |
| 19 | """Set the value of the focus node and return a new zipper.""" |
| 20 | # Edge Case: Empty tree |
| 21 | if not self.tree: |
| 22 | return Zipper({'value': value, 'left': None, 'right': None}, self.breadcrumbs) |
| 23 | |
| 24 | new_tree = { |
| 25 | 'value': value, |
| 26 | 'left': self.tree.get('left'), |
| 27 | 'right': self.tree.get('right') |
| 28 | } |
| 29 | return Zipper(new_tree, self.breadcrumbs) |
| 11 | 30 | |
| 12 | 31 | def left(self): |
| 13 | | pass |
| 32 | """Move focus to the left child and return a new zipper.""" |
| 33 | # Edge Case: Empty tree or no left child |
| 34 | if not self.tree or not self.tree.get('left'): |
| 35 | return None |
| 36 | |
| 37 | new_breadcrumbs = self.breadcrumbs + [{ |
| 38 | 'parent': self.tree, |
| 39 | 'side': 'left', |
| 40 | 'sibling': self.tree.get('right') |
| 41 | }] |
| 42 | |
| 43 | return Zipper(self.tree['left'], new_breadcrumbs) |
| 14 | 44 | |
| 15 | | def set_left(self): |
| 16 | | pass |
| 45 | def set_left(self, subtree): |
| 46 | """Set the left child of the focus node and return a new zipper.""" |
| 47 | # Edge Case: Empty tree |
| 48 | if not self.tree: |
| 49 | new_tree = {'value': None, 'left': subtree, 'right': None} |
| 50 | return Zipper(new_tree, self.breadcrumbs) |
| 51 | |
| 52 | new_tree = { |
| 53 | 'value': self.tree['value'], |
| 54 | 'left': subtree, |
| 55 | 'right': self.tree.get('right') |
| 56 | } |
| 57 | return Zipper(new_tree, self.breadcrumbs) |
| 17 | 58 | |
| 18 | 59 | def right(self): |
| 19 | | pass |
| 60 | """Move focus to the right child and return a new zipper.""" |
| 61 | # Edge Case: Empty tree or no right child |
| 62 | if not self.tree or not self.tree.get('right'): |
| 63 | return None |
| 64 | |
| 65 | new_breadcrumbs = self.breadcrumbs + [{ |
| 66 | 'parent': self.tree, |
| 67 | 'side': 'right', |
| 68 | 'sibling': self.tree.get('left') |
| 69 | }] |
| 70 | |
| 71 | return Zipper(self.tree['right'], new_breadcrumbs) |
| 20 | 72 | |
| 21 | | def set_right(self): |
| 22 | | pass |
| 73 | def set_right(self, subtree): |
| 74 | """Set the right child of the focus node and return a new zipper.""" |
| 75 | # Edge Case: Empty tree |
| 76 | if not self.tree: |
| 77 | new_tree = {'value': None, 'left': None, 'right': subtree} |
| 78 | return Zipper(new_tree, self.breadcrumbs) |
| 79 | |
| 80 | new_tree = { |
| 81 | 'value': self.tree['value'], |
| 82 | 'left': self.tree.get('left'), |
| 83 | 'right': subtree |
| 84 | } |
| 85 | return Zipper(new_tree, self.breadcrumbs) |
| 23 | 86 | |
| 24 | 87 | def up(self): |
| 25 | | pass |
| 88 | """Move focus to the parent and return a new zipper.""" |
| 89 | # Edge Case: Already at root (no breadcrumbs) |
| 90 | if not self.breadcrumbs: |
| 91 | return None |
| 92 | |
| 93 | last_crumb = self.breadcrumbs[-1] |
| 94 | parent = last_crumb['parent'] |
| 95 | sibling = last_crumb['sibling'] |
| 96 | side = last_crumb['side'] |
| 97 | |
| 98 | # Reconstruct the parent with current tree in the correct position |
| 99 | new_parent = parent.copy() |
| 100 | new_parent[side] = self.tree |
| 101 | if sibling is not None: |
| 102 | opposite_side = 'left' if side == 'right' else 'right' |
| 103 | new_parent[opposite_side] = sibling |
| 104 | else: |
| 105 | opposite_side = 'left' if side == 'right' else 'right' |
| 106 | new_parent[opposite_side] = None |
| 107 | |
| 108 | return Zipper(new_parent, self.breadcrumbs[:-1]) |
| 26 | 109 | |
| 27 | 110 | def to_tree(self): |
| 28 | | pass |
| 111 | """Get the full tree from the zipper.""" |
| 112 | # Edge Case: Empty tree |
| 113 | if not self.tree and not self.breadcrumbs: |
| 114 | return None |
| 115 | |
| 116 | current = self |
| 117 | while current.breadcrumbs: |
| 118 | current = current.up() |
| 119 | # Edge Case: Reached top but up() returned None |
| 120 | if current is None: |
| 121 | return None |
| 122 | return current.tree |
| 123 | |
| 124 | def prev(self): |
| 125 | """Move focus to the previous child (left child) and return a new zipper.""" |
| 126 | return self.left() |
| 127 | |
| 128 | def next(self): |
| 129 | """Move focus to the next child (right child) and return a new zipper.""" |
| 130 | return self.right() |
| 131 | |
| 132 | def insert_before(self, subtree): |
| 133 | """Insert a new subtree before the focus node (as left child) and return a new zipper.""" |
| 134 | # Save current left child |
| 135 | current_left = self.tree.get('left') |
| 136 | # Create new subtree with the original left child as its left child |
| 137 | if subtree: |
| 138 | new_subtree = { |
| 139 | 'value': subtree.get('value'), |
| 140 | 'left': current_left, |
| 141 | 'right': subtree.get('right') |
| 142 | } |
| 143 | else: |
| 144 | new_subtree = {'value': None, 'left': current_left, 'right': None} |
| 145 | # Set the new subtree as left child |
| 146 | return self.set_left(new_subtree) |
| 147 | |
| 148 | def insert_after(self, subtree): |
| 149 | """Insert a new subtree after the focus node (as right child) and return a new zipper.""" |
| 150 | # Save current right child |
| 151 | current_right = self.tree.get('right') |
| 152 | # Create new subtree with the original right child as its right child |
| 153 | if subtree: |
| 154 | new_subtree = { |
| 155 | 'value': subtree.get('value'), |
| 156 | 'left': subtree.get('left'), |
| 157 | 'right': current_right |
| 158 | } |
| 159 | else: |
| 160 | new_subtree = {'value': None, 'left': None, 'right': current_right} |
| 161 | # Set the new subtree as right child |
| 162 | return self.set_right(new_subtree) |
| 163 | |
| 164 | def delete(self): |
| 165 | """Remove the focus node and move focus to next, prev, or parent. Return a new zipper.""" |
| 166 | if not self.breadcrumbs: |
| 167 | # At root - return empty tree |
| 168 | return Zipper(None, []) |
| 169 | |
| 170 | last_crumb = self.breadcrumbs[-1] |
| 171 | parent = last_crumb['parent'] |
| 172 | side = last_crumb['side'] |
| 173 | sibling = last_crumb['sibling'] |
| 174 | |
| 175 | # Priority: next (right) → prev (left) → parent |
| 176 | if self.tree.get('right'): |
| 177 | # Move to right child and remove current node from parent |
| 178 | new_parent = parent.copy() |
| 179 | new_parent[side] = self.tree['right'] |
| 180 | return Zipper(self.tree['right'], self.breadcrumbs[:-1] + [{ |
| 181 | 'parent': new_parent, |
| 182 | 'side': side, |
| 183 | 'sibling': sibling |
| 184 | }]) |
| 185 | elif self.tree.get('left'): |
| 186 | # Move to left child and remove current node from parent |
| 187 | new_parent = parent.copy() |
| 188 | new_parent[side] = self.tree['left'] |
| 189 | return Zipper(self.tree['left'], self.breadcrumbs[:-1] + [{ |
| 190 | 'parent': new_parent, |
| 191 | 'side': side, |
| 192 | 'sibling': sibling |
| 193 | }]) |
| 194 | else: |
| 195 | # No children, move to parent and remove this node |
| 196 | new_parent = parent.copy() |
| 197 | new_parent[side] = None |
| 198 | return Zipper(new_parent, self.breadcrumbs[:-1]) |
| 199 | |
| 200 | # Handled Edge Cases: Empty tree, missing value, no left child, no right child, already at root |