Rev 4645: Implement a basic algorithm for the pure-python KnownGraph code. in http://bazaar.launchpad.net/~jameinel/bzr/2.0b1-stable-groupcompress-order

[John Arbash Meinel]

At http://bazaar.launchpad.net/~jameinel/bzr/2.0b1-stable-groupcompress-order

------------------------------------------------------------
revno: 4645
revision-id: john at arbash-meinel.com-20090824210650-bgltzh9dlb3wdgyu
parent: john at arbash-meinel.com-20090824205421-r2uqik20dfxx8fcp
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 2.0b1-stable-groupcompress-order
timestamp: Mon 2009-08-24 16:06:50 -0500
message:
  Implement a basic algorithm for the pure-python KnownGraph code.
-------------- next part --------------
=== modified file 'bzrlib/_known_graph_py.py'
--- a/bzrlib/_known_graph_py.py	2009-08-24 20:45:24 +0000
+++ b/bzrlib/_known_graph_py.py	2009-08-24 21:06:50 +0000
@@ -97,6 +97,10 @@
         return [node for node in self._nodes.itervalues()
                 if not node.parent_keys]
 
+    def _find_tips(self):
+        return [node for node in self._nodes.itervalues()
+                      if not node.child_keys]
+
     def _find_gdfo(self):
         nodes = self._nodes
         known_parent_gdfos = {}
@@ -229,6 +233,40 @@
         To do this, we use the same basic algorithm as topo_sort, but when we
         aren't sure what node to access next, we sort them lexicographically.
         """
+        tips = self._find_tips()
+        # Split the tips based on prefix
+        prefix_tips = {}
+        for node in tips:
+            if node.key.__class__ is str or len(node.key) == 1:
+                prefix = ''
+            else:
+                prefix = node.key[0]
+            prefix_tips.setdefault(prefix, []).append(node)
+
+        num_seen_children = dict.fromkeys(self._nodes, 0)
+
+        result = []
+        for prefix in sorted(prefix_tips):
+            pending = sorted(prefix_tips[prefix], key=lambda n:n.key,
+                             reverse=True)
+            while pending:
+                node = pending.pop()
+                # TODO: test ghosts
+                # if node.parent_keys is None:
+                #     # Ghost node, skip it
+                #     continue
+                result.append(node.key)
+                for parent_key in sorted(node.parent_keys):
+                    parent_node = self._nodes[parent_key]
+                    seen_children = num_seen_children[parent_key] + 1
+                    if seen_children == len(parent_node.child_keys):
+                        # All children have been processed, enqueue this parent
+                        pending.append(parent_node)
+                        # This has been queued up, stop tracking it
+                        del num_seen_children[parent_key]
+                    else:
+                        num_seen_parents[parent_key] = seen_children
+        return result
 
     def merge_sort(self, tip_key):
         """Compute the merge sorted graph output."""