import java.io.*;

class Alignment
	{
	private static int CHARACTERS_PER_ROW = 60;	// modify this to adjust the output
	protected Sequence seq1, seq2;
	protected GappedSequence gappedSeq1, gappedSeq2;
	protected String colons = "";
	protected String scorematrix;
	protected ScoreMatrix scoreMatrix;
	protected int alignmentScore = -88888888;

	    // the edit matrix and auxiliary matrices

	protected int[][] L, E, F;
	protected int imax, jmax;

	public Alignment(Sequence sequence1, Sequence sequence2, String matrix) throws ErrorInScoreMatrixException, ErrorInSequenceException
		{
		seq1 = sequence1;		
		seq2 = sequence2;		
		gappedSeq1 = new GappedSequence(seq1.getLength()+seq2.getLength());
		gappedSeq2 = new GappedSequence(seq1.getLength()+seq2.getLength());
		gappedSeq1.id = seq1.id.toString();
		gappedSeq2.id = seq2.id.toString();
		colons = new String();
		scorematrix = matrix;
		scoreMatrix = new ScoreMatrix();
		scoreMatrix.load(matrix);
		}

	public Alignment(Sequence sequence1, Sequence sequence2) throws ErrorInScoreMatrixException, ErrorInSequenceException
		{
		this (sequence1, sequence2, "pam250");
		}


	    // for a nonsense alignment, call this method:

	public void fillEditMatrix()
		{
		int i, j;
		int l1 = seq1.getLength() + 1;
		int l2 = seq2.getLength() + 1;

		// l1 and l2 are the sequence lengths + 1
		// and the edit matrix is an l1 x l2 - matrix:

		L = new int [l1][l2];
		}

	    // for a global alignment with linear gap costs, call this method:

	public void fillEditMatrix(int g) throws ErrorInSequenceException, ErrorInScoreMatrixException
		{
		int i, j;
		int l1 = seq1.getLength() + 1;
		int l2 = seq2.getLength() + 1;

		// l1 and l2 are the sequence lengths + 1
		// and the edit matrix is an l1 x l2 - matrix:

		L = new int [l1][l2];

		// initialization of array L...

		L[0][0] = 0;
		for (i=1; i<l1; i++)	L[i][0] = L[i-1][0] + g;
		for (i=1; i<l2; i++)	L[0][i] = L[0][i-1] + g;

		// fill in the 2-dim array...

		for (j=1; j<l2; j++)
			for (i=1; i<l1; i++)
				{
				L[i][j] = max((L[i-1][j]+g),L[i-1][j-1]+scoreMatrix.sim(seq1.getLetter(i),seq2.getLetter(j)),L[i][j-1]+g);
				}
		alignmentScore = L[l1-1][l2-1];
		}



	    // for a SW-alignment, call this method

	public void fillEditMatrix(int openGapPenalty, int extensionGapPenalty) throws ErrorInSequenceException, ErrorInScoreMatrixException
		{
		int i, j;
		int l1 = seq1.getLength() + 1;
		int l2 = seq2.getLength() + 1;

		// l1 and l2 are the sequence lengths + 1
		// and the edit matrix is an l1 x l2 - matrix:

		L = new int [l1][l2];
		E = new int [l1][l2];
		F = new int [l1][l2];

		// initialization of array L, E , F

		L[0][0] = 0;
		L[1][0] = L[0][1] = openGapPenalty;		

		for (i=2; i<l1; i++)	L[i][0] = L[i-1][0] + extensionGapPenalty;
		for (j=2; j<l2; j++)	L[0][j] = L[0][j-1] + extensionGapPenalty;
		for (i=1; i<l1; i++)	E[i][0] = -1000000000;
		for (j=1; j<l2; j++)	F[0][j] = -1000000000;

		// fill in the 2-dim arrays

		for (j=1; j<l2; j++)
			{
			for (i=1; i<l1; i++)
				{
				E[i][j] = max(L[i][j-1]+openGapPenalty, E[i][j-1]+extensionGapPenalty); 
				F[i][j] = max(L[i-1][j]+openGapPenalty, F[i-1][j]+extensionGapPenalty); 
				L[i][j] = max(0, E[i][j], L[i-1][j-1]+scoreMatrix.sim(seq1.getLetter(i),seq2.getLetter(j)), F[i][j]);
				
				if (L[i][j] > alignmentScore)	
					{
					alignmentScore = L[i][j];
					imax = i;
					jmax = j;
					}
				}
			}
		}


	    // backtracking for global alignment

     	public void backTracking(int g) throws ErrorInScoreMatrixException, ErrorInSequenceException
		{
		int i = L.length - 1;
		int j = L[0].length - 1;

		while (i>0 && j>0)
			{
			if (L[i][j] == (L[i-1][j] + g))
				align(seq1.getLetter(i--), '-');
			else if (L[i][j] == (L[i][j-1] +g))
				align('-', seq2.getLetter(j--));
			else	align(seq1.getLetter(i--), seq2.getLetter(j--));
			}
		if (i!=0)	while (i!=0)	align(seq1.getLetter(i--), '-');
		if (j!=0)	while (j!=0)	align('-', seq2.getLetter(j--));
		}


	    /****************************************************************************
	     ****** backtracking for Smith-Waterman-Alignment    ************************
	     **************************************************************************/

     	public void backTracking() throws ErrorInScoreMatrixException, ErrorInSequenceException
		{
		int i = imax;
		int j = jmax;
		boolean stop = false;

		System.out.println("Local Alignment ends at (" + i + ", " + j + ")"); 

		while (stop!=true && i>0 && j>0)
			{
			if (L[i][j] == 0)	stop = true;
			else if (L[i][j] == E[i][j])	align('-', seq2.getLetter(j--));
			else if (L[i][j] == F[i][j])	align(seq1.getLetter(i--), '-');
			else				align(seq1.getLetter(i--), seq2.getLetter(j--));
			}
		if (i!=0 && stop!=true)		while (i!=0 && L[i][j] != 0)	align(seq1.getLetter(i--), '-');
		if (j!=0 && stop!=true)		while (j!=0 && L[i][j] != 0)	align('-', seq2.getLetter(j--));

		System.out.println("Local Alignment begins at (" + i + ", " + j + ")"); 
		}


	public void align(char letter1, char letter2) throws ErrorInScoreMatrixException, ErrorInSequenceException
		{
		short sim;
		if (letter1 != '-' && letter2 != '-')	sim = scoreMatrix.sim(letter1, letter2);
		else	sim = -1;
		gappedSeq1.insLetter(letter1);
		gappedSeq2.insLetter(letter2);

	       	if (letter1==letter2)	colons = ':' + colons;
		else if (sim>=0)	colons = '.' + colons;
		else			colons = ' ' + colons;
		}
		

        public int getLength() { return(seq1.getLength()); }

	public void print() throws ErrorInSequenceException
		{
		int printedCharacters = 0;
		int length = gappedSeq1.getLength();

		System.out.println("\nAlignmentScore = " + alignmentScore);

		while (printedCharacters < length)
			{
			String row1, row2, row3;
			row1=row2=row3="";
			for (int i=printedCharacters; i<length && (i-printedCharacters) < CHARACTERS_PER_ROW; i++)
				{
				row1 += gappedSeq1.getLetter(i+1); 
				row2 += colons.charAt(i);
				row3 += gappedSeq2.getLetter(i+1); 
				}
			row1 += "   ";
			row3 += "   ";
			row1 += gappedSeq1.id;
			row3 += gappedSeq2.id;
			printedCharacters += CHARACTERS_PER_ROW;
			System.out.print("\n" + row1 + "\n" + row2 + "\n" + row3 + "\n");
			}
	        }		


	protected int max(int a, int b, int c)
		{
		if (c>b && c>a)	return(c);
		else return((b>a)?b:a);
		}

	protected int max(int a, int b, int c, int d)
		{
		if (d>c && d>b && d>a)	return(d);
		else if (c>b && c>a)	return(c);
		else return((b>a)?b:a);
		}

	protected int max(int a, int b) { return((b>a)?b:a); }
	}