Re: Definition of a sequence

[Tim Hill <drtimhill@...>]

> 
> However, tables have two features that work if you have a sequence: the length operator will return the last integral index and ipairs will iterate, *in order* from 1 to max n. However, ipairs is merely duplicating `for i=1, t# do`, so it isn't critical, and length could be written in Lua, save for the token. So I guess I see your point..... Or maybe the length operator is more to blame?
> 
> As far as red black trees: that works if the tree is holding structures that are native in C, but I'm not sure how you'd implement it in C and have it work in a table. 
> 
> Even for me, this isn't something that I can know if it's a problem or not, until the library is used. IRL: there may be very few insertions in very small tables. If it gets bad, I'll get fancy. 
> 
> -Andrew 

It’s late and i’m typing from memory .. but didn’t ipairs() finally settle down to just stopping at the first nil (in 5.3 that is)?

As far as the RB tree goes, one approach is to use the tree node address as light userdata keys for the table. There are of course many others. This also keeps the nodes small which helps with tree efficiency as others have noted.

So it goes like this ..
1. Lua has integer index for entry in table.
2. You call helper C function, passing in index.
3. C code looks up item in tree
4. Code pushes node address onto Lua stack as light userdata, and returns this.
5. Lua uses the return value as the index into the table.

Inserting/removal of course is just as easy. With a bit more finesse you can hide the tree behind a metatable and directly index the table using integer keys and have __index() do the lookup behind the scenes.

—Tim