Class: Stupidedi::Zipper::AbstractCursor

Inherits:
Object
  • Object
show all
Defined in:
lib/stupidedi/zipper/abstract_cursor.rb

Querying the Tree Location collapse

Traversing the Tree collapse

Editing the Tree collapse

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

Returns:



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

Returns:



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

Note:

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.

Returns:

  • (Array) 


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

Returns:



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.

Returns:



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

Returns:



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.

Returns:



348
 
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 348

abstract :delete

#depth ⇒ Integer

Distance from the root node

Returns:

  • (Integer) 


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

Returns:



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

Returns:



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

Returns:



268
 
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 268

abstract :first

#first? ⇒ Boolean

Returns:

  • (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.

Returns:

  • (Array) 


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

Returns:



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

Returns:



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

Returns:



273
 
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 273

abstract :last

#last? ⇒ Boolean

Returns:

  • (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

Returns:



258
 
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 258

abstract :next

#node ⇒ #leaf?, ...

Returns:



11
 
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 11

abstract :node

#path ⇒ AbstractPath

Returns:



14
 
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 14

abstract :path

#prepend ⇒ EditedCursor

Insert a new sibling node before (to the left of) the current node, and navigate to the new sibling node

Returns:



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

Returns:



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

Returns:



263
 
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 263

abstract :prev

#replace ⇒ AbstractCursor

Replace the current node with the given node

Returns:



340
 
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 340

abstract :replace, :args => %w(node)

#root ⇒ RootCursor

Navigate to the root node

Returns:



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

Returns:



253
 
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 253

abstract :up