Re: Set class (was Microlight)

[Dirk Laurie <dirk.laurie@...>]

BTW, #s is (a) unavoidably O(N) [1] 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;

  __add = function(t,u)    
    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