Set Operations

wiki

Testing for set elements

Set operations can be quite useful, e.g to test if an element is in set or list. Lua does not have built-in set operators, but we can build them using tables:

function contains(t, e)
  for i = 1,#t do
    if t[i] == e then return true end
  end
  return false
end

t = { "abc","def","ghi" }

print(contains(t,"def"))  --> true
print(contains(t,"ddd"))  --> false

This can be optimized by turning the table t into a dictionary (i.e. the list elements become keys). For example,

t = {["abc"] = true, ["def"] = true, ["ghi"] = true}
print(t["def"]) --> true  (t contains "def")
print(t["ddd"]) --> nil  (t does not contain "def")

For a cleaner syntax, we can use a function Set to create the dictionary table from the list table:

function Set(t)
  local s = {}
  for _,v in pairs(t) do s[v] = true end
  return s
end

function contains(t, e)
  return t[e]
end

t = Set{"abc", "def", "ghi"}

print (contains(t,"def"))  --> true
print (t["def"])           --> true (same as above)
print (contains(t,"ddd"))  --> nil
print (t["ddd"])           --> nil (same as above)

Index of Elements

Though sets are by definition unordered, we may still want to retrieve the index of an element in a list used to define the set. The above code can be modified to help out here:

function OrderedSet(t)
  local s = {}
  for i,v in ipairs(t) do s[v] = i end -- key value is index
  return s
end

function contains(t,e) return t[e] end
function indexof(t,e) return t[e] end 

t = OrderedSet{"abc", "def", "ghi"}

if contains(t,"def") then
  print (indexof(t,"def"))
end
--> 2

Old Lua 4 Version of Code

For historical reference, below are the Lua 4 versions of some of the above code.

function contains(t,e)
  for i=1,getn(t) do
    if t[i]==e then return 1 end
  end
  return nil  -- element not found, return false
end

t = { "abc","def","ghi" }

print (contains(t,"def"))  -- gives you 1 (true)

function makeDict(t)
  local d={}
  for i=1,getn(t) do d[ t[i] ]=1 end
  return d  -- return dictionary we have created
end

function contains(t,e)
  return t[e]
end

t = makeDict { "abc","def","ghi" }

print (contains(t,"def"))  -- gives you 1 (true)
print (t["def"])  -- same as above

function makeDict(t)
  local d={}
  for i=1,getn(t) do d[ t[i] ]=i end  -- key value is index
  return d
end

function contains(t,e) return t[e] end
function indexOf(t,e) return t[e] end 

t = makeDict { "abc","def","ghi" }

if contains(t,"def") then
  print (indexOf(t,"def"))
end