File: test_knots.py

package info (click to toggle)
python-cogent 1.4.1-1.2
links: PTS, VCS
area: non-free
in suites: squeeze
size: 13,260 kB
ctags: 20,087
sloc: python: 116,163; ansic: 732; makefile: 74; sh: 9
file content (1382 lines) | stat: -rw-r--r-- 54,917 bytes
#!/usr/bin/env python
# test_knots.py

"""Provides tests for classes and functions in the file knots.py
"""

from __future__ import division
from cogent.util.unit_test import TestCase, main
from cogent.util.dict2d import Dict2D
from cogent.struct.rna2d import Pairs
from cogent.struct.knots import PairedRegion, PairedRegionFromPairs,\
    PairedRegions, PairedRegionsFromPairs, ConflictMatrix,\
    opt_all, contains_true, empty_matrix,\
    pick_multi_best, dp_matrix_multi, matrix_solutions,\
    opt_single_random, opt_single_property,\
    inc_order, inc_length, inc_range,\
    find_max_conflicts, find_min_gain,\
    conflict_elimination, add_back_non_conflicting,\
    num_bps, hydrogen_bonds,\
    nussinov_fill, nussinov_traceback, nussinov_restricted

__author__ = "Sandra Smit"
__copyright__ = "Copyright 2007-2009, The Cogent Project"
__contributors__ = ["Sandra Smit, Rob Knight"]
__license__ = "GPL"
__version__ = "1.4.1"
__maintainer__ = "Sandra Smit"
__email__ = "sandra.smit@colorado.edu"
__status__ = "Production"


class PairedRegionTests(TestCase):
    """Tests for PairedRegion class"""

    def test_init_valid(self):
        """PairedRegion __init__: should work as expected on valid input
        """
        pr = PairedRegion(3,10,2)
        self.assertEqual(pr.Start, 3)
        self.assertEqual(pr.End, 10)
        self.assertEqual(pr.Length, 2)
        self.assertEqual(pr.Pairs, [(3,10),(4,9)])

        pr = PairedRegion(3,10,2, Id=0)
        self.assertEqual(pr.Id, 0)
        pr = PairedRegion(3,10,2, Id='A')
        self.assertEqual(pr.Id, 'A')

        self.assertRaises(ValueError, PairedRegion, 4, 10, 0)

    def test_init_weird(self):
        """PairedRegion __init__: no error checking
        """
        pr = PairedRegion(3,6,4)
        self.assertEqual(pr.Start, 3)
        self.assertEqual(pr.End, 6)
        self.assertEqual(pr.Length, 4)
        self.assertEqual(pr.Pairs, [(3,6),(4,5),(5,4),(6,3)])

    def test_str(self):
        """PairedRegion __str__: should print pairs"""
        pr = PairedRegion(3,10,2)
        p = Pairs([(3,10),(4,9)])
        self.assertEqual(str(pr), str(p))
    
    def test_len(self):
        """PairedRegion __len__: should return number of pairs"""
        pr = PairedRegion(3,10,2)
        self.assertEqual(len(pr), 2)

    def test_eq(self):
        """PairedRegion __eq__: should use pairs and IDs"""
        pr1 = PairedRegion(3,10,2)
        pr2 = PairedRegion(3,10,2)
        pr3 = PairedRegion(3,10,2, Id='A')
        pr4 = PairedRegion(3,10,2, Id='A')
        pr5 = PairedRegion(3,20,4, Id='A')
        self.assertEqual(pr1==pr2, True) # same pairs, no IDs
        self.assertEqual(pr3==pr4, True) # same pairs, same IDs
        self.assertEqual(pr1==pr3, False) # same pairs, diff ID
        self.assertEqual(pr3==pr5, False) # diff pairs, same IDs

    def test_upstream(self):
        """PairedRegions upstream: single and multiple pair(s)"""
        pr = PairedRegion(3,10,2)
        self.assertEqual(pr.upstream(), [3,4])
        pr = PairedRegion(3,10,1)
        self.assertEqual(pr.upstream(), [3])

    def test_downstream(self):
        """PairedRegions downstream: single and multiple pair(s)"""
        pr = PairedRegion(3,10,2)
        self.assertEqual(pr.downstream(), [9,10])
        pr = PairedRegion(3,10,1)
        self.assertEqual(pr.downstream(), [10])

    def test_paired(self):
        """PairedRegion paired: single and multiple pair(s)"""
        pr = PairedRegion(3,10,2)
        self.assertEqual(pr.paired(), [3,4,9,10])
        pr = PairedRegion(3,10,1)
        self.assertEqual(pr.paired(), [3,10])

    def test_regionRange(self):
        """PairedRegion regionRange: single and multiple pair(s)"""
        pr = PairedRegion(3,10,2)
        self.assertEqual(pr.range(), 4) 
        pr = PairedRegion(1,10,4)
        self.assertEqual(pr.range(), 2)
        pr = PairedRegion(1,5,1)
        self.assertEqual(pr.range(), 3)

        # no error checking
        pr = PairedRegion(5,8,3) # 5,6,7,-- 6,7,8
        self.assertEqual(pr.range(), -2)

    def test_overlapping(self):
        """PairedRegion overlapping: identical and different regions"""
        pr1 = PairedRegion(1,10,2)
        pr2 = PairedRegion(3,15,2)
        self.assertEqual(pr1.overlapping(pr2), False)
        self.assertEqual(pr2.overlapping(pr1), False)

        pr1 = PairedRegion(1,10,2)
        pr2 = PairedRegion(2,15,2)
        pr3 = PairedRegion(9,20,4)
        self.assertEqual(pr1.overlapping(pr2), True)
        self.assertEqual(pr2.overlapping(pr1), True)
        self.assertEqual(pr1.overlapping(pr3), True)

        bl1 = PairedRegion(2,10,1)
        bl2 = PairedRegion(12,20,3)
        self.assertEqual(bl1.overlapping(bl2), False)

        pr1 = PairedRegion(1,10,2, Id='A')
        pr2 = PairedRegion(1,10,2, Id='A')
        pr3 = PairedRegion(1,10,2, Id='B')
        self.assertEqual(pr1.overlapping(pr2), True)
        self.assertEqual(pr1.overlapping(pr3), True) # ignore ID
    
    def test_conflicting(self):
        """PairedRegion conflicting: identical, nested and pseudoknot"""
        bl1 = PairedRegion(2,10,3)
        bl2 = PairedRegion(12,20,3)
        # identical blocks are NOT conflicting...
        self.assertEqual(bl1.conflicting(bl1), False) # identical blocks
        
        self.assertEqual(bl1.conflicting(bl2), False) # one after the other
        self.assertEqual(bl2.conflicting(bl1), False) # one after the other

        bl1 = PairedRegion(1,30,2) #[(1,30),(2,29)]
        bl2 = PairedRegion(14,20,2) #[(14,20),(15,19)]
        self.assertEqual(bl1.conflicting(bl2), False) # one inside the other
        self.assertEqual(bl2.conflicting(bl1), False) # one inside the other
        
        bl1 = PairedRegion(1,10,2) #[(1,10),(2,9)]
        bl2 = PairedRegion(4,15,3) #[(4,15),(5,14),(6,13)]
        self.assertEqual(bl1.conflicting(bl2), True) # pseudoknot
        self.assertEqual(bl2.conflicting(bl1), True) # pseudoknot

    def test_score(self):
        """PairedRegion score: should take arbitrary scoring function"""
        f = lambda x: x.Length # scoring function
        bl1 = PairedRegion(2,10,3)
        bl2 = PairedRegion(12,30,4)
        bl1.score(f) # set Score attribute for bl1
        bl2.score(f) # set Score attribute for bl2
        self.assertEqual(bl1.Score, 3)
        self.assertEqual(bl2.Score, 4)

    def test_PairedRegionFromPairs(self):
        """PairedRegionFromPairs: should handle valid input"""
        p = Pairs([(3,10),(4,9),(5,8)])
        pr = PairedRegionFromPairs(p, Id='A')
        self.assertEqual(pr.Start, 3)
        self.assertEqual(pr.End, 10)
        self.assertEqual(pr.Length, 3)
        self.assertEqual(pr.Id, 'A')
        self.assertEqual(pr.Pairs, [(3,10),(4,9),(5,8)])
    
    def test_PairedRegionFromPairs_invalid(self):
        """PairedRegionFromPairs: conflicts and error checking"""
        p = Pairs([(3,10),(4,9),(4,None)])
        self.assertRaises(ValueError, PairedRegionFromPairs, p)
    
        # no error checking on input pairs...
        p = Pairs([(3,10),(4,9),(6,8)]) # not a real paired region
        pr = PairedRegionFromPairs(p, Id='A')
        self.assertEqual(pr.Start, 3)
        self.assertEqual(pr.End, 10)
        self.assertEqual(pr.Length, 3)
        self.assertEqual(pr.Id, 'A')
        # NOTE: Pairs will be different than input because assumption does
        # not hold
        self.assertEqual(pr.Pairs, [(3,10),(4,9),(5,8)])

        self.assertRaises(ValueError, PairedRegionFromPairs, [])

class PairedRegionsTests(TestCase):
    """Tests for PairedRegions class"""

    def test_init(self):
        """PairedRegions __init__: should accept list of PairedRegion objects
        """
        pr1 = PairedRegion(3,10,2)
        pr2 = PairedRegion(12,20,3)
        obs = PairedRegions([pr1, pr2])
        self.assertEqual(obs[0].Start, 3)
        self.assertEqual(obs[1].Id, None)
        self.assertEqual(obs[1].End, 20)

    def test_init_no_validation(self):
        """PairedRegions __init__: does not perform validation
        """
        # can give any list of arbitrary object as input
        obs = PairedRegions([1,2,3])
        self.assertEqual(obs[0], 1)

    def test_str(self):
        """PairedRegions __str__: full and empty list
        """
        pr1 = PairedRegion(3,10,2)
        pr2 = PairedRegion(12,20,3, Id='A')
        prs = PairedRegions([pr1, pr2])
        self.assertEqual(str(prs), "(None:3,10,2; A:12,20,3;)")

    def test_eq(self):
        """PairedRegions __eq__: with/without IDs, in or out of order
        """
        pr1 = PairedRegion(3,10,2)
        pr2 = PairedRegion(12,20,3, Id='A')
        prs1 = PairedRegions([pr1, pr2])
        pr3 = PairedRegion(3,10,3)
        pr4 = PairedRegion(20,30,3, Id='A')
        prs2 = PairedRegions([pr3, pr4])
        pr5 = PairedRegion(3,10,2)
        pr6 = PairedRegion(12,20,3, Id='A')
        prs3 = PairedRegions([pr5, pr6])
        prs4 = PairedRegions([pr6, pr5])
        self.assertEqual(prs1==prs2, False)
        self.assertEqual(prs1==prs1, True)
        self.assertEqual(prs1==prs3, True)
        self.assertEqual(prs1==prs4, True)

    def test_ne(self):
        """PairedRegions __ne__: with/without IDs, in or out of order
        """
        pr1 = PairedRegion(3,10,2)
        pr2 = PairedRegion(12,20,3, Id='A')
        prs1 = PairedRegions([pr1, pr2])
        pr3 = PairedRegion(3,10,3)
        pr4 = PairedRegion(20,30,3, Id='A')
        prs2 = PairedRegions([pr3, pr4])
        pr5 = PairedRegion(3,10,2)
        pr6 = PairedRegion(12,20,3, Id='A')
        prs3 = PairedRegions([pr5, pr6])
        prs4 = PairedRegions([pr6, pr5])
        self.assertEqual(prs1!=prs2, True)
        self.assertEqual(prs1!=prs1, False)
        self.assertEqual(prs1!=prs3, False)
        self.assertEqual(prs1!=prs4, False)

    def test_byId(self):
        """PairedRegions byId: unique IDs and duplicates
        """
        pr1 = PairedRegion(3,10,2, Id='A')
        pr2 = PairedRegion(12,20,3, Id='B')
        prs1 = PairedRegions([pr1, pr2])
        obs = prs1.byId()
        self.assertEqual(obs['A'], pr1)
        self.assertEqual(obs['B'], pr2)
        self.assertEqual(len(obs), 2)

        pr3 = PairedRegion(3,10,2, Id='A')
        pr4 = PairedRegion(12,20,3, Id='A')
        prs2 = PairedRegions([pr3, pr4])
        self.assertRaises(ValueError, prs2.byId)

        pr3 = PairedRegion(3,10,2)
        pr4 = PairedRegion(12,20,3)
        prs2 = PairedRegions([pr3, pr4])
        self.assertRaises(ValueError, prs2.byId)

        self.assertEqual(PairedRegions().byId(), {})

    def test_numberOfRegions(self):
        """PairedRegions numberOfRegions: full and empty"""
        pr1 = PairedRegion(2,10,2)
        pr2 = PairedRegion(11,20,4)
        prs1 = PairedRegions([pr1,pr2])
        prs2 = PairedRegions([pr1,pr1,pr2,pr2])
        self.assertEqual(prs1.numberOfRegions(), 2)
        self.assertEqual(prs2.numberOfRegions(), 4)
        self.assertEqual(PairedRegions().numberOfRegions(), 0)

    def test_totalLength(self):
        """PairedRegions totalLength: full and empty"""
        pr1 = PairedRegion(2,10,2)
        pr2 = PairedRegion(11,20,4)
        prs1 = PairedRegions([pr1,pr2])
        self.assertEqual(prs1.totalLength(), 6)
        
        self.assertEqual(PairedRegions().totalLength(), 0)

    def test_totalScore(self):
        """PairedRegions totalScore: full, empty, None"""
        pr1 = PairedRegion(2,10,2)
        pr1.Score = 3
        pr2 = PairedRegion(11,20,4)
        pr2.Score = 2
        pr3 = PairedRegion(11,20,4)
        pr3.Score = None
        pr4 = PairedRegion(11,20,4)
        pr4.Score = "abc"
        pr5 = PairedRegion(11,20,4)
        
        prs1 = PairedRegions([pr1,pr2])
        prs2 = PairedRegions([pr1,pr3])
        prs3 = PairedRegions([pr1,pr4])
        prs4 = PairedRegions([pr1,pr5])
        
        self.assertEqual(prs1.totalScore(), 5)
        self.assertRaises(ValueError, prs2.totalScore)
        self.assertRaises(ValueError, prs3.totalScore)
        self.assertRaises(ValueError, prs4.totalScore)

    def test_toPairs(self):
        """PairedRegions toPairs: good data"""
        pr1 = PairedRegion(2,10,2)
        pr2 = PairedRegion(11,20,4)
        prs1 = PairedRegions([pr2,pr1])
        exp = [(2,10),(3,9),(11,20),(12,19),(13,18),(14,17)]
        self.assertEqual(prs1.toPairs(), exp)

        prs2 = PairedRegions([pr1,pr1])
        exp = [(2,10),(2,10),(3,9),(3,9)]
        self.assertEqual(prs2.toPairs(), exp)

        self.assertEqual(PairedRegions().toPairs(), Pairs())

    def test_byStartEnd(self):
        """PairedRegions byStartEnd: unique and duplicate keys"""
        pr1 = PairedRegion(2,10,2)
        pr2 = PairedRegion(11,20,4)
        prs1 = PairedRegions([pr2,pr1])
        exp = {(2,10): pr1, (11,20): pr2}
        self.assertEqual(prs1.byStartEnd(), exp)

        pr3 = PairedRegion(2,10,2, Id='A')
        pr4 = PairedRegion(2,10,3, Id='B')
        prs2 = PairedRegions([pr3,pr4])
        self.assertRaises(ValueError, prs2.byStartEnd)

    def test_lowestStart(self):
        """PairedRegions lowestStart: full and empty object"""
        pr1 = PairedRegion(2,10,2)
        pr2 = PairedRegion(11,20,4)
        pr3 = PairedRegion(2,30,5,Id='A')
        prs1 = PairedRegions([pr2,pr1,pr3])
        self.assertEqual(prs1.lowestStart(), 2)

        self.assertEqual(PairedRegions().lowestStart(), None)

    def test_highestEnd(self):
        """PairedRegions highestEnd: full and empty object"""
        pr1 = PairedRegion(2,10,2)
        pr2 = PairedRegion(11,20,4)
        pr3 = PairedRegion(2,30,5,Id='A')
        prs1 = PairedRegions([pr2,pr1,pr3])
        self.assertEqual(prs1.highestEnd(), 30)

        self.assertEqual(PairedRegions().highestEnd(), None)

    def test_sortedIds(self):
        """PairedRegions sortedIds: full and empty list"""
        pr1 = PairedRegion(2,10,2, Id='C')
        pr2 = PairedRegion(11,20,4, Id='A')
        pr3 = PairedRegion(2,30,5,Id='B')
        prs1 = PairedRegions([pr1,pr2,pr3])
        self.assertEqual(prs1.sortedIds(), ['A','B','C'])

        pr1 = PairedRegion(2,10,2, Id='C')
        pr2 = PairedRegion(11,20,4, Id='A')
        pr3 = PairedRegion(2,30,5,Id='C')
        prs1 = PairedRegions([pr1,pr2,pr3])
        self.assertEqual(prs1.sortedIds(), ['A','C','C'])

        pr1 = PairedRegion(2,10,2)
        pr2 = PairedRegion(11,20,4, Id='A')
        pr3 = PairedRegion(2,30,5,Id=2)
        prs1 = PairedRegions([pr1,pr2,pr3])
        self.assertEqual(prs1.sortedIds(), [None, 2, 'A'])

    def test_upstream(self):
        """PairedRegions upstream: full and empty"""
        self.assertEqual(PairedRegions().upstream(), [])
        pr1 = PairedRegion(2,10,2, Id='C')
        pr2 = PairedRegion(11,20,4, Id='A')
        pr3 = PairedRegion(4,30,1,Id='B')
        prs1 = PairedRegions([pr1,pr2,pr3])
        exp = [2,3,11,12,13,14,4]
        exp.sort()
        self.assertEqual(prs1.upstream(), exp)

    def test_downstream(self):
        """PairedRegions upstream: full and empty"""
        self.assertEqual(PairedRegions().downstream(), [])
        pr1 = PairedRegion(2,10,2, Id='C')
        pr2 = PairedRegion(11,20,4, Id='A')
        pr3 = PairedRegion(4,30,1,Id='B')
        prs1 = PairedRegions([pr1,pr2,pr3])
        exp = [10,9,20,19,18,17,30]
        exp.sort()
        self.assertEqual(prs1.downstream(), exp)

    def test_pairedPos(self):
        """PairedRegions pairedPos: full and empty"""
        self.assertEqual(PairedRegions().pairedPos(), [])
        pr1 = PairedRegion(2,10,2, Id='C')
        pr2 = PairedRegion(11,20,4, Id='A')
        pr3 = PairedRegion(4,30,1,Id='B')
        prs1 = PairedRegions([pr1,pr2,pr3])
        exp = [2,3,11,12,13,14,4,10,9,20,19,18,17,30]
        exp.sort()
        self.assertEqual(prs1.pairedPos(), exp)

    def test_boundaries(self):
        """PairedRegions boundaries: full and empty"""
        self.assertEqual(PairedRegions().boundaries(), [])
        pr1 = PairedRegion(2,10,2, Id='C')
        pr2 = PairedRegion(11,20,4, Id='A')
        pr3 = PairedRegion(4,30,1,Id='B')
        prs1 = PairedRegions([pr1,pr2,pr3])
        exp = [2,10,11,20,4,30]
        exp.sort()
        self.assertEqual(prs1.boundaries(), exp)

    def test_enumeratedBoundaries(self):
        """PairedRegions enumeratedBoundaries: full and empty"""
        self.assertEqual(PairedRegions().enumeratedBoundaries(), {})
        pr1 = PairedRegion(2,10,2, Id='C')
        pr2 = PairedRegion(11,20,4, Id='A')
        pr3 = PairedRegion(4,30,1,Id='B')
        prs1 = PairedRegions([pr1,pr2,pr3])
        exp = {0:2,2:10,3:11,4:20,1:4,5:30}
        self.assertEqual(prs1.enumeratedBoundaries(), exp)

    def test_invertedEnumeratedBoundaries(self):
        """PairedRegions invertedEnumeratedBoundaries: full and empty"""
        self.assertEqual(PairedRegions().invertedEnumeratedBoundaries(), {})
        pr1 = PairedRegion(2,10,2, Id='C')
        pr2 = PairedRegion(11,20,4, Id='A')
        pr3 = PairedRegion(4,30,1,Id='B')
        prs1 = PairedRegions([pr1,pr2,pr3])
        exp = {2:0,10:2,11:3,20:4,4:1,30:5}
        self.assertEqual(prs1.invertedEnumeratedBoundaries(), exp)

        pr1 = PairedRegion(3,10,2)
        pr2 = PairedRegion(5,10,3)
        prs = PairedRegions([pr1, pr2])
        self.assertRaises(ValueError, prs.invertedEnumeratedBoundaries)

    def test_merge(self):
        """PairedRegions merge: different, duplicates, empty"""
        pr1 = PairedRegion(3,10,2, Id='A')
        pr2 = PairedRegion(11,20,3, Id='B')
        pr3 = PairedRegion(15,25,1, Id='C')
        prs1 = PairedRegions([pr1, pr2])
        prs2 = PairedRegions([pr1, pr3])
        prs3 = PairedRegions()

        exp = PairedRegions([pr1,pr2,pr3])
        self.assertEqual(prs1.merge(prs2), exp)
        self.assertEqual(prs2.merge(prs1), exp)
        self.assertEqual(prs1.merge(prs3), prs1)
        self.assertEqual(prs2.merge(prs3), prs2)

    def test_conflicting_no_ids(self):
        """PairedRegions conflicting: raises error on duplicate IDs
        """
        pr1 = PairedRegion(1,10,2)
        pr2 = PairedRegion(11,20,2)
        prs = PairedRegions([pr1, pr2])
        self.assertRaises(ValueError, prs.conflicting) #conflicting IDs

    def test_conflicting(self):
        """PairedRegions conflicting: works when IDs are set and unique
        """
        pr1 = PairedRegion(3,10,2, Id='A')
        pr2 = PairedRegion(11,20,3, Id='B')
        pr3 = PairedRegion(15,25,1, Id='C')
        prs = PairedRegions([pr1,pr2,pr3])
        self.assertEqual(prs.conflicting(), PairedRegions([pr2,pr3]))

        prs = PairedRegions()
        self.assertEqual(prs.conflicting(), PairedRegions())

    def test_non_conflicting_no_ids(self):
        """PairedRegions nonConflicting: raises error on duplicate IDs
        """
        pr1 = PairedRegion(1,10,2)
        pr2 = PairedRegion(11,20,2)
        prs = PairedRegions([pr1, pr2])
        self.assertRaises(ValueError, prs.nonConflicting) #conflicting IDs

    def test_non_conflicting(self):
        """PairedRegions nonConflicting: works when IDs are set and unique
        """
        pr1 = PairedRegion(3,10,2, Id='A')
        pr2 = PairedRegion(11,20,3, Id='B')
        pr3 = PairedRegion(15,25,1, Id='C')
        prs = PairedRegions([pr1,pr2,pr3])
        self.assertEqual(prs.nonConflicting(), PairedRegions([pr1]))

        prs = PairedRegions()
        self.assertEqual(prs.conflicting(), PairedRegions())

    def test_conflictCliques(self):
        """PairedRegions conflictCliques: should work when IDs are unique"""
        pr1 = PairedRegion(3,10,2, Id='A')
        pr2 = PairedRegion(11,20,3, Id='B')
        pr3 = PairedRegion(15,25,1, Id='C')
        pr4 = PairedRegion(30,40,2, Id='D')
        pr5 = PairedRegion(28,35,1, Id='E')
        prs = PairedRegions([pr1,pr2,pr3,pr4, pr5])
        obs = prs.conflictCliques()
        exp = [PairedRegions([pr2,pr3]),PairedRegions([pr5,pr4])]
        for i in obs:
            self.failUnless(i in exp)
        self.assertEqual(len(obs), len(exp))

        prs = PairedRegions()
        self.assertEqual(prs.conflictCliques(), [])

    def test_PairedRegionsFromPairs(self):
        """PairedRegionsFromPairs: should work on valid input"""
        p = Pairs([(1,10),(2,9),(12,20),(13,19),(14,18)])
        prs = PairedRegionsFromPairs(p)
        self.assertEqual(len(prs), 2)
        self.assertEqual(prs[0].Id, 0)
        self.assertEqual(prs[0].Pairs, [(1,10),(2,9)])
        self.assertEqual(prs[0].Start, 1)
        self.assertEqual(prs[0].End, 10)

        self.assertEqual(PairedRegionsFromPairs(Pairs()), PairedRegions())

    def test_PairedRegionsFromPairs_conflict(self):
        """PairedRegionsFromPairs: should raise error on overlapping pairs"""
        p = Pairs([(2,20),(5,10),(10,15)])
        self.assertRaises(ValueError, PairedRegionsFromPairs, p)

class ConflictMatrixTests(TestCase):
    """Tests for ConflictMatrix class"""

    def test_conflict_matrix_from_pairs(self):
        """ConflixtMatrix __init__: Pairs as input, w/wo conflict """
        
        f = ConflictMatrix
        # conflict free
        d = [(1,10),(2,9),(12,20),(13,19),(14,18)]
        exp = Dict2D({0:{0:False,1:False},1:{0:False,1:False}})
        self.assertEqual(f(d).Matrix, exp)
        self.failIf(not isinstance(f(d).Matrix, Dict2D))
        
        # 1 conflict
        d = [(1,10),(2,9),(12,20),(13,19),(14,18),(15,30),(16,29)]
        exp = Dict2D({0:{0:False,1:False,2:False},\
            1:{0:False,1:False,2:True},\
            2:{0:False,1:True,2:False}})
        self.assertEqual(f(d).Matrix, exp)

        # 1 conflict
        d = Pairs([(1,10),(2,9),(12,20),(13,19),(14,18),(15,30),(16,29)])
        exp = Dict2D({0:{0:False,1:False,2:False},\
            1:{0:False,1:False,2:True},\
            2:{0:False,1:True,2:False}})
        m = f(d).Matrix
        self.assertEqual(m, exp)
        self.assertEqual(m.RowOrder, [0,1,2])
        self.assertEqual(m.ColOrder, [0,1,2])
        
        d = [] # empty input
        exp = Dict2D()
        self.assertEqual(f(d).Matrix, exp)

    def test_ConflictMatrix_Pairs_overlap(self):
        """ConflictMatrix __init__: raises error on overlapping pairs"""
        p = Pairs([(1,10),(2,9),(3,9),(12,20)])
        self.assertRaises(ValueError, ConflictMatrix, p)

    def test_conflict_matrix_from_PairedRegions(self):
        """ConflictMatrix __init__: PairedRegions as input, w/wo conflict
        """
        f = ConflictMatrix
        # conflict free
        pr1 = PairedRegion(1,10,2, Id=0)
        pr2 = PairedRegion(12,20,3, Id=1)
        prs = PairedRegions([pr1,pr2])
        exp = Dict2D({0:{0:False,1:False},1:{0:False,1:False}})
        self.assertEqual(f(prs).Matrix, exp)
        self.failIf(not isinstance(f(prs).Matrix, Dict2D))
        
        pr1 = PairedRegion(1,10,2, Id=0)
        pr2 = PairedRegion(12,20,3, Id=1)
        pr3 = PairedRegion(15,30,2, Id=2)
        prs = PairedRegions([pr1,pr2, pr3])
        # 1 conflict
        exp = Dict2D({0:{0:False,1:False,2:False},\
            1:{0:False,1:False,2:True},\
            2:{0:False,1:True,2:False}})
        self.assertEqual(f(prs).Matrix, exp)
        
        # 1 conflict
        pr1 = PairedRegion(1,10,2, Id=4)
        pr2 = PairedRegion(12,20,3, Id=1)
        pr3 = PairedRegion(15,30,2, Id=9)
        prs = PairedRegions([pr1,pr2, pr3])
        exp = Dict2D({1:{4:False,1:False,9:True},\
            4:{1:False,4:False,9:False},\
            9:{1:True,4:False,9:False}})
        m = f(prs).Matrix
        self.assertEqual(m, exp)
        self.assertEqual(m.RowOrder, [1,4,9])
        self.assertEqual(m.ColOrder, [1,4,9])
        
        prs = PairedRegions()
        exp = Dict2D()
        self.assertEqual(f(prs).Matrix, exp)
        # input some weird data. Other errors might occur.
        self.assertRaises(ValueError, f, 'ABC')
        self.assertRaises(ValueError, f, [('a','b'),('c','d')])

    def test_ConflictMatrix_PairedRegions_overlap(self):
        """ConflictMatrix __init__: raises error on overlapping PairedRegions
        """
        pr1 = PairedRegion(1,10,2, Id='A')
        pr2 = PairedRegion(8,20,2, Id='B')
        prs = PairedRegions([pr1, pr2])
        self.assertRaises(ValueError, ConflictMatrix, prs)
        
    def test_conflictsOf(self):
        """ConflictMatrix conflictsOf: with/without conflicts"""
        p = Pairs([(1,10),(5,15),(20,30),(25,35),(24,32),(0,80)])
        cm = ConflictMatrix(p)
        self.assertEqual(cm.conflictsOf(0), [])
        self.assertEqual(cm.conflictsOf(1), [2])
        self.assertEqual(cm.conflictsOf(2), [1])
        self.assertEqual(cm.conflictsOf(3), [4,5])

        p = Pairs([(1,10),(11,20)])
        cm = ConflictMatrix(p)
        self.assertEqual(cm.conflictsOf(0), [])
        self.assertEqual(cm.conflictsOf(1), [])
        self.assertRaises(KeyError, cm.conflictsOf, 2)
        
    def test_conflicting(self):
        """ConflictMatrix conflicting: full and empty Pairs"""
        p = Pairs([(1,10),(5,15),(20,30),(25,35),(24,32),(0,80)])
        cm = ConflictMatrix(p)
        obs = cm.conflicting()
        exp = [1,2,3,4,5]
        self.assertEqual(obs, exp)

        self.assertEqual(ConflictMatrix(Pairs()).conflicting(), [])

    def test_nonConflicting(self):
        """ConflictMatrix nonConflicting: full and empty Pairs"""
        p = Pairs([(1,10),(5,15),(20,30),(25,35),(24,32),(0,80)])
        cm = ConflictMatrix(p)
        obs = cm.nonConflicting()
        exp = [0]
        self.assertEqual(obs, exp)

        self.assertEqual(ConflictMatrix(Pairs()).nonConflicting(), [])

    def test_conflictCliques(self):
        """ConflictMatrix conflictCliques: full and empty Pairs"""
        p = Pairs([(1,10),(5,15),(20,30),(25,35),(24,32),(0,80)])
        cm = ConflictMatrix(p)
        obs = cm.conflictCliques()
        exp = [[1,2],[3,4,5]]
        self.assertEqual(obs, exp)

        self.assertEqual(ConflictMatrix(Pairs()).conflictCliques(), [])
    
    
class DPTests(TestCase):
    """Tests for opt_all and related functions"""

    def test_num_bps(self):
        """num_bps: should return length of paired region"""
        f = num_bps
        pr1 = PairedRegion(0,10,3)
        self.assertEqual(f(pr1), 3)

    def test_hydrogen_bonds(self):
        """hydrogen_bonds: score GC, AU, and GU base pairs"""
        f = hydrogen_bonds('UACGAAAUGCGUG')
        pr1 = PairedRegion(0,12,5)
        self.assertEqual(f(pr1),10)

        f = hydrogen_bonds('UACGAAA') # sequence too short
        pr1 = PairedRegion(0,12,5)
        self.assertRaises(IndexError, f, pr1)
    
    def test_contains_true(self):
        """contains_true: should return True if True in input"""
        f = contains_true
        self.assertEqual(f([True]), True)
        self.assertEqual(f([True, False]), True)
        self.assertEqual(f([1, 0]), True)
        self.assertEqual(f([1]), True)
        self.assertEqual(f([False]), False)
        self.assertEqual(f([3]), False)
        self.assertEqual(f(["a","b","c"]), False)
        self.assertEqual(f("abc"), False)

    def test_empty_matrix(self):
        """empty_matrix: valid input and error"""
        f = empty_matrix
        p = PairedRegions()
        exp = [[[p],[p]], [[p],[p]]]
        self.assertEqual(f(2), exp)
        
        self.assertEqual(f(1), [[[p]]])

        self.assertRaises(ValueError, f, 0)

    def test_pick_multi_best_max(self):
        """pick_multi_best: max, full and empty list"""
        pr1 = PairedRegion(2,10,2, Id='A')
        pr2 = PairedRegion(4,15,3, Id='B')
        pr3 = PairedRegion(20,40,5, Id='C')
        pr4 = PairedRegion(22,30,3, Id='D')
        for i in [pr1,pr2,pr3,pr4]:
            i.score(num_bps)
        prs1 = PairedRegions([pr1, pr2])
        prs2 = PairedRegions([pr3])
        prs3 = PairedRegions([pr4])
        self.assertEqualItems(pick_multi_best([prs1, prs2, prs3]), [prs1, prs2])

        self.assertEqual(pick_multi_best([]), [PairedRegions()])

    def test_pick_multi_best_min(self):
        """pick_multi_best: min, full and empty list"""
        f = lambda x: -1
        pr1 = PairedRegion(2,10,2)
        pr2 = PairedRegion(4,15,3)
        pr3 = PairedRegion(20,40,5)
        pr4 = PairedRegion(22,30,3)
        for i in [pr1,pr2,pr3,pr4]:
            i.score(f)
        prs1 = PairedRegions([pr1, pr2])
        prs2 = PairedRegions([pr3])
        prs3 = PairedRegions([pr4])
        self.assertEqual(pick_multi_best([prs1, prs2, prs3], goal='min'),\
            [prs1])

        self.assertEqual(pick_multi_best([], goal='min'), [PairedRegions()])

    def test_dp_matrix_multi_toy(self):
        """dp_matrix_multi: test on initial toy example"""
        pr0 = PairedRegion(0, 70, 2, Id='C')
        pr1 = PairedRegion(10, 30, 4, Id='A')
        pr2 = PairedRegion(20, 50, 3, Id='B')
        pr3 = PairedRegion(40, 90, 2, Id='E')
        pr4 = PairedRegion(60, 80, 3, Id='D')
        prs = PairedRegions([pr0, pr1, pr2, pr3, pr4])  
        obs = dp_matrix_multi(prs)
        self.assertEqual(obs[0][0], [PairedRegions()])
        self.assertEqual(obs[0][3], [PairedRegions([pr1])])
        self.assertEqual(obs[2][5], [PairedRegions([pr2])])
        self.assertEqual(obs[4][9], [PairedRegions([pr3,pr4])])
        self.assertEqual(obs[2][9], [PairedRegions([pr2,pr4])])
        self.assertEqual(obs[1][8], [PairedRegions([pr1,pr4])])
        self.assertEqual(obs[1][9], [PairedRegions([pr1,pr3,pr4])])
        self.assertEqual(obs[0][9], [PairedRegions([pr1,pr3,pr4])])

    def test_dp_matrix_multi_lsu(self):
        """dp_matrix_multi: test on LSU rRNA domain I case"""

        pr0 = PairedRegion(56, 69, 3, Id=0)
        pr1 = PairedRegion(60, 92, 1, Id=1)
        pr2 = PairedRegion(62, 89, 3, Id=2)
        pr3 = PairedRegion(75, 109, 6, Id=3)
        pr4 = PairedRegion(84, 96, 3, Id=4)
        prs = PairedRegions([pr0, pr1, pr2, pr3, pr4])
        obs = dp_matrix_multi(prs)
        self.assertEqual(obs[0][0], [PairedRegions()])
        self.assertEqual(obs[0][5], [PairedRegions([pr0])])
        self.assertEqual(obs[1][6], [PairedRegions([pr2])])
        self.assertEqual(obs[1][7], [PairedRegions([pr1,pr2])])
        self.assertEqualItems(obs[2][8],\
            [PairedRegions([pr2]),PairedRegions([pr4])])
        self.assertEqual(obs[1][9], [PairedRegions([pr3,pr4])])
        self.assertEqual(obs[0][9], [PairedRegions([pr0,pr3,pr4])])

    def test_dp_matrix_multi_artificial(self):
        """dp_matrix_multi: test on artificial structure"""

        pr0 = PairedRegion(0, 77, 2, Id=0)
        pr1 = PairedRegion(7, 75, 5, Id=1)
        pr2 = PairedRegion(13, 83, 3, Id=2)
        pr3 = PairedRegion(18, 41, 5, Id=3)
        pr4 = PairedRegion(23, 53, 10, Id=4)
        pr5 = PairedRegion(33, 70, 3, Id=5)
        pr6 = PairedRegion(59, 93, 9, Id=6)
        pr7 = PairedRegion(78, 96, 3, Id=7)
        prs = PairedRegions([pr0, pr1, pr2, pr3, pr4, pr5, pr6, pr7])
        obs = dp_matrix_multi(prs)
        self.assertEqual(obs[0][0], [PairedRegions()])
        self.assertEqual(obs[0][6], [PairedRegions([pr3])])
        self.assertEqual(obs[0][7], [PairedRegions([pr4])])
        self.assertEqual(obs[9][15], [PairedRegions([pr7])])
        self.assertEqual(obs[1][10], [PairedRegions([pr1,pr4])])
        self.assertEqual(obs[0][11], [PairedRegions([pr0,pr1,pr4])])
        self.assertEqual(obs[3][14], [PairedRegions([pr4, pr6])])
        self.assertEqual(obs[3][14], [PairedRegions([pr4, pr6])])
        self.assertEqual(obs[0][13], [PairedRegions([pr0, pr1, pr4])])
        self.assertEqual(obs[0][14], [PairedRegions([pr4, pr6])])
        self.assertEqual(obs[1][15], [PairedRegions([pr4, pr6])])
        self.assertEqual(obs[0][15], [PairedRegions([pr0, pr1, pr4, pr7])])

    def test_pick_multi_best_saturated(self):
        """pick_multi_best: should only include saturated solutions"""
        pr1 = PairedRegion(2,10,2, Id='A')
        pr1.Score = 2
        pr2 = PairedRegion(15,25,2, Id='B')
        pr2.Score = 2
        pr3 = PairedRegion(4,22,4, Id='C')
        pr3.Score = 0
        prs1 = PairedRegions([pr1])
        prs2 = PairedRegions([pr2])
        prs3 = PairedRegions([pr1, pr3])
        self.assertEqualItems(pick_multi_best([prs1, prs2, prs3]),\
            [prs2, prs3])
        self.assertEqual(pick_multi_best([]), [PairedRegions()])

    def test_matrix_solutions(self):
        """matrix_solutions: should return contents of top-right cell"""
        pr0 = PairedRegion(56, 69, 3, Id=0)
        pr1 = PairedRegion(60, 92, 1, Id=1)
        pr2 = PairedRegion(62, 89, 3, Id=2)
        pr3 = PairedRegion(75, 109, 6, Id=3)
        pr4 = PairedRegion(84, 96, 3, Id=4)
        prs = PairedRegions([pr0, pr1, pr2, pr3, pr4])
        obs = matrix_solutions(prs)
        self.assertEqual(obs, [PairedRegions([pr0,pr3,pr4])])

        # error, size should be at least 1
        prs = PairedRegions()
        self.assertRaises(ValueError, matrix_solutions, prs)

        pr = PairedRegion(2,20, 5, Id='A')
        prs = PairedRegions([pr])
        obs = matrix_solutions(prs)
        self.assertEqual(obs, [prs])

    def test_opt_all_nested(self):
        """opt_all: should return input when already nested"""
        p = Pairs([(1,10),(2,9),(20,30),(22,29)])
        obs = opt_all(p)
        self.assertEqual(len(obs),1)
        self.assertEqual(obs[0], p)

        p = Pairs()
        self.assertEqual(opt_all(p), [[]])

    def test_opt_all_overlap(self):
        """opt_all: should raise error on overlapping pairs"""
        p = Pairs([(1,10),(2,9),(9,30),(22,29),(1,None)])
        self.assertRaises(ValueError, opt_all, p)

    def test_opt_all_knot(self):
        """opt_all: single/multiple solution(s)"""
        p = Pairs([(1,10),(2,9),(3,15),(4,14),(11,20),(12,19),(25,30)])
        obs = opt_all(p)
        exp = Pairs([(1,10),(2,9),(11,20),(12,19),(25,30)])
        exp_rem = [(3,15),(4,14)]
        self.assertEqual(len(obs), 1)
        self.assertEqual(obs[0], exp)
        self.assertEqual(opt_all(p, return_removed=True)[0][1],\
            exp_rem)
        
        p = Pairs([(1,10),(2,9),(4,14),(3,15)])
        obs = opt_all(p)
        self.assertEqual(len(obs), 2)
        self.assertEqualItems(obs, [Pairs([(1,10),(2,9)]),\
            Pairs([(3,15),(4,14)])])
        exp_rem = [(Pairs([(1,10),(2,9)]),Pairs([(3,15),(4,14)])),\
            (Pairs([(3,15),(4,14)]),Pairs([(1,10),(2,9)]))]
        self.assertEqualItems(opt_all(p, return_removed=True),\
            exp_rem)

    def test_opt_all_some_non_conflicting(self):
        """opt_all: some conflicting, other not"""
        p = Pairs([(30,40),(10,20),(12,17),(13,None),(17,12),(35,45),(36,44)])
        exp = Pairs([(10,20),(12,17),(35,45),(36,44)])
        exp_rem = [(30,40)]
        self.assertEqual(opt_all(p, return_removed=True),\
            [(exp,exp_rem)])

    def test_opt_all_scoring1(self):
        """opt_all: one optimal in bps, both optimal in energy"""
        p = Pairs([(1,10),(2,9),(4,15),(5,14),(6,13)])
        obs_bps = opt_all(p, goal='max', scoring_function=num_bps)
        obs_energy = opt_all(p, goal='max',\
            scoring_function=hydrogen_bonds('CCCAAAUGGGGUCGUUC'))
        exp_bps = [[(4,15),(5,14),(6,13)]]
        exp_energy = [[(1,10),(2,9)],[(4,15),(5,14),(6,13)]]
        self.assertEqualItems(obs_bps, exp_bps)
        self.assertEqualItems(obs_energy, exp_energy)

    def test_opt_all_scoring2(self):
        """opt_all: both optimal in bps, one optimal in energy"""
        p = Pairs([(0,9),(1,8),(2,7),(3,13),(4,12),(5,11)])
        obs_bps = opt_all(p, goal='max', scoring_function=num_bps)
        obs_energy = opt_all(p, goal='max',\
            scoring_function=hydrogen_bonds('CCCAAAAGGGUUUU'))
        exp_bps = [[(0,9),(1,8),(2,7)],[(3,13),(4,12),(5,11)]]
        exp_energy = [[(0,9),(1,8),(2,7)]]
        self.assertEqualItems(obs_bps, exp_bps)
        self.assertEqualItems(obs_energy, exp_energy)

    def test_opt_all_scoring3(self):
        """opt_all: one optimal in bps, the other optimal in energy"""
        p = Pairs([(0,11),(1,10),(2,9),(4,15),(5,14),(6,13),(7,12)])
        obs_bps = opt_all(p, goal='max', scoring_function=num_bps)
        obs_energy = opt_all(p, goal='max',\
            scoring_function=hydrogen_bonds('CCCCAAAAGGGGUUUU'))
        exp_bps = [[(4,15),(5,14),(6,13),(7,12)]]
        exp_energy = [[(0,11),(1,10),(2,9)]]
        self.assertEqualItems(obs_bps, exp_bps)
        self.assertEqualItems(obs_energy, exp_energy)
    
    def test_opt_single_random(self):
        """opt_single_random: should return single solution"""
        p = Pairs ([(10,20),(11,19),(15,25),(16,24)])
        exp1, exp_rem1 = [(10,20),(11,19)], [(15,25),(16,24)]
        exp2, exp_rem2 = [(15,25),(16,24)], [(10,20),(11,19)]
        obs = opt_single_random(p)
        self.failUnless(obs == exp1 or obs == exp2)
        obs = opt_single_random(p, return_removed=True)
        self.failUnless(obs == (exp1, exp_rem1) or obs == (exp2, exp_rem2))
           
    def test_opt_single_property(self):
        """opt_single_property: three properties"""
        # one solution single region, other solution two regions
        p = Pairs ([(10,20),(25,35),(26,34),(27,33),\
            (12,31),(13,30),(14,29),(15,28)])
        exp = [(12,31),(13,30),(14,29),(15,28)]
        exp_rem = [(10,20),(25,35),(26,34),(27,33)]
        self.assertEqual(opt_single_property(p), exp)
        self.assertEqual(opt_single_property(p, return_removed=True),\
            (exp,exp_rem))

        # both two blocks, one shorter average range
        p = Pairs ([(10,20),(22,40),(23,39),(24,38),\
            (17,26),(18,25),(36,43),(37,42)])
        exp = [(17,26),(18,25),(36,43),(37,42)]
        exp_rem = [(10,20),(22,40),(23,39),(24,38)]
        self.assertEqual(opt_single_property(p), exp)
        self.assertEqual(opt_single_property(p, return_removed=True),\
            (exp,exp_rem))

        # both single block over same range, pick lowest start
        p = Pairs([(10,20),(15,25)])
        exp = [(10,20)]
        exp_rem = [(15,25)]
        self.assertEqual(opt_single_property(p), exp)
        self.assertEqual(opt_single_property(p, return_removed=True),\
            (exp,exp_rem))

class EliminationMethodsTests(TestCase):
    """Tests for conflict_elimination and related functions"""
        
    def test_find_max_conflicts(self):
        """find_max_conflicts: simple case"""
        f = find_max_conflicts
        pr0 = PairedRegion(0, 77, 2, Id=0)
        pr1 = PairedRegion(7, 75, 5, Id=1)
        pr2 = PairedRegion(13, 83, 3, Id=2)
        pr3 = PairedRegion(18, 41, 5, Id=3)
        pr4 = PairedRegion(23, 53, 10, Id=4)
        pr5 = PairedRegion(33, 70, 3, Id=5)
        pr6 = PairedRegion(59, 93, 9, Id=6)
        pr7 = PairedRegion(78, 96, 3, Id=7)
        prs = PairedRegions([pr0, pr1, pr2, pr3, pr4, pr5, pr6, pr7])
        id_to_pr = prs.byId()
        cm = ConflictMatrix(prs)
        conf = cm.conflicting()
        self.assertEqual(f(conf, cm, prs.byId()), 6)

        prs = PairedRegions([pr0, pr1, pr2, pr3, pr4, pr5, pr7])
        id_to_pr = prs.byId()
        cm = ConflictMatrix(prs)
        conf = cm.conflicting()
        self.assertEqual(f(conf, cm, prs.byId()), 2)

        prs = PairedRegions([pr0, pr1, pr3, pr4, pr5, pr7])
        id_to_pr = prs.byId()
        cm = ConflictMatrix(prs)
        conf = cm.conflicting()
        self.assertEqual(f(conf, cm, prs.byId()), 5)

    def test_find_max_conflicts_on_start(self):
        """find_max_conflicts: in case of equal conflicts and gain"""
        f = find_max_conflicts
        pr0 = PairedRegion(10, 20, 2, Id=0)
        pr1 = PairedRegion(15, 25, 2, Id=1)
        prs = PairedRegions([pr0, pr1])
        id_to_pr = prs.byId()
        cm = ConflictMatrix(prs)
        conf = cm.conflicting()
        self.assertEqual(f(conf, cm, prs.byId()), 1)

    def test_find_min_gain(self):
        """find_min_gain: differentiate on gain only"""
        f = find_min_gain
        pr0 = PairedRegion(0, 77, 2, Id=0)
        pr1 = PairedRegion(7, 75, 5, Id=1)
        pr2 = PairedRegion(13, 83, 3, Id=2)
        pr3 = PairedRegion(18, 41, 5, Id=3)
        pr4 = PairedRegion(23, 53, 10, Id=4)
        pr5 = PairedRegion(33, 70, 3, Id=5)
        pr6 = PairedRegion(59, 93, 9, Id=6)
        pr7 = PairedRegion(78, 96, 3, Id=7)
        prs = PairedRegions([pr0, pr1, pr2, pr3, pr4, pr5, pr6, pr7])
        id_to_pr = prs.byId()
        cm = ConflictMatrix(prs)
        conf = cm.conflicting()
        self.assertEqual(f(conf, cm, prs.byId()), 5)

        prs = PairedRegions([pr0, pr1, pr2, pr3, pr4, pr6, pr7])
        id_to_pr = prs.byId()
        cm = ConflictMatrix(prs)
        conf = cm.conflicting()
        self.assertEqual(f(conf, cm, prs.byId()), 2)

    def test_find_min_gain_conf(self):
        """find_min_gain: in case of equal gain, differentiate on conflicts"""
        f = find_min_gain
        pr0 = PairedRegion(10,30,3, Id=0)
        pr1 = PairedRegion(1,20,6, Id=1)
        pr2 = PairedRegion(22,40,2, Id=2)
        pr3 = PairedRegion(50,80,3, Id=3)
        pr4 = PairedRegion(60,90,8, Id=4)

        prs = PairedRegions([pr0, pr1, pr2, pr3, pr4])
        id_to_pr = prs.byId()
        cm = ConflictMatrix(prs)
        conf = cm.conflicting()
        self.assertEqual(f(conf, cm, prs.byId()), 0)

    def test_find_min_gain_start(self):
        """find_min_gain: in case of equal gain and number of conflicts"""
        f = find_min_gain
        pr0 = PairedRegion(10,30,3, Id=0)
        pr1 = PairedRegion(1,20,6, Id=1)
        pr2 = PairedRegion(22,40,2, Id=2)
        pr3 = PairedRegion(50,80,3, Id=3)
        pr4 = PairedRegion(60,90,7, Id=4)
        pr5 = PairedRegion(45,55,1, Id=5)

        prs = PairedRegions([pr0, pr1, pr2, pr3, pr4, pr5])
        id_to_pr = prs.byId()
        cm = ConflictMatrix(prs)
        conf = cm.conflicting()
        self.assertEqual(f(conf, cm, prs.byId()), 3)

    def test_add_back_non_conflicting(self):
        """add_back_non_conflicting: should add all non-confl regions"""
        f = add_back_non_conflicting
        pr0 = PairedRegion(10,20,3, Id=0)
        pr1 = PairedRegion(30,40,2, Id=1)
        pr2 = PairedRegion(50,60,2, Id=2)
        pr3 = PairedRegion(45,55,3, Id=3) # confl with pr1 and pr2
        pr4 = PairedRegion(0,90,7, Id=4) # not confl with 1,2,3
        pr5 = PairedRegion(32,38,2, Id=5) # not confl with 1,2,3
        prs = PairedRegions([pr0, pr1, pr2])
        removed = {3: pr3, 4: pr4, 5: pr5}
        exp_prs = PairedRegions([pr0, pr1, pr2, pr4, pr5])
        exp_rem = {3: pr3}
        self.assertEqual(f(prs, removed), (exp_prs, exp_rem))

    def test_add_back_non_conflicting_order(self):
        """add_back_non_conflicting: should add 5' side first"""
        f = add_back_non_conflicting
        pr0 = PairedRegion(10,20,3, Id=0)
        pr1 = PairedRegion(30,40,2, Id=1)
        pr2 = PairedRegion(50,60,2, Id=2)
        pr3 = PairedRegion(45,55,3, Id=3) # confl with pr1 and pr2
        pr4 = PairedRegion(0,90,7, Id=4) # not confl with 1,2,3
        pr5 = PairedRegion(80,95,2, Id=5) # not confl with 1,2,3
        prs = PairedRegions([pr0, pr1, pr2])
        removed = {3: pr3, 4: pr4, 5: pr5}
        exp_prs = PairedRegions([pr0, pr1, pr2, pr4 ])
        exp_rem = {3: pr3, 5: pr5}
        self.assertEqual(f(prs, removed), (exp_prs, exp_rem))

    def test_elim_most_conflict(self):
        """conflict_elimination: find_max_conflicts, simple case"""
        f = conflict_elimination
        func = find_max_conflicts
        pr0 = PairedRegion(0, 77, 2, Id=0)
        pr1 = PairedRegion(7, 75, 5, Id=1)
        pr2 = PairedRegion(13, 83, 3, Id=2)
        pr3 = PairedRegion(18, 41, 5, Id=3)
        pr4 = PairedRegion(23, 53, 10, Id=4)
        pr5 = PairedRegion(33, 70, 3, Id=5)
        pr6 = PairedRegion(59, 93, 9, Id=6)
        pr7 = PairedRegion(78, 96, 3, Id=7)
        prs = PairedRegions([pr0, pr1, pr2, pr3, pr4, pr5, pr6, pr7]) 
        pairs = prs.toPairs()
        exp = PairedRegions([pr0, pr1, pr4, pr7]).toPairs()
        exp_rem = PairedRegions([pr2, pr3, pr5, pr6]).toPairs()
        self.assertEqual(f(pairs, func), exp)
        self.assertEqual(f(pairs, func, return_removed=True), (exp, exp_rem))

    def test_elim_mc_circular(self):
        """conflict_elimination: find_max_conflicts, circular removal"""
        # simply remove in order of most conflicts, don't add back
        prfp = PairedRegionFromPairs
        f = conflict_elimination
        func = find_max_conflicts
        pr0 = prfp([(13, 65), (14, 64)], Id=0)
        pr1 = prfp([(15, 102), (16, 101), (17, 100), (18, 99), (19, 98)], Id=1)
        pr2 = prfp([(22, 72), (23, 71), (24, 70), (25, 69),\
            (26, 68), (27, 67), (28, 66)], Id=2)
        pr3 = prfp([(31, 147), (32, 146), (33, 145), (34, 144), (35, 143),\
            (36, 142), (37, 141), (38, 140), (39, 139)], Id=3)
        pr4 = prfp([(42, 129), (43, 128), (44, 127)], Id=4)
        pr5 = prfp([(46, 149), (47, 148)], Id=5)
        pr6 = prfp([(49, 92), (50, 91), (51, 90), (52, 89), (53, 88)], Id=6)
        pr7 = prfp([(75, 138), (76, 137), (77, 136), (78, 135)], Id=7)
        prs = PairedRegions([pr0, pr1, pr2, pr3, pr4, pr5, pr6, pr7])
        exp = PairedRegions([pr3, pr6]).toPairs()
        exp_rem = PairedRegions([pr0, pr1, pr2, pr4, pr5, pr7]).toPairs()
        self.assertEqual(f(prs.toPairs(), func, add_back=False,\
            return_removed=True), (exp, exp_rem))

        # add back circular removals
        exp = PairedRegions([pr3, pr4, pr6]).toPairs()
        exp_rem = PairedRegions([pr0, pr1, pr2, pr5, pr7]).toPairs()
        self.assertEqual(f(prs.toPairs(), func, add_back=True,\
            return_removed=True), (exp, exp_rem))

    def test_elim_min_gain(self):
        """conflict_elimination: find_min_gain, simple case"""
        f = conflict_elimination
        func = find_min_gain
        pr0 = PairedRegion(0, 77, 2, Id=0)
        pr1 = PairedRegion(7, 75, 5, Id=1)
        pr2 = PairedRegion(13, 83, 3, Id=2)
        pr3 = PairedRegion(18, 41, 5, Id=3)
        pr4 = PairedRegion(23, 53, 10, Id=4)
        pr5 = PairedRegion(33, 70, 3, Id=5)
        pr6 = PairedRegion(59, 93, 9, Id=6)
        pr7 = PairedRegion(78, 96, 3, Id=7)
        prs = PairedRegions([pr0, pr1, pr2, pr3, pr4, pr5, pr6, pr7]) 
        pairs = prs.toPairs()
        exp = PairedRegions([pr4, pr6]).toPairs()
        exp_rem = PairedRegions([pr0, pr1, pr2, pr3, pr5, pr7]).toPairs()
        self.assertEqual(f(pairs, func), exp)
        self.assertEqual(f(pairs, func, return_removed=True), (exp, exp_rem))

    def test_elim_min_gain_circular(self):
        """conflict_elimination: find_min_gain, circular removal"""
        # simply remove in order of most conflicts, don't add back
        prfp = PairedRegionFromPairs
        f = conflict_elimination
        func = find_min_gain
        pr0 = prfp([(5, 170), (6, 169), (7, 168), (8, 167), (9, 166),\
            (10, 165)], Id=0)
        pr1 = prfp([(25, 62), (26, 61)], Id=1)
        pr2 = prfp([(29, 46), (30, 45), (31, 44)], Id=2)
        pr3 = prfp([(48, 124), (49, 123)], Id=3)
        pr4 = prfp([(67, 183), (68, 182), (69, 181), (70, 180), (71, 179),\
            (72, 178), (73, 177), (74, 176), (75, 175), (76, 174)], Id=4)
        pr5 = prfp([(82, 172), (83, 171)], Id=5)
        pr6 = prfp([(117, 135), (118, 134), (119, 133)], Id=6)
        pr7 = prfp([(151, 199), (152, 198), (153, 197), (154, 196),\
            (155, 195), (156, 194), (157, 193), (158, 192), (159, 191),\
            (160, 190)], Id=7)
        prs = PairedRegions([pr0, pr1, pr2, pr3, pr4, pr5, pr6, pr7])
        exp = PairedRegions([pr1, pr2, pr4, pr6]).toPairs()
        exp_rem = PairedRegions([pr0, pr3, pr5, pr7]).toPairs()
        self.assertEqual(f(prs.toPairs(), func, add_back=False,\
            return_removed=True), (exp, exp_rem))

        # add back circular removals
        exp = PairedRegions([pr1, pr2, pr4, pr5, pr6]).toPairs()
        exp_rem = PairedRegions([pr0, pr3, pr7]).toPairs()
        self.assertEqual(f(prs.toPairs(), func, add_back=True,\
            return_removed=True), (exp, exp_rem))
 

class IncrementalMethodsTests(TestCase):
    """Tests for incremental pseudoknot-removal methods"""
    
    def test_inc_order_forward(self):
        """nested_in_order: starting at 5' end"""
        f = inc_order
        p = Pairs([(1,10),(2,9),(3,15),(4,14),(11,20),(12,19),(25,30)])
        exp = Pairs([(1,10),(2,9),(11,20),(12,19),(25,30)])
        exp_rem = Pairs([(3,15),(4,14)])
        self.assertEqual(f(p,reversed=False), exp)
        self.assertEqual(f(p,return_removed=True), (exp, exp_rem))

        p = Pairs([(1,20),(2,30),(3,29),(4,28),(5,27),(7,24)])
        exp = Pairs([(1,20)])
        exp_rem = Pairs([(2,30),(3,29),(4,28),(5,27),(7,24)])
        self.assertEqual(f(p,reversed=False), exp)
        self.assertEqual(f(p,return_removed=True), (exp, exp_rem))

        self.assertEqual(f([]), [])

        p = [(1,10),(3,13)] # input as list of tuples
        exp = Pairs([(1,10)])
        self.assertEqual(f(p), exp)

        p = [(1,10),(4,7),(2,9),(5,None)] # pseudoknot-free
        exp = [(1,10),(2,9),(4,7)]
        self.assertEqual(f(p), exp)

        p = [(1,10),(2,10)] #conflict
        self.assertRaises(ValueError, f, p)

    def test_inc_order_reversed(self):
        """nested_in_order: starting at 3' end"""
        f = inc_order
        p = Pairs([(1,10),(2,9),(3,15),(4,14),(24,31),(25,30)])
        exp = Pairs([(3,15),(4,14),(24,31),(25,30)])
        exp_rem = Pairs([(1,10),(2,9)])
        self.assertEqual(f(p,reversed=True), exp)
        self.assertEqual(f(p, reversed=True, return_removed=True),\
            (exp, exp_rem))

        p = Pairs([(1,20),(2,30),(3,29),(4,28),(5,27),(7,24)])
        exp = Pairs([(2,30),(3,29),(4,28),(5,27),(7,24)])
        exp_rem = Pairs([(1,20)])
        self.assertEqual(f(p,reversed=True), exp)
        self.assertEqual(f(p, reversed=True, return_removed=True),\
            (exp, exp_rem))

        self.assertEqual(f([], reversed=True), [])

        p = [(1,10),(3,13)] # input as list of tuples
        exp = Pairs([(3,13)])
        self.assertEqual(f(p, reversed=True), exp)

        p = [(1,10),(4,7),(2,9),(5,None)] # pseudoknot-free
        exp = [(1,10),(2,9),(4,7)]
        self.assertEqual(f(p), exp)

        p = [(1,10),(2,10)] #conflict
        self.assertRaises(ValueError, f, p)

    def test_inc_length(self):
        """inc_length: should handle standard input
        """
        f = inc_length
        # All blocks in conflict, start empty, add first
        p = Pairs([(1,10),(2,9),(3,8),(5,13),(6,12),(7,11)])
        exp = Pairs([(1,10),(2,9),(3,8)])
        self.assertEqual(f(p), exp)

        # Start with length 3 and 2, add 1 block
        p = Pairs([(1,10),(2,9),(3,8),(20,30),(21,29),(25,40),(32,38)])
        exp = Pairs([(1,10),(2,9),(3,8),(20,30),(21,29),(32,38)])
        self.assertEqual(f(p), exp)

        p = Pairs([(1,10),(2,9),(3,8),(12,20),(13,19),(15,23),(16,22)])
        exp_5 = Pairs([(1,10),(2,9),(3,8),(12,20),(13,19)])
        exp_3 = Pairs([(1,10),(2,9),(3,8),(15,23),(16,22)])
        self.assertEqual(f(p), exp_5)
        self.assertEqual(f(p, reversed=True), exp_3)
        self.assertEqual(f(p, return_removed=True),(exp_5,[(15,23),(16,22)]))

        p = [(1,10),(4,7),(2,9),(5,None)] # pseudoknot-free
        exp = [(1,10),(2,9),(4,7)]
        self.assertEqual(f(p), exp)
        
        p = [(1,10),(2,10)] #conflict
        self.assertRaises(ValueError, f, p)

    def test_inc_length_rev(self):
        """inc_length: should prefer 3' side when reversed is True
        """
        f = inc_length
        p = Pairs([(1,10),(2,9),(5,20),(6,19)])
        self.assertEqual(f(p), [(1,10),(2,9)])
        self.assertEqual(f(p, reversed=True), [(5,20),(6,19)])

    def test_inc_range(self):
        """inc_range: should handle normal input
        """
        f = inc_range
        p = [(1,5),(4,20),(15,23),(16,22)]
        exp = [(1,5),(15,23),(16,22)]
        self.assertEqual(f(p), exp)
        self.assertEqual(f(p, return_removed=True), (exp, [(4,20)]))

        p = [(1,11),(5,15)] # same range
        self.assertEqual(f(p), [(1,11)]) # 5' wins
        self.assertEqual(f(p, reversed=True), [(5,15)]) # 3' wins

        p = [(1,10),(2,10)] #conflict
        self.assertRaises(ValueError, f, p)

    def test_inc_range_empty(self):
        """inc_range: should handle empty or pseudoknot-free pairs
        """
        f = inc_range
        p = []
        exp = []
        self.assertEqual(f(p), exp)

        p = [(1,10),(4,7),(2,9),(5,None)]
        exp = [(1,10),(2,9),(4,7)]
        self.assertEqual(f(p), exp)

class NussinovTests(TestCase):
    """Tests for restricted nussinov algorithm and related functions"""

    def test_nussinov_fill(self):
        """nussinov_fill: basic test"""
        p = Pairs([(0,7),(1,6),(2,5),(3,9),(4,8)])
        exp = [[0,0,0,0,0,1,2,3,3,3],
                [0,0,0,0,0,1,2,2,2,2],
                [0,0,0,0,0,1,1,1,1,2],
                [0,0,0,0,0,0,0,0,1,2],
                [0,0,0,0,0,0,0,0,1,1,],
                [0,0,0,0,0,0,0,0,0,0],
                [0,0,0,0,0,0,0,0,0,0],
                [0,0,0,0,0,0,0,0,0,0],
                [0,0,0,0,0,0,0,0,0,0],
                [0,0,0,0,0,0,0,0,0,0]]
        obs = nussinov_fill(p,size=10)
        self.assertEqual(obs, exp)

    def test_nussinov_traceback(self):
        """nussinov_traceback: basic test"""
        p = Pairs([(0,7),(1,6),(2,5),(3,9),(4,8)])
        m = nussinov_fill(p,size=10)
        exp = set([(0,7),(1,6),(2,5)])
        obs = nussinov_traceback(m, 0, 9, p)
        self.assertEqual(obs, exp)

    def test_nussinov_restricted(self):
        """nussinov_restricted: basic test"""
        p = Pairs([(0,7),(1,6),(2,5),(3,9),(4,8)])
        obs = nussinov_restricted(p)
        obs_rem = nussinov_restricted(p, return_removed=True)
        exp = [(0,7),(1,6),(2,5)]
        exp_rem = ([(0,7),(1,6),(2,5)],[(3,9),(4,8)])
        self.assertEqual(obs, exp)
        self.assertEqual(obs_rem, exp_rem)
        
        p = Pairs([(0,7),(1,6),(2,6)])
        self.assertRaises(ValueError, nussinov_restricted, p)

        p = Pairs([(0,7),(1,6),(2,5)])
        exp = Pairs([(0,7),(1,6),(2,5)])
        self.assertEqual(nussinov_restricted(p), exp)

    def test_nussinov_restricted_bi(self):
        """nussinov_restricted: include bifurcation"""
        p = Pairs([(0,7),(1,6),(2,14),(3,13),(4,12),(5,11),\
            (8,17),(9,16),(10,15)])
        obs = nussinov_restricted(p)
        obs_rem = nussinov_restricted(p, return_removed=True)
        exp = [(0,7),(1,6),(8,17),(9,16),(10,15)]
        exp_rem = ([(0,7),(1,6),(8,17),(9,16),(10,15)],\
            [(2,14),(3,13),(4,12),(5,11)])
        self.assertEqual(obs, exp)
        self.assertEqual(obs_rem, exp_rem)



if __name__ == "__main__":
    main()