← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/tests/test_graph.py

  • Committer: John Arbash Meinel
  • Date: 2008-07-13 04:06:16 UTC
  • mto: This revision was merged to the branch mainline in revision 3543.
  • Revision ID: john@arbash-meinel.com-20080713040616-fl43f8inkw19qj2l
Bring in the code to collapse linear portions of the graph.
Also, start handling when we get NULL_REVISION instead of a tuple key
from various apis.
We could probably handle it at a different level if we really wanted.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/tests/test_graph.py
1384
1384
        # Use sorted because we don't care about the order, just that each is
1385
1385
        # only present 1 time.
1386
1386
        self.assertEqual(['a', 'b'], sorted(self.inst_pp.calls))
 
1387
 
 
1388
 
 
1389
class TestCollapseLinearRegions(tests.TestCase):
 
1390
 
 
1391
    def assertCollapsed(self, collapsed, original):
 
1392
        self.assertEqual(collapsed,
 
1393
                         _mod_graph.collapse_linear_regions(original))
 
1394
 
 
1395
    def test_collapse_nothing(self):
 
1396
        d = {1:[2, 3], 2:[], 3:[]}
 
1397
        self.assertCollapsed(d, d)
 
1398
        d = {1:[2], 2:[3, 4], 3:[5], 4:[5], 5:[]}
 
1399
        self.assertCollapsed(d, d)
 
1400
 
 
1401
    def test_collapse_chain(self):
 
1402
        # Any time we have a linear chain, we should be able to collapse
 
1403
        d = {1:[2], 2:[3], 3:[4], 4:[5], 5:[]}
 
1404
        self.assertCollapsed({1:[5], 5:[]}, d)
 
1405
        d = {5:[4], 4:[3], 3:[2], 2:[1], 1:[]}
 
1406
        self.assertCollapsed({5:[1], 1:[]}, d)
 
1407
        d = {5:[3], 3:[4], 4:[1], 1:[2], 2:[]}
 
1408
        self.assertCollapsed({5:[2], 2:[]}, d)
 
1409
 
 
1410
    def test_collapse_with_multiple_children(self):
 
1411
        #    7
 
1412
        #    |
 
1413
        #    6
 
1414
        #   / \
 
1415
        #  4   5
 
1416
        #  |   |
 
1417
        #  3   2
 
1418
        #   \ /
 
1419
        #    1
 
1420
        #
 
1421
        # 4 and 5 cannot be removed because 6 has 2 children
 
1422
        # 3 and 2 cannot be removed because 1 has 2 parents
 
1423
        d = {1:[2, 3], 2:[4], 4:[6], 3:[5], 5:[6], 6:[7], 7:[]}
 
1424
        self.assertCollapsed(d, d)