Re: Lua 5.2 Length Operator and tables (bug?)

[Roberto Ierusalimschy <roberto@...>]

> Suppose that we patch a Lua interpreter slightly to add another field
> to the "Table" structure - i.e., to:
> 
>   http://www.lua.org/source/5.2/lobject.h.html#Table

This change would increase the size of any empty table by 12%.


> Let's call this new field "npik", for the "number of positive integer
> keys" in the table. It is relatively cheap to keep it up to date - we
> only need to modify the code that implements "T[key] = val".

The change is simple, but not too simple. (It has to consider the
four kinds of changes: nil->nil, nil->non-nil, non-nil->nil, and
non-nil->non-nil.) Moreover, its cost will be at least O(n) on the
size of the table (only it will be amortized).


> Suppose that we add a function "npik" that reads the npik field of a
> table; then we can implement "issequence" as just the translation of
> this to C:
> 
>     issequence = function (T)
>         for i=1,npik(T) do
>           if T[i] == nil then return false end
>         end
>         return true
>       end

This is still a O(n) operation. I do not think we need 'npik' to write
an O(n) 'issequence' function:

function issequence (t)
  local n = #t    -- assumes 5.1 definition
  local i = 0
  for k in pairs(t) do
    if type(k) == 'number' and k > 0 then   -- positive numeric key?
      if k ~= math.floor(k) or k > n then   -- not in set {1..n} ?
        return false
      end
      i = i + 1  -- count it
    end
  end
  return i == n   -- set is complete?
end

-- Roberto