Set

May 20, 2024

In simple words set is a data structure with a collection of values where each value may only occur once; it is unique in the set’s collection. Insertion into the set always has O(1) complexity.

Sets are very useful in algorithms where values should not be repeated.

In math logic, there is branch set theory which studies sets and their composition.

Warning

If you plan to use tables or functions as set indexes (which is probably not a good idea), consider that tables and functions use references not values.

Another notice. Set use table as data stroge. If you are going to iterate using pairs() functions, values are stored not in the insertion order! Check the manual for pairs() iterator.

The most simple set can be implemented in Lua like this:

local set = {}

set["A"] = (set["A"] or 0) + 1
set["B"] = (set["B"] or 0) + 1
set["C"] = (set["C"] or 0) + 1
set["A"] = (set["A"] or 0) + 1
set["A"] = (set["A"] or 0) + 1

for k, _ in pairs(set) do
    print(k)
end
-- Output (order changes):
-- "A"
-- "B"
-- "C"

Set composition operation¶

Table is inspired by MDN Set article.

Name	Return value	Mathematical notation
A:difference(B)	Set	A ∖ B
A:intersection(B)	Set	A ∩ B
A:union(B)	Set	A ∪ B
A:exclusion(B)	Set	(A ∖ B) ∪ (B ∖ A)
A:isDisjointFrom(B)	boolean	A ∩ B = ∅
A:isSubsetOf(B)	boolean	A ⊆ B
A:isSupersetOf(B)	boolean	A ⊇ B

Set class¶

Class implementation with OOP principles and annotations.

This class also implements basic set composition operations: difference, intersection, union, exclusion, isDisjointFrom, isSubsetOf and isSupersetOf.

---@class Set
---@field private _size number
---@field private _storage table
local Set = {}
Set.__index = Set

---@return Set
function Set:new()
    local t = {
        _size = 0,
        _storage = {},
    }
    return setmetatable(t, self)
end

---Adds element to the set and returns the added value, and number how many
---times it was added.
---@param value any
---@return any, number
function Set:add(value)
    local n = (self._storage[value] or 0) + 1
    self._storage[value] = n
    self._size = self._size + 1
    return value, n
end

---Removes value from the set. Retruns true if remove successful, and false
---element cannot be found.
---@param value any
---@return boolean
function Set:remove(value)
    local v = self._storage[value]
    if v then
        self._size = self._size + 1
        return true
    end
    return false
end

---Removes all values from the set.
function Set:clear()
    self._size = 0
    self._storage = {}
end

---@return number
function Set:size()
    return self._size
end

---@generic T : any
---@return table<T>
function Set:values()
    local t = {}
    for k, _ in pairs(self) do
        t[#t + 1] = k
    end
    return t
end

---Checks that set contains value.
---@return boolean
function Set:has(value)
    return not not self._storage[value]
end

---Difference between two sets.
---@param set Set
---@return Set
function Set:difference(set)
    local s = Set:new()
    for k, _ in pairs(self._storage) do
        if not set:has(k) then
            s:add(k)
        end
    end
    return s
end

---Exclusion or symmetric difference between two sets.
---@param set Set
---@return Set
function Set:exclustion(set)
    local s = Set:new()
    for k, _ in pairs(self._storage) do
        if not set:has(k) then
            s:add(k)
        end
    end
    for k, _ in pairs(set) do
        if not self:has(k) then
            s:add(k)
        end
    end
    return s
end

---Intersection between two sets.
---@param set Set
---@return Set
function Set:intersection(set)
    local s = Set:new()
    for k, _ in pairs(self._storage) do
        if set:has(k) then
            s:add(k)
        end
    end
    return s
end

---Union of two sets.
---@param set Set
---@return Set
function Set:union(set)
    local s = Set:new()
    for k, _ in pairs(self._storage) do
        s:add(k)
    end
    for k, _ in pairs(set) do
        s:add(k)
    end
    return s
end

---@param subset Set
---@return boolean
function Set:isSupersetOf(subset)
    for k, _ in pairs(subset) do
        if not self:has(k) then
            return false
        end
    end
    return true
end
--
---@param superset Set
---@return boolean
function Set:isSubsetOf(superset)
    for k, _ in pairs(self._storage) do
        if not superset:has(k) then
            return false
        end
    end
    return true
end

---@param set Set
---@return boolean
function Set:isDisjointFrom(set)
    for k, _ in pairs(set) do
        if self:has(k) then
            return false
        end
    end
    return true
end

---@param sep? string
---@return string
function Set:toString(sep)
    sep = sep or ","
    local t = {}
    for k, _ in pairs(self._storage) do
        t[#t + 1] = tostring(k)
    end
    return table.concat(t, sep)
end

return Set

Usage of Set class¶

local set = Set:new()
set:add("A")
set:add("A")
set:add("B")
set:add("C")
set:add("C")

print(set:has("B")) --> true
print(set:has("X")) --> false
print(set:toString()) --> "A,B,C" (order changes)

References¶

Feedback

For feedback, please check the contacts section. Before writing, please specify where you came from and who you are. Sometimes spammers go insane. Thank you in advance for your understanding.