/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/_known_graph_py.py

  • Committer: Aaron Bentley
  • Date: 2009-09-29 04:40:55 UTC
  • mfrom: (4717 +trunk)
  • mto: This revision was merged to the branch mainline in revision 4718.
  • Revision ID: aaron@aaronbentley.com-20090929044055-e9jtpmz6eyut711h
Merged bzr.dev into fix_get_mtime.

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
232
281
                 in tsort.merge_sort(as_parent_map, tip_key,
233
282
                                     mainline_revisions=None,
234
283
                                     generate_revno=True)]
 
284
    
 
285
    def get_parent_keys(self, key):
 
286
        """Get the parents for a key
 
287
        
 
288
        Returns a list containg the parents keys. If the key is a ghost,
 
289
        None is returned. A KeyError will be raised if the key is not in
 
290
        the graph.
 
291
        
 
292
        :param keys: Key to check (eg revision_id)
 
293
        :return: A list of parents
 
294
        """
 
295
        return self._nodes[key].parent_keys
 
296
 
 
297
    def get_child_keys(self, key):
 
298
        """Get the children for a key
 
299
        
 
300
        Returns a list containg the children keys. A KeyError will be raised
 
301
        if the key is not in the graph.
 
302
        
 
303
        :param keys: Key to check (eg revision_id)
 
304
        :return: A list of children
 
305
        """
 
306
        return self._nodes[key].child_keys