← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: Martin Pool
  • Date: 2009-09-14 01:48:28 UTC
  • mfrom: (4685 +trunk)
  • mto: This revision was merged to the branch mainline in revision 4688.
  • Revision ID: mbp@sourcefrog.net-20090914014828-ydr9rlkdfq2sv57z
Merge news

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
22
22
    osutils,
23
23
    revision,
24
24
    trace,
25
 
    tsort,
26
25
    )
27
26
from bzrlib.symbol_versioning import deprecated_function, deprecated_in
28
27
 
312
311
        # get there.
313
312
        return known_revnos[cur_tip] + num_steps
314
313
 
 
314
    def find_lefthand_distances(self, keys):
 
315
        """Find the distance to null for all the keys in keys.
 
316
 
 
317
        :param keys: keys to lookup.
 
318
        :return: A dict key->distance for all of keys.
 
319
        """
 
320
        # Optimisable by concurrent searching, but a random spread should get
 
321
        # some sort of hit rate.
 
322
        result = {}
 
323
        known_revnos = []
 
324
        ghosts = []
 
325
        for key in keys:
 
326
            try:
 
327
                known_revnos.append(
 
328
                    (key, self.find_distance_to_null(key, known_revnos)))
 
329
            except errors.GhostRevisionsHaveNoRevno:
 
330
                ghosts.append(key)
 
331
        for key in ghosts:
 
332
            known_revnos.append((key, -1))
 
333
        return dict(known_revnos)
 
334
 
315
335
    def find_unique_ancestors(self, unique_revision, common_revisions):
316
336
        """Find the unique ancestors for a revision versus others.
317
337
 
906
926
        An ancestor may sort after a descendant if the relationship is not
907
927
        visible in the supplied list of revisions.
908
928
        """
 
929
        from bzrlib import tsort
909
930
        sorter = tsort.TopoSorter(self.get_parent_map(revisions))
910
931
        return sorter.iter_topo_order()
911
932