Class: Fr::TZipper::AbstractCursor

Inherits:
Object
  • Object
show all
Defined in:
lib/fr/tzipper/abstract_cursor.rb

Querying the Tree Location collapse

Traversing the Tree collapse

Editing the Tree collapse

Instance Method Details

#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:



323
324
325
326
327
328
329
330
331
 
# File 'lib/fr/tzipper/abstract_cursor.rb', line 323

def append_child(child)
  if node.leaf?
    raise Errors::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:



48
49
50
51
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
 
# File 'lib/fr/tzipper/abstract_cursor.rb', line 48

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 |zipper|
    until zipper.last?
      zipper = zipper.next
      between.concat(zipper.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:



200
201
202
203
204
205
206
207
208
209
210
211
212
 
# File 'lib/fr/tzipper/abstract_cursor.rb', line 200

def child(n)
  if n < 0
    raise Errors::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:



217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
 
# File 'lib/fr/tzipper/abstract_cursor.rb', line 217

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:



184
185
186
187
188
189
190
191
192
193
194
195
 
# File 'lib/fr/tzipper/abstract_cursor.rb', line 184

def dangle
  if node.leaf?
    raise Errors::ZipperError,
      "cannot descend into leaf node"
  end

  if leaf?
    DanglingCursor.new(self)
  else
    down
  end
end

#depth ⇒ Object 



16
17
18
 
# File 'lib/fr/tzipper/abstract_cursor.rb', line 16

def depth
  path.depth
end

#descendant(n, *ns) ⇒ AbstractCursor

Recursively descend to each node’s ‘nth` child

Returns:



236
237
238
239
240
241
242
243
244
 
# File 'lib/fr/tzipper/abstract_cursor.rb', line 236

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:



166
167
168
169
170
171
172
173
174
175
176
177
178
 
# File 'lib/fr/tzipper/abstract_cursor.rb', line 166

def down
  @__down ||= begin
    if leaf?
      raise Errors::ZipperError,
        "cannot descend into leaf node"
    end

    head, *tail = @node.children

    MemoizedCursor.new(head,
      Hole.new([], @path, tail), self)
  end
end

#first? ⇒ Boolean

Returns:

  • (Boolean) 


21
22
23
 
# File 'lib/fr/tzipper/abstract_cursor.rb', line 21

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:



148
149
150
151
152
153
154
155
156
157
158
 
# File 'lib/fr/tzipper/abstract_cursor.rb', line 148

def flatten
  nodes = []
  queue = [node]

  while node = queue.shift
    nodes << node
    queue.unshift(*node.children) unless node.leaf?
  end

  nodes
end

#insert_left(sibling) ⇒ Object 



301
302
303
 
# File 'lib/fr/tzipper/abstract_cursor.rb', line 301

def insert_left(sibling)
  prepend(sibling)
end

#insert_right(sibling) ⇒ Object 



296
297
298
 
# File 'lib/fr/tzipper/abstract_cursor.rb', line 296

def insert_right(sibling)
  append(sibling)
end

#last? ⇒ Boolean

Returns:

  • (Boolean) 


26
27
28
 
# File 'lib/fr/tzipper/abstract_cursor.rb', line 26

def last?
  path.last?
end

#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:



309
310
311
312
313
314
315
316
317
 
# File 'lib/fr/tzipper/abstract_cursor.rb', line 309

def prepend_child(child)
  if node.leaf?
    raise Errors::ZipperError,
      "cannot add child to leaf node"
  end

  EditedCursor.new(child,
    Hole.new([], path, node.children), self)
end

#root ⇒ RootCursor

Navigate to the root node

Returns:



274
275
276
277
278
 
# File 'lib/fr/tzipper/abstract_cursor.rb', line 274

def root
  cursor = self
  cursor = cursor.up until cursor.root?
  cursor
end