//
// Caitlin Howell
// CS577, Homework 4
// LCS Dynamic Programming Algorithm Implemenation
// Due December 9, 1997
//
// File LCSTable.java
//
// Class LCSTable
//
// this is the 2 dimensional array which stores the LCS arrows and 
// total match values

// LCSCell is the class that makes up each individual cell in the
// table we are using to determine the longest common string.

import LCSCell;

public class LCSTable
{
// s1 and s1 are the two strings that we are finding the LCS of
	private String s1,s2;

// rows and columns are the number of rows and columns in the table
	private int rows;
	private int columns;

// LTable is the table we will use to determine the LCS
	private LCSCell[][] LTable;


// LCS stores the longest common subsequence
	private String LCS = new String("");

	public LCSTable(String string1, String string2)
	{
		s1 = new String(string1);
		s2 = new String(string2);
		columns = s1.length() + 1;
		rows = s2.length() + 1;
		LTable = new LCSCell[rows][];
		for(int i = 0; i < rows; i++)
		{
			LTable[i] = new LCSCell[columns];
			for(int j = 0; j < columns; j++)
			{
			  LTable[i][j] = new LCSCell(0,'+');
			}
		}
	}

// Init carries out the calculations outlined in the algorithm on
// page 317 of the textbook.

	public void init()
	{
		int temp1, temp2;

		for (int l = 1; l < rows; l++)
		{ 
			LTable[l][0].changeTotal(0);
			LTable[l][0].changeArrow('+');
		}
		for (int k = 0; k < columns; k++)
		{
			LTable[0][k].changeTotal(0);
			LTable[0][k].changeArrow('+');
		}
		
		for (int i = 1; i < rows; i++)
		{
		  for (int j = 1; j < columns; j++)
		  {
			if (s1.charAt(j-1) == s2.charAt(i-1))
			{
				temp1 = LTable[i-1][j-1].total();
				LTable[i][j].changeTotal(temp1+1);
				LTable[i][j].changeArrow('\\');
			}
			else
			{
				temp1 = LTable[i-1][j].total();
				temp2 = LTable[i][j-1].total();
				if (temp1 >= temp2)
				{
					LTable[i][j].changeTotal(temp1);
					LTable[i][j].changeArrow('^');
				}
				else
				{
					LTable[i][j].changeTotal(temp2);
					LTable[i][j].changeArrow('<');
				}
			}
		  }
		}
	} 


// LCS length returns the longest common string length (stored in the
// bottom right of the array, as in the textbook

	public int lcsLength()
	{
		return LTable[rows-1][columns-1].total();
	}
	
// printTbl returns a text formatted version of the array
// so that it can be easily printed out

	public String printTbl()
	{
		String accu = new String("");
		accu = accu.concat("     "); 
		for (int i = 0; i < columns - 1; i++)
		{
			accu = accu.concat("  ");
			accu = accu.concat(String.valueOf(s1.charAt(i)));
		}
		accu = accu.concat("\n");

 		for (int k = 0; k < rows; k++)
		{
			if (k > 0)
			{
			  accu = accu.concat(String.valueOf(s2.charAt(k-1)));
			  accu = accu.concat("  ");
			}
			else accu = accu.concat("   ");

			for (int l = 0; l < columns; l++)
			{

			  accu = accu.concat(String.valueOf(LTable[k][l].arrow()));
			  accu = accu.concat(String.valueOf(LTable[k][l].total()));
			  accu = accu.concat(" ");
			}
			accu = accu.concat("\n");
		}
		return accu;
	}


// LCS calls recursiveLCS, which implements the recursive solution on
// page 318 of the textbook.
// LCS returns the longest common string.

	public String lcs()
	{
		LCS = "";

		recursiveLCS(s2,rows-1,columns-1);
		System.out.println(LCS);
		return LCS;
	}

	private String recursiveLCS(String X, int i, int j)
	{
		if ((i == 0) || (j == 0))
		{
			return "";
		}
		if (LTable[i][j] != null) {
		  if (LTable[i][j].arrow() == '\\')
		  {
			recursiveLCS(X, i-1, j-1);
			String temp = String.valueOf(X.charAt(i-1));
			LCS = LCS.concat(temp);
			System.out.println(temp);
		  }
	  	  else if (LTable[i][j].arrow() == '^')
		  {
			recursiveLCS(X,i-1,j);
		  }
		  else
		  {
			recursiveLCS(X,i,j-1);
		  }
		}
		return "";
	}
}