Nested Table Iterator

[adrix89]

One problem with iterating nested tables is that (usually) you need to know the 'scope' in addition to the key and the value.

A while ago I wrote a library for accessing nested tabled. It uses "cocatecated sting keys" as described here. Just make sure to get the code from the repo as the version on the forums may be slightly out of date.

It works with cyclic tables too.

Recursion is probably mandatory for this thing.

My implementation is non-recursive (see table.gckeys). I used breadth-first traversal with a queue.

Pretty interesting stuff. I don't know why I haven't stumbled upon it when I was scouring the whole site for examples on the subject.

[socket2810]

Probably you should rather iterate through all the tables with a simple recursive function while adding all values to a return table, then iterate through that table, however, if you really want an iterator function, I've quickly made one for you, coupled with an example after said function:

Code: Select all

function iter_function(e)
  local it, t -- current iterator/table
  local stack = {}
  table.insert(stack, {e, nil}) -- push first table with its last returned index
  
  local function getNext()
    if(t ~= stack[#stack]) then -- check if we're currently iterating on the top table
      it, t = pairs(stack[#stack][1]) -- if not, now we start iterating over its elements
    end
      
    local k, v = it(t, stack[#stack][2]) -- get next element while providing last returned index
    
    if(k) then
      stack[#stack][2] = k -- store the returned key
      
      if(type(v) == "table") then -- if the returned value is a table, start iterating over it
        table.insert(stack, {v,  nil}) -- push the table on the stack
        
        return getNext() -- start iterating over it
      else      
        return k, v
      end
    else -- no more elements to iterate on the current table
      table.remove(stack, #stack) -- pop the table we finished iterating
      
      if(#stack ~= 0) then -- if there is more tables to iterate, we recursively call this function
        return getNext()
      end
    end
    
  end
  
  return getNext
end

local list = {
  {
    {
      stuff = 'value'
    },
    
    {3, 7, 8}
  }, 
  
  {
    {
      {4, 5, 6 },
      {
        stuff = 'value2'
      }
    }
  },
  
  {2, 1},
  
  {
    {name = 'love'}
  },
  
  15
}

for k, v in iter_function(list) do
  print(k, v)
end

[Azhukar]

table.insert(stack, {e, nil}) -- push first table with its last returned index

Think about using tables themselves as an index for your stack.

[adrix89]

Probably you should rather iterate through all the tables with a simple recursive function while adding all values to a return table, then iterate through that table, however, if you really want an iterator function, I've quickly made one for you, coupled with an example after said function:

That is way over my head. What advantage would it have compared to other solutions? can you explain a bit what it does?

Also I already have my solution so feel free to discuss techniques not specific to my particular case for people who use search(there is no posts on stackoverflow so we must be doing something right)
Maybe some optimization techniques?

[socket2810]

It is simply easier. The function I made that does what you asked isn't something easy to do for someone new to Lua, not everyone knows how iterator functions works in Lua, or ipairs/pairs/next for example. Also if you have all your results before you iterate over them, you will also know how many results there are before using them. Here is the function:

Code: Select all

function iter_function(e, l)
  local ret = { }
  
  for k, v in pairs(e) do
    --print(k, v)
    if(type(v) == "table") then
      iter_function(v, l or ret)
    else
      table.insert(l or ret, {k, v})
    end
  end
  
  return pairs(ret)
end

for i, v in iter_function(list) do
   print(v[1], v[2])
end

@Azhukar
But then I wouldn't have a stack.

[Azhukar]

But then I wouldn't have a stack.

You do not need the order of the elements.

[socket2810]

But then I wouldn't have a stack.

You do not need the order of the elements.

Perhaps I don't, but I'd want to. As a matter of fact, I just tried to make it without using a stack, and even after I had exceeded my personal amount of not indicated programming practices, I still didn't managed to do it. Maybe you could chime in on how you would make such a function in the way you described?

[Azhukar]

Maybe you could chime in on how you would make such a function in the way you described?

Using next:

Code: Select all

function iter_function(e)
	local _new = {} --value unique to this function
	local passed = {} --prevents looping inside table
	
	local stack = {}
	stack[e] = _new --add first table
	passed[e] = true
	
	local function getNext()
		local currentTable,currentKey = next(stack)
		
		if (currentTable==nil) then return end --end of stack
		
		if (currentKey==_new) then currentKey = nil end --start of a new table
		
		local k,v = next(currentTable,currentKey)
		stack[currentTable] = k --remember last key
		
		if (k==nil) then
			return getNext() --end of table
		elseif (type(v)=="table") then
			if (passed[v]==nil) then
				passed[v] = true
				stack[v] = _new --add to stack
			end
			return getNext()
		else
			return k,v
		end
	end

	return getNext
end

Using next without recursion:

Code: Select all

function iter_function(e)
	local _new = {} --value unique to this function
	local passed = {} --prevents looping inside table
	
	local stack = {}
	stack[e] = _new --add first table
	passed[e] = true
	
	local function getNext()
		local currentTable,currentKey = next(stack)
		while (currentTable~=nil) do
			if (currentKey==_new) then currentKey = nil end --start of a new table
			
			local k,v = next(currentTable,currentKey)
			stack[currentTable] = k --remember last key
			
			if (type(v)=="table") then
				if (passed[v]==nil) then
					passed[v] = true
					stack[v] = _new --add to stack
				end
			elseif (k~=nil) then
				return k,v
			end
			
			currentTable,currentKey = next(stack)
		end
	end

	return getNext
end

Using coroutines:

Code: Select all

local function process(value,key,passed)
	local passed = passed or {} --in case of loops
	if (type(value)=="table" and passed[value]==nil) then
		passed[value] = true
		for k,v in pairs(value) do
			process(v,k,passed)
		end
	else
		coroutine.yield(key,value)
	end
end

local function iter_function(e)
	return coroutine.wrap(process),e
end

I personally prefer coroutines because they are more elegant.

[socket2810]

Thanks for those, even thought I still can't understand how you're using next in your "stack". I profiled all our functions and surprisingly yours, using hash tables were faster than mine using an array (the coroutine solution was barely faster, thought). Perhaps my solution returning the table contents orderly takes its toll on Lua. Comparison: (values in 1/100 of a second)

Code: Select all

Stack based	112.07983398438
Using next	76.056640625
Next without recursion	76.042724609375
Coroutine based	103.08666992188

[Azhukar]

Perhaps my solution returning the table contents orderly takes its toll on Lua.

You're not returning them orderly as there is no order to them in the first place. Using pairs/next is inherently unpredictable (except perhaps for next on numeric keys) as far as key order is concerned.

In your function you're using table.insert/remove which is one of the slowest methods of adding/removing a value to an array. You're also creating many tables to store your iterator and state.

The other factor in regards to speed is localization of variables, doing table.x is in fact indexing a table called table for key x. Localizing functions that you use repeatedly - before using them - will in simple traversals such as these increase relative speed by quite a bit. The only non localized variables used in my "next" variant is the function next and type.

Try measuring the speed of the various functions once you localize things like coroutine.yield

Example:

Code: Select all

local coroutine_yield = coroutine.yield
local coroutine_wrap = coroutine.wrap
local type = type
local pairs = pairs

local function process(value,key,passed)
	local passed = passed or {} --in case of loops
	if (type(value)=="table" and passed[value]==nil) then
		passed[value] = true
		for k,v in pairs(value) do
			process(v,k,passed)
		end
	else
		coroutine_yield(key,value)
	end
end

local function iter_function(e)
	return coroutine_wrap(process),e
end

I still can't understand how you're using next in your "stack"

next(table,key) called without key argument returns the "first" key and value of a table, called on my stack it in essence returns any key-value pair inside the stack, which is respectively a table in queue to be processed and the last key from the table that was processed.

I'm using the _new variable to represent nil inside the stack so that I can add tables on which next wasn't called yet, since adding nil to a key doesn't create a new table field.