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

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")

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)

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