DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

Snippets has posted 5883 posts at DZone. View Full User Profile

Lua: Descending Table Traversal Round 2: Iterator Object

12.05.2005
| 5199 views |
  • submit to reddit
        This is some concept code I threw together for Lua to see how feasable it was to make a lua object/table into an iterator that you can manipulate.  This iterator descends through all tables and subtables of any queued table.  It returns the "path" we're at, as a string, the current table, the key, and the value.

Code:
traverse = {}
function traverse:new(tname)
	local o = {}
	o.names = {}
	o.queue = {}
	o.cur = {
		tbl = nil,
		path = nil,
		state = nil,
	}

	local mt = {}
	function mt:__call(tn)
		return o:iter(tn)
	end
	mt.__index = self
	setmetatable(o, mt)

	if tname then
		o:enqueue(tname)
	end
	return o
end
function traverse:next()
	local v
	local names, queue, cur = self.names, self.queue, self.cur

	local function _poptbl()
		if cur.tbl then
			names[cur.tbl] = nil
		end
		cur.tbl = table.remove(queue, 1)
		cur.path = names[cur.tbl]
		cur.state = nil
	end

	repeat
		-- Find something to return to the user...
		if not cur.state then
			-- Pop a new table off the stack
			_poptbl()
			if not cur.tbl then
				-- No more tables to process
				return nil
			end
		end
		cur.state,v = next(cur.tbl, cur.state)
	until cur.state

	if type(v) == "table" then
		local path = cur.path.."."..cur.state
		names[v] = path
		table.insert(queue, v)
	end
	return cur.path,cur.tbl,cur.state,v
end
function traverse:iter(tname)
	if tname then
		self:enqueue(tname)
	end
	return function(...) return self:next(unpack(arg)) end, nil, nil
end
function traverse:enqueue(tname)
	local v = _G[tname]
	table.insert(self.queue, v)
	self.names[v] = tname
end
function traverse:reset()
	self.names = {}
	self.queue = {}
end
local traverse_mt = {
    __call = function(self, tname)
             	if tname then
             		return self:new(tname):iter()
             	else
             		return self:new()
             	end
             end
}
setmetatable(traverse, traverse_mt)

Example Usage:
foo = {a={},b={},c={"bar"},d={e={},f={"moo"}},1,2,3,4,5}
bar = {"alpha", "beta", "theta", omega = {}}

local mytraverser = traverse()
mytraverser:enqueue("bar")
mytraverser:enqueue("foo")
for p,t,k,v in mytraverser() do
--for p,t,k,v in traverse('foo') do
	print(string.format("%s[%s] = %s",tostring(p),tostring(k),tostring(v)))
end

Output from Example Usage:
bar[1] = alpha
bar[2] = beta
bar[3] = theta
bar[omega] = table: 0x510650
foo[1] = 1
foo[2] = 2
foo[3] = 3
foo[4] = 4
foo[5] = 5
foo[a] = table: 0x5102d0
foo[c] = table: 0x510370
foo[b] = table: 0x510320
foo[d] = table: 0x5103c0
foo.c[1] = bar
foo.d[e] = table: 0x5104c0
foo.d[f] = table: 0x510510
foo.d.f[1] = moo