WikiGOD at 05:50, 2 May 2021

2021-05-02T05:50:12Z

WikiGOD at 05:47, 2 May 2021

2021-05-02T05:47:42Z

← Older revision		Revision as of 05:47, 2 May 2021
Line 8:		Line 8:
	-- @TODO Consider adding a `clone` function, since `mw.clone` doesn't work.		-- @TODO Consider adding a `clone` function, since `mw.clone` doesn't work.
	-- @TODO Consider using `pairs` internally, to cut down on (en\|de)coding.		-- @TODO Consider using `pairs` internally, to cut down on (en\|de)coding.
	-- @TODO Consider using `~~Dev~~:Inspect` for `tostring`.		-- @TODO Consider using `Module::Inspect` for `tostring`.
	--------------------------------------------------------------------------------		--------------------------------------------------------------------------------
	local p = {}		local p = {}

WikiGOD at 05:22, 2 May 2021

2021-05-02T05:22:37Z

← Older revision		Revision as of 05:22, 2 May 2021
Line 32:		Line 32:
	__mode = "k",		__mode = "k",
	__index = function ()		__index = function ()
	error("This set has not been initialized correctly. Please use `~~Dev~~:Set.init` to construct new instances")		error("This set has not been initialized correctly. Please use `Module:Set.init` to construct new instances")
	end,		end,
	})		})
Line 137:		Line 137:
	local function size(set)		local function size(set)
	if not is(set) then		if not is(set) then
	error("bad argument #1 to '~~Dev~~:Set.size' (set expected, got " .. type(set) .. ")", 2)		error("bad argument #1 to 'Module:Set.size' (set expected, got " .. type(set) .. ")", 2)
	end		end

WikiGOD: 1 revision imported

2021-04-30T02:24:02Z

1 revision imported

← Older revision		Revision as of 02:24, 30 April 2021
(No difference)

Mediawiki>Siroopwafel: Remove pretty comment before module return (produces catastrophic defect in LuaDoc/LDoc/Docbunto)

2020-06-02T20:10:12Z

Remove pretty comment before module return (produces catastrophic defect in LuaDoc/LDoc/Docbunto)

New page

-- <nowiki>
--------------------------------------------------------------------------------
-- Library for building and manipulating sets.
--
-- @author [[User:DarthKitty]]
-- @version 0.5.0
--
-- @TODO Consider adding a `clone` function, since `mw.clone` doesn't work.
-- @TODO Consider using `pairs` internally, to cut down on (en|de)coding.
-- @TODO Consider using `Dev:Inspect` for `tostring`.
--------------------------------------------------------------------------------
local p = {}

--------------------------------------------------------------------------------
-- Pass-by-reference placeholders for values that cannot be used as table keys.
-- We use functions instead of tables, since the latter are mutable.
--------------------------------------------------------------------------------
local placeholders = {
["nil"] = function () end,
["NaN"] = function () end,
}

--------------------------------------------------------------------------------
-- An ephemeron table is the closest approximation of JavaScript's `WeakMap`
-- object, and can be used to store private, per-instance data. This is more
-- efficient than using a closure, since it doesn't rebuild the whole
-- metatable for every instance.
--
-- @see <http://fitzgeraldnick.com/2014/01/13/hiding-implementation-details-with-e6-weakmaps.html>
--------------------------------------------------------------------------------
local internals = setmetatable({}, {
__mode = "k",
__index = function ()
error("This set has not been initialized correctly. Please use `Dev:Set.init` to construct new instances")
end,
})

--------------------------------------------------------------------------------
-- Metatable for set instances. Provides method syntax and overloaded operators
-- for convenience.
--------------------------------------------------------------------------------
local Set = {
__index = {},
__newindex = function ()
error("cannot change a protected table")
end,
__metatable = false,
}

--------------------------------------------------------------------------------
-- Wraps a given value for use as a table key.
--
-- @param {*} value
-- The value to wrap.
-- @returns {*}
-- The wrapped value.
--------------------------------------------------------------------------------
local function encode(value)
-- Per IEEE 754, NaN is the only value which does not equal itself. Tables
-- cannot generate false-positives, since the `__eq` metamethod is not
-- called if the values being compared are primitively equal.
local isNaN = value ~= value

if value == nil then
return placeholders["nil"]
elseif isNaN then
return placeholders["NaN"]
else
return value
end
end

--------------------------------------------------------------------------------
-- Unwraps a given value after being used as a table key.
--
-- @param {*} value
-- The value to unwrap.
-- @returns {*}
-- The unwrapped value.
--------------------------------------------------------------------------------
local function decode(value)
if value == placeholders["nil"] then
return nil
elseif value == placeholders["NaN"] then
return 0 / 0 -- There's no `NaN` literal.
else
return value
end
end

--------------------------------------------------------------------------------
-- Constructs a set instance.
--
-- @returns {table}
-- A new set.
--------------------------------------------------------------------------------
local function init()
local set = setmetatable({}, Set)

internals[set] = {
elements = {},
size = 0,
prevElement = nil,
}

return set
end

p.init = init

--------------------------------------------------------------------------------
-- Checks if a value is a set, as defined by this library.
--
-- @param {*} value
-- The value to check.
-- @returns {boolean}
-- Whether the value is a set.
--------------------------------------------------------------------------------
local function is(value)
return (pcall(function ()
return internals[value]
end))
end

p.is = is

--------------------------------------------------------------------------------
-- Fetches the number of elements in a set.
--
-- @see [[wikipedia:Cardinality]]
--
-- @param {table} set
-- A set.
-- @returns {number}
-- The number of elements in the set.
--------------------------------------------------------------------------------
local function size(set)
if not is(set) then
error("bad argument #1 to 'Dev:Set.size' (set expected, got " .. type(set) .. ")", 2)
end

return internals[set].size
end

p.size = size
Set.__index.size = size

--------------------------------------------------------------------------------
-- Checks if a set has a particular element.
--
-- @param {table} set
-- The set to search.
-- @param {*} element
-- The element to search for.
-- @returns {boolean}
-- Whether the set contains the element.
--------------------------------------------------------------------------------
local function contains(set, element)
if not is(set) then
error("bad argument #1 to 'Dev:Set.contains' (set expected, got " .. type(set) .. ")", 2)
end

return not not internals[set].elements[encode(element)]
end

p.contains = contains
Set.__index.contains = contains

--------------------------------------------------------------------------------
-- Fetches the "next" element in a set, wrapping around to the "beginning" if
-- the "previous" was also the "last". Since sets are unordered, the meaning of
-- those terms is determined by the built-in `next` function.
--
-- This method is provided as a workaround for Lua's horribly-designed iterator
-- "protocol". Iterators use `nil` to signal the end of a sequence, but since
-- this "class" accepts `nil` elements, it is impossible to write an iterator
-- which will always loop over every element. Furthermore, because sets are not
-- ordered, such an iterator would stop at an arbitrary position.
--
-- Instead, combining this method with `Dev:Set.size` allows users to loop over
-- a set numerically, much like the `"n"` field trick utilized for sequential
-- tables with holes.
--
-- @param {table} set
-- A set.
-- @returns {*}
-- An element in the set.
--------------------------------------------------------------------------------
local function nextElement(set)
if not is(set) then
error("bad argument #1 to 'Dev:Set.nextElement' (set expected, got " .. type(set) .. ")", 2)
end

local element = next(internals[set].elements, internals[set].prevElement)

-- If we've reached the end of the set, start over from the beginning.
if element == nil then
element = next(internals[set].elements, element)
end

-- Advance the pointer.
internals[set].prevElement = element

return decode(element)
end

p.nextElement = nextElement
Set.__index.nextElement = nextElement

--------------------------------------------------------------------------------
-- Adds one element to a set.
--
-- @param {table} set
-- The set to add to.
-- @param {*} element
-- The element to add.
-- @returns {table}
-- The same set instance.
--------------------------------------------------------------------------------
local function add(set, element)
if not is(set) then
error("bad argument #1 to 'Dev:Set.add' (set expected, got " .. type(set) .. ")", 2)
end

if not contains(set, element) then
internals[set].elements[encode(element)] = true
internals[set].size = internals[set].size + 1
end

return set
end

p.add = add
Set.__index.add = add

--------------------------------------------------------------------------------
-- Removes one element from a set.
--
-- @param {table} set
-- The set to remove from.
-- @param {*} element
-- The element to remove.
-- @returns {table}
-- The same set instance.
--------------------------------------------------------------------------------
local function remove(set, element)
if not is(set) then
error("bad argument #1 to 'Dev:Set.remove' (set expected, got " .. type(set) .. ")", 2)
end

if contains(set, element) then
internals[set].elements[encode(element)] = nil
internals[set].size = internals[set].size - 1
end

return set
end

p.remove = remove
Set.__index.remove = remove

--------------------------------------------------------------------------------
-- Removes all elements from a set.
--
-- @param {table} set
-- The set to remove from.
-- @returns {table}
-- The same set instance.
--------------------------------------------------------------------------------
local function clear(set)
if not is(set) then
error("bad argument #1 to 'Dev:Set.clear' (set expected, got " .. type(set) .. ")", 2)
end

for i = 1, size(set) do
remove(set, nextElement(set))
end

return set
end

p.clear = clear
Set.__index.clear = clear

--------------------------------------------------------------------------------
-- Constructs a set with one or more elements.
--
-- @param {...*} ...
-- The elements to add.
-- @returns {table}
-- The set.
--------------------------------------------------------------------------------
local function of(...)
local set = init()

for i = 1, select("#", ...) do
add(set, select(i, ...))
end

return set
end

p.of = of

--------------------------------------------------------------------------------
-- Constructs a set from a the key-value pairs of a table, adding keys that
-- correspond to "truthy" values and ignoring the rest.
--
-- @param {table} tbl
-- The table to iterate over.
-- @returns {table}
-- The set.
--------------------------------------------------------------------------------
local function fromPairs(tbl)
local typ = type(tbl)

if typ ~= "table" then
error("bad argument #1 to 'Dev:Set.fromPairs' (table expected, got " .. typ .. ")", 2)
end

local set = init()

for key, value in pairs(tbl) do
if value then
add(set, key)
end
end

return set
end

p.fromPairs = fromPairs

--------------------------------------------------------------------------------
-- Builds a new set from two existing ones, where each element of the former is
-- also an element of both of the latter.
--
-- @see [[wikipedia:Intersection (set theory)]]
--
-- @param {table} oldSet1
-- A set.
-- @param {table} oldSet2
-- A set.
-- @returns {table}
-- A new set.
--------------------------------------------------------------------------------
local function intersection(oldSet1, oldSet2)
if not is(oldSet1) then
error("bad argument #1 to 'Dev:Set.intersection' (set expected, got " .. type(oldSet1) .. ")", 2)
end

if not is(oldSet1) then
error("bad argument #2 to 'Dev:Set.intersection' (set expected, got " .. type(oldSet2) .. ")", 2)
end

local newSet = init()

for i = 1, size(oldSet1) do
local element = nextElement(oldSet1)

if contains(oldSet2, element) then
add(newSet, element)
end
end

return newSet
end

p.intersection = intersection
Set.__index.intersection = intersection
Set.__mul = intersection

--------------------------------------------------------------------------------
-- Builds a new set from two existing ones, where each element of the former is
-- also an element of either of the latter.
--
-- @see [[wikipedia:Union (set theory)]]
--
-- @param {table} oldSet1
-- A set.
-- @param {table} oldSet2
-- A set.
-- @returns {table}
-- A new set.
--------------------------------------------------------------------------------
local function union(oldSet1, oldSet2)
if not is(oldSet1) then
error("bad argument #1 to 'Dev:Set.union' (set expected, got " .. type(oldSet1) .. ")", 2)
end

if not is(oldSet2) then
error("bad argument #2 to 'Dev:Set.union' (set expected, got " .. type(oldSet2) .. ")", 2)
end

local newSet = init()

for _, oldSet in ipairs{oldSet1, oldSet2} do
for i = 1, size(oldSet) do
add(newSet, nextElement(oldSet))
end
end

return newSet
end

p.union = union
Set.__index.union = union
Set.__add = union

--------------------------------------------------------------------------------
-- Builds a new set from two existing ones, where each element of the former is
-- also an element of the first of the latter, but not the second.
--
-- @see [[wikipedia:Complement (set theory)#Relative complement]]
--
-- @param {table} oldSet1
-- A set.
-- @param {table} oldSet2
-- A set.
-- @returns {table}
-- A new set.
--------------------------------------------------------------------------------
local function difference(oldSet1, oldSet2)
if not is(oldSet1) then
error("bad argument #1 to 'Dev:Set.difference' (set expected, got " .. type(oldSet1) .. ")", 2)
end

if not is(oldSet1) then
error("bad argument #2 to 'Dev:Set.difference' (set expected, got " .. type(oldSet2) .. ")", 2)
end

local newSet = init()

for i = 1, size(oldSet1) do
local element = nextElement(oldSet1)

if not contains(oldSet2, element) then
add(newSet, element)
end
end

return newSet
end

p.difference = difference
Set.__index.difference = difference
Set.__sub = difference

--------------------------------------------------------------------------------
-- Builds a new set from two existing ones, where each element of the former is
-- also an element of one of the latter, but not both.
--
-- @see [[wikipedia:Symmetric difference]]
--
-- @param {table} oldSet1
-- A set.
-- @param {table} oldSet2
-- A set.
-- @returns {table}
-- A new set.
--------------------------------------------------------------------------------
local function symmetricDifference(oldSet1, oldSet2)
if not is(oldSet1) then
error("bad argument #1 to 'Dev:Set.symmetricDifference' (set expected, got " .. type(oldSet1) .. ")", 2)
end

if not is(oldSet1) then
error("bad argument #2 to 'Dev:Set.symmetricDifference' (set expected, got " .. type(oldSet2) .. ")", 2)
end

local newSet = init()

for _, oldSet in ipairs{oldSet1, oldSet2} do
for i = 1, size(oldSet) do
local element = nextElement()

if contains(newSet, element) then
remove(newSet, element)
else
add(newSet, element)
end
end
end

return newSet
end

p.symmetricDifference = symmetricDifference
Set.__index.symmetricDifference = symmetricDifference
Set.__pow = symmetricDifference

--------------------------------------------------------------------------------
-- Checks if two sets have no elements in common.
--
-- @see [[wikipedia:Disjoint sets]]
--
-- @param {table} set1
-- A set.
-- @param {table} set2
-- A set.
-- @returns {boolean}
-- Whether the two sets have no elements in common.
--------------------------------------------------------------------------------
local function isDisjointFrom(set1, set2)
if not is(set1) then
error("bad argument #1 to 'Dev:Set.isDisjointFrom' (set expected, got " .. type(set1) .. ")", 2)
end

if not is(set1) then
error("bad argument #2 to 'Dev:Set.isDisjointFrom' (set expected, got " .. type(set2) .. ")", 2)
end

for i = 1, size(set1) do
if contains(set2, nextElement(set1)) then
return false
end
end

return true
end

p.isDisjointFrom = isDisjointFrom
Set.__index.isDisjointFrom = isDisjointFrom

--------------------------------------------------------------------------------
-- Checks if every element of one set is also an element of another.
--
-- @see [[wikipedia:Subset]]
--
-- @param {table} set1
-- A set.
-- @param {table} set2
-- A set.
-- @returns {boolean}
-- Whether every element of the first set is also an element of the second.
--------------------------------------------------------------------------------
local function isSubsetOf(set1, set2)
if not is(set1) then
error("bad argument #1 to 'Dev:Set.isSubsetOf' (set expected, got " .. type(set1) .. ")", 2)
end

if not is(set1) then
error("bad argument #2 to 'Dev:Set.isSubsetOf' (set expected, got " .. type(set2) .. ")", 2)
end

for i = 1, size(set1) do
if not contains(set2, nextElement(set1)) then
return false
end
end

return true
end

p.isSubsetOf = isSubsetOf
Set.__index.isSubsetOf = isSubsetOf
Set.__le = isSubsetOf

--------------------------------------------------------------------------------
-- Checks if every element of one set is also an element of another, but not the
-- inverse.
--
-- @see [[wikipedia:Subset]]
--
-- @param {table} set1
-- A set.
-- @param {table} set2
-- A set.
-- @returns {boolean}
-- Whether every element of the first set is also an element of the second,
-- but not the inverse.
--------------------------------------------------------------------------------
local function isProperSubsetOf(set1, set2)
if not is(set1) then
error("bad argument #1 to 'Dev:Set.isProperSubsetOf' (set expected, got " .. type(set1) .. ")", 2)
end

if not is(set1) then
error("bad argument #2 to 'Dev:Set.isProperSubsetOf' (set expected, got " .. type(set2) .. ")", 2)
end

return size(set1) < size(set2) and isSubsetOf(set1, set2)
end

p.isProperSubsetOf = isProperSubsetOf
Set.__index.isProperSubsetOf = isProperSubsetOf
Set.__lt = isProperSubsetOf

--------------------------------------------------------------------------------
-- Checks if every element of one set is also an element of another, and vice
-- versa.
--
-- @param {table} set1
-- A set.
-- @param {table} set2
-- A set.
-- @returns {boolean}
-- Whether every element of the first set is also an element of the second,
-- and vice versa.
--------------------------------------------------------------------------------
local function equals(set1, set2)
if not is(set1) then
error("bad argument #1 to 'Dev:Set.equals' (set expected, got " .. type(set1) .. ")", 2)
end

if not is(set1) then
error("bad argument #2 to 'Dev:Set.equals' (set expected, got " .. type(set2) .. ")", 2)
end

return size(set1) == size(set2) and isSubsetOf(set1, set2)
end

p.equals = equals
Set.__index.equals = equals
Set.__eq = equals

--------------------------------------------------------------------------------
-- Generates a string representation of a set.
--
-- @param {table} set
-- A set.
-- @returns {string}
-- A string representation of the set.
--------------------------------------------------------------------------------
local function tostring_(set)
local tmp = {}

for i = 1, size(set) do
tmp[i] = tostring(nextElement(set))
end

return "Set { " .. table.concat(tmp, ", ") .. " }"
end

Set.__tostring = tostring_

-- Makes it slightly more convenient to construct set instances, by allowing
-- users to omit ".of".
return setmetatable(p, {
__call = function (self, ...)
return self.of(...)
end,
})

Module:Set - Revision history

WikiGOD at 05:50, 2 May 2021

WikiGOD at 05:47, 2 May 2021

WikiGOD at 05:22, 2 May 2021

WikiGOD: 1 revision imported

Mediawiki>Siroopwafel: Remove pretty comment before module return (produces catastrophic defect in LuaDoc/LDoc/Docbunto)