Re: table.maxn...

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

2015-06-01 0:22 GMT+02:00 Coda Highland <chighland@gmail.com>:
[as corrected 21 minutes later]

> function isSequence(t)
>   counter = 0
>   numNumeric = 0
>   for k, _ in pairs(t) do
>     if (type(k) == "number") and (k > 0) and (k == math.floor(k)) then
>       numNumeric = numNumeric + 1
>       counter = counter + k - numNumeric
>     end
>   end
>   return counter == 0
> end
>
> This uses O(1) space and O(n) time, compared to the O(n) space and
> potentially O(n^2) time your function needed (but probably O(n log n)
> assuming that Lua grows the array intelligently and uses a smart
> sorting algorithm). It works because the counter is SIGNED, and for
> a proper sequence you will always add and subtract every natural
> number between 1 and #t exactly once, while a table with gaps will
> result in a positive number.

Alternatively one can take a Procrustean approach and say that
if the table is not a valid sequence, it will be made into one.

function getmetafield (value,field)
-- if the metatable exists, return field, metatable
-- if the metatable does not exist, return nothing
    local mt = getmetatable(value)
    if mt then return mt[field], mt end
end

function to_Sequence(t)
-- if t does not a valid __len metamethod, define one that returns
--   the original length as traversed by "ipairs", creating a new
--   metatable if necessary.
-- return original __len and original metatable
   local len,orig_mt = getmetafield(t,"__len")
   if len then return len,orig_mt end
   local n=0
   for k in ipairs(t) do n=k end
   local mt = orig_mt or {}
   mt.__len = function() return n end
   setmetatable(t,mt)
   return len,orig_mt
end

function undo_to_Sequence(t,len,orig_mt)
-- restores t to what it was before to_Sequence
   if len then return end
   if orig_mt then orig_mt.__len = nil
      else setmetatable(t,nil)
   end
end