← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: Alexander Belchenko
  • Date: 2008-02-06 15:33:12 UTC
  • mto: This revision was merged to the branch mainline in revision 3231.
  • Revision ID: bialix@ukr.net-20080206153312-qycs7u05d7fjtwqq
Ian's review

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
 
 
452
427
    def iter_topo_order(self, revisions):
453
428
        """Iterate through the input revisions in topological order.
454
429
 
498
473
            return set(heads)
499
474
 
500
475
 
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
 
 
531
476
class _BreadthFirstSearcher(object):
532
477
    """Parallel search breadth-first the ancestry of revisions.
533
478
 
569
514
            # exclude keys for them. However, while we could have a second
570
515
            # look-ahead result buffer and shuffle things around, this method
571
516
            # is typically only called once per search - when memoising the
572
 
            # results of the search. 
 
517
            # results of the search.
573
518
            found, ghosts, next, parents = self._do_query(self._next_query)
574
519
            # pretend we didn't query: perhaps we should tweak _do_query to be
575
520
            # entirely stateless?