#!/home/kragen/devel/luajit-2.0/src/luajit
-- Do the samefringe problem in Lua using coroutines.

function visit(node)
   if node then
      if node.a then
         visit(node.a)
         visit(node.b)
      else
         coroutine.yield(node.leaf)
      end
   end
end

function iterate(conclist)
   return coroutine.create(function() visit(conclist) end)
end

function samefringe(a, b)
   a, b = iterate(a), iterate(b)

   while true do
      a_t, a_v = coroutine.resume(a)
      b_t, b_v = coroutine.resume(b)
      if not a_t and not b_t then return true end
      if not a_t or  not b_t then return false end
      if a_v ~= b_v then return false end
   end
end

assert(samefringe({a={a={leaf=1}, b={leaf=2}}, b={leaf=3}},
                  {a={leaf=1}, b={a={leaf=2}, b={leaf=3}}}))

assert(not samefringe({a={a={leaf=2}, b={leaf=2}}, b={leaf=3}},
                      {a={leaf=1}, b={a={leaf=2}, b={leaf=3}}}))

assert(not samefringe({a={a={leaf=1}, b={leaf=2}}, b={leaf=3}},
                      {a={leaf=1}, b={a={leaf=2}, b={leaf=4}}}))

assert(not samefringe({a={a={leaf=1}, b={leaf=2}}, b={a={leaf=3}, b={leaf=4}}},
                      {a={leaf=1}, b={a={leaf=2}, b={leaf=3}}}))

assert(not samefringe({a={a={leaf=1}, b={leaf=2}}, b={leaf=3}},
                      {a={leaf=1}, b={a={leaf=2}, b={a={leaf=3}, b={leaf=4}}}}))