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
    return function()
       i = i + 1
       if shiftback > 0 then
          tbl[i] = tbl[i+shiftback]
       if tbl[i] ~= nil then
          return i, tbl[i], remove
       for n = 1, shiftback-1 do
          tbl[i+n] = nil
       return nil

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
    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.