package source;

public class LongestCommonSubsequence {

	/**
	 * @param args
	 */
	private static Cell[][] table;
	private static char[] X;
	private static char[] Y;
	private static int count = 0;
	
	public static void createTable(int rows, int cols) {
		table = new Cell[rows+1][cols+1];
		for (int j = 0; j <= rows; j++)
			for (int i = 0; i <= cols; i++){
				if (i == 0 || j == 0)
					table[j][i] = new Cell(0,0);
				else
					table[j][i] = new Cell(-1, -2);
				//table[j][i].setCost(-1);
				//table[j][i].setDir(-2);
			}
	}
	public static int findLCS() {
		createTable(X.length, Y.length);
		int cost = LCSLookup(X.length, Y.length);
		return cost;
	}
	public static int LCSLookup(int j, int i) {
		if (i == 0 || j == 0) {
			count++;
			return 0;
		}
		if (table[j][i].getCost()!= -1) {
			count++;
			return table[j][i].getCost();
		}
		if (X[j-1] == Y[i-1]) {
			table[j][i].setCost(LCSLookup(j-1,i-1) + 1);
			table[j][i].setDir(0);
			count++;
			return table[j][i].getCost();
		}
		else {
			count++;
			table[j][i].setCost(Math.max(LCSLookup(j, i-1), LCSLookup(j-1,i)));
			if (table[j][i].getCost()== table[j][i-1].getCost())
				table[j][i].setDir(-1);
			else 
				table[j][i].setDir(1);
			return table[j][i].getCost();
		}
	}
	public static int getCount(){
		return count;
	}
	public static void resetCount(){
		count = 0;
	}
	public static String getSubsequence() {
		String subSeq = "";
		int i = table[0].length-1;
		int j = table.length-1;
		while (j != 0 && i != 0) {
			if (table[j][i].getDir() == 0) {
				subSeq = Y[i-1] + subSeq;
				i--;
				j--;
			}
			else if(table[j][i].getDir() == 1){
				j--;
			}
			else {
				i--;
			}
		}
		return subSeq;
	}
		
	
	public static void main(String[] args) {
		char[] XX = {'G','A', 'T','C', 'T', 'A', 'G'};
		char[] YY = {'A', 'G', 'C','T','T','A', 'C','A', 'G','C'};
		X = XX;
		Y = YY;
		//createTable(Y.length, X.length);
		int seqLength = findLCS();
		System.out.println ("Sequence X =" + X.length);
		System.out.println("Sequnce Y = " + Y.length);
		System.out.println("The LCS is " + getSubsequence()+ "  length = "+ seqLength);
		System.out.println("Number of call to LCSLookup = " + count);
		// TODO Auto-generated method stub

	}

}