Class: Stupidedi::Zipper::AbstractCursor
- Inherits:
-
Object
- Object
- Stupidedi::Zipper::AbstractCursor
- Defined in:
- lib/stupidedi/zipper/abstract_cursor.rb
Direct Known Subclasses
Querying the Tree Location collapse
-
#between(other) ⇒ Array
Returns nodes between this zipper and the other, including ‘self.node` and `other.node` as end points.
-
#depth ⇒ Integer
Distance from the root node.
- #first? ⇒ Boolean
-
#flatten ⇒ Array
Flattens the subtree into an Array of nodes.
- #last? ⇒ Boolean
Traversing the Tree collapse
-
#child(n) ⇒ AbstractCursor
Navigate to the ‘nth` child node.
-
#children ⇒ Array<MemoizedCursor>
Returns a list of cursors, one pointing to each child node.
-
#dangle ⇒ AbstractCursor
Navigate to the first child node, or if there are no children, create a placeholder where the first child node will be placed.
-
#descendant(n, *ns) ⇒ AbstractCursor
Recursively descend to each node’s ‘nth` child.
-
#down ⇒ MemoizedCursor
Navigate to the first child node.
-
#first ⇒ AbstractCursor
Navigate to the first (leftmost) sibling node.
-
#last ⇒ AbstractCursor
Navigate to the last (rightmost) sibling node.
-
#next ⇒ AbstractCursor
Navigate to the next (rightward) sibling node.
-
#prev ⇒ AbstractCursor
Navigate to the previous (leftward) sibling node.
-
#root ⇒ RootCursor
Navigate to the root node.
-
#up ⇒ AbstractCursor
Navigate to the parent node.
Editing the Tree collapse
-
#append ⇒ EditedCursor
Insert a new sibling node after (to the right of) the current node, and navigate to the new sibling node.
-
#append_child(child) ⇒ EditedCursor
Insert a new child node after (to the right of) any existing children nodes and navigate to the new child node.
-
#delete ⇒ EditedCursor
Remove the current node, and navigate to the next (rightward) node if one exists.
-
#insert_left(sibling) ⇒ EditedCursor
Insert a new sibling node before (to the left of) the current node, and navigate to the new sibling node.
-
#insert_right(sibling) ⇒ EditedCursor
Insert a new sibling node after (to the right of) the current node, and navigate to the new sibling node.
-
#prepend ⇒ EditedCursor
Insert a new sibling node before (to the left of) the current node, and navigate to the new sibling node.
-
#prepend_child(child) ⇒ EditedCursor
Insert a new child node before (to the left of) any existing children nodes and navigate to the new child node.
-
#replace ⇒ AbstractCursor
Replace the current node with the given node.
Instance Method Summary collapse
Instance Method Details
#append ⇒ EditedCursor
Insert a new sibling node after (to the right of) the current node, and navigate to the new sibling node
291 |
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 291 abstract :append, :args => %w(sibling) |
#append_child(child) ⇒ EditedCursor
Insert a new child node after (to the right of) any existing children nodes and navigate to the new child node
327 328 329 330 331 332 333 334 335 |
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 327 def append_child(child) if node.leaf? raise Exceptions::ZipperError, "cannot add child to leaf node" end EditedCursor.new(child, Hole.new(node.children.reverse, path, []), self) end |
#between(other) ⇒ Array
This method assumes ‘other` is a zipper for the same tree as the tree wrapped by `this`. In general, there is no way to know if that is or isn’t the case, without comparing the entire tree. If this method is called on two different trees, the results are undefined.
Returns nodes between this zipper and the other, including ‘self.node` and `other.node` as end points. When this and the other zipper point to the same node within the tree, a single node is returned. Otherwise, the nodes are returned in order according to a left-to-right depth-first pre-order traversal.
52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 |
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 52 def between(other) # Collect ancestors of self, sorted oldest first (deepest last). This # forms a boundary of nodes, which is called a "spine" below zipper = self lspine = [self] until zipper.root? zipper = zipper.up lspine.unshift(zipper) end # Collect ancestors of self, sorted oldest first (deepest last). This # forms a list of boundary nodes, which is called a "spine" below zipper = other rspine = [other] until zipper.root? zipper = zipper.up rspine.unshift(zipper) end # Now we have two spines, both beginning with the root node. We remove # the prefix common to both spines. while a = lspine.first and b = rspine.first if a.path == b.path lspine.shift rspine.shift else break end end if lspine.empty? # The other node is a child of self's node, and rspine contains all # the nodes along the path between the two nodes, not including the # self node. return node.cons(rspine.map(&:node)) elsif rspine.empty? # Self's node is a child of other's node, and lspine contains all # the nodes along the path between the two nodes, not including the # other node return other.node.cons(lspine.map(&:node)) elsif lspine.head.path.position > rspine.head.path.position # The first elements of lspine and rspine are siblings that share a # common parent. Arrange them such that lspine is on the left, and # so rspine is on the right lspine, rspine = rspine, lspine end between = [] # Starting at the bottom of the left spine working upward, accumulate # all the nodes to the right of the spine. Remember this is contained # within the subtree under lspine.head lspine.each{|z| between << z.node } lspine.tail.reverse.each do |zipper1| until zipper1.last? zipper2 = zipper1.next between.concat(zipper2.flatten) end end # For the sibling nodes directly between (not including) lspine.head # and rspine.head, we can accumulate the entire subtrees. count = rspine.head.path.position - lspine.head.path.position - 1 zipper = lspine.head count.times do zipper = zipper.next between.concat(zipper.flatten) end between << rspine.head.node rspine.tail.each do |zipper| count = zipper.path.position zipper = zipper.first # We have to do a bit more work to traverse the siblings in left-to- # right order, because `zipper` is now the left spine. We start on # the first sibling and move left a fixed number of times count.times do between.concat(zipper.flatten) zipper = zipper.next end # Now zipper is along the left spine. We don't expand it here, but the # next item in rspine is the next child along the left spine between << zipper.node end between end |
#child(n) ⇒ AbstractCursor
Navigate to the ‘nth` child node
204 205 206 207 208 209 210 211 212 213 214 215 216 |
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 204 def child(n) if n < 0 raise Exceptions::ZipperError, "child index cannot be negative" end cursor = down until n.zero? cursor = cursor.next n -= 1 end cursor end |
#children ⇒ Array<MemoizedCursor>
Returns a list of cursors, one pointing to each child node.
221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 |
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 221 def children children = [] unless leaf? zipper = down children << zipper until zipper.last? zipper = zipper.next children << zipper end end children end |
#dangle ⇒ AbstractCursor
Navigate to the first child node, or if there are no children, create a placeholder where the first child node will be placed
188 189 190 191 192 193 194 195 196 197 198 199 |
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 188 def dangle if node.leaf? raise Exceptions::ZipperError, "cannot descend into leaf node" end if leaf? DanglingCursor.new(self) else down end end |
#delete ⇒ EditedCursor
Remove the current node, and navigate to the next (rightward) node if one exists. Otherwise, navigate to the previous (leftward) node if one exists. Otherwise, create a placeholder where the next sibling node will be created.
348 |
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 348 abstract :delete |
#depth ⇒ Integer
Distance from the root node
20 21 22 |
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 20 def depth path.depth end |
#descendant(n, *ns) ⇒ AbstractCursor
Recursively descend to each node’s ‘nth` child
240 241 242 243 244 245 246 247 248 |
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 240 def descendant(n, *ns) cursor = self n.cons(ns).each do |n| cursor = cursor.child(n) end cursor end |
#down ⇒ MemoizedCursor
Navigate to the first child node
170 171 172 173 174 175 176 177 178 179 180 181 182 |
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 170 def down @__down ||= begin if leaf? raise Exceptions::ZipperError, "cannot descend into leaf node" end head, *tail = @node.children MemoizedCursor.new(head, Hole.new([], @path, tail), self) end end |
#first ⇒ AbstractCursor
Navigate to the first (leftmost) sibling node
268 |
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 268 abstract :first |
#first? ⇒ Boolean
25 26 27 |
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 25 def first? path.first? end |
#flatten ⇒ Array
Flattens the subtree into an Array of nodes. The nodes are arranged according to a depth-first left-to-right preorder traversal.
152 153 154 155 156 157 158 159 160 161 162 |
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 152 def flatten nodes = [] queue = [node] while node = queue.shift nodes << node queue.unshift(*node.children) unless node.leaf? end nodes end |
#insert_left(sibling) ⇒ EditedCursor
Insert a new sibling node before (to the left of) the current node, and navigate to the new sibling node
305 306 307 |
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 305 def insert_left(sibling) prepend(sibling) end |
#insert_right(sibling) ⇒ EditedCursor
Insert a new sibling node after (to the right of) the current node, and navigate to the new sibling node
300 301 302 |
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 300 def insert_right(sibling) append(sibling) end |
#last ⇒ AbstractCursor
Navigate to the last (rightmost) sibling node
273 |
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 273 abstract :last |
#last? ⇒ Boolean
30 31 32 |
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 30 def last? path.last? end |
#next ⇒ AbstractCursor
Navigate to the next (rightward) sibling node
258 |
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 258 abstract :next |
#node ⇒ #leaf?, ...
11 |
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 11 abstract :node |
#prepend ⇒ EditedCursor
Insert a new sibling node before (to the left of) the current node, and navigate to the new sibling node
297 |
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 297 abstract :prepend, :args => %w(sibling) |
#prepend_child(child) ⇒ EditedCursor
Insert a new child node before (to the left of) any existing children nodes and navigate to the new child node
313 314 315 316 317 318 319 320 321 |
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 313 def prepend_child(child) if node.leaf? raise Exceptions::ZipperError, "cannot add child to leaf node" end EditedCursor.new(child, Hole.new([], path, node.children), self) end |
#prev ⇒ AbstractCursor
Navigate to the previous (leftward) sibling node
263 |
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 263 abstract :prev |
#replace ⇒ AbstractCursor
Replace the current node with the given node
340 |
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 340 abstract :replace, :args => %w(node) |
#root ⇒ RootCursor
Navigate to the root node
278 279 280 281 282 |
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 278 def root cursor = self cursor = cursor.up until cursor.root? cursor end |
#up ⇒ AbstractCursor
Navigate to the parent node
253 |
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 253 abstract :up |