Andrew de los Reyes | 5815155 | 2010-03-10 20:07:08 -0800 | [diff] [blame] | 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 "update_engine/graph_types.h" |
| 9 | #include "update_engine/topological_sort.h" |
| 10 | |
| 11 | using std::make_pair; |
| 12 | using std::vector; |
| 13 | |
| 14 | namespace chromeos_update_engine { |
| 15 | |
| 16 | class TopologicalSortTest : public ::testing::Test {}; |
| 17 | |
| 18 | namespace { |
| 19 | // Returns true if the value is found in vect. If found, the index is stored |
| 20 | // in out_index if out_index is not null. |
| 21 | template<typename T> |
| 22 | bool IndexOf(const vector<T>& vect, |
| 23 | const T& value, |
| 24 | typename vector<T>::size_type* out_index) { |
| 25 | for (typename vector<T>::size_type i = 0; i < vect.size(); i++) { |
| 26 | if (vect[i] == value) { |
| 27 | if (out_index) { |
| 28 | *out_index = i; |
| 29 | } |
| 30 | return true; |
| 31 | } |
| 32 | } |
| 33 | return false; |
| 34 | } |
| 35 | } // namespace {} |
| 36 | |
| 37 | TEST(TopologicalSortTest, SimpleTest) { |
| 38 | int counter = 0; |
| 39 | const Vertex::Index n_a = counter++; |
| 40 | const Vertex::Index n_b = counter++; |
| 41 | const Vertex::Index n_c = counter++; |
| 42 | const Vertex::Index n_d = counter++; |
| 43 | const Vertex::Index n_e = counter++; |
| 44 | const Vertex::Index n_f = counter++; |
| 45 | const Vertex::Index n_g = counter++; |
| 46 | const Vertex::Index n_h = counter++; |
| 47 | const Vertex::Index n_i = counter++; |
| 48 | const Vertex::Index n_j = counter++; |
| 49 | const Graph::size_type kNodeCount = counter++; |
| 50 | |
| 51 | Graph graph(kNodeCount); |
| 52 | |
| 53 | graph[n_i].out_edges.insert(make_pair(n_j, EdgeProperties())); |
| 54 | graph[n_i].out_edges.insert(make_pair(n_c, EdgeProperties())); |
| 55 | graph[n_i].out_edges.insert(make_pair(n_e, EdgeProperties())); |
| 56 | graph[n_i].out_edges.insert(make_pair(n_h, EdgeProperties())); |
| 57 | graph[n_c].out_edges.insert(make_pair(n_b, EdgeProperties())); |
| 58 | graph[n_b].out_edges.insert(make_pair(n_a, EdgeProperties())); |
| 59 | graph[n_e].out_edges.insert(make_pair(n_d, EdgeProperties())); |
| 60 | graph[n_e].out_edges.insert(make_pair(n_g, EdgeProperties())); |
| 61 | graph[n_g].out_edges.insert(make_pair(n_d, EdgeProperties())); |
| 62 | graph[n_g].out_edges.insert(make_pair(n_f, EdgeProperties())); |
| 63 | graph[n_d].out_edges.insert(make_pair(n_a, EdgeProperties())); |
| 64 | |
| 65 | vector<Vertex::Index> sorted; |
| 66 | TopologicalSort(graph, &sorted); |
| 67 | |
| 68 | for (Vertex::Index i = 0; i < graph.size(); i++) { |
| 69 | vector<Vertex::Index>::size_type src_index = 0; |
| 70 | EXPECT_TRUE(IndexOf(sorted, i, &src_index)); |
| 71 | for (Vertex::EdgeMap::const_iterator it = graph[i].out_edges.begin(); |
| 72 | it != graph[i].out_edges.end(); ++it) { |
| 73 | vector<Vertex::Index>::size_type dst_index = 0; |
| 74 | EXPECT_TRUE(IndexOf(sorted, it->first, &dst_index)); |
| 75 | EXPECT_LT(dst_index, src_index); |
| 76 | } |
| 77 | } |
| 78 | } |
| 79 | |
| 80 | } // namespace chromeos_update_engine |