← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_known_graph_py.py

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_known_graph_py.py
97
97
        return [node for node in self._nodes.itervalues()
98
98
                if not node.parent_keys]
99
99
 
 
100
    def _find_tips(self):
 
101
        return [node for node in self._nodes.itervalues()
 
102
                      if not node.child_keys]
 
103
 
100
104
    def _find_gdfo(self):
101
105
        nodes = self._nodes
102
106
        known_parent_gdfos = {}
218
222
        # We started from the parents, so we don't need to do anymore work
219
223
        return topo_order
220
224
 
 
225
    def gc_sort(self):
 
226
        """Return a reverse topological ordering which is 'stable'.
 
227
 
 
228
        There are a few constraints:
 
229
          1) Reverse topological (all children before all parents)
 
230
          2) Grouped by prefix
 
231
          3) 'stable' sorting, so that we get the same result, independent of
 
232
             machine, or extra data.
 
233
        To do this, we use the same basic algorithm as topo_sort, but when we
 
234
        aren't sure what node to access next, we sort them lexicographically.
 
235
        """
 
236
        tips = self._find_tips()
 
237
        # Split the tips based on prefix
 
238
        prefix_tips = {}
 
239
        for node in tips:
 
240
            if node.key.__class__ is str or len(node.key) == 1:
 
241
                prefix = ''
 
242
            else:
 
243
                prefix = node.key[0]
 
244
            prefix_tips.setdefault(prefix, []).append(node)
 
245
 
 
246
        num_seen_children = dict.fromkeys(self._nodes, 0)
 
247
 
 
248
        result = []
 
249
        for prefix in sorted(prefix_tips):
 
250
            pending = sorted(prefix_tips[prefix], key=lambda n:n.key,
 
251
                             reverse=True)
 
252
            while pending:
 
253
                node = pending.pop()
 
254
                if node.parent_keys is None:
 
255
                    # Ghost node, skip it
 
256
                    continue
 
257
                result.append(node.key)
 
258
                for parent_key in sorted(node.parent_keys, reverse=True):
 
259
                    parent_node = self._nodes[parent_key]
 
260
                    seen_children = num_seen_children[parent_key] + 1
 
261
                    if seen_children == len(parent_node.child_keys):
 
262
                        # All children have been processed, enqueue this parent
 
263
                        pending.append(parent_node)
 
264
                        # This has been queued up, stop tracking it
 
265
                        del num_seen_children[parent_key]
 
266
                    else:
 
267
                        num_seen_children[parent_key] = seen_children
 
268
        return result
 
269
 
221
270
    def merge_sort(self, tip_key):
222
271
        """Compute the merge sorted graph output."""
223
272
        from bzrlib import tsort