Skip to content

Instantly share code, notes, and snippets.

@randrews
Created May 16, 2015 05:19
Show Gist options
  • Save randrews/76adcf823139165000b4 to your computer and use it in GitHub Desktop.
Save randrews/76adcf823139165000b4 to your computer and use it in GitHub Desktop.
Iterators
print("Basic for loop:\n-------------------------")
t = {'a','b','c','d','e'}
for i, v in ipairs(t) do
print(i,v)
end
--------------------------------------------------
print("\nTriangular series:\n-------------------------")
function triangular(_, n)
if not n then n = 0 end
n = n + 1
return n, n * (n+1) / 2
end
for n, v in triangular do
print(v)
if n == 10 then break end
end
--------------------------------------------------
print("\nIterative DFT:\n-------------------------")
tree = {a = {p = {p = {l = {e = {}}}},
n = {t = {}}}}
function dft(tree)
local value_stack = {}
local node_stack = {}
return function()
-- These represent the current node:
local value, node = value_stack[#value_stack], node_stack[#node_stack]
-- Now, to find the next node:
if not next(node_stack) then
-- Node stack empty, push the root node:
table.insert(value_stack, (next(tree)))
table.insert(node_stack, tree)
elseif next(node[value]) then
-- Otherwise, if the current node has children, push them on to the stack:
table.insert(value_stack, (next(node[value])))
table.insert(node_stack, node[value])
elseif next(node, value) then
-- Otherwise, if there's a right sibling, alter the stack to show it:
value_stack[#value_stack] = next(node, value)
else
-- Otherwise, pop the stack and find the next node of our parent
while true do
table.remove(node_stack)
table.remove(value_stack)
-- Must be the end of the tree:
if not next(node_stack) then return nil end
local value, node = value_stack[#value_stack], node_stack[#node_stack]
if next(node, value) then
value_stack[#value_stack] = next(node, value)
break
end
end
end
-- Return the top of the value stack, and the current value stack
return value_stack[#value_stack], value_stack
end
end
for node, path in dft(tree) do
print(node, inspect(path))
end
--------------------------------------------------
print("\nCoroutine DFT:\n-------------------------")
tree = {a = {p = {p = {l = {e = {}}}},
n = {t = {}}}}
local stack = {}
function traverse(node)
for k, v in pairs(node) do
table.insert(stack, k)
coroutine.yield(k, stack)
if type(v) == 'table' then
traverse(v)
end
table.remove(stack)
end
end
local co = coroutine.create(traverse)
repeat
local _, node, path = coroutine.resume(co, tree)
print(node, inspect(path))
until not node
--------------------------------------------------
print("\nCoroutine iterator DFT:\n-------------------------")
tree = {a = {p = {p = {l = {e = {}}}},
n = {t = {}}}}
function co_dft(tree)
local stack = {}
local function traverse(node)
for k, v in pairs(node) do
table.insert(stack, k)
coroutine.yield(k, stack)
if type(v) == 'table' then
traverse(v)
end
table.remove(stack)
end
end
local co = coroutine.create(function() traverse(tree) end)
return function()
local _, value, stack = coroutine.resume(co)
return value, stack
end
end
for node, path in co_dft(tree) do
print(node, inspect(path))
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment