← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tsort.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2009-08-17 21:06:55 UTC
  • mfrom: (4615.1.3 2.0b1-merge-sort)
  • Revision ID: pqm@pqm.ubuntu.com-20090817210655-w8d1xxic3wi6gs61
(jam) Tweak how merge_sort handles right parents when the left parent
        is already processed.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tsort.py
545
545
                    if not left_subtree_pushed_stack[-1]:
546
546
                        # recurse depth first into the primary parent
547
547
                        next_node_name = pending_parents_stack[-1].pop(0)
 
548
                        is_left_subtree = True
 
549
                        left_subtree_pushed_stack[-1] = True
548
550
                    else:
549
551
                        # place any merges in right-to-left order for scheduling
550
552
                        # which gives us left-to-right order after we reverse
554
556
                        # display nicely (you get smaller trees at the top
555
557
                        # of the combined merge).
556
558
                        next_node_name = pending_parents_stack[-1].pop()
 
559
                        is_left_subtree = False
557
560
                    if next_node_name in completed_node_names:
558
561
                        # this parent was completed by a child on the
559
562
                        # call stack. skip it.
570
573
                        # this indicates a cycle.
571
574
                        raise errors.GraphCycleError(node_name_stack)
572
575
                    next_merge_depth = 0
573
 
                    if left_subtree_pushed_stack[-1]:
 
576
                    if is_left_subtree:
574
577
                        # a new child branch from name_stack[-1]
 
578
                        next_merge_depth = 0
 
579
                    else:
575
580
                        next_merge_depth = 1
576
 
                    else:
577
 
                        next_merge_depth = 0
578
 
                        left_subtree_pushed_stack[-1] = True
579
581
                    next_merge_depth = (
580
582
                        node_merge_depth_stack[-1] + next_merge_depth)
581
583
                    push_node(