Rev 3398: Simple brute-force implementation of find_unique_ancestors in http://bzr.arbash-meinel.com/branches/bzr/1.4-dev/find_unique_ancestors

[John Arbash Meinel]

At http://bzr.arbash-meinel.com/branches/bzr/1.4-dev/find_unique_ancestors

------------------------------------------------------------
revno: 3398
revision-id: john at arbash-meinel.com-20080424165813-nzlmhwbj05c8ao1c
parent: john at arbash-meinel.com-20080423230918-3dwdjgum1qm2nntb
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: find_unique_ancestors
timestamp: Thu 2008-04-24 11:58:13 -0500
message:
  Simple brute-force implementation of find_unique_ancestors
modified:
  bzrlib/graph.py                graph_walker.py-20070525030359-y852guab65d4wtn0-1
  bzrlib/tests/test_graph.py     test_graph_walker.py-20070525030405-enq4r60hhi9xrujc-1
-------------- next part --------------
=== modified file 'bzrlib/graph.py'
--- a/bzrlib/graph.py	2008-04-23 23:09:18 +0000
+++ b/bzrlib/graph.py	2008-04-24 16:58:13 +0000
@@ -207,6 +207,27 @@
         right = searchers[1].seen
         return (left.difference(right), right.difference(left))
 
+    def find_unique_ancestors(self, unique_revision, common_revisions):
+        """Find the unique ancestors for a revision versus others.
+
+        This returns the ancestry of unique_revision, excluding all revisions
+        in the ancestry of common_revisions. If unique_revision is in the
+        ancestry, then the empty set will be returned.
+
+        :param unique_revision: The revision_id whose ancestry we are
+            interested in.
+        :param common_revisions: Revision_ids of ancestries to exclude.
+        :return: A set of revisions in the ancestry of unique_revision
+        """
+        common_revisions = set(common_revisions)
+        # Simple brute force implementation. Ugly, but gets the tests working
+        # first.
+        if unique_revision in common_revisions:
+            return set()
+        unique_ancestors = set(x[0] for x in self.iter_ancestry([unique_revision]))
+        common_ancestors = set(x[0] for x in self.iter_ancestry(common_revisions))
+        return unique_ancestors - common_ancestors
+
     @symbol_versioning.deprecated_method(symbol_versioning.one_one)
     def get_parents(self, revisions):
         """Find revision ids of the parents of a list of revisions

=== modified file 'bzrlib/tests/test_graph.py'
--- a/bzrlib/tests/test_graph.py	2008-04-23 20:33:41 +0000
+++ b/bzrlib/tests/test_graph.py	2008-04-24 16:58:13 +0000
@@ -1055,6 +1055,40 @@
         self.assertEqual(set(['head', NULL_REVISION]), result.get_keys())
 
 
+class TestFindUniqueAncestors(tests.TestCase):
+
+    def make_graph(self, ancestors):
+        return _mod_graph.Graph(_mod_graph.DictParentsProvider(ancestors))
+
+    def assertFindUniqueAncestors(self, graph, expected, node, common):
+        actual = graph.find_unique_ancestors(node, common)
+        self.assertEqual(expected, sorted(actual))
+
+    def test_empty_set(self):
+        graph = self.make_graph(ancestry_1)
+        self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev1'])
+        self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev2b'])
+        self.assertFindUniqueAncestors(graph, [], 'rev3', ['rev1', 'rev3'])
+
+    def test_single_node(self):
+        graph = self.make_graph(ancestry_1)
+        self.assertFindUniqueAncestors(graph, ['rev2a'], 'rev2a', ['rev1'])
+        self.assertFindUniqueAncestors(graph, ['rev2b'], 'rev2b', ['rev1'])
+        self.assertFindUniqueAncestors(graph, ['rev3'], 'rev3', ['rev2a'])
+
+    def test_in_ancestry(self):
+        graph = self.make_graph(ancestry_1)
+        self.assertFindUniqueAncestors(graph, [], 'rev1', ['rev3'])
+        self.assertFindUniqueAncestors(graph, [], 'rev2b', ['rev4'])
+
+    def test_multiple_revisions(self):
+        graph = self.make_graph(ancestry_1)
+        self.assertFindUniqueAncestors(graph,
+            ['rev4'], 'rev4', ['rev3', 'rev2b'])
+        self.assertFindUniqueAncestors(graph,
+            ['rev2a', 'rev3', 'rev4'], 'rev4', ['rev2b'])
+
+
 class TestCachingParentsProvider(tests.TestCase):
 
     def setUp(self):