test_alignment.py

"""
Unit tests for DNA sequence alignment algorithms.

This module contains comprehensive tests for:
- Basic alignment algorithm
- Efficient alignment algorithm
- Core alignment utilities
- String processing
- Input/output operations
"""

import unittest
import os
import sys
import tempfile

# Add src directory to path
sys.path.insert(0, os.path.join(os.path.dirname(__file__), 'src'))

from basic import basic
from efficient import efficient
from alignment_core import (
    init_dp_table, 
    compute_cell_cost, 
    validate_sequences
)
from string_processor import processStrings
from io_utils import readInput, writeOutput
from cost_constants import ALPHA, DELTA


class TestAlignmentCore(unittest.TestCase):
    """Test core alignment utilities."""
    
    def test_init_dp_table(self):
        """Test DP table initialization."""
        m, n = 3, 4
        dp = init_dp_table(m, n)
        
        # Check dimensions
        self.assertEqual(len(dp), m + 1)
        self.assertEqual(len(dp[0]), n + 1)
        
        # Check base cases
        self.assertEqual(dp[0][0], 0)
        for i in range(1, m + 1):
            self.assertEqual(dp[i][0], i * DELTA)
        for j in range(1, n + 1):
            self.assertEqual(dp[0][j], j * DELTA)
    
    def test_compute_cell_cost(self):
        """Test cell cost computation."""
        seq1, seq2 = "AC", "AG"
        dp = init_dp_table(2, 2)
        
        # Fill first cell
        cost = compute_cell_cost(seq1, seq2, 1, 1, dp)
        # A-A match should be 0
        expected = dp[0][0] + ALPHA['A']['A']
        self.assertEqual(cost, expected)
        self.assertEqual(cost, 0)
    
    def test_validate_sequences_valid(self):
        """Test validation accepts valid sequences."""
        try:
            validate_sequences("ACGT", "TGCA")
        except ValueError:
            self.fail("validate_sequences raised ValueError for valid input")
    
    def test_validate_sequences_invalid(self):
        """Test validation rejects invalid sequences."""
        with self.assertRaises(ValueError):
            validate_sequences("ACGX", "ACGT")
        
        with self.assertRaises(ValueError):
            validate_sequences("ACGT", "ACG123")


class TestBasicAlgorithm(unittest.TestCase):
    """Test basic alignment algorithm."""
    
    def test_identical_sequences(self):
        """Test alignment of identical sequences."""
        seq1 = seq2 = "ACGT"
        cost, aligned1, aligned2 = basic(seq1, seq2)
        
        # Cost should be 0 for identical sequences
        self.assertEqual(cost, 0)
        self.assertEqual(aligned1, seq1)
        self.assertEqual(aligned2, seq2)
    
    def test_empty_sequences(self):
        """Test alignment with empty sequences."""
        # One empty sequence
        cost1, aligned1, aligned2 = basic("ACGT", "")
        self.assertEqual(cost1, 4 * DELTA)
        self.assertEqual(aligned1, "ACGT")
        self.assertEqual(aligned2, "____")
        
        # Both empty
        cost2, aligned1, aligned2 = basic("", "")
        self.assertEqual(cost2, 0)
        self.assertEqual(aligned1, "")
        self.assertEqual(aligned2, "")
    
    def test_single_character(self):
        """Test alignment of single characters."""
        # Matching characters
        cost1, _, _ = basic("A", "A")
        self.assertEqual(cost1, 0)
        
        # Mismatching characters
        cost2, _, _ = basic("A", "C")
        self.assertEqual(cost2, ALPHA['A']['C'])
    
    def test_small_sequences(self):
        """Test alignment of small sequences."""
        seq1, seq2 = "ACG", "AGT"
        cost, aligned1, aligned2 = basic(seq1, seq2)
        
        # Cost should be reasonable
        self.assertIsInstance(cost, int)
        self.assertGreater(cost, 0)
        
        # Aligned sequences should have same length
        self.assertEqual(len(aligned1), len(aligned2))
        
        # Should contain original characters (possibly with gaps)
        self.assertTrue(all(c in "ACGT_" for c in aligned1))
        self.assertTrue(all(c in "ACGT_" for c in aligned2))
    
    def test_known_example(self):
        """Test with a known example from CSCI 570."""
        seq1 = "ACTG"
        seq2 = "TACG"
        
        cost, aligned1, aligned2 = basic(seq1, seq2)
        
        # Verify basic properties
        self.assertIsInstance(cost, int)
        self.assertEqual(len(aligned1), len(aligned2))
        
        # Cost should be positive (sequences are different)
        self.assertGreater(cost, 0)


class TestEfficientAlgorithm(unittest.TestCase):
    """Test efficient (Hirschberg) alignment algorithm."""
    
    def test_identical_sequences(self):
        """Test alignment of identical sequences."""
        seq1 = seq2 = "ACGT"
        cost, aligned1, aligned2 = efficient(seq1, seq2)
        
        # Cost should be 0 for identical sequences
        self.assertEqual(cost, 0)
        self.assertEqual(aligned1, seq1)
        self.assertEqual(aligned2, seq2)
    
    def test_empty_sequences(self):
        """Test alignment with empty sequences."""
        # One empty sequence
        cost1, aligned1, aligned2 = efficient("ACGT", "")
        self.assertEqual(cost1, 4 * DELTA)
        self.assertEqual(aligned1, "ACGT")
        self.assertEqual(aligned2, "____")
        
        # Both empty
        cost2, aligned1, aligned2 = efficient("", "")
        self.assertEqual(cost2, 0)
        self.assertEqual(aligned1, "")
        self.assertEqual(aligned2, "")
    
    def test_single_character(self):
        """Test alignment of single characters."""
        # Matching characters
        cost1, _, _ = efficient("A", "A")
        self.assertEqual(cost1, 0)
        
        # Mismatching characters
        cost2, _, _ = efficient("A", "C")
        self.assertEqual(cost2, ALPHA['A']['C'])
    
    def test_matches_basic(self):
        """Test that efficient algorithm matches basic algorithm results."""
        test_cases = [
            ("A", "A"),
            ("AC", "AG"),
            ("ACGT", "AGCT"),
            ("ACTG", "TACG"),
            ("AAAA", "TTTT"),
            ("ACG", ""),
            ("", "TGC"),
        ]
        
        for seq1, seq2 in test_cases:
            with self.subTest(seq1=seq1, seq2=seq2):
                cost_basic, aligned1_basic, aligned2_basic = basic(seq1, seq2)
                cost_efficient, aligned1_efficient, aligned2_efficient = efficient(seq1, seq2)
                
                # Costs must be identical
                self.assertEqual(
                    cost_basic, 
                    cost_efficient,
                    f"Cost mismatch for {seq1} vs {seq2}: basic={cost_basic}, efficient={cost_efficient}"
                )
                
                # Aligned sequence lengths must match
                self.assertEqual(len(aligned1_basic), len(aligned2_basic))
                self.assertEqual(len(aligned1_efficient), len(aligned2_efficient))
    
    def test_longer_sequences(self):
        """Test efficient algorithm with longer sequences."""
        seq1 = "ACGTACGTACGT"
        seq2 = "TGCATGCATGCA"
        
        cost, aligned1, aligned2 = efficient(seq1, seq2)
        
        # Verify basic properties
        self.assertIsInstance(cost, int)
        self.assertEqual(len(aligned1), len(aligned2))
        self.assertGreater(cost, 0)


class TestAlgorithmConsistency(unittest.TestCase):
    """Test that both algorithms produce consistent results."""
    
    def test_cost_consistency(self):
        """Verify both algorithms produce same cost."""
        test_sequences = [
            ("ACGT", "ACGT"),
            ("ACGT", "TGCA"),
            ("AAA", "TTT"),
            ("ACGTACGT", "TGCATGCA"),
            ("A", "ACGT"),
            ("ACGT", "A"),
        ]
        
        for seq1, seq2 in test_sequences:
            with self.subTest(seq1=seq1, seq2=seq2):
                cost_basic, _, _ = basic(seq1, seq2)
                cost_efficient, _, _ = efficient(seq1, seq2)
                
                self.assertEqual(
                    cost_basic, 
                    cost_efficient,
                    f"Algorithms disagree on cost for '{seq1}' vs '{seq2}'"
                )
    
    def test_alignment_length_consistency(self):
        """Verify both algorithms produce same alignment length."""
        test_sequences = [
            ("ACGT", "ACGT"),
            ("AC", "TG"),
            ("ACGT", "AG"),
        ]
        
        for seq1, seq2 in test_sequences:
            with self.subTest(seq1=seq1, seq2=seq2):
                _, aligned1_basic, aligned2_basic = basic(seq1, seq2)
                _, aligned1_efficient, aligned2_efficient = efficient(seq1, seq2)
                
                self.assertEqual(len(aligned1_basic), len(aligned2_basic))
                self.assertEqual(len(aligned1_efficient), len(aligned2_efficient))


class TestStringProcessor(unittest.TestCase):
    """Test string processing utilities."""
    
    def test_simple_input(self):
        """Test processing simple input without duplications."""
        lines = ["ACGT", "TGCA"]
        seq1, seq2 = processStrings(lines)
        
        self.assertEqual(seq1, "ACGT")
        self.assertEqual(seq2, "TGCA")
    
    def test_single_duplication(self):
        """Test processing with single duplication."""
        lines = ["AC", "1", "TG"]
        seq1, seq2 = processStrings(lines)
        
        # After index 1: AC -> A + AC + C = AACC
        self.assertEqual(seq1, "AACC")
        self.assertEqual(seq2, "TG")
    
    def test_multiple_duplications(self):
        """Test processing with multiple duplications."""
        lines = ["A", "0", "0", "C"]
        seq1, seq2 = processStrings(lines)
        
        # A -> A + A = AA (after index 0)
        # AA -> A + AA + A = AAAA (after index 0 again)
        self.assertEqual(seq1, "AAAA")
        self.assertEqual(seq2, "C")
    
    def test_case_normalization(self):
        """Test that sequences are normalized to uppercase."""
        lines = ["acgt", "tgca"]
        seq1, seq2 = processStrings(lines)
        
        self.assertEqual(seq1, "ACGT")
        self.assertEqual(seq2, "TGCA")
    
    def test_empty_input(self):
        """Test handling of empty input."""
        with self.assertRaises((ValueError, IndexError)):
            processStrings([])
    
    def test_invalid_index(self):
        """Test handling of invalid duplication index."""
        lines = ["AC", "10", "TG"]  # Index 10 is out of bounds for "AC"
        
        with self.assertRaises(IndexError):
            processStrings(lines)


class TestIOUtils(unittest.TestCase):
    """Test input/output utilities."""
    
    def setUp(self):
        """Create temporary directory for test files."""
        self.temp_dir = tempfile.mkdtemp()
    
    def tearDown(self):
        """Clean up temporary files."""
        import shutil
        shutil.rmtree(self.temp_dir, ignore_errors=True)
    
    def test_read_input(self):
        """Test reading input file."""
        # Create test input file
        test_file = os.path.join(self.temp_dir, "test_input.txt")
        with open(test_file, 'w') as f:
            f.write("ACGT\n")
            f.write("1\n")
            f.write("\n")  # Empty line (should be skipped)
            f.write("TGCA\n")
        
        lines = readInput(test_file)
        
        self.assertEqual(len(lines), 3)
        self.assertEqual(lines[0], "ACGT")
        self.assertEqual(lines[1], "1")
        self.assertEqual(lines[2], "TGCA")
    
    def test_read_nonexistent_file(self):
        """Test reading non-existent file."""
        with self.assertRaises(FileNotFoundError):
            readInput("nonexistent_file.txt")
    
    def test_write_output(self):
        """Test writing output file."""
        output_file = os.path.join(self.temp_dir, "test_output.txt")
        
        # Write test output
        writeOutput(
            cost=100,
            aligned1="ACGT",
            aligned2="A_GT",
            elapsed_time=12.345,
            peak_mem=2048,
            length=8,
            output_file=output_file
        )
        
        # Verify file was created
        self.assertTrue(os.path.exists(output_file))
        
        # Verify content
        with open(output_file, 'r') as f:
            lines = f.readlines()
        
        self.assertEqual(lines[0].strip(), "100")
        self.assertEqual(lines[1].strip(), "ACGT")
        self.assertEqual(lines[2].strip(), "A_GT")
        self.assertIn("12.345", lines[3])
        self.assertEqual(lines[4].strip(), "2048")


class TestCostConstants(unittest.TestCase):
    """Test cost constant configuration."""
    
    def test_alpha_symmetry(self):
        """Test that mismatch matrix is symmetric."""
        bases = ['A', 'C', 'G', 'T']
        
        for base1 in bases:
            for base2 in bases:
                self.assertEqual(
                    ALPHA[base1][base2],
                    ALPHA[base2][base1],
                    f"Matrix not symmetric for {base1}-{base2}"
                )
    
    def test_alpha_diagonal_zero(self):
        """Test that matching bases have zero cost."""
        bases = ['A', 'C', 'G', 'T']
        
        for base in bases:
            self.assertEqual(
                ALPHA[base][base],
                0,
                f"Matching {base}-{base} should have zero cost"
            )
    
    def test_delta_positive(self):
        """Test that gap penalty is positive."""
        self.assertGreater(DELTA, 0)
    
    def test_alpha_values_reasonable(self):
        """Test that mismatch penalties are reasonable."""
        bases = ['A', 'C', 'G', 'T']
        
        for base1 in bases:
            for base2 in bases:
                cost = ALPHA[base1][base2]
                self.assertGreaterEqual(cost, 0)
                self.assertLess(cost, 200)  # Reasonable upper bound


class TestIntegration(unittest.TestCase):
    """Integration tests for complete workflow."""
    
    def setUp(self):
        """Create temporary directory for test files."""
        self.temp_dir = tempfile.mkdtemp()
    
    def tearDown(self):
        """Clean up temporary files."""
        import shutil
        shutil.rmtree(self.temp_dir, ignore_errors=True)
    
    def test_end_to_end_basic(self):
        """Test complete workflow with basic algorithm."""
        # Create test input
        input_file = os.path.join(self.temp_dir, "input.txt")
        with open(input_file, 'w') as f:
            f.write("ACGT\n")
            f.write("TGCA\n")
        
        output_file = os.path.join(self.temp_dir, "output.txt")
        
        # Read input
        lines = readInput(input_file)
        seq1, seq2 = processStrings(lines)
        
        # Run alignment
        cost, aligned1, aligned2 = basic(seq1, seq2)
        
        # Write output
        writeOutput(cost, aligned1, aligned2, 10.0, 1024, len(seq1) + len(seq2), output_file)
        
        # Verify output exists
        self.assertTrue(os.path.exists(output_file))
    
    def test_end_to_end_efficient(self):
        """Test complete workflow with efficient algorithm."""
        # Create test input
        input_file = os.path.join(self.temp_dir, "input.txt")
        with open(input_file, 'w') as f:
            f.write("ACGT\n")
            f.write("TGCA\n")
        
        output_file = os.path.join(self.temp_dir, "output.txt")
        
        # Read input
        lines = readInput(input_file)
        seq1, seq2 = processStrings(lines)
        
        # Run alignment
        cost, aligned1, aligned2 = efficient(seq1, seq2)
        
        # Write output
        writeOutput(cost, aligned1, aligned2, 10.0, 1024, len(seq1) + len(seq2), output_file)
        
        # Verify output exists
        self.assertTrue(os.path.exists(output_file))


def run_tests(verbosity: int = 2) -> bool:
    """Run all tests with specified verbosity."""
    loader = unittest.TestLoader()
    suite = loader.loadTestsFromModule(sys.modules[__name__])
    runner = unittest.TextTestRunner(verbosity=verbosity)
    result = runner.run(suite)
    return result.wasSuccessful()


if __name__ == '__main__':
    # Run tests
    success = run_tests(verbosity=2)
    sys.exit(0 if success else 1)