00040.rb

# pnodes => path
# ppath  => parent

class Zipper
  attr_reader :parent, :path, :node, :lefts, :rights, :at_end

  def initialize(branch, children, make_node, node, lefts = nil, path = nil, parent = nil, rights = nil, changed = false, at_end = false)
    @branch    = branch
    @children  = children
    @make_node = make_node

    @node      = node
    @lefts     = lefts
    @path      = path
    @parent    = parent
    @rights    = rights
    @changed   = changed
    @at_end    = at_end
  end

  def new(changes = {})
    self.class.new(
      @branch,
      @children,
      @make_node,
      changes.fetch(:node)    { self.node     },
      changes.fetch(:lefts)   { self.lefts    },
      changes.fetch(:path)    { self.path     },
      changes.fetch(:parent)  { self.parent   },
      changes.fetch(:rights)  { self.rights   },
      changes.fetch(:changed) { self.changed? },
      changes.fetch(:end)     { self.end?     }
    )
  end

  def self.array_zip(node)
    self.new(
      ->(node) { node.respond_to? :to_ary },
      ->(node) { node.empty? ? nil : node },
      ->(node, children) { children },
      node
    )
  end

  def branch?
    @branch.(node)
  end

  def children
    raise "called children on a leaf node" unless branch?
    @cs ||= @children.(node)
  end

  def make_node(node, children)
    @make_node.(node, children)
  end

  def changed?
    @changed
  end

  def end?
    @at_end
  end

  def down
    if branch? && children
      new(
        node: children.first,
        lefts: [],
        path: path ? [node] + path : [node],
        parent: self,
        rights: children.drop(1)
      )
    end
  end

  def up
    if path
      return parent unless changed?
      parent_path = path.drop(1)
      new(
        node:   make_node(node, lefts + [node] + rights),
        lefts:  parent.lefts,
        path:   parent_path.empty? ? nil : parent_path,
        parent: parent.parent,
        rights: parent.rights
      )
    end
  end

  def root
    return node unless path
    up.root
  end

  def right
    if path && rights && !rights.empty?
      new(
        node:   rights.first,
        lefts:  lefts + [node],
        rights: rights.drop(1)
      )
    end
  end

  #def rightmost

  def left
    if path && lefts && !lefts.empty?
      new(
        node:   lefts.last,
        lefts:  lefts[0...-1],
        rights: [node] + rights
      )
    end
  end

  # def leftmost

  def insert_left(item)
    raise "insert at top" unless path
    new(
      lefts:   lefts + [item],
      changed: true
    )
  end

  def insert_right(item)
    raise "insert at top" unless path
    new(
      rights:  [item] + rights,
      changed: true
    )
  end

  def replace(item)
    new(
      node: item,
      changed: true
    )
  end

  def edit(&block)
    new(
      node: block.(item),
      changed: true
    )
  end

  def insert_child(item)
    replace(make_node(node, [item] + children))
  end

  def append_child(item)
    replace(make_node(node, children + [item]))
  end

  def next
    backtrack = ->(node) {
      if node.up
        node.up.right || backtrack.(node.up)
      else
        node.new(end: true)
      end
    }

    (self if end?) ||
      (branch? && down) ||
      right ||
      backtrack.(self)
  end

  # def prev

  # def remove

  def each
    return to_enum unless block_given?
    loc = self
    until (loc = loc.next).end?
      yield loc
    end
  end
end

zip = Zipper.array_zip(
  [
    ['x', '+', 'y'],
    ['a', '*', 'b']
  ]
)

zip # => #<Zipper:0x007fe297587b50 @branch=#<Proc:0x007fe297587df8@-:38 (lambda)>, @children=#<Proc:0x007fe297587d30@-:39 (lambda)>, @make_node=#<Proc:0x007fe297587c40@-:40 (lambda)>, @node=[["x", "+", "y"], ["a", "*", "b"]], @lefts=nil, @path=nil, @parent=nil, @rights=nil, @changed=false, @at_end=false>

zip.node # => [["x", "+", "y"], ["a", "*", "b"]]

zip.branch? # => true
zip.children # => [["x", "+", "y"], ["a", "*", "b"]]

zip.down.down.root # => [["x", "+", "y"], ["a", "*", "b"]]

zip.down.insert_child(:foo).root # => [[:foo, "x", "+", "y"], ["a", "*", "b"]]

zip.each {|n|
  p n.node
}


# >> ["x", "+", "y"]
# >> "x"
# >> "+"
# >> "y"
# >> ["a", "*", "b"]
# >> "a"
# >> "*"
# >> "b"