OLD | NEW |
---|---|
(Empty) | |
1 // Copyright (c) 2010 The Chromium OS Authors. All rights reserved. | |
2 // Use of this source code is governed by a BSD-style license that can be | |
3 // found in the LICENSE file. | |
4 | |
5 #include <utility> | |
6 #include <vector> | |
7 #include <gtest/gtest.h> | |
8 #include "chromeos/obsolete_logging.h" | |
Daniel Erat
2010/03/11 01:31:49
you don't need this include, do you? (noticed bec
adlr
2010/03/11 04:12:08
removed
| |
9 #include "update_engine/graph_types.h" | |
10 #include "update_engine/topological_sort.h" | |
11 | |
12 using std::make_pair; | |
13 using std::vector; | |
14 | |
15 namespace chromeos_update_engine { | |
16 | |
17 class TopologicalSortTest : public ::testing::Test {}; | |
18 | |
19 namespace { | |
20 // Returns true if the value is found in vect. If found, the index is stored | |
21 // in out_index if out_index is not null. | |
22 template<typename T> | |
23 bool IndexOf(const vector<T>& vect, | |
24 const T& value, | |
25 typename vector<T>::size_type* out_index) { | |
26 for (typename vector<T>::size_type i = 0; i < vect.size(); i++) { | |
27 if (vect[i] == value) { | |
28 if (out_index) { | |
29 *out_index = i; | |
30 } | |
31 return true; | |
32 } | |
33 } | |
34 return false; | |
35 } | |
36 } // namespace {} | |
37 | |
38 TEST(TopologicalSortTest, SimpleTest) { | |
39 int counter = 0; | |
40 const Vertex::Index n_a = counter++; | |
41 const Vertex::Index n_b = counter++; | |
42 const Vertex::Index n_c = counter++; | |
43 const Vertex::Index n_d = counter++; | |
44 const Vertex::Index n_e = counter++; | |
45 const Vertex::Index n_f = counter++; | |
46 const Vertex::Index n_g = counter++; | |
47 const Vertex::Index n_h = counter++; | |
48 const Vertex::Index n_i = counter++; | |
49 const Vertex::Index n_j = counter++; | |
50 const Graph::size_type kNodeCount = counter++; | |
51 | |
52 Graph graph(kNodeCount); | |
53 | |
54 graph[n_i].out_edges.insert(make_pair(n_j, EdgeProperties())); | |
55 graph[n_i].out_edges.insert(make_pair(n_c, EdgeProperties())); | |
56 graph[n_i].out_edges.insert(make_pair(n_e, EdgeProperties())); | |
57 graph[n_i].out_edges.insert(make_pair(n_h, EdgeProperties())); | |
58 graph[n_c].out_edges.insert(make_pair(n_b, EdgeProperties())); | |
59 graph[n_b].out_edges.insert(make_pair(n_a, EdgeProperties())); | |
60 graph[n_e].out_edges.insert(make_pair(n_d, EdgeProperties())); | |
61 graph[n_e].out_edges.insert(make_pair(n_g, EdgeProperties())); | |
62 graph[n_g].out_edges.insert(make_pair(n_d, EdgeProperties())); | |
63 graph[n_g].out_edges.insert(make_pair(n_f, EdgeProperties())); | |
64 graph[n_d].out_edges.insert(make_pair(n_a, EdgeProperties())); | |
65 | |
66 vector<Vertex::Index> sorted; | |
67 TopologicalSort(graph, &sorted); | |
68 | |
69 for (Vertex::Index i = 0; i < graph.size(); i++) { | |
70 vector<Vertex::Index>::size_type src_index = 0; | |
71 EXPECT_TRUE(IndexOf(sorted, i, &src_index)); | |
72 for (Vertex::EdgeMap::const_iterator it = graph[i].out_edges.begin(); | |
73 it != graph[i].out_edges.end(); ++it) { | |
74 vector<Vertex::Index>::size_type dst_index = 0; | |
75 EXPECT_TRUE(IndexOf(sorted, it->first, &dst_index)); | |
76 EXPECT_LT(dst_index, src_index); | |
77 } | |
78 } | |
79 } | |
80 | |
81 } // namespace chromeos_update_engine | |
OLD | NEW |