← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tsort.py

  • Committer: John Arbash Meinel
  • Date: 2009-08-17 15:38:52 UTC
  • mfrom: (4615.1.1 2.0b1-merge-sort)
  • mto: This revision was merged to the branch mainline in revision 4629.
  • Revision ID: john@arbash-meinel.com-20090817153852-9127xf3aabmcoegt
Bring in the changes to merge_sort.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tsort.py
580
580
                    if not left_subtree_pushed_stack[-1]:
581
581
                        # recurse depth first into the primary parent
582
582
                        next_node_name = pending_parents_stack[-1].pop(0)
 
583
                        is_left_subtree = True
 
584
                        left_subtree_pushed_stack[-1] = True
583
585
                    else:
584
586
                        # place any merges in right-to-left order for scheduling
585
587
                        # which gives us left-to-right order after we reverse
589
591
                        # display nicely (you get smaller trees at the top
590
592
                        # of the combined merge).
591
593
                        next_node_name = pending_parents_stack[-1].pop()
 
594
                        is_left_subtree = False
592
595
                    if next_node_name in completed_node_names:
593
596
                        # this parent was completed by a child on the
594
597
                        # call stack. skip it.
605
608
                        # this indicates a cycle.
606
609
                        raise errors.GraphCycleError(node_name_stack)
607
610
                    next_merge_depth = 0
608
 
                    if left_subtree_pushed_stack[-1]:
 
611
                    if is_left_subtree:
609
612
                        # a new child branch from name_stack[-1]
 
613
                        next_merge_depth = 0
 
614
                    else:
610
615
                        next_merge_depth = 1
611
 
                    else:
612
 
                        next_merge_depth = 0
613
 
                        left_subtree_pushed_stack[-1] = True
614
616
                    next_merge_depth = (
615
617
                        node_merge_depth_stack[-1] + next_merge_depth)
616
618
                    push_node(