  lua-l archive

• Subject: Re: Set class (was Microlight)
• From: Dirk Laurie <dirk.laurie@...>
• Date: Tue, 21 Feb 2012 14:56:58 +0200

BTW, #s is (a) unavoidably O(N)  and (b) only works for 5.2.  So
perhaps we need count_keys() as well.

In the Set class I think #s can be implemented as O(1).  I'll try to work
up a proof-of-concept.

It's attached.  Since it is only proof-of-concept I have not bothered to do the other set metamethods (__sub, __mul, __le, __lt, __eq, …)

```-- a Set class
-- Dirk Laurie (with a lot of help from PiL), license MIT
-- 21 February 2012

-- Usage:
--[[
set=require"set"
s = set(lst,tbl)
]]
-- s gets the non-false 'ipairs' values of lst, all 'pairs' keys of tbl)
-- The elements of the set are the keys of s, all values in s are 'true'

-- Examples
--[[
s = set({10,20,30},{a=1,b=2,c=3})
t = s + set{3}
print(#t)  --> 7
t.a = false   -- or nil
print(#t)  --> 6
t[false] = 0  (false is a legal element, 0 counts as true)
print(#t)  --> 7
ml = require "ml"
print(table.concat(ml.keys(t),',')) --> 10,30,c,b,3,a,20
--]]

local secret_set = {}
local secret_n = {}
local forward = {}

local set_mt = {

__index = function (t,k)
local s=t[secret_set]
return s[k]
end;

__newindex = function (t,k,v)
local s=t[secret_set]
local sk = s[k]
if v and not sk then
t[secret_n] = t[secret_n]+1
s[k] = true
elseif sk and not v then
t[secret_n] = t[secret_n]-1
s[k] = false
end
end;

__len = function (t) return t[secret_n] end;

__pairs = function(t) return pairs(t[secret_set]) end;

assert(getmetatable(u)==getmetatable(t),"expected set, got "..type(u))
local s=forward.Set(nil,t[secret_set])
for k in pairs(u) do s[k]=true end
return s
end;

}

forward.Set = function (values,keys)
local proxy = {}
local t ={}
if type(values)=='table' then
for k,v in ipairs(values) do t[v]=true
end
else assert(values==nil,"expected table, got "..type(values))
end
if type(keys)=='table' then
for k in pairs(keys) do t[k]=true end
else assert(keys==nil,"expected table, got "..type(keys))
end
local n=0
for k in pairs(t) do n=n+1 end
proxy[secret_set] = t
proxy[secret_n] = n
setmetatable(proxy, set_mt)
return proxy
end

return forward.Set
```