Rev 4629: Bring in the changes to merge_sort. in http://bazaar.launchpad.net/~jameinel/bzr/1.19-known-graph-sorted

[John Arbash Meinel]

At http://bazaar.launchpad.net/~jameinel/bzr/1.19-known-graph-sorted

------------------------------------------------------------
revno: 4629 [merge]
revision-id: john at arbash-meinel.com-20090817153852-9127xf3aabmcoegt
parent: john at arbash-meinel.com-20090816172208-2mh7z0uapy6y0gsv
parent: john at arbash-meinel.com-20090817152618-3547nakodq02savp
committer: John Arbash Meinel <john at arbash-meinel.com>
branch nick: 1.19-known-graph-sorted
timestamp: Mon 2009-08-17 10:38:52 -0500
message:
  Bring in the changes to merge_sort.
modified:
  bzrlib/tests/test_tsort.py     testtsort.py-20051025073946-27da871c394d5be4
  bzrlib/tsort.py                tsort.py-20051025073946-7808f6aaf7d07208
-------------- next part --------------
=== modified file 'bzrlib/tests/test_tsort.py'
--- a/bzrlib/tests/test_tsort.py	2009-08-13 21:52:56 +0000
+++ b/bzrlib/tests/test_tsort.py	2009-08-17 15:38:52 +0000
@@ -233,7 +233,7 @@
         self.assertSortAndIterate(graph, 'F',
             [(0, 'F', 0, (3,), False),
              (1, 'D', 1, (2,2,1), False),
-             (2, 'C', 1, (2,1,1), True), # XXX: Shouldn't it be merge_depth=2?
+             (2, 'C', 2, (2,1,1), True),
              (3, 'B', 0, (2,), False),
              (4, 'A', 0, (1,), True),
              ], True)

=== modified file 'bzrlib/tsort.py'
--- a/bzrlib/tsort.py	2009-08-14 21:33:09 +0000
+++ b/bzrlib/tsort.py	2009-08-17 15:38:52 +0000
@@ -580,6 +580,8 @@
                     if not left_subtree_pushed_stack[-1]:
                         # recurse depth first into the primary parent
                         next_node_name = pending_parents_stack[-1].pop(0)
+                        is_left_subtree = True
+                        left_subtree_pushed_stack[-1] = True
                     else:
                         # place any merges in right-to-left order for scheduling
                         # which gives us left-to-right order after we reverse
@@ -589,6 +591,7 @@
                         # display nicely (you get smaller trees at the top
                         # of the combined merge).
                         next_node_name = pending_parents_stack[-1].pop()
+                        is_left_subtree = False
                     if next_node_name in completed_node_names:
                         # this parent was completed by a child on the
                         # call stack. skip it.
@@ -605,12 +608,11 @@
                         # this indicates a cycle.
                         raise errors.GraphCycleError(node_name_stack)
                     next_merge_depth = 0
-                    if left_subtree_pushed_stack[-1]:
+                    if is_left_subtree:
                         # a new child branch from name_stack[-1]
+                        next_merge_depth = 0
+                    else:
                         next_merge_depth = 1
-                    else:
-                        next_merge_depth = 0
-                        left_subtree_pushed_stack[-1] = True
                     next_merge_depth = (
                         node_merge_depth_stack[-1] + next_merge_depth)
                     push_node(