Lua Zipper Example

gistfile1.lua

-- Author: Michael-Keith Bernard
-- Date: July 27, 2012
-- Notes: An example Binary Tree Zipper implementation in Lua

function node(v, left, right)
  local n = {}
  n.value = v
  n.left = left
  n.right = right
  return n
end

function zipper(root)
  local z = {}
  z.root = root
  z.stack = {}

  function z:value()
    return root.value
  end

  function z:set_value(v)
    self.root.value = v
    return self
  end

  function z:set_root(n)
    self.root = n
    return self
  end

  function z:zip_left()
    table.insert(self.stack, {"r", self.root})
    self.root = self.root.left
    return self
  end

  function z:zip_right()
    table.insert(self.stack, {"l", self.root})
    self.root = self.root.right
    return self
  end

  function z:to_root()
    if #z.stack > 0 then
      return z:unzip():to_root()
    else
      return self
    end
  end

  function z:unzip()
    local t, new_root = unpack(table.remove(self.stack))
    if t == "l" then
      new_root.right = self.root
    else
      new_root.left = self.root
    end
    self.root = new_root
    return self
  end

  function z:debug()
    print("Root:")
    print("  Value: "..self.root.value)
    print("  Left: "..tostring(self.root.left))
    print("  Right: "..tostring(self.root.right))
    print("Stack:")
    for i, v in ipairs(self.stack) do
      local t, tree = unpack(v)
      print("  Direction: "..t.." Tree: "..tostring(tree))
    end
    print()
  end

  return z
end

function test_zipper()
  local tree = node(1, node(2), node(3, node(4, node(5, nil, node(6)))))
  local z = zipper(tree)

  z:debug()
  z:zip_right()
  z:debug()
  z:zip_left()
  z:debug()
  z:zip_left()
  z:debug()
  z:zip_right()
  z:debug()
  z:unzip()
  z:debug()
  z:to_root()
  z:debug()
end

test_zipper()