PcoWSkbVqDnWTu_dm2ix
We use cookies on this site to enhance your user experience

Oct 21 2018, 8:27 PM PST 2 min

A set is a collection of elements with no order or duplicate elements. In other words, an element either is or is not contained within a set.

Set = {}
Set.__index = Set
--Construct a set from an (optional) list of items
function Set.new(items)
	local s = {}
	for _, v in ipairs(items or {}) 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)

Outputs:

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

Produces:

Users: (Gordonrox, MrDoomBringer, Telamon, GoldenUrg, Camoy, Blocco)
Without Gs: (MrDoomBringer, Telamon, Camoy, Blocco)
Admins with Gs: (Gordonrox)
Tags:
  • datatype
  • data-structure