← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

merge 2.0 branch rev 4647

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
1
 
# Copyright (C) 2007 Canonical Ltd
 
1
# Copyright (C) 2007, 2008, 2009 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
21
21
    errors,
22
22
    revision,
23
23
    trace,
24
 
    tsort,
25
24
    )
26
25
from bzrlib.symbol_versioning import deprecated_function, deprecated_in
27
26
 
311
310
        # get there.
312
311
        return known_revnos[cur_tip] + num_steps
313
312
 
 
313
    def find_lefthand_distances(self, keys):
 
314
        """Find the distance to null for all the keys in keys.
 
315
 
 
316
        :param keys: keys to lookup.
 
317
        :return: A dict key->distance for all of keys.
 
318
        """
 
319
        # Optimisable by concurrent searching, but a random spread should get
 
320
        # some sort of hit rate.
 
321
        result = {}
 
322
        known_revnos = []
 
323
        ghosts = []
 
324
        for key in keys:
 
325
            try:
 
326
                known_revnos.append(
 
327
                    (key, self.find_distance_to_null(key, known_revnos)))
 
328
            except errors.GhostRevisionsHaveNoRevno:
 
329
                ghosts.append(key)
 
330
        for key in ghosts:
 
331
            known_revnos.append((key, -1))
 
332
        return dict(known_revnos)
 
333
 
314
334
    def find_unique_ancestors(self, unique_revision, common_revisions):
315
335
        """Find the unique ancestors for a revision versus others.
316
336
 
905
925
        An ancestor may sort after a descendant if the relationship is not
906
926
        visible in the supplied list of revisions.
907
927
        """
 
928
        from bzrlib import tsort
908
929
        sorter = tsort.TopoSorter(self.get_parent_map(revisions))
909
930
        return sorter.iter_topo_order()
910
931
 
1655
1676
            removed.add(node)
1656
1677
 
1657
1678
    return result
 
1679
 
 
1680
 
 
1681
_counters = [0,0,0,0,0,0,0]
 
1682
try:
 
1683
    from bzrlib._known_graph_pyx import KnownGraph
 
1684
except ImportError:
 
1685
    from bzrlib._known_graph_py import KnownGraph