# 
# patch "ChangeLog"
#  from [dabaf521855697e3621527d7a6663b65e866cda4]
#    to [e76bb61fc2a6d919837fa71ae1693f314b1a2e46]
# 
# patch "revision.cc"
#  from [17fd287fc24d034e44c2134091c8a71d4c6afbdb]
#    to [58a437f9ad3145e4edf8a176319e9c97a15febf7]
# 
--- ChangeLog
+++ ChangeLog
@@ -1,3 +1,7 @@
+2005-05-30  Timothy Brownawell  <address@hidden>
+
+	* revision.cc (toposort): Better algorithm.
+
 2005-05-29  Timothy Brownawell  <address@hidden>
 
 	* contrib/monoprof.sh: Add support for using valgrind for
--- revision.cc
+++ revision.cc
@@ -14,6 +14,7 @@
 #include <string>
 #include <iterator>
 #include <functional>
+#include <list>
 
 #include <boost/lexical_cast.hpp>
 #include <boost/dynamic_bitset.hpp>
@@ -713,30 +714,37 @@
 {
   sorted.clear();
   typedef std::multimap<revision_id, revision_id>::iterator gi;
+  typedef std::map<revision_id, int>::iterator pi;
   std::multimap<revision_id, revision_id> graph;
   app.db.get_revision_ancestry(graph);
   std::set<revision_id> leaves;
   app.db.get_revision_ids(leaves);
-  while (!graph.empty())
+  std::map<revision_id, int> pcount;
+  for (gi i = graph.begin(); i != graph.end(); ++i)
+    pcount.insert(std::make_pair(i->first, 0));
+  for (gi i = graph.begin(); i != graph.end(); ++i)
+    ++(pcount[i->second]);
+  // first find the set of graph roots
+  std::list<revision_id> roots;
+  for (pi i = pcount.begin(); i != pcount.end(); ++i)
+    if(i->second==0)
+      roots.push_back(i->first);
+  while (!roots.empty())
     {
-      // first find the set of current graph roots
-      std::set<revision_id> roots;
-      for (gi i = graph.begin(); i != graph.end(); ++i)
-        roots.insert(i->first);
-      for (gi i = graph.begin(); i != graph.end(); ++i)
-        roots.erase(i->second);
-      // now stick them in our ordering (if wanted), and remove them from the
-      // graph
-      for (std::set<revision_id>::const_iterator i = roots.begin();
-           i != roots.end(); ++i)
-        {
-          L(F("new root: %s\n") % (*i));
-          if (revisions.find(*i) != revisions.end())
-            sorted.push_back(*i);
-          graph.erase(*i);
-          leaves.erase(*i);
-        }
+      // now stick them in our ordering (if wanted) and remove them from the
+      // graph, calculating the new roots as we go
+      L(F("new root: %s\n") % (roots.front()));
+      if (revisions.find(roots.front()) != revisions.end())
+        sorted.push_back(roots.front());
+      for(gi i = graph.lower_bound(roots.front());
+          i != graph.upper_bound(roots.front()); i++)
+        if(--(pcount[i->second]) == 0)
+          roots.push_back(i->second);
+      graph.erase(roots.front());
+      leaves.erase(roots.front());
+      roots.pop_front();
     }
+  I(graph.empty());
   for (std::set<revision_id>::const_iterator i = leaves.begin();
        i != leaves.end(); ++i)
     {