57 lines
1.5 KiB
Lua
57 lines
1.5 KiB
Lua
local type, insert, remove = type, table.insert, table.remove
|
|
|
|
None = {} -- a unique object for a truncated branch (i.e. empty subtree)
|
|
function isbranch(node) return type(node) == 'table' and #node == 2 end
|
|
function left(node) return node[1] end
|
|
function right(node) return node[2] end
|
|
|
|
function fringeiter(tree)
|
|
local agenda = {tree}
|
|
local function push(item) insert(agenda, item) end
|
|
local function pop() return remove(agenda) end
|
|
return function()
|
|
while #agenda > 0 do
|
|
node = pop()
|
|
if isbranch(node) then
|
|
push(right(node))
|
|
push(left(node))
|
|
elseif node == None then
|
|
-- continue
|
|
else
|
|
return node
|
|
end
|
|
end
|
|
end
|
|
end
|
|
|
|
function same_fringe(atree, btree)
|
|
local anext = fringeiter(atree or None)
|
|
local bnext = fringeiter(btree or None)
|
|
local pos = 0
|
|
repeat
|
|
local aitem, bitem = anext(), bnext()
|
|
pos = pos + 1
|
|
if aitem ~= bitem then
|
|
return false, string.format("at position %d, %s ~= %s", pos, aitem, bitem)
|
|
end
|
|
until not aitem
|
|
return true
|
|
end
|
|
|
|
t1 = {1, {2, {3, {4, {5, None}}}}}
|
|
t2 = {{1,2}, {{3, 4}, 5}}
|
|
t3 = {{{1,2}, 3}, 4}
|
|
|
|
function compare_fringe(label, ta, tb)
|
|
local equal, nonmatch = same_fringe(ta, tb)
|
|
io.write(label .. ": ")
|
|
if equal then
|
|
print("same fringe")
|
|
else
|
|
print(nonmatch)
|
|
end
|
|
end
|
|
|
|
compare_fringe("(t1, t2)", t1, t2)
|
|
compare_fringe("(t1, t3)", t1, t3)
|