symmetric difference


See On Github

Data

Contributor

Generic placeholder thumbnail

by Yonaba

in lua

Source Code

-- Symmetric difference implementation
-- See: http://en.wikipedia.org/wiki/Symmetric_difference

-- Returns a copy of a given array t where keys and values were swapped
local function swapKeysAndValues(t)
  local _t = {}
  for k,v in pairs(t) do _t[v] = k end
  return _t
end

-- Returns the symmetric difference of two sets  (i.e, all
-- the elements which are either in first set or the second
-- set, but not in both)
-- s1 : a first set
-- s2 : a second set
-- returns : an array of values from the given sets
local function symmdiff(s1, s2)
  local t1 = swapKeysAndValues(s1)
  local t2 = swapKeysAndValues(s2)
  local r = {}
  
  for _, v in pairs(s1) do
    if not t2[v] then table.insert(r, v) end
  end
  
  for _, v in pairs(s2) do
    if not t1[v] then table.insert(r, v) end
  end  
  
  return r
end

return symmdiff
-- Tests for symmdiff.lua
local symdiff = require 'symdiff'

local total, pass = 0, 0

local function dec(str, len)
  return #str < len
     and str .. (('.'):rep(len-#str))
      or str:sub(1,len)
end

local function run(message, f)
  total = total + 1
  local ok, err = pcall(f)
  if ok then pass = pass + 1 end
  local status = ok and 'PASSED' or 'FAILED'
  print(('%02d. %68s: %s'):format(total, dec(message,68), status))
end

local function same(t1, t2)
  if #t1~=#t2 then return false end
  for k,v in pairs(t1) do
    if t2[k] ~= v then return false end
  end
  return true
end

run('Symmetric difference', function()
  local s1, s2 = {1, 2, 3, 4}, {3, 4, 5, 6}
  assert(same(symdiff(s1,s2),{1,2,5,6}))
  
  local s1, s2 = {}, {}
  assert(same(symdiff(s1,s2),{}))
  
  local s1, s2 = {1}, {2}
  assert(same(symdiff(s1,s2),{1,2}))
  
  local s1, s2 = {3}, {3}
  assert(same(symdiff(s1,s2),{}))
end)

print(('-'):rep(80))
print(('Total : %02d: Pass: %02d - Failed : %02d - Success: %.2f %%')
  :format(total, pass, total-pass, (pass*100/total)))