← 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: Robert Collins
  • Date: 2006-03-28 11:16:28 UTC
  • mto: (1626.2.1 integration)
  • mto: This revision was merged to the branch mainline in revision 1628.
  • Revision ID: robertc@robertcollins.net-20060328111628-47766b0fdfa443ab
Add MergeSort facility to bzrlib.tsort.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_tsort.py
19
19
 
20
20
 
21
21
from bzrlib.tests import TestCase
22
 
from bzrlib.tsort import topo_sort, TopoSorter
 
22
from bzrlib.tsort import topo_sort, TopoSorter, MergeSorter, merge_sort
23
23
from bzrlib.errors import GraphCycleError
24
24
 
25
25
 
84
84
                                   (7, [2, 3]),
85
85
                                   (8, [0, 1, 4, 5, 6])]),
86
86
                                  [0, 1, 2, 3, 4, 5, 6, 7, 8])
 
87
 
 
88
 
 
89
class MergeSortTests(TestCase):
 
90
 
 
91
    def assertSortAndIterate(self, graph, branch_tip, result_list):
 
92
        """Check that merge based sorting and iter_topo_order on graph works."""
 
93
        self.assertEquals(result_list, merge_sort(graph, branch_tip))
 
94
        self.assertEqual(result_list,
 
95
                         list(MergeSorter(graph, branch_tip).iter_topo_order()))
 
96
 
 
97
    def test_merge_sort_empty(self):
 
98
        # sorting of an emptygraph does not error
 
99
        self.assertSortAndIterate({}, None, [])
 
100
 
 
101
    def test_merge_sort_not_empty_no_tip(self):
 
102
        # merge sorting of a branch starting with None should result
 
103
        # in an empty list: no revisions are dragged in.
 
104
        self.assertSortAndIterate({0: []}.items(), None, [])
 
105
 
 
106
    def test_merge_sort_one_revision(self):
 
107
        # sorting with one revision as the tip returns the correct fields:
 
108
        # sequence - 0, revision id, merge depth - 0, end_of_merge
 
109
        self.assertSortAndIterate({'id': []}.items(),
 
110
                                  'id',
 
111
                                  [(0, 'id', 0, True)])
 
112
    
 
113
    def test_sequence_numbers_increase_no_merges(self):
 
114
        # emit a few revisions with no merges to check the sequence
 
115
        # numbering works in trivial cases
 
116
        self.assertSortAndIterate(
 
117
            {'A': [],
 
118
             'B': ['A'],
 
119
             'C': ['B']}.items(),
 
120
            'C',
 
121
            [(0, 'C', 0, False),
 
122
             (1, 'B', 0, False),
 
123
             (2, 'A', 0, True),
 
124
             ]
 
125
            )
 
126
 
 
127
    def test_sequence_numbers_increase_with_merges(self):
 
128
        # test that sequence numbers increase across merges
 
129
        self.assertSortAndIterate(
 
130
            {'A': [],
 
131
             'B': ['A'],
 
132
             'C': ['A', 'B']}.items(),
 
133
            'C',
 
134
            [(0, 'C', 0, False),
 
135
             (1, 'B', 1, True),
 
136
             (2, 'A', 0, True),
 
137
             ]
 
138
            )
 
139
        
 
140
    def test_merge_depth_with_nested_merges(self):
 
141
        # the merge depth marker should reflect the depth of the revision
 
142
        # in terms of merges out from the mainline
 
143
        # revid, depth, parents:
 
144
        #  A 0   [D, B]   
 
145
        #  B  1  [C, F]   
 
146
        #  C  1  [H] 
 
147
        #  D 0   [H, E]
 
148
        #  E  1  [G, F]
 
149
        #  F   2 [G]
 
150
        #  G  1  [H]
 
151
        #  H 0
 
152
        self.assertSortAndIterate(
 
153
            {'A': ['D', 'B'],
 
154
             'B': ['C', 'F'],
 
155
             'C': ['H'],
 
156
             'D': ['H', 'E'],
 
157
             'E': ['G', 'F'],
 
158
             'F': ['G'],
 
159
             'G': ['H'],
 
160
             'H': []
 
161
             }.items(),
 
162
            'A',
 
163
            [(0, 'A', 0, False),
 
164
             (1, 'B', 1, False),
 
165
             (2, 'C', 1, True),
 
166
             (3, 'D', 0, False),
 
167
             (4, 'E', 1, False),
 
168
             (5, 'F', 2, True),
 
169
             (6, 'G', 1, True),
 
170
             (7, 'H', 0, True),
 
171
             ]
 
172
            )
 
173
 
 
174
    def test_end_of_merge_not_last_revision_in_branch(self):
 
175
        # within a branch only the last revision gets an
 
176
        # end of merge marker.
 
177
        self.assertSortAndIterate(
 
178
            {'A': ['B'],
 
179
             'B': [],
 
180
             },
 
181
            'A',
 
182
            [(0, 'A', 0, False),
 
183
             (1, 'B', 0, True)
 
184
             ]
 
185
            )
 
186
 
 
187
    def test_end_of_merge_multiple_revisions_merged_at_once(self):
 
188
        # when multiple branches are merged at once, both of their
 
189
        # branch-endpoints should be listed as end-of-merge.
 
190
        # Also, the order of the multiple merges should be 
 
191
        # left-right shown top to bottom.
 
192
        # * means end of merge
 
193
        # A 0    [H, B, E] 
 
194
        # B  1   [D, C]
 
195
        # C   2  [D]       *
 
196
        # D  1   [H]       *
 
197
        # E  1   [G, F]
 
198
        # F   2  [G]       *
 
199
        # G  1   [H]       *
 
200
        # H 0    []        *
 
201
        self.assertSortAndIterate(
 
202
            {'A': ['H', 'B', 'E'],
 
203
             'B': ['D', 'C'],
 
204
             'C': ['D'],
 
205
             'D': ['H'],
 
206
             'E': ['G', 'F'],
 
207
             'F': ['G'],
 
208
             'G': ['H'],
 
209
             'H': [],
 
210
             },
 
211
            'A',
 
212
            [(0, 'A', 0, False),
 
213
             (1, 'B', 1, False),
 
214
             (2, 'C', 2, True),
 
215
             (3, 'D', 1, True),
 
216
             (4, 'E', 1, False),
 
217
             (5, 'F', 2, True),
 
218
             (6, 'G', 1, True),
 
219
             (7, 'H', 0, True),
 
220
             ]
 
221
            )