← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: Ian Clatworthy
  • Date: 2010-02-19 03:02:07 UTC
  • mto: (4797.23.1 integration-2.1)
  • mto: This revision was merged to the branch mainline in revision 5055.
  • Revision ID: ian.clatworthy@canonical.com-20100219030207-zpbzx021zavx4sqt
What's New in 2.1 - a summary of changes since 2.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
1
 
# Copyright (C) 2007, 2008, 2009 Canonical Ltd
 
1
# Copyright (C) 2007-2010 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
19
19
from bzrlib import (
20
20
    debug,
21
21
    errors,
 
22
    osutils,
22
23
    revision,
23
24
    trace,
24
 
    tsort,
25
25
    )
26
26
from bzrlib.symbol_versioning import deprecated_function, deprecated_in
27
27
 
311
311
        # get there.
312
312
        return known_revnos[cur_tip] + num_steps
313
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
 
314
335
    def find_unique_ancestors(self, unique_revision, common_revisions):
315
336
        """Find the unique ancestors for a revision versus others.
316
337
 
905
926
        An ancestor may sort after a descendant if the relationship is not
906
927
        visible in the supplied list of revisions.
907
928
        """
 
929
        from bzrlib import tsort
908
930
        sorter = tsort.TopoSorter(self.get_parent_map(revisions))
909
931
        return sorter.iter_topo_order()
910
932
 
1657
1679
    return result
1658
1680
 
1659
1681
 
 
1682
class GraphThunkIdsToKeys(object):
 
1683
    """Forwards calls about 'ids' to be about keys internally."""
 
1684
 
 
1685
    def __init__(self, graph):
 
1686
        self._graph = graph
 
1687
 
 
1688
    def heads(self, ids):
 
1689
        """See Graph.heads()"""
 
1690
        as_keys = [(i,) for i in ids]
 
1691
        head_keys = self._graph.heads(as_keys)
 
1692
        return set([h[0] for h in head_keys])
 
1693
 
 
1694
 
1660
1695
_counters = [0,0,0,0,0,0,0]
1661
1696
try:
1662
1697
    from bzrlib._known_graph_pyx import KnownGraph
1663
 
except ImportError:
 
1698
except ImportError, e:
 
1699
    osutils.failed_to_load_extension(e)
1664
1700
    from bzrlib._known_graph_py import KnownGraph