lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]


On Apr 18, 2012, at 7:00 PM, Roberto Ierusalimschy wrote:

> 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

FWIW, here is an alternative implementation:

local function is_seq( aTable )
  for aKey in pairs( aTable ) do
    if not( type( aKey ) == 'number' and aKey > 0 and aKey == math.floor( aKey ) and aTable[ math.max( aKey - 1, 1 ) ] ~= nil ) then
      return false
    end
  end

  return true
end