Re: [Lua-users-stdlib] Upheaval (blame Jamie Webb!)

[Jamie W. <j...@jm...>]

On Wednesday 04 February 2004 18:36, Reuben Thomas wrote:
> n is evil.

Perhaps, but the weird hidden n is a bit evil too. I agree that that is 
something that ought to be rationalised one way or the other though.

> > Also, next() doesn't honour numerical order.
>
> Doesn't matter unless the mapped function is assuming something about the
> underlying list. It shouldn't be.

Lua isn't a pure language. If map doesn't do what users expect, they will just 
go back to their for-loops.

> Cos it is. Discussed on the list; look at the code if you're not
> convinced. It's necessary because the table can be rehashed while you're
> traversing it. I think Squirrel avoids this.

The code below definately runs in O(N), meaning next() is O(1):

t = {}
for i = 1,N do t[i] = true end

k,v = next(t)
while k do
   t[k] = false
   k,v = next(t,k)
end

I can believe there are situations in which it is linear (can't be bothered to 
look at the source), but for the normal case where the keys are not modified, 
it doesn't appear to be.