-
Notifications
You must be signed in to change notification settings - Fork 2
/
tree_graph.lua
64 lines (50 loc) · 1.71 KB
/
tree_graph.lua
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
-- Optimizations.
local ipairs = ipairs;
local assert = assert;
local error = error;
function createTreeNodeIterator(children_cb, parent_cb)
local iterator = {};
local endNode = nil;
local curNode = nil;
function iterator.setCurrentNode(node)
curNode = node;
endNode = parent_cb(curNode);
end
function iterator.getCurrentNode()
return curNode;
end
function iterator.isEnd()
return ( curNode == endNode );
end
local function get_item_idx_in_table(t, i)
for m,n in ipairs(t) do
if (n == i) then
return m;
end
end
error("assumed child node not found during tree iteration; has the tree been changed during walking?");
end
function iterator.next()
local cur_children = children_cb(curNode);
local tryNextChild = 1;
while (true) do
-- First try going down the child.
local attemptCurNode = cur_children[tryNextChild];
if (attemptCurNode) then
curNode = attemptCurNode;
break;
end
-- If there is no more child to go down to, then we try going along the next child
-- of the parent.
local prev_node = curNode;
curNode = parent_cb(curNode);
if (curNode == endNode) then
-- Quit if we have no more siblings to go along by.
break;
end
cur_children = children_cb(curNode);
tryNextChild = get_item_idx_in_table(cur_children, prev_node) + 1;
end
end
return iterator;
end