]> git.proxmox.com Git - rustc.git/blob - src/librustc_data_structures/graph/tests.rs
Imported Upstream version 1.9.0+dfsg1
[rustc.git] / src / librustc_data_structures / graph / tests.rs
1 // Copyright 2015 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
4 //
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
10
11 use graph::*;
12 use std::fmt::Debug;
13
14 type TestNode = Node<&'static str>;
15 type TestEdge = Edge<&'static str>;
16 type TestGraph = Graph<&'static str, &'static str>;
17
18 fn create_graph() -> TestGraph {
19 let mut graph = Graph::new();
20
21 // Create a simple graph
22 //
23 // A -+> B --> C
24 // | | ^
25 // | v |
26 // F D --> E
27
28 let a = graph.add_node("A");
29 let b = graph.add_node("B");
30 let c = graph.add_node("C");
31 let d = graph.add_node("D");
32 let e = graph.add_node("E");
33 let f = graph.add_node("F");
34
35 graph.add_edge(a, b, "AB");
36 graph.add_edge(b, c, "BC");
37 graph.add_edge(b, d, "BD");
38 graph.add_edge(d, e, "DE");
39 graph.add_edge(e, c, "EC");
40 graph.add_edge(f, b, "FB");
41
42 return graph;
43 }
44
45 #[test]
46 fn each_node() {
47 let graph = create_graph();
48 let expected = ["A", "B", "C", "D", "E", "F"];
49 graph.each_node(|idx, node| {
50 assert_eq!(&expected[idx.0], graph.node_data(idx));
51 assert_eq!(expected[idx.0], node.data);
52 true
53 });
54 }
55
56 #[test]
57 fn each_edge() {
58 let graph = create_graph();
59 let expected = ["AB", "BC", "BD", "DE", "EC", "FB"];
60 graph.each_edge(|idx, edge| {
61 assert_eq!(&expected[idx.0], graph.edge_data(idx));
62 assert_eq!(expected[idx.0], edge.data);
63 true
64 });
65 }
66
67 fn test_adjacent_edges<N: PartialEq + Debug, E: PartialEq + Debug>(graph: &Graph<N, E>,
68 start_index: NodeIndex,
69 start_data: N,
70 expected_incoming: &[(E, N)],
71 expected_outgoing: &[(E, N)]) {
72 assert!(graph.node_data(start_index) == &start_data);
73
74 let mut counter = 0;
75 for (edge_index, edge) in graph.incoming_edges(start_index) {
76 assert!(graph.edge_data(edge_index) == &edge.data);
77 assert!(counter < expected_incoming.len());
78 debug!("counter={:?} expected={:?} edge_index={:?} edge={:?}",
79 counter,
80 expected_incoming[counter],
81 edge_index,
82 edge);
83 match expected_incoming[counter] {
84 (ref e, ref n) => {
85 assert!(e == &edge.data);
86 assert!(n == graph.node_data(edge.source()));
87 assert!(start_index == edge.target);
88 }
89 }
90 counter += 1;
91 }
92 assert_eq!(counter, expected_incoming.len());
93
94 let mut counter = 0;
95 for (edge_index, edge) in graph.outgoing_edges(start_index) {
96 assert!(graph.edge_data(edge_index) == &edge.data);
97 assert!(counter < expected_outgoing.len());
98 debug!("counter={:?} expected={:?} edge_index={:?} edge={:?}",
99 counter,
100 expected_outgoing[counter],
101 edge_index,
102 edge);
103 match expected_outgoing[counter] {
104 (ref e, ref n) => {
105 assert!(e == &edge.data);
106 assert!(start_index == edge.source);
107 assert!(n == graph.node_data(edge.target));
108 }
109 }
110 counter += 1;
111 }
112 assert_eq!(counter, expected_outgoing.len());
113 }
114
115 #[test]
116 fn each_adjacent_from_a() {
117 let graph = create_graph();
118 test_adjacent_edges(&graph, NodeIndex(0), "A", &[], &[("AB", "B")]);
119 }
120
121 #[test]
122 fn each_adjacent_from_b() {
123 let graph = create_graph();
124 test_adjacent_edges(&graph,
125 NodeIndex(1),
126 "B",
127 &[("FB", "F"), ("AB", "A")],
128 &[("BD", "D"), ("BC", "C")]);
129 }
130
131 #[test]
132 fn each_adjacent_from_c() {
133 let graph = create_graph();
134 test_adjacent_edges(&graph, NodeIndex(2), "C", &[("EC", "E"), ("BC", "B")], &[]);
135 }
136
137 #[test]
138 fn each_adjacent_from_d() {
139 let graph = create_graph();
140 test_adjacent_edges(&graph, NodeIndex(3), "D", &[("BD", "B")], &[("DE", "E")]);
141 }