Rev 62: Change to using a _MergeSortNode so that it matches KG.merge_sort. in http://bzr.arbash-meinel.com/plugins/history_db

John Arbash Meinel john at arbash-meinel.com
Wed Apr 7 22:06:51 BST 2010


At http://bzr.arbash-meinel.com/plugins/history_db

------------------------------------------------------------
revno: 62
revision-id: john at arbash-meinel.com-20100407210635-syhdace9q90ib8p4
parent: john at arbash-meinel.com-20100407204932-c16n3focq5d8bpvr
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: history_db
timestamp: Wed 2010-04-07 16:06:35 -0500
message:
  Change to using a _MergeSortNode so that it matches KG.merge_sort.
-------------- next part --------------
=== modified file 'history_db.py'
--- a/history_db.py	2010-04-07 20:49:32 +0000
+++ b/history_db.py	2010-04-07 21:06:35 +0000
@@ -423,6 +423,26 @@
             self._db_conn.commit()
 
 
+class _MergeSortNode(object):
+    """A simple object that represents one entry in the merge sorted graph."""
+
+    __slots__ = ('key', 'merge_depth', 'revno', 'end_of_merge',
+                 '_left_parent', '_left_pending_parent',
+                 '_pending_parents', '_is_first',
+                 )
+
+    def __init__(self, key, merge_depth, left_parent, pending_parents,
+                 is_first):
+        self.key = key
+        self.merge_depth = merge_depth
+        self.revno = None
+        self.end_of_merge = None
+        self._left_parent = left_parent
+        self._left_pending_parent = left_parent
+        self._pending_parents = pending_parents
+        self._is_first = is_first
+
+
 class _IncrementalMergeSort(object):
     """Context for importing partial history."""
     # Note: all of the ids in this object are database ids. the revision_ids
@@ -804,20 +824,19 @@
                                     if p not in self._ghosts])
         # v- logically probably better as a tuple or object. We currently
         # modify it in place, so we use a list
-        self._depth_first_stack.append([db_id, merge_depth, left_parent,
-                                        left_parent, pending_parents,
-                                        is_first])
+        self._depth_first_stack.append(
+            _MergeSortNode(db_id, merge_depth, left_parent, pending_parents,
+                           is_first))
 
     def _pop_node(self):
         """Move the last node from the _depth_first_stack to _scheduled_stack.
 
         This is the most left-hand node that we are able to find.
         """
-        (db_id, merge_depth, left_parent_id, _, _,
-         is_first) = self._depth_first_stack.pop()
-        if left_parent_id is not None:
-            parent_revno = self._imported_dotted_revno[left_parent_id][0]
-            if is_first: # We simply number as parent + 1
+        node = self._depth_first_stack.pop()
+        if node._left_parent is not None:
+            parent_revno = self._imported_dotted_revno[node._left_parent][0]
+            if node._is_first: # We simply number as parent + 1
                 if len(parent_revno) == 1:
                     mini_revno = parent_revno[0] + 1
                     revno = (mini_revno,)
@@ -880,20 +899,24 @@
             # when we start new numbering, end_of_merge is True. For mainline
             # revisions, this is only true when we don't have a parent.
             end_of_merge = True
-            if left_parent_id is not None and merge_depth == 0:
+            if node._left_parent is not None and node.merge_depth == 0:
                 end_of_merge = False
         else:
-            prev_db_id, prev_revno, _, prev_depth = self._scheduled_stack[-1]
-            if prev_depth < merge_depth:
+            prev_node = self._scheduled_stack[-1]
+            if prev_node.merge_depth < node.merge_depth:
                 end_of_merge = True
-            elif (prev_depth == merge_depth
-                  and prev_db_id not in self._parent_map[db_id]):
+            elif (prev_node.merge_depth == node.merge_depth
+                  and prev_node.key not in self._parent_map[node.key]):
                 # Next node is not a direct parent
                 end_of_merge = True
             else:
                 end_of_merge = False
-        self._imported_dotted_revno[db_id] = (revno, end_of_merge, merge_depth)
-        self._scheduled_stack.append((db_id, revno, end_of_merge, merge_depth))
+        node.revno = revno
+        node.end_of_merge = end_of_merge
+        self._imported_dotted_revno[node.key] = (revno, end_of_merge,
+                                                 node.merge_depth)
+        node._pending_parents = None
+        self._scheduled_stack.append(node)
 
     def _compute_merge_sort(self):
         self._depth_first_stack = []
@@ -903,25 +926,26 @@
 
         while self._depth_first_stack:
             last = self._depth_first_stack[-1]
-            if last[3] is None and not last[4]:
+            if last._left_pending_parent is None and not last._pending_parents:
                 # The parents have been processed, pop the node
                 self._pop_node()
                 continue
-            while last[3] is not None or last[4]:
-                if last[3] is not None:
+            while (last._left_pending_parent is not None
+                   or last._pending_parents):
+                if last._left_pending_parent is not None:
                     # Push on the left-hand-parent
-                    next_db_id = last[3]
-                    last[3] = None
+                    next_db_id = last._left_pending_parent
+                    last._left_pending_parent = None
                 else:
-                    pending_parents = last[4]
+                    pending_parents = last._pending_parents
                     next_db_id = pending_parents[-1]
-                    last[4] = pending_parents[:-1]
+                    last._pending_parents = pending_parents[:-1]
                 if next_db_id in self._imported_dotted_revno:
                     continue
-                if next_db_id == last[2]: #Is the left-parent?
-                    next_merge_depth = last[1]
+                if next_db_id == last._left_parent: #Is the left-parent?
+                    next_merge_depth = last.merge_depth
                 else:
-                    next_merge_depth = last[1] + 1
+                    next_merge_depth = last.merge_depth + 1
                 self._push_node(next_db_id, next_merge_depth)
                 # And switch to the outer loop
                 break

=== modified file 'test_importer.py'
--- a/test_importer.py	2010-04-07 20:49:32 +0000
+++ b/test_importer.py	2010-04-07 21:06:35 +0000
@@ -271,6 +271,12 @@
 
 class Test_IncrementalMergeSort(TestCaseWithGraphs):
 
+    def assertScheduledStack(self, inc_importer, expected):
+        """Check that the merge_sort result is as expected."""
+        actual = [(node.key, node.revno, node.end_of_merge, node.merge_depth)
+                  for node in inc_importer._scheduled_stack]
+        self.assertEqual(expected, actual)
+
     def test_step_by_step(self):
         b = self.make_interesting_branch()
         b._tip_revision = 'G' # Something older
@@ -354,11 +360,12 @@
         self.assertEqual({0: 3, (1, 1): 2, (1, 2): 2},
                          inc_importer._branch_to_child_count)
         inc_importer._compute_merge_sort()
-        self.assertEqual([(self.H_id, (1, 3, 1), True, 1),
+        self.assertScheduledStack(inc_importer,
+                         [(self.H_id, (1, 3, 1), True, 1),
                           (self.I_id, (4,), False, 0),
                           (self.J_id, (1, 2, 3), True, 1),
                           (self.N_id, (5,), False, 0),
-                         ], inc_importer._scheduled_stack)
+                         ])
 
     def test__find_interesting_ancestry(self):
         b = self.make_interesting_branch()
@@ -450,11 +457,12 @@
         inc_importer = history_db._IncrementalMergeSort(importer, self.O_id)
         inc_importer._find_interesting_ancestry()
         inc_importer._compute_merge_sort()
-        self.assertEqual([(self.K_id, (1, 2, 4), True, 1),
+        self.assertScheduledStack(inc_importer,
+                         [(self.K_id, (1, 2, 4), True, 1),
                           (self.L_id, (1, 4, 1), True, 2),
                           (self.M_id, (1, 2, 5), False, 1),
                           (self.O_id, (6,), False, 0),
-                         ], inc_importer._scheduled_stack)
+                         ])
         # We have to load G to get E, but we shouldn't have to load D_id, so
         # that should be where we stop.
         self.assertEqual(self.D_id, inc_importer._imported_mainline_id)
@@ -469,8 +477,7 @@
         inc_importer = history_db._IncrementalMergeSort(importer, self.B_id)
         inc_importer._find_interesting_ancestry()
         inc_importer._compute_merge_sort()
-        self.assertEqual([(self.B_id, (2,), False, 0),
-                         ], inc_importer._scheduled_stack)
+        self.assertScheduledStack(inc_importer, [(self.B_id, (2,), False, 0)])
 
     def test_handles_multi_roots(self):
         # Graph:
@@ -497,9 +504,10 @@
         self.assertEqual(set([self.E_id, self.F_id]),
                          inc_importer._interesting_ancestor_ids)
         inc_importer._compute_merge_sort()
-        self.assertEqual([(self.E_id, (0, 2, 1), True, 1),
+        self.assertScheduledStack(inc_importer,
+                         [(self.E_id, (0, 2, 1), True, 1),
                           (self.F_id, (4,), False, 0),
-                         ], inc_importer._scheduled_stack)
+                         ])
 
     def test_handles_partial_complex_multi_roots(self):
         # Graph:
@@ -535,9 +543,10 @@
         self.assertEqual(set([self.K_id, self.J_id]),
                          inc_importer._interesting_ancestor_ids)
         inc_importer._compute_merge_sort()
-        self.assertEqual([(self.J_id, (0, 3, 1), True, 1),
+        self.assertScheduledStack(inc_importer,
+                         [(self.J_id, (0, 3, 1), True, 1),
                           (self.K_id, (6,), False, 0),
-                         ], inc_importer._scheduled_stack)
+                         ])
         # We only have to walk back and stop at D because we have found (0,2,1)
         # which must be the latest branch.
         self.assertEqual(self.D_id, inc_importer._imported_mainline_id)
@@ -553,8 +562,9 @@
         inc_importer = history_db._IncrementalMergeSort(importer, self.A_id)
         inc_importer._find_interesting_ancestry()
         inc_importer._compute_merge_sort()
-        self.assertEqual([(self.A_id, (1,), True, 0),
-                         ], inc_importer._scheduled_stack)
+        self.assertScheduledStack(inc_importer,
+                         [(self.A_id, (1,), True, 0),
+                         ])
 
     def test_skips_ghosts(self):
         b = self.make_branch_with_ghosts()
@@ -566,9 +576,10 @@
         inc_importer._compute_merge_sort()
         # G is not mentioned in merge_sorted, neither as a left-hand parent,
         # nor as a right-hand parent
-        self.assertEqual([(self.A_id, (1,), True, 0),
+        self.assertScheduledStack(inc_importer,
+                         [(self.A_id, (1,), True, 0),
                           (self.B_id, (2,), False, 0),
                           (self.C_id, (3,), False, 0),
                           (self.D_id, (0, 1, 1), True, 1),
                           (self.E_id, (4,), False, 0),
-                         ], inc_importer._scheduled_stack)
+                         ])



More information about the bazaar-commits mailing list