lua-users home
lua-l archive

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

Am 02.11.2013 18:27 schröbte Thijs Schreijer:


Well noted! Also including the fix by Ashwin Hirchi (I love this list!)

local function ipairs_remove(tbl)
    local i = 0
    local shiftback = 0
    local remove = function()
       shiftback = shiftback + 1
       i = i - 1
    end
    return function()
       i = i + 1
       if shiftback > 0 then
          tbl[i] = tbl[i+shiftback]
       end
       if tbl[i] ~= nil then
          return i, tbl[i], remove
       end
       for n = 1, shiftback-1 do
          tbl[i+n] = nil
       end
       return nil
    end
end



This contains some nasty side effects when not finishing the loop
(return, break, or goto). Only when the loop finishes the remaining
elements are cleared. So if you don't finish, they get duplicated.
If you modify the code to clear them while looping, then breaking the
loop results in a hole in the list (possibly even worse).
Maybe a for loop iterator is the wrong interface for this particular problem. Maybe something like `table.foreachi_rm()`? 
Or the "second loop" method in form of a `compact()` function ...

    local n = #t
    for i = 1, n do
      if should_remove( t[ i ] ) then t[ i ] = nil end
    end
    compact( t, n )   -- or compact( t, 1, n )



So I think the remove() function should use table.remove() to clear the entry to prevent those sideeffects


That would make it O(n*m) again (m: elements to remove).



Having said that, I think the most elegant solution is backward traversal, as Pasi Mankinen already mentioned


... which is also O(n*m), although with less copy operations on average.



Thijs



Philipp