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(sibling) ⇒ EditedCursor

Insert a new sibling node after (to the right of) the current node, and navigate to the new sibling node

Returns:



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

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:



324
325
326
327
328
329
330
331
332
 
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 324

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) 


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
143
 
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 49

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



201
202
203
204
205
206
207
208
209
210
211
212
213
 
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 201

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:



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

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:



185
186
187
188
189
190
191
192
193
194
195
196
 
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 185

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:



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

abstract :delete

#depth ⇒ Integer

Distance from the root node

Returns:

  • (Integer) 


17
18
19
 
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 17

def depth
  path.depth
end

#descendant(n, *ns) ⇒ AbstractCursor

Recursively descend to each node's nth child

Returns:



237
238
239
240
241
242
243
244
245
 
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 237

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:



167
168
169
170
171
172
173
174
175
176
177
178
179
 
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 167

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:



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

abstract :first

#first? ⇒ Boolean

True when the node has no leftward siblings

Returns:

  • (Boolean) 


22
23
24
 
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 22

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) 


149
150
151
152
153
154
155
156
157
158
159
 
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 149

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:



302
303
304
 
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 302

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:



297
298
299
 
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 297

def insert_right(sibling)
  append(sibling)
end

#last ⇒ AbstractCursor

Navigate to the last (rightmost) sibling node

Returns:



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

abstract :last

#last? ⇒ Boolean

True when the node has no rightward siblings

Returns:

  • (Boolean) 


27
28
29
 
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 27

def last?
  path.last?
end

#leaf? ⇒ Boolean

This method is abstract.

True if the node has no children

Returns:

  • (Boolean) 


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

abstract :leaf?

#next ⇒ AbstractCursor

Navigate to the next (rightward) sibling node

Returns:



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

abstract :next

#node ⇒ #leaf?, ...

Returns:



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

abstract :node

#path ⇒ AbstractPath

Returns:



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

abstract :path

#prepend(sibling) ⇒ EditedCursor

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

Returns:



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

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:



310
311
312
313
314
315
316
317
318
 
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 310

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:



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

abstract :prev

#replace(node) ⇒ AbstractCursor

Replace the current node with the given node

Returns:



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

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

#root ⇒ RootCursor

Navigate to the root node

Returns:



275
276
277
278
279
 
# File 'lib/stupidedi/zipper/abstract_cursor.rb', line 275

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

#root? ⇒ Boolean

This method is abstract.

True if the node has no parent

Returns:

  • (Boolean) 


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

abstract :root?

#up ⇒ AbstractCursor

Navigate to the parent node

Returns:



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

abstract :up