← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/graph.py

  • Committer: Aaron Bentley
  • Date: 2010-08-15 14:28:35 UTC
  • mto: (5365.6.7 annotate-revspec)
  • mto: This revision was merged to the branch mainline in revision 5443.
  • Revision ID: aaron@aaronbentley.com-20100815142835-iqbryps5woojcesr
Implement find_descendants.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
258
258
        right = searchers[1].seen
259
259
        return (left.difference(right), right.difference(left))
260
260
 
 
261
    def find_descendants(self, old_key, new_key):
 
262
        """Find descendants of old_key that are ancestors of new_key."""
 
263
        child_map = self.get_child_map(self._find_descendant_ancestors(
 
264
            old_key, new_key))
 
265
        graph = Graph(DictParentsProvider(child_map))
 
266
        searcher = graph._make_breadth_first_searcher([old_key])
 
267
        list(searcher)
 
268
        return searcher.seen
 
269
 
 
270
    def _find_descendant_ancestors(self, old_key, new_key):
 
271
        """Find ancestors of new_key that may be descendants of old_key."""
 
272
        stop = self._make_breadth_first_searcher([old_key])
 
273
        descendants = self._make_breadth_first_searcher([new_key])
 
274
        for revisions in descendants:
 
275
            old_stop = stop.seen.intersection(revisions)
 
276
            descendants.stop_searching_any(old_stop)
 
277
            seen_stop = descendants.find_seen_ancestors(stop.step())
 
278
            descendants.stop_searching_any(seen_stop)
 
279
        return descendants.seen.difference(stop.seen)
 
280
 
 
281
    def get_child_map(self, keys):
 
282
        """Get a mapping from parents to children of the specified keys.
 
283
 
 
284
        This is simply the inversion of get_parent_map.  Only supplied keys
 
285
        will be discovered as children.
 
286
        :return: a dict of key:child_list for keys.
 
287
        """
 
288
        parent_map = self._parents_provider.get_parent_map(keys)
 
289
        parent_child = {}
 
290
        for child, parents in sorted(parent_map.items()):
 
291
            for parent in parents:
 
292
                parent_child.setdefault(parent, []).append(child)
 
293
        return parent_child
 
294
 
261
295
    def find_distance_to_null(self, target_revision_id, known_revision_ids):
262
296
        """Find the left-hand distance to the NULL_REVISION.
263
297