Set (collection)

A set is a datatype like an array, but with no duplicate elements.

Set = {}
Set.__index = Set
--Construct a set from an (optional) list of items
function Set.new(...)
	local s = {}
	for _, v in ipairs({...}) do
		s[v] = true
	end
	return setmetatable(s, Set)
end

--Functions to add, remove, and check for items
function Set:contains(x) return self[x] == true end
function Set:add(x)      self[x] = true         end
function Set:remove(x)   self[x] = false        end

--Convert to string for easy debugging
function Set:__tostring()
	local elems = {}
	for v in pairs(self) do
		table.insert(elems, tostring(v))
	end
	return '(' .. table.concat(elems, ', ') .. ')'
end

One benefit of building sets in this way is that checking if a set contains a value is very efficient:

local evenNums = Set.new(2, 4, 6, 8, 10)
local oddNums = Set.new()

for i = 1, 10 do
	if not evenNums:contains(x) then
		oddNums.add(x)
	end
end
print(evenNums)
print(oddNums)

(10, 6, 2, 8, 4)

(1, 7, 5, 3, 9)

Note that by definition, a set has no concept of ordering.

Useful operations on sets

There are a bunch of useful operations that can be done on sets. One useful analogy is to think of them like venn diagrams. We might want to find the union of two sets, ie values that appear in either set, and the intersection, values that appear in both.

function Set:union(s2)
	local result = Set.new()
	for entry in pairs(self) do
		result[entry] = true
	end
	for entry in pairs(s2) do
		result[entry] = true
	end
	return result
end
function Set:intersection(s2)
	local result = Set.new()
	for entry in pairs(self) do
		if s2[entry] then
			result[entry] = true
		end
	end
	return result
end
function Set:without(s2)
	local result = Set.new()
	for entry in pairs(self) do
		result[entry] = true
	end
	for entry in pairs(s2) do
		result[entry] = nil
	end
	return result
end
Set.__add = Set.union
Set.__sub = Set.without

local wikiadmins = Set.new("Telamon", "MrDoomBringer", "Gordonrox")
local wikiwriters = Set.new("Blocco", "Camoy", "GoldenUrg")
print("Users:", wikiadmins + wikiwriters)

local namesBeginingWithG = Set.new("Gordonrox", "GoldenUrg")
print("Without Gs:", wikiadmins + wikiwriters - namesBeginingWithG)

print("Admins with Gs:", wikiadmins:intersection(namesBeginingWithG))

Users: (Gordonrox, MrDoomBringer, Telamon, GoldenUrg, Camoy, Blocco) Without Gs: (MrDoomBringer, Telamon, Camoy, Blocco)

Admins with Gs: (Gordonrox)