/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/tsort.py

  • Committer: John Arbash Meinel
  • Date: 2009-08-17 18:36:14 UTC
  • mto: This revision was merged to the branch mainline in revision 4629.
  • Revision ID: john@arbash-meinel.com-20090817183614-ss5shqo00p002imm
Move the topo_sort implementation into KnownGraph, rather than calling back to it.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tsort.py
23
23
    graph as _mod_graph,
24
24
    revision as _mod_revision,
25
25
    )
 
26
from collections import deque
26
27
 
27
28
 
28
29
__all__ = ["topo_sort", "TopoSorter", "merge_sort", "MergeSorter"]
46
47
    topo_sort is faster when the whole list is needed, while when iterating
47
48
    over a part of the list, TopoSorter.iter_topo_order should be used.
48
49
    """
49
 
    kg = _mod_graph.KnownGraph(dict(graph))
 
50
    kg = _mod_graph.KnownGraph(graph)
50
51
    return kg.topo_sort()
51
52
 
52
53
 
409
410
 
410
411
        # seed the search with the tip of the branch
411
412
        if (branch_tip is not None and
412
 
            branch_tip != _mod_revision.NULL_REVISION and
413
 
            branch_tip != (_mod_revision.NULL_REVISION,)):
 
413
            branch_tip != _mod_revision.NULL_REVISION):
414
414
            parents = self._graph.pop(branch_tip)
415
415
            self._push_node(branch_tip, 0, parents)
416
416
 
459
459
            left_subtree_pushed_stack_append(False)
460
460
            pending_parents_stack_append(list(parents))
461
461
            # as we push it, check if it is the first child
462
 
            parent_info = None
463
462
            if parents:
464
463
                # node has parents, assign from the left most parent.
465
 
                try:
466
 
                    parent_info = revnos[parents[0]]
467
 
                except KeyError:
468
 
                    # Left-hand parent is a ghost, consider it not to exist
469
 
                    pass
470
 
            if parent_info is not None:
 
464
                parent_info = revnos[parents[0]]
471
465
                first_child = parent_info[1]
472
466
                parent_info[1] = False
473
467
            else:
501
495
            pending_parents_stack_pop()
502
496
 
503
497
            parents = original_graph[node_name]
504
 
            parent_revno = None
505
498
            if parents:
506
499
                # node has parents, assign from the left most parent.
507
 
                try:
508
 
                    parent_revno = revnos[parents[0]][0]
509
 
                except KeyError:
510
 
                    # left-hand parent is a ghost, treat it as not existing
511
 
                    pass
512
 
            if parent_revno is not None:
 
500
                parent_revno = revnos[parents[0]][0]
513
501
                if not first_child:
514
502
                    # not the first child, make a new branch
515
503
                    base_revno = parent_revno[0]
640
628
        self._left_subtree_pushed_stack.append(False)
641
629
        self._pending_parents_stack.append(list(parents))
642
630
        # as we push it, figure out if this is the first child
643
 
        parent_info = None
 
631
        parents = self._original_graph[node_name]
644
632
        if parents:
645
633
            # node has parents, assign from the left most parent.
646
 
            try:
647
 
                parent_info = self._revnos[parents[0]]
648
 
            except KeyError:
649
 
                # Left-hand parent is a ghost, consider it not to exist
650
 
                pass
651
 
        if parent_info is not None:
 
634
            parent_info = self._revnos[parents[0]]
652
635
            first_child = parent_info[1]
653
636
            parent_info[1] = False
654
637
        else:
672
655
        self._pending_parents_stack.pop()
673
656
 
674
657
        parents = self._original_graph[node_name]
675
 
        parent_revno = None
676
658
        if parents:
677
659
            # node has parents, assign from the left most parent.
678
 
            try:
679
 
                parent_revno = self._revnos[parents[0]][0]
680
 
            except KeyError:
681
 
                # left-hand parent is a ghost, treat it as not existing
682
 
                pass
683
 
        if parent_revno is not None:
 
660
            parent_revno = self._revnos[parents[0]][0]
684
661
            if not first_child:
685
662
                # not the first child, make a new branch
686
663
                base_revno = parent_revno[0]