Re: ipairs_remove - remove items from array while iterating it

[Hisham <h@...>]

On 1 November 2013 18:34, Dirk Laurie <dirk.laurie@gmail.com> wrote:
> 2013/11/1 Hisham <h@hisham.hm>:
>
>> A simple idea crossed my mind and I thought some of you might enjoy,
>> so I decided to share.
>>
>> After a number of times when I had to iterate arrays, mark some
>> elements for removal, and then remove them in a second loop, I wished
>> I'd be able to do it in one go.
>
> The second-loop method is O(n).
>
>> ipairs_remove returns the index and value as usual, plus a "remove"
>> function that removes the current element from the array and adjusts
>> the iteration so it keeps going (if you table.remove() the current
>> element during an ipairs iteration, you end up skipping the next
>> item). It never occured to me before to return a utility function like
>> this through the iterator; it seems an elegant solution.
>
> Elegant, but O(n^2).

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

local t = { "a", "b", "c", "d", "e" }

for i, v in ipairs(t) do
   print(i, v)
end

print("****")

for i, v, remove in ipairs_remove(t) do
   print(i, v)
   if v == "b" or v == "d" then remove() end
end

print("****")

for i, v in ipairs(t) do
   print(i, v)
end

-- Hisham