Rev 4638: Move the topo_sort implementation into KnownGraph, rather than calling back to it. in http://bazaar.launchpad.net/~jameinel/bzr/1.19-known-graph-sorted

[John Arbash Meinel]

At http://bazaar.launchpad.net/~jameinel/bzr/1.19-known-graph-sorted

------------------------------------------------------------
revno: 4638
revision-id: john at arbash-meinel.com-20090817183614-ss5shqo00p002imm
parent: john at arbash-meinel.com-20090817181706-gm0g0k0ag9dnhowp
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.19-known-graph-sorted
timestamp: Mon 2009-08-17 13:36:14 -0500
message:
  Move the topo_sort implementation into KnownGraph, rather than calling back to it.
-------------- next part --------------
=== modified file 'bzrlib/_known_graph_py.py'
--- a/bzrlib/_known_graph_py.py	2009-08-17 16:35:07 +0000
+++ b/bzrlib/_known_graph_py.py	2009-08-17 18:36:14 +0000
@@ -18,6 +18,7 @@
 """
 
 from bzrlib import (
+    errors,
     revision,
     tsort,
     )
@@ -173,10 +174,38 @@
         return heads
 
     def topo_sort(self):
-        as_parent_map = dict((node.key, node.parent_keys)
-                             for node in self._nodes.itervalues()
-                              if node.parent_keys is not None)
-        return tsort.topo_sort(as_parent_map)
+        """Return the nodes in topological order.
+
+        All parents must occur before all children.
+        """
+        for node in self._nodes.itervalues():
+            if node.gdfo is None:
+                raise errors.GraphCycleError(self._nodes)
+        pending = self._find_tails()
+        pending_pop = pending.pop
+        pending_append = pending.append
+
+        topo_order = []
+        topo_order_append = topo_order.append
+
+        num_seen_parents = dict.fromkeys(self._nodes, 0)
+        while pending:
+            node = pending_pop()
+            if node.parent_keys is not None:
+                # We don't include ghost parents
+                topo_order_append(node.key)
+            for child_key in node.child_keys:
+                child_node = self._nodes[child_key]
+                seen_parents = num_seen_parents[child_key] + 1
+                if seen_parents == len(child_node.parent_keys):
+                    # All parents have been processed, enqueue this child
+                    pending_append(child_node)
+                    # This has been queued up, stop tracking it
+                    del num_seen_parents[child_key]
+                else:
+                    num_seen_parents[child_key] = seen_parents
+        # We started from the parents, so we don't need to do anymore work
+        return topo_order
 
     def merge_sort(self, tip_key):
         """Compute the merge sorted graph output."""

=== modified file 'bzrlib/graph.py'
--- a/bzrlib/graph.py	2009-08-04 04:36:34 +0000
+++ b/bzrlib/graph.py	2009-08-17 18:36:14 +0000
@@ -21,7 +21,6 @@
     errors,
     revision,
     trace,
-    tsort,
     )
 from bzrlib.symbol_versioning import deprecated_function, deprecated_in
 
@@ -926,6 +925,7 @@
         An ancestor may sort after a descendant if the relationship is not
         visible in the supplied list of revisions.
         """
+        from bzrlib import tsort
         sorter = tsort.TopoSorter(self.get_parent_map(revisions))
         return sorter.iter_topo_order()
 

=== modified file 'bzrlib/tsort.py'
--- a/bzrlib/tsort.py	2009-08-17 16:35:07 +0000
+++ b/bzrlib/tsort.py	2009-08-17 18:36:14 +0000
@@ -18,8 +18,11 @@
 """Topological sorting routines."""
 
 
-from bzrlib import errors
-import bzrlib.revision as _mod_revision
+from bzrlib import (
+    errors,
+    graph as _mod_graph,
+    revision as _mod_revision,
+    )
 from collections import deque
 
 
@@ -44,50 +47,8 @@
     topo_sort is faster when the whole list is needed, while when iterating
     over a part of the list, TopoSorter.iter_topo_order should be used.
     """
-    # store a dict of the graph.
-    graph = dict(graph)
-    # this is the stack storing on which the sorted nodes are pushed.
-    node_stack = []
-
-    # count the number of children for every node in the graph
-    node_child_count = dict.fromkeys(graph.iterkeys(), 0)
-    for parents in graph.itervalues():
-        for parent in parents:
-            # don't count the parent if it's a ghost
-            if parent in node_child_count:
-                node_child_count[parent] += 1
-    # keep track of nodes without children in a separate list
-    nochild_nodes = deque([node for (node, n) in node_child_count.iteritems()
-                                 if n == 0])
-
-    graph_pop = graph.pop
-    node_stack_append = node_stack.append
-    nochild_nodes_pop = nochild_nodes.pop
-    nochild_nodes_append = nochild_nodes.append
-
-    while nochild_nodes:
-        # pick a node without a child and add it to the stack.
-        node_name = nochild_nodes_pop()
-        node_stack_append(node_name)
-
-        # the parents of the node lose it as a child; if it was the last
-        # child, add the parent to the list of childless nodes.
-        parents = graph_pop(node_name)
-        for parent in parents:
-            if parent in node_child_count:
-                node_child_count[parent] -= 1
-                if node_child_count[parent] == 0:
-                    nochild_nodes_append(parent)
-
-    # if there are still nodes left in the graph,
-    # that means that there is a cycle
-    if graph:
-        raise errors.GraphCycleError(graph)
-
-    # the nodes where pushed on the stack child first, so this list needs to be
-    # reversed before returning it.
-    node_stack.reverse()
-    return node_stack
+    kg = _mod_graph.KnownGraph(graph)
+    return kg.topo_sort()
 
 
 class TopoSorter(object):