Wikipedia

Module:Sandbox/Alexiscoutinho/Lua set: Difference between revisions

Browse history interactively
← Previous editNext edit →
Content deleted Content added
m Updated TableTools dependency
Implemented hash collision handling by adding a function hash table and, most importantly, by greatly improving the internal data representation with "_elements" and "_elements_obj". Improved valid element check. Converted "_get", "_set" and "_del" to normal methods. Optimized some methods by using "_get" instead of "has".
Line 2:
local libraryUtil = require('libraryUtil')
local TableTools = require('Module:TableTools')
local warn = require('Module:Warning')
 
local basic_types = {boolean=1, string=1, number=1, ['function']=1}
-- Note: hash collisions are not handled yet
 
local frozenset = class('frozenset', {
 
local f_hashes = {} -- so that function elements can be properly compared and ordered in frozenset._hash
local f_hashes_mt = {
__index = function (t, key)
local h = tonumber('0x' .. mw.hash.hashValue('fnv1a32', tostring(os.time() + math.random())))
f_hashes[key] = h
return h
end,
__mode = 'k'
}
setmetatable(f_hashes, f_hashes_mt)
 
 
local frozenset, _frozenset = class('frozenset', {
__init = function (self, args)
local elements = {}
self._elements = elements
self._elements_obj = {}
 
if #args == 0 then -- for performance
self._elements = elements
return
elseif #args == 1 then
local arg = args[1]
if type(arg) == 'string' then
local c
for i = 1, mw.ustring.len(arg) do
elements[c = mw.ustring.sub(arg, i,i)] = true
elements[c] = c
end
self._elements = elements
return
elseif pcall(pairs, arg) or pcall(ipairs, arg) then
Line 26 ⟶ 43:
if TableTools.isArrayLike(args) then
for i, v in ipairs(args) do
if type(pcall(pairs, v) or== pcall(ipairs,'table' v))or and not (isinstance(v) and v.hash) == nil then
error(("TypeError: invalid element #%d type (got %s, awhich mutableis collectionnot hashable)"):format(i, type(v)), 3)
end
self._set(elements, v)
end
else
for k in pairs(args) do
if type(pcall(pairs, k) or== pcall(ipairs,'table' k))or and not (isinstance(k) and k.hash) == nil then
error(("TypeError: invalid element type (got %s, awhich mutableis collectionnot hashable)"):format(type(k)), 3)
end
self._set(elements, k)
end
end
end,
 
_get = function (self, elem)
self._elements = elements
if basic_types[type(elem)] then
return self._elements[elem]
else
local elements_obj = self._elements_obj
local h = elem.hash()
 
while elements_obj[h] ~= nil do
if elements_obj[h] == elem then
return elem
end
h = h + 1
end
end
end,
 
_set = function (self, elem)
if basic_types[type(elem)] then
self._elements[elem] = elem
else
local elements_obj = self._elements_obj
local h = elem.hash()
 
while elements_obj[h] ~= nil do
if elements_obj[h] == elem then
return
end
h = h + 1
end
elements_obj[h] = elem -- otherwise different objects with the same content would duplicate
end
end,
 
__pairs = function (self)
local elems = self._elements
local k, v
 
local function iterator(elements)
local function iterator()
k, v = next(elements, k)
ifk, v == truenext(elems, thenk)
if k == nil and elems == self._elements then
return k
elems = self._elements_obj
else
returnk, v --= nilnext(elems, at the endk)
end
return v -- nil at the very end
end
 
return iterator, self._elements
return iterator
end,
 
Line 60 ⟶ 111:
end,
 
_get_keySort = function (elementsitem1, elemitem2)
-- "number" < "string", so numbers will be sorted before strings.
if isinstance(elem) and elem.hash then
local type1, type2 = type(item1), type(item2)
return elements[elem.hash()]
if type1 ~= type2 then
return type1 < type2
elseif type1 == 'number' or type1 == 'string' then
return item1 < item2
elseif type1 == 'boolean' then
return tostring(item1) < tostring(item2)
else
local hash1, hash2
return elements[elem]
if type1 == 'function' then
end
hash1, hash2 = f_hashes[item1], f_hashes[item2]
end,
if hash1 == hash2 then
 
warn(("HashWarning: function hash collision at %d"):format(hash1), 2)--what should be the level?
_set = function (elements, elem)
end
if isinstance(elem) and elem.hash then
else
elements[elem.hash()] = elem -- otherwise different objects with the same content would duplicate
hash1, hash2 = item1.hash(), item2.hash()
else
if hash1 == hash2 then
elements[elem] = true
warn(("HashWarning: object hash collision at %d"):format(hash1), 2)
end
end
return hash1 < hash2
end
end,
 
_hash = function (self)
if self.__hash ~= nil then
return self.__hash
end
 
-- frozensets with the same elements/keys (meaning equal) may have a different order, so 'order' them before hashing
-- frozensets with the same elements (meaning equal) may have a different order, so 'order' them before hashing
local ordered_keys = TableTools.keysToList(self._elements)
local ordered_elems = TableTools.keysToList(self, self._keySort, true)
-- convert keys to strings for table.concat; note that information will be lost for functions
 
for i, key in ipairs(ordered_keys) do
-- convert elements to strings for table.concat
if type(key) == 'string' then
local elemType
ordered_keys[i] = "'" .. key .. "'"
for i, elem in ipairs(ordered_elems) do
elemType = type(elem)
if elemType == 'number' or elemType == 'boolean' then
ordered_elems[i] = tostring(elem)
elseif elemType == 'string' then
ordered_elems[i] = "'" .. elem .. "'"
elseif elemType == 'function' then
ordered_elems[i] = 'f' .. f_hashes[elem]
else
ordered_keysordered_elems[i] = tostring'o' .. elem.hash(key)
end
end
 
local str = '{' .. table.concat(ordered_keysordered_elems, ',') .. '}' -- wrap in {} to differentiate from tuple
self.__hash = tonumber('0x' .. mw.hash.hashValue('fnv1a32', str))
return self.__hash
Line 98 ⟶ 167:
__tostring = function (self)
local string_elems = {}
local elemType
 
for elem in pairs(self) do
ifelemType = type(elem) == 'string' then
if elemType == 'string' then
string_elems[#string_elems+1] = "'" .. elem .. "'"
elseif elemType == 'function' then
string_elems[#string_elems+1] = 'f' .. f_hashes[elem]
else
string_elems[#string_elems+1] = tostring(elem)
end
end
 
local str = '{' .. table.concat(string_elems, ', ') .. '}'
return str
Line 110 ⟶ 185:
 
len = function (self)
return TableTools.size(self._elements) + TableTools.size(self._elements_obj)
end,
 
Line 116 ⟶ 191:
if isinstance(elem, 'set') then
elem = frozenset{elem}
elseif type(pcall(pairs, elem) or== pcall(ipairs,'table' elem))or and not (isinstance(elem) and elem.hash) == nil then
error(("TypeError: invalid element type (got %s, awhich mutableis collectionnot hashable)"):format(type(elem)), 2)
end
return self._get(self._elements, elem) ~= nil and true or false
end,
 
Line 125 ⟶ 200:
libraryUtil.checkTypeMulti('isdisjoint', 1, other, {'set', 'frozenset'})
for elem in pairs(other) do
if self._get(self._elements, elem) ~= nil then
return false
end
Line 138 ⟶ 213:
__le = function (a, b)
for elem in pairs(a) do
if not b._get(b._elements, elem) == nil then
return false
end
Line 160 ⟶ 235:
 
__add = function (a, b)
local elementssum, _sum = a.__class{}
for elem in pairs(a) do
a_sum._set(elements, elem)
end
for elem in pairs(b) do
b_sum._set(elements, elem)
end
return a.__class{elements}sum
end,
 
Line 177 ⟶ 252:
 
__mul = function (a, b)
local elementsproduct, _product = a.__class{}
for elem in pairs(a) do
if b._get(b._elements, elem) ~= nil then
b_product._set(elements, elem)
end
end
return a.__class{elements}product
end,
 
Line 193 ⟶ 268:
 
__sub = function (a, b)
local elementsdifference, _difference = a.__class{}
for elem in pairs(a) do
if not b._get(b._elements, elem) == nil then
b_difference._set(elements, elem)
end
end
return a.__class{elements}difference
end,
 
Line 207 ⟶ 282:
 
__pow = function (a, b)
local elementssymm_diff, _symm_diff = a.__class{}
for elem in pairs(a) do
if not b._get(b._elements, elem) == nil then
b_symm_diff._set(elements, elem)
end
end
for elem in pairs(b) do
if not a._get(a._elements, elem) == nil then
a_symm_diff._set(elements, elem)
end
end
return a.__class{elements}symm_diff
end,
 
copy = function (self)
return (self.__class{self}) -- to not leak the private instance
end,
 
Line 229 ⟶ 304:
end,
 
__staticmethods = {'_get', '_set_keySort'},
__protected = {'_get', '_set'}
})
Line 235 ⟶ 310:
 
local set = class('set', frozenset, {
_del = function (elementsself, elem)
if isinstancebasic_types[type(elem) and elem.hash] then
elementsself._elements[elem.hash()] = nil
else
local elements_obj = self._elements_obj
elements[elem] = nil
local h = elem.hash()
 
while elements_obj[h] ~= nil do
if elements_obj[h] == elem then
elements_obj[h] = nil
return
end
h = h + 1
end
end
end,
 
update = function (self, ...)
local others, other = {...}, nil
for i = 1, select('#', ...) do
other = frozenset{others[i]}
for elem in pairs(other) do
self._set(self._elements, elem)
end
end
Line 254 ⟶ 338:
 
intersection_update = function (self, ...)
local others, other_, _other = {...}, nil
for i = 1, select('#', ...) do
other_, _other = frozenset_frozenset{others[i]}
for elem in pairs(self) do -- probably faster than iterating through (likely longer) "other"
if _other._get(elem) == nil then
if not other.has(elem) then -- probably faster than iterating through (likely longer) other to access self._get
self._del(self._elements, elem)
end
end
Line 266 ⟶ 350:
 
difference_update = function (self, ...)
local others, other_, _other = {...}, nil
for i = 1, select('#', ...) do
other_, _other = frozenset_frozenset{others[i]}
for elem in pairs(self) do
if other_other.has_get(elem) ~= nil then
self._del(self._elements, elem)
end
end
Line 278 ⟶ 362:
 
symmetric_difference_update = function (self, other)
otherlocal _, _other = frozenset_frozenset{other}
for elem in pairs(self) do
if other_other.has_get(elem) ~= nil then
self._del(self._elements, elem)
end
end
for elem in pairs(other_other) do
if not self._get(self._elements, elem) == nil then
self._set(self._elements, elem)
end
end
Line 292 ⟶ 376:
 
add = function (self, elem)
if type(pcall(pairs, elem) or== pcall(ipairs,'table' elem))or and not (isinstance(elem) and elem.hash) == nil then
error(("TypeError: invalid element type (got %s, awhich mutableis collectionnot hashable)"):format(type(elem)), 2)
end
self._set(self._elements, elem)
end,
 
Line 301 ⟶ 385:
if isinstance(elem, 'set') then
elem = frozenset{elem}
elseif type(pcall(pairs, elem) or== pcall(ipairs,'table' elem))or and not (isinstance(elem) and elem.hash) == nil then
error(("TypeError: invalid element type (got %s, awhich mutableis collectionnot hashable)"):format(type(elem)), 2)
end
if not self._get(self._elements, elem) then== --nil cannot use self.has since error level would be incorrectthen
error(("KeyError: %s"):format(tostring(elem)), 2)
end
self._del(self._elements, elem)
end,
 
Line 313 ⟶ 397:
if isinstance(elem, 'set') then
elem = frozenset{elem}
elseif type(pcall(pairs, elem) or== pcall(ipairs,'table' elem))or and not (isinstance(elem) and elem.hash) == nil then
error(("TypeError: invalid element type (got %s, awhich mutableis collectionnot hashable)"):format(type(elem)), 2)
end
self._del(self._elements, elem)
end,
 
Line 322 ⟶ 406:
local k, v = next(self._elements)
if k == nil then
k, v = next(self._elements_obj)
error("KeyError: pop from an empty set", 2)
if k == nil then
end
error("KeyError: pop from an empty set", 2)
if v == true then
end
self._del(self._elements, k)
return k
else
self._del(self._elements, v)
return v
end
self._del(v)
return v
end,
 
clear = function (self)
self._elements = {}
self._elements_obj = {}
end,
 
__staticmethods = {'_del'},
__protected = {'_del'}
})
Retrieved from "https://en.wikipedia.org/wiki/Module:Sandbox/Alexiscoutinho/Lua_set"