← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: Andrew Bennetts
  • Date: 2008-03-17 17:16:11 UTC
  • mfrom: (3290 +trunk)
  • mto: This revision was merged to the branch mainline in revision 3756.
  • Revision ID: andrew.bennetts@canonical.com-20080317171611-o9wdrnf0m7qwo198
Merge from bzr.dev.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
424
424
                raise errors.NoCommonAncestor(left_revision, right_revision)
425
425
            revisions = lca
426
426
 
 
427
    def iter_ancestry(self, revision_ids):
 
428
        """Iterate the ancestry of this revision.
 
429
 
 
430
        :param revision_ids: Nodes to start the search
 
431
        :return: Yield tuples mapping a revision_id to its parents for the
 
432
            ancestry of revision_id.
 
433
            Ghosts will be returned with None as their parents, and nodes
 
434
            with no parents will have NULL_REVISION as their only parent. (As
 
435
            defined by get_parent_map.)
 
436
            There will also be a node for (NULL_REVISION, ())
 
437
        """
 
438
        pending = set(revision_ids)
 
439
        processed = set()
 
440
        while pending:
 
441
            processed.update(pending)
 
442
            next_map = self.get_parent_map(pending)
 
443
            next_pending = set()
 
444
            for item in next_map.iteritems():
 
445
                yield item
 
446
                next_pending.update(p for p in item[1] if p not in processed)
 
447
            ghosts = pending.difference(next_map)
 
448
            for ghost in ghosts:
 
449
                yield (ghost, None)
 
450
            pending = next_pending
 
451
 
427
452
    def iter_topo_order(self, revisions):
428
453
        """Iterate through the input revisions in topological order.
429
454
 
473
498
            return set(heads)
474
499
 
475
500
 
 
501
class FrozenHeadsCache(object):
 
502
    """Cache heads() calls, assuming the caller won't modify them."""
 
503
 
 
504
    def __init__(self, graph):
 
505
        self.graph = graph
 
506
        self._heads = {}
 
507
 
 
508
    def heads(self, keys):
 
509
        """Return the heads of keys.
 
510
 
 
511
        Similar to Graph.heads(). The main difference is that the return value
 
512
        is a frozen set which cannot be mutated.
 
513
 
 
514
        :see also: Graph.heads.
 
515
        :param keys: The keys to calculate heads for.
 
516
        :return: A frozenset containing the heads.
 
517
        """
 
518
        keys = frozenset(keys)
 
519
        try:
 
520
            return self._heads[keys]
 
521
        except KeyError:
 
522
            heads = frozenset(self.graph.heads(keys))
 
523
            self._heads[keys] = heads
 
524
            return heads
 
525
 
 
526
    def cache(self, keys, heads):
 
527
        """Store a known value."""
 
528
        self._heads[frozenset(keys)] = frozenset(heads)
 
529
 
 
530
 
476
531
class _BreadthFirstSearcher(object):
477
532
    """Parallel search breadth-first the ancestry of revisions.
478
533