← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_tsort.py

  • Committer: Matt Nordhoff
  • Date: 2009-04-04 02:50:01 UTC
  • mfrom: (4253 +trunk)
  • mto: This revision was merged to the branch mainline in revision 4256.
  • Revision ID: mnordhoff@mattnordhoff.com-20090404025001-z1403k0tatmc8l91
Merge bzr.dev, fixing conflicts.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_tsort.py
12
12
#
13
13
# You should have received a copy of the GNU General Public License
14
14
# along with this program; if not, write to the Free Software
15
 
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
16
 
17
17
 
18
18
"""Tests for topological sort."""
50
50
    def test_tsort_cycle(self):
51
51
        """TopoSort traps graph with cycles"""
52
52
        self.assertSortAndIterateRaise(GraphCycleError,
53
 
                                       {0: [1], 
 
53
                                       {0: [1],
54
54
                                        1: [0]}.items())
55
55
 
56
56
    def test_tsort_cycle_2(self):
57
57
        """TopoSort traps graph with longer cycle"""
58
58
        self.assertSortAndIterateRaise(GraphCycleError,
59
 
                                       {0: [1], 
60
 
                                        1: [2], 
 
59
                                       {0: [1],
 
60
                                        1: [2],
61
61
                                        2: [0]}.items())
62
 
                 
 
62
 
63
63
    def test_tsort_1(self):
64
64
        """TopoSort simple nontrivial graph"""
65
 
        self.assertSortAndIterate({0: [3], 
 
65
        self.assertSortAndIterate({0: [3],
66
66
                                   1: [4],
67
67
                                   2: [1, 4],
68
 
                                   3: [], 
 
68
                                   3: [],
69
69
                                   4: [0, 3]}.items(),
70
70
                                  [3, 0, 4, 1, 2])
71
71
 
72
72
    def test_tsort_partial(self):
73
73
        """Topological sort with partial ordering.
74
74
 
75
 
        If the graph does not give an order between two nodes, they are 
 
75
        If the graph does not give an order between two nodes, they are
76
76
        returned in lexicographical order.
77
77
        """
78
78
        self.assertSortAndIterate(([(0, []),
140
140
                                  'id',
141
141
                                  [(0, 'id', 0, (1,), True)],
142
142
                                  True)
143
 
    
 
143
 
144
144
    def test_sequence_numbers_increase_no_merges(self):
145
145
        # emit a few revisions with no merges to check the sequence
146
146
        # numbering works in trivial cases
244
244
        # the merge depth marker should reflect the depth of the revision
245
245
        # in terms of merges out from the mainline
246
246
        # revid, depth, parents:
247
 
        #  A 0   [D, B]   
248
 
        #  B  1  [C, F]   
249
 
        #  C  1  [H] 
 
247
        #  A 0   [D, B]
 
248
        #  B  1  [C, F]
 
249
        #  C  1  [H]
250
250
        #  D 0   [H, E]
251
251
        #  E  1  [G, F]
252
252
        #  F   2 [G]
403
403
    def test_end_of_merge_multiple_revisions_merged_at_once(self):
404
404
        # when multiple branches are merged at once, both of their
405
405
        # branch-endpoints should be listed as end-of-merge.
406
 
        # Also, the order of the multiple merges should be 
 
406
        # Also, the order of the multiple merges should be
407
407
        # left-right shown top to bottom.
408
408
        # * means end of merge
409
 
        # A 0    [H, B, E] 
 
409
        # A 0    [H, B, E]
410
410
        # B  1   [D, C]
411
411
        # C   2  [D]       *
412
412
        # D  1   [H]       *
483
483
        # and thus when truncated to D,B,A it should show
484
484
        # A 0
485
485
        # B 0
486
 
        # C 1 
 
486
        # C 1
487
487
        # because C is brought in by B in this view and D
488
488
        # is the terminating revision id
489
489
        # this should also preserve revision numbers: C should still be 2.1.1
566
566
             ],
567
567
            True
568
568
            )
569
 
        
 
569
 
570
570
    def test_revnos_are_globally_assigned(self):
571
571
        """revnos are assigned according to the revision they derive from."""
572
 
        # in this test we setup a number of branches that all derive from 
573
 
        # the first revision, and then merge them one at a time, which 
 
572
        # in this test we setup a number of branches that all derive from
 
573
        # the first revision, and then merge them one at a time, which
574
574
        # should give the revisions as they merge numbers still deriving from
575
575
        # the revision were based on.
576
576
        # merge 3: J: ['G', 'I']