ScanBF.lua

-- Perform a breadth first traversal of an instance's descendant tree.
--
-- >  for obj in scanBF(root) do
-- >     print(obj)
-- >  end

local function scanBF(root)
	local queue = {} -- Queue containing stacks of children
	local qIdx0 = 1 -- Queue front index
	local qIdx1 = 0 -- Queue back index
	
	local front = {root} -- Cached front element of the queue
	local fIdx = 1 -- Index to the top of the front element
	
	return function()
		if queue then -- Fall through when there is nothing left to traverse
			local item = front[fIdx] -- Get the top element of the front stack
			local children = item:GetChildren()
			
			-- Enqueue the current item's children, if any
			if #children > 0 then
				qIdx1 += 1
				queue[qIdx1] = children
			end
			
			if fIdx > 1 then
				-- The front stack still has unprocessed members; pop it
				fIdx -= 1
				
			else
				-- The front stack is exhausted
				if qIdx0 <= qIdx1 then -- Queue is not empty. Move on to the next stack
					front = queue[qIdx0]
					fIdx = #front
					qIdx0 += 1
					
				else -- Queue is empty. Free references and stop
					queue = nil
					front = nil
				end
			end
			
			return item
		end
	end
end