From d7466d98bb192952a31255bee53c9d74192dedd6 Mon Sep 17 00:00:00 2001
From: Alexander Karatarakis <alkarata@microsoft.com>
Date: Tue, 11 Apr 2017 14:44:14 -0700
Subject: Extract toposort into a free function

---
 toolsrc/include/vcpkg_Graphs.h | 72 +++++++++++++++++++++++++-----------------
 1 file changed, 43 insertions(+), 29 deletions(-)

(limited to 'toolsrc/include')

diff --git a/toolsrc/include/vcpkg_Graphs.h b/toolsrc/include/vcpkg_Graphs.h
index b97f7ac50..1f90710fd 100644
--- a/toolsrc/include/vcpkg_Graphs.h
+++ b/toolsrc/include/vcpkg_Graphs.h
@@ -17,39 +17,55 @@ namespace vcpkg::Graphs
         FULLY_EXPLORED
     };
 
-    template <class V>
-    class Graph
+    template <class V, class Func>
+    static void topological_sort_internal(V vertex,
+                                          ExplorationStatus& status,
+                                          const Func adjacency_list_provider,
+                                          std::unordered_map<V, ExplorationStatus>& exploration_status,
+                                          std::vector<V>& sorted)
     {
-        template <class Func>
-        static void topological_sort_internal(V vertex,
-                                                   ExplorationStatus& status,
-                                                   const Func adjacency_list_provider,
-                                                   std::unordered_map<V, ExplorationStatus>& exploration_status,
-                                                   std::vector<V>& sorted)
-        {
-            status = ExplorationStatus::PARTIALLY_EXPLORED;
+        status = ExplorationStatus::PARTIALLY_EXPLORED;
 
-            auto neighbours = adjacency_list_provider(vertex);
+        auto neighbours = adjacency_list_provider(vertex);
 
-            for (V neighbour : neighbours)
+        for (V neighbour : neighbours)
+        {
+            ExplorationStatus& neighbour_status = exploration_status[neighbour];
+            if (neighbour_status == ExplorationStatus::NOT_EXPLORED)
             {
-                ExplorationStatus& neighbour_status = exploration_status[neighbour];
-                if (neighbour_status == ExplorationStatus::NOT_EXPLORED)
-                {
-                    topological_sort_internal(neighbour, neighbour_status, adjacency_list_provider, exploration_status, sorted);
-                }
-                else if (neighbour_status == ExplorationStatus::PARTIALLY_EXPLORED)
-                {
-                    throw std::runtime_error("cycle in graph");
-                }
+                topological_sort_internal(neighbour, neighbour_status, adjacency_list_provider, exploration_status, sorted);
             }
+            else if (neighbour_status == ExplorationStatus::PARTIALLY_EXPLORED)
+            {
+                throw std::runtime_error("cycle in graph");
+            }
+        }
+        status = ExplorationStatus::FULLY_EXPLORED;
+        sorted.push_back(vertex);
+    }
 
-            status = ExplorationStatus::FULLY_EXPLORED;
-            sorted.push_back(vertex);
+    template <class V, class Func>
+    std::vector<V> topological_sort(const std::vector<V>& starting_vertices, const Func adjacency_list_provider)
+    {
+        std::vector<V> sorted;
+        std::unordered_map<V, ExplorationStatus> exploration_status;
+
+        for (auto& vertex : starting_vertices)
+        {
+            ExplorationStatus& status = exploration_status[vertex];
+            if (status == ExplorationStatus::NOT_EXPLORED)
+            {
+                topological_sort_internal(vertex, status, adjacency_list_provider, exploration_status, sorted);
+            }
         }
 
-    public:
+        return sorted;
+    }
 
+    template <class V>
+    class Graph
+    {
+    public:
         void add_vertex(V v)
         {
             this->vertices[v];
@@ -88,11 +104,9 @@ namespace vcpkg::Graphs
                     ExplorationStatus& status = exploration_status[vertex];
                     if (status == ExplorationStatus::NOT_EXPLORED)
                     {
-                        topological_sort_internal(vertex,
-                                                       status,
-                                                       [this](const V& v) { return this->vertices.at(v); },
-                                                       exploration_status,
-                                                       sorted);
+                        topological_sort_internal(vertex, status,
+                                                  [this](const V& v) { return this->vertices.at(v); },
+                                                  exploration_status, sorted);
                     }
                 }
             }
-- 
cgit v1.2.3