Re: table.maxn...
[
Date Prev][
Date Next][
Thread Prev][
Thread Next]
[
Date Index]
[
Thread Index]
- Subject: Re: table.maxn...
- From: Dirk Laurie <dirk.laurie@...>
- Date: Mon, 1 Jun 2015 08:54:34 +0200
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