lib/stupidedi/zipper/abstract_cursor.rb
# frozen_string_literal: true
module Stupidedi
using Refinements
module Zipper
class AbstractCursor
# @return [#leaf?, #children, #copy]
abstract :node
# @return [AbstractPath]
abstract :path
# @group Querying the Tree Location
#########################################################################
# (see AbstractPath#depth)
def depth
path.depth
end
# (see AbstractPath#first?)
def first?
path.first?
end
# (see AbstractPath#last?)
def last?
path.last?
end
# True if the node has no children
abstract :leaf?
# True if the node has no parent
abstract :root?
# 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.
#
# @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.
#
# @return [Array]
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
# Flattens the subtree into an Array of nodes. The nodes are arranged
# according to a depth-first left-to-right preorder traversal.
#
# @return [Array]
def flatten
nodes = []
queue = [node]
while node = queue.shift
nodes << node
queue.unshift(*node.children) unless node.leaf?
end
nodes
end
# @group Traversing the Tree
#########################################################################
# Navigate to the first child node
#
# @return [MemoizedCursor]
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
# Navigate to the first child node, or if there are no children,
# create a placeholder where the first child node will be placed
#
# @return [AbstractCursor]
def dangle
if node.leaf?
raise Exceptions::ZipperError,
"cannot descend into leaf node"
end
if leaf?
DanglingCursor.new(self)
else
down
end
end
# Navigate to the `nth` child node
#
# @return [AbstractCursor]
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
# Returns a list of cursors, one pointing to each child node.
#
# @return [Array<MemoizedCursor>]
def children
children = []
unless leaf?
zipper = down
children << zipper
until zipper.last?
zipper = zipper.next
children << zipper
end
end
children
end
# Recursively descend to each node's `nth` child
#
# @return [AbstractCursor]
def descendant(n, *ns)
cursor = self
n.cons(ns).each do |n_|
cursor = cursor.child(n_)
end
cursor
end
# Navigate to the parent node
#
# @return [AbstractCursor]
abstract :up
# Navigate to the next (rightward) sibling node
#
# @return [AbstractCursor]
abstract :next
# Navigate to the previous (leftward) sibling node
#
# @return [AbstractCursor]
abstract :prev
# Navigate to the first (leftmost) sibling node
#
# @return [AbstractCursor]
abstract :first
# Navigate to the last (rightmost) sibling node
#
# @return [AbstractCursor]
abstract :last
# Navigate to the root node
#
# @return [RootCursor]
def root
cursor = self
cursor = cursor.up until cursor.root?
cursor
end
# @group Editing the Tree
#########################################################################
# Insert a new sibling node after (to the right of) the current node,
# and navigate to the new sibling node
#
# @return [EditedCursor]
abstract :append, :args => %w(sibling)
# Insert a new sibling node before (to the left of) the current node,
# and navigate to the new sibling node
#
# @return [EditedCursor]
abstract :prepend, :args => %w(sibling)
# (see #append)
def insert_right(sibling)
append(sibling)
end
# (see #prepend)
def insert_left(sibling)
prepend(sibling)
end
# Insert a new child node before (to the left of) any existing children
# nodes and navigate to the new child node
#
# @return [EditedCursor]
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
# Insert a new child node after (to the right of) any existing children
# nodes and navigate to the new child node
#
# @return [EditedCursor]
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
# Replace the current node with the given node
#
# @return [AbstractCursor]
abstract :replace, :args => %w(node)
# 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.
#
# @return [EditedCursor]
abstract :delete
# @endgroup
#########################################################################
end
end
end