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
use super::ControlFlowGraph;
use super::super::indexed_vec::IndexVec;
#[cfg(test)]
mod test;
pub fn post_order_from<G: ControlFlowGraph>(graph: &G, start_node: G::Node) -> Vec<G::Node> {
post_order_from_to(graph, start_node, None)
}
pub fn post_order_from_to<G: ControlFlowGraph>(graph: &G,
start_node: G::Node,
end_node: Option<G::Node>)
-> Vec<G::Node> {
let mut visited: IndexVec<G::Node, bool> = IndexVec::from_elem_n(false, graph.num_nodes());
let mut result: Vec<G::Node> = Vec::with_capacity(graph.num_nodes());
if let Some(end_node) = end_node {
visited[end_node] = true;
}
post_order_walk(graph, start_node, &mut result, &mut visited);
result
}
fn post_order_walk<G: ControlFlowGraph>(graph: &G,
node: G::Node,
result: &mut Vec<G::Node>,
visited: &mut IndexVec<G::Node, bool>) {
if visited[node] {
return;
}
visited[node] = true;
for successor in graph.successors(node) {
post_order_walk(graph, successor, result, visited);
}
result.push(node);
}
pub fn reverse_post_order<G: ControlFlowGraph>(graph: &G, start_node: G::Node) -> Vec<G::Node> {
let mut vec = post_order_from(graph, start_node);
vec.reverse();
vec
}