Difference between two tables as a table

Question

IN SHORT

t1 = {1,3,5,7,9}

t2 = {1,2,3,4,5,6,7,8,9}

result wanted: t3 = {2,4,6,8}

LONG EXPLANATION

I have a list of objects in a scene, and I have a list of all objects not in the scene. I am trying to write a simple bit of code that will allow me to add objects to the scene but make sure that it does not load an object that has already been loaded.

So I can say something like....

SafeAdd (2, currentOBJlist, notLoadedOBJList)

and have the app load in 2 random objects from "notLoadedOBJList" but the chosen object not be in the "currentOBJlist"

Answer 1

Unsorted arrays

A table in Lua is also a map/dictionary/set besides being a array/list.

Make a set by assigning true to every element in a list; that way, you get to use it as a set by looking up the key. If the key returned is nil then it's non-existent, else it'd return true.

function notInScene(allObjects, objectsInScene)
  -- build a set out of objectsInScene
  -- this step can be avoided, if it's already a set
  local set = {}
  for _, v in ipairs(objectsInScene) do
    set[v] = true
  end

  -- populate output
  local notPresent = { }
  for _, v in ipairs(allObjects) do
    if (set[v] == nil) then
      table.insert(notPresent, v)
    end
  end
  return notPresent
end

local t1 = {1,3,5,7,9}
local t2 = {1,2,3,4,5,6,7,8,9}
local t3 = notPresent(t2, t1)
for _, v in ipairs(t3) do print(v) end

Output

2
4
6
8

Notice that we're duplicating objectsInScene as a set; this should be avoided, if possible i.e. make objectsInScene a set while originally building it.

Sorted arrays

If both lists are guaranteed to be sorted, we can do much better than building a set and then looking it up -- a two-pass solution, not very efficient.

function notInScene(allObjects, objectsInScene)
  j = 1
  local notPresent = {}
  for i = 1, #allObjects do
    if (allObjects[i] == objectsInScene[j]) then
      j = j + 1
    elseif (allObjects[i] < objectsInScene[j]) then
      table.insert(notPresent, allObjects[i])
    end
    i = i + 1
  end
  return notPresent
end

This gives the same result but without spending extra space or time; it's preferable over the previous method.