lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]

Also posted on

So I've been writing deep-copy algorithms, and I wanna test them to see if they work the way I want them to. While I do have access to the original->copy map, I want a general-purpose deep-compare algorithm that must be able to compare table keys (tables as keys?). The #Lua channel on Freenode thinks it's impossible, I just think it's really hard.

My deep-copy algorithm(s) are avaliable here: (it's not very organized, but there are 3 of them, one uses recursive calls, the other uses a todo table, and the other simulates a call stack (in a very ugly but 5.1-compatible way))

Recursive version:

    local function deep(inp,copies)
      if type(inp) ~= "table" then
        return inp
      local out = {}
      copies = (type(copies) == "table") and copies or {}
copies[inp] = out -- use normal assignment so we use copies' metatable (if any) for key,value in next,inp do -- skip metatables by using next directly
        -- we want a copy of the key and the value
        -- if one is not available on the copies table, we have to make one
-- we can't do normal assignment here because metatabled copies tables might set metatables

-- out[copies[key] or deep(key,copies)]=copies[value] or deep(value,copies) rawset(out,copies[key] or deep(key,copies),copies[value] or deep(value,copies))
      return out

Simulated stack version:

    local function deep(inp,copies)
      -- push
local stack = {{inp = inp, key = nil, value = nil, next = false, skipNext = false, out = nil}}
      local currentResult

      copies = (type(copies) == "table") and copies or {}

      -- I run ZBS from stock Lua (5.1), it's not label-friendly
      while true do

        if #stack == 0 then
          return currentResult
        local entry = stack[#stack]

        if not then
          entry.out = {}
          copies[entry.inp] = entry.out
        local rep = false
        local ret = false
        while true do
            local key,value = entry.key, entry.value
            if not entry.skipNext then
              key,value = next(entry.inp, entry.key)
              if not key then
                --goto Out
              entry.key = key
            entry.skipNext = false
   = true
            print(key, value)
if (type(key) ~= "table" or copies[key]) and (type(value) ~= "table" or copies[value]) then
              rawset(entry.out,copies[key] or key,copies[value] or value)
              entry.key,entry.value = key,value
              --goto Next
              rep = true
            if not (type(key) ~= "table" or copies[key]) then
              -- push
              entry.skipNext = true
stack[#stack+1] = {inp = key, key = nil, value = nil, next = false, skipNext = false, out = nil}
            elseif not (type(value) ~= "table" or copies[value]) then
              -- push
              entry.skipNext = true
stack[#stack+1] = {inp = value, key = nil, value = nil, next = false, skipNext = false, out = nil}
            --goto Return
            ret = true
          until true
          if not rep then break end
          rep = false
        if not ret then
          currentResult = entry.out
          -- pop
          stack[#stack] = nil
        --goto Return

"Todo table" (not sure what to call it) version:

    local function deep(inp,copies)
      local todo = {[inp] = {}}
      copies = type(copies) == "table" and copies or {}
      copies[inp] = todo[inp]

      -- we can't use pairs or for here because we modify todo
      while next(todo) do
        local i,o = next(todo)
        todo[i] = nil
        for k,v in next,i do
          if copies[k] ~= nil then
            k = copies[k]
          elseif type(k) == "table" then
            local t = {}
            todo[k] = t
            copies[k] = t
            k = t
          if copies[v] ~= nil then
            v = copies[v]
          elseif type(v) == "table" then
            local t = {}
            todo[v] = t
            copies[v] = t
            v = t
      return copies[inp] -- heh :P

I found things like this which don't really handle tables as keys: (Copy of snippet below)

    function deepcompare(t1,t2,ignore_mt)
      local ty1 = type(t1)
      local ty2 = type(t2)
      if ty1 ~= ty2 then return false end
      -- non-table types can be directly compared
      if ty1 ~= 'table' and ty2 ~= 'table' then return t1 == t2 end
      -- as well as tables which have the metamethod __eq
      local mt = getmetatable(t1)
      if not ignore_mt and mt and mt.__eq then return t1 == t2 end
      for k1,v1 in pairs(t1) do
        local v2 = t2[k1]
        if v2 == nil or not deepcompare(v1,v2) then return false end
      for k2,v2 in pairs(t2) do
        local v1 = t1[k2]
        if v1 == nil or not deepcompare(v1,v2) then return false end
      return true

Serializing is also not an option, as order of serialization is "random".