adventures with iterators

[Sven Olsen <sven2718@...>]

Yesterday I managed to trigger the "invalid key to next" error -- which is what tends to happen when you add new keys to a table while iterating through it.  For example:

local t={[1]=0,[3]=0,[5]=0,[12]=0}

for k,v in pairs(t) do

if k==5 then

t[k]=nil

t[4]=0

t[1622]=0

end

end

I know that pairs() is as fast as it is largely because it disallows this kind of editing.  And in any case, throwing an error isn't unreasonable, because it's hard to say, for certain, what the program ought to do in such a case.  An iteration like:

for k,v in pairs(shallow_copy(t)) do ...

has clearer behavior, and won't break.

But it occurred to me that a shallow copy isn't the only way of avoiding the issue.  A few days ago, I had cause to write an iterator that traverses the keys of a table in sorted order.  It was done as a non-allocating C function, and while slower than pairs, I've realized that it gives me another tool for handling cases where a table may need to change inside a traversal.  One that works, essentially, because in-order iteration provides another way of specifying what ought to happen when the table is modified.

I'm feeling unreasonably pleased with myself for figuring this out.

-Sven

PS:  Here's the non-allocating sorted key traversal code.  Maybe it's worth putting on the wiki somewhere?  There's already 2 versions of sorted iteration posted under Sample Code -- this would be yet a third, but it does have different pros and cons.   Each iterator call traverses the entire table, so walking through a table with spairs() is a O(n^2) operation.  The upside is that it's non-allocating, and has sensible behavior in the case of table modifications.

static int sorted_iter(lua_State *L) {

lua_settop(L, 2);  

lua_pushnil(L);

lua_pushnil(L);

lua_pushnil(L);

// 1: table

// 2: oldkey

// 3: newkey

// 4: newvalue

// 5: currentkey

// 6: currentvalue

while(lua_next(L,1)) {

if( lua_isnil(L,2) || lua_compare(L,2,5,LUA_OPLT) ) {

if( lua_isnil(L,3) || lua_compare(L,5,3,LUA_OPLT) ) {

lua_pushvalue(L,5);

lua_replace(L,3);

lua_replace(L,4);

continue;

}

}

lua_pop(L,1);

}

lua_settop(L,4);

return 2;

}

static int spairs(lua_State *L) {

lua_settop(L,1);

lua_pushcfunction(L, sorted_iter);

lua_pushvalue(L,1);

lua_pushnil(L);

return 3;

}