/*********************************************************************
File: main.cpp
Author: Eric Breimer

Description: Reads the input from two files and writes them to 
two character vectors.  Computes the longest common subsequence (LCS) 
of the two character vectors and prints the input strings and LCS to 
cout.
*********************************************************************/
#include <vector>
#include <iostream>
#include <fstream>
#include <algorithm>

using std::vector;
using std::ifstream;
using std::reverse;
using std::cout;
using std::cerr;
using std::endl;

/*********************************************************************
Function: Read Input

Description:  Reads the characters from a file and writes them to a
character vector.

Input: File name (character array)
Output: Character vector
*********************************************************************/
vector<char> ReadInput(const char * name) {
  vector<char> input;
  char ch;
  ifstream in;
  in.open(name);
  if(in == NULL) {
    cerr << "Failure to open " << name << endl;
    return input;
  } 
  in >> ch; 
  while (in != NULL) {
    input.push_back(ch);
    in >> ch;
  }
  in.close();
  return input;
}

/*********************************************************************
Function: Print Input
Description:  Prints character vector to cout
Input: Character vector
*********************************************************************/
void PrintInput(const vector<char> & vec) {
  int x;
  for (x = 0; x < vec.size(); x++)
    cout << vec[x];
  cout << endl;
}

/*********************************************************************
Function: Max
Input: Integers a and b
Output: Maximum of a and b
*********************************************************************/
int Max(const int a, const int b) {
  if (a > b)
    return a;
  else
    return b;
}

/*********************************************************************
Function: Compute LCS

Description:  Computes the longest common subsequence of two character
vectors

Input: Character vectors A and B
Output: Character vector LCS
*********************************************************************/
vector<char> ComputeLCS(const vector<char> & A, 
			const vector<char> & B) {
  int n = A.size();             // Size of input 1
  int m = B.size();             // Size of input 2
  vector<char> LCS;             // LCS vector
  vector<int> temp;             // Temp vector
  vector<vector<int> > M;       // Dynamic programming matrix
  int i, j;                     // Loop counters

  for (i = 0; i <= n; i++)      // Initialize matrix
    temp.push_back(0);
  for (j = 0; j <= m; j++)
    M.push_back(temp);

  // ADD CODE HERE
  // -------------
  // Compute each cell of the matrix.
  // You should use the computation described in the lab
  // It is important that the values be computed in the
  // correct order.
  // Hint:  this should be a simple nested loop
  for (j = 0; j < m; j++)        
    for (i = 0; i < n; i++)
      if (A[i]==B[j])
	M[j+1][i+1] = M[j][i] + 1;
      else
        M[j+1][i+1] = Max(M[j+1][i],M[j][i+1]);


  // ADD CODE HERE
  // -------------
  // Backtrack over the matrix and reconstruct the LCS
  // Hint: this should be a while loop that starts with
  // i = n; j = m; and backtracks until either i or j 
  // equals zero.
  i = n;
  j = m;
  while ((i > 0) && (j > 0)) {
    if (A[i-1]==B[j-1]) {
      LCS.push_back(A[i-1]);
      i--;
      j--;
    }
    else if (M[j-1][i] > M[j][i-1])
      j--;
    else 
      i--;
  }
  // ADD CODE HERE
  // -------------
  // After backtracking it is necessary to reverse the LCS.
  // You can write your own reverse algorithm or use the STL reverse
  reverse(LCS.begin(),LCS.end());
  return LCS;
}

/*********************************************************************
Function: Main
*********************************************************************/
int main() {
  vector<char> A;               // Input 1 vector
  vector<char> B;               // Input 2 vector                
  vector<char> LCS;             // LCS vector
  char file1[] = "input1.txt";  // Input 1 file name
  char file2[] = "input2.txt";  // Input 2 file name

  A = ReadInput(file1);         // Read input 1
  B = ReadInput(file2);         // Read input 2
  LCS = ComputeLCS(A,B);        // Compute LCS

  cout << file1 << endl;        // Print input 1
  PrintInput(A);
  cout << endl;

  cout << file2 << endl;        // Print input 2
  PrintInput(B);
  cout << endl;

  cout << "LCS" << endl;        // Print LCS
  PrintInput(LCS);
  cout << endl;
 
  return 0;
}