← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/index.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2009-08-19 18:04:49 UTC
  • mfrom: (4593.5.43 1.19-known-graph-sorted)
  • Revision ID: pqm@pqm.ubuntu.com-20090819180449-p5dibldf9pcp24n4
(jam) Add VersionedFiles.get_known_graph_ancestry and
        KnownGraph.merge_sort()

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/index.py
333
333
        if combine_backing_indices is not None:
334
334
            self._combine_backing_indices = combine_backing_indices
335
335
 
 
336
    def find_ancestry(self, keys, ref_list_num):
 
337
        """See CombinedGraphIndex.find_ancestry()"""
 
338
        pending = set(keys)
 
339
        parent_map = {}
 
340
        missing_keys = set()
 
341
        while pending:
 
342
            next_pending = set()
 
343
            for _, key, value, ref_lists in self.iter_entries(pending):
 
344
                parent_keys = ref_lists[ref_list_num]
 
345
                parent_map[key] = parent_keys
 
346
                next_pending.update([p for p in parent_keys if p not in
 
347
                                     parent_map])
 
348
                missing_keys.update(pending.difference(parent_map))
 
349
            pending = next_pending
 
350
        return parent_map, missing_keys
 
351
 
336
352
 
337
353
class GraphIndex(object):
338
354
    """An index for data with embedded graphs.