← 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 15:20:14 UTC
  • mto: (5365.6.7 annotate-revspec)
  • mto: This revision was merged to the branch mainline in revision 5443.
  • Revision ID: aaron@aaronbentley.com-20100815152014-vlnikxr8mhkxwiga
Implement find_lefthand_merger.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/graph.py
896
896
                stop.add(parent_id)
897
897
        return found
898
898
 
 
899
    def find_lefthand_merger(self, merged_key, tip_key):
 
900
        """Find the first lefthand ancestor of tip_key that merged merged_key.
 
901
 
 
902
        We do this by first finding the descendants of merged_key, then
 
903
        walking through the lefthand ancestry of tip_key until we find a key
 
904
        that doesn't descend from merged_key.  Its child is the key that
 
905
        merged merged_key.
 
906
 
 
907
        :return: The first lefthand ancestor of tip_key to merge merged_key.
 
908
            merged_key if it is a lefthand ancestor of tip_key.
 
909
            None if no ancestor of tip_key merged merged_key.
 
910
        """
 
911
        descendants = self.find_descendants(merged_key, tip_key)
 
912
        candidate_iterator = self.iter_lefthand_ancestry(tip_key)
 
913
        last_candidate = None
 
914
        for candidate in candidate_iterator:
 
915
            if candidate not in descendants:
 
916
                return last_candidate
 
917
            last_candidate = candidate
 
918
 
899
919
    def find_unique_lca(self, left_revision, right_revision,
900
920
                        count_steps=False):
901
921
        """Find a unique LCA.