Table traversal

[Dirk Laurie <dirk.laurie@...>]

A possibly useful addition to the repertoire of table iterators is
"traverse", which recursively visits every non-table value in a table
and returns not that value but a key-table pair (k,s) so that s[k]
refers to the table entry.  This can be extended to allow the cloning
of table structure and the simultaneous traversal of several tables.

For example, this is a deep table copy:

   t2={}
   for k,s1,s2 in traverse(t1,t2) do s2[k]=s1[k] end

An implementation as a module (Lua 5.1/5.2) is attached.

Dirk

local function traverse(...)
-- (c) 2011 Dirk Laurie.  Released under the zlib/libpng license.
--   traverse = require "traverse"
local help = [[  
`traverse(t1,..)`  returns an iterator that visits all the non-table 
items in t1, to be used thus:

   for k,s1,s2,...,sn in traverse(t1,t2,...,tn) do

t1 must be a table with no repeated subtables.  In the course of the 
iteration, the structure of t1 is cloned into t2,t3,...,tn, so that 
if e.g. t1[i][j][k] is a table, then t2[i][j][k] etc will also be 
tables.  If there is no existing table value at that position, an empty 
table is created by the iterator.  If a non-table value is stored at 
that position, an error is raised.

The values returned by the iterator are such that s1[k],s2[k],...,sn[k]
refer to corresponding items in t1,t2,...,tn.  No actual value is 
assigned by the iterator to the items s2[k] etc.  That can be done
inside the loop governed by the iterator.  For example, a deep copy 
of a table can be implemented thus:

   s2={}
   for k,s1,s2 in traverse(t1,t2) do s2[k]=s1[k] end
]]
local t={...}
if #t==0 then error(help) end
print (#t)
for k=1,#t do if type(t[k])~='table' then error("bad argument #"..k..
" to 'traverse' (table expected, got "..type(t[k])..")") 
   end end
return coroutine.wrap( function ()
   for k,v in pairs(t[1]) do
      if type(v)~='table' then coroutine.yield(k,unpack(t))
      else
         for j=2,#t do if not t[j][k] then t[j][k]={} end end
         local s={}
         for j=1,#t do s[j] = t[j][k] 
            end
         iter=traverse(unpack(s))
         while true do
            s = {iter()}
            if not s[1] then break end
            coroutine.yield(unpack(s)) 
            end
         end 
      end
   end )
end   

return traverse