/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/graph.py

  • Committer: Lukáš Lalinský
  • Date: 2007-12-17 17:28:25 UTC
  • mfrom: (3120 +trunk)
  • mto: This revision was merged to the branch mainline in revision 3123.
  • Revision ID: lalinsky@gmail.com-20071217172825-tr3pqm1mhvs3gwnn
Merge bzr.dev.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
16
16
 
17
17
from bzrlib import (
18
18
    errors,
 
19
    revision,
19
20
    tsort,
20
21
    )
21
22
from bzrlib.deprecated_graph import (node_distances, select_farthest)
22
 
from bzrlib.revision import NULL_REVISION
23
23
 
24
24
# DIAGRAM of terminology
25
25
#       A
44
44
# 2. Since len(['D', 'E']) > 1, find_lca('D', 'E') => ['A']
45
45
 
46
46
 
 
47
class DictParentsProvider(object):
 
48
 
 
49
    def __init__(self, ancestry):
 
50
        self.ancestry = ancestry
 
51
 
 
52
    def __repr__(self):
 
53
        return 'DictParentsProvider(%r)' % self.ancestry
 
54
 
 
55
    def get_parents(self, revisions):
 
56
        return [self.ancestry.get(r, None) for r in revisions]
 
57
 
47
58
 
48
59
class _StackedParentsProvider(object):
49
60
 
231
242
            order if they need it.
232
243
        """
233
244
        candidate_heads = set(keys)
 
245
        if revision.NULL_REVISION in candidate_heads:
 
246
            # NULL_REVISION is only a head if it is the only entry
 
247
            candidate_heads.remove(revision.NULL_REVISION)
 
248
            if not candidate_heads:
 
249
                return set([revision.NULL_REVISION])
234
250
        if len(candidate_heads) < 2:
235
251
            return candidate_heads
236
252
        searchers = dict((c, self._make_breadth_first_searcher([c]))
299
315
            common_walker.start_searching(new_common)
300
316
        return candidate_heads
301
317
 
302
 
    def find_unique_lca(self, left_revision, right_revision):
 
318
    def find_unique_lca(self, left_revision, right_revision,
 
319
                        count_steps=False):
303
320
        """Find a unique LCA.
304
321
 
305
322
        Find lowest common ancestors.  If there is no unique  common
310
327
 
311
328
        Note that None is not an acceptable substitute for NULL_REVISION.
312
329
        in the input for this method.
 
330
 
 
331
        :param count_steps: If True, the return value will be a tuple of
 
332
            (unique_lca, steps) where steps is the number of times that
 
333
            find_lca was run.  If False, only unique_lca is returned.
313
334
        """
314
335
        revisions = [left_revision, right_revision]
 
336
        steps = 0
315
337
        while True:
 
338
            steps += 1
316
339
            lca = self.find_lca(*revisions)
317
340
            if len(lca) == 1:
318
 
                return lca.pop()
 
341
                result = lca.pop()
 
342
                if count_steps:
 
343
                    return result, steps
 
344
                else:
 
345
                    return result
319
346
            if len(lca) == 0:
320
347
                raise errors.NoCommonAncestor(left_revision, right_revision)
321
348
            revisions = lca
334
361
        """Determine whether a revision is an ancestor of another.
335
362
 
336
363
        We answer this using heads() as heads() has the logic to perform the
337
 
        smallest number of parent looksup to determine the ancestral
 
364
        smallest number of parent lookups to determine the ancestral
338
365
        relationship between N revisions.
339
366
        """
340
367
        return set([candidate_descendant]) == self.heads(