Class: Stupidedi::Zipper::AbstractCursor

323
324
325
326
327
328
329
330
331

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

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

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/stupidedi/zipper/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

200
201
202
203
204
205
206
207
208
209
210
211
212

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

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

217
218
219
220
221
222
223
224
225
226
227
228
229
230
231

# File 'lib/stupidedi/zipper/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

184
185
186
187
188
189
190
191
192
193
194
195

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

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

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

344

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

abstract :delete

16
17
18

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

def depth
  path.depth
end

236
237
238
239
240
241
242
243
244

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

def descendant(n, *ns)
  cursor = self

  n.cons(ns).each do |n|
    cursor = cursor.child(n)
  end

  cursor
end

166
167
168
169
170
171
172
173
174
175
176
177
178

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

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

264

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

abstract :first

21
22
23

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

def first?
  path.first?
end

148
149
150
151
152
153
154
155
156
157
158

# File 'lib/stupidedi/zipper/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

301
302
303

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

def insert_left(sibling)
  prepend(sibling)
end

296
297
298

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

def insert_right(sibling)
  append(sibling)
end

269

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

abstract :last

26
27
28

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

def last?
  path.last?
end

254

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

abstract :next

7

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

abstract :node

10

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

abstract :path

293

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

abstract :prepend, :args => %w(sibling)

309
310
311
312
313
314
315
316
317

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

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

259

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

abstract :prev

336

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

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

274
275
276
277
278

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

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

249

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

abstract :up