// cyk_parse.cpp  CYK Parser  Given G =(V, T, P, S) in Chomsky Normal Form
//                            accept or reject input string x
//                algorithm form book, p 140, Fig 6.8

#include "cykp.h"

// verbose amount to print is global

bool cyk_parse(var_type &V, ter_type &T, prod_type &P, variable &S, string x)
{
  var_type VV[60][60];   //  n+1 to make indexing nice
  bool B_OK;             // result of test B in V[i][k]
  bool C_OK;             // result of test C in V[i+k][j-k]
  bool Accepted = false; // can print "accepted"
  int n = x.size();      // number of terminals in string
  int i;                 // loop index
  int j;                 // loop index
  int k;                 // loop index
  
  prod_type::const_iterator p_iter; // loop through productions
  var_type::const_iterator  v_iter; // loop through set of variables
  
  if(verbose>=3) cout << "run CYK algorithm to build array, size="
                      << n << endl;

  if(n==0)
  {
    if(accept_null)
    {
      cout << "null string accepted by G, string is in L(G)" << endl;
      return true;
    }    
    else
    {
      cout << "null string rejected by G, string is not in L(G)" << endl;
      return false;
    }
  }

  // build first row of VV
  
  for(i=1; i<=n; i++) // loop through the symbols in x    1)
  {
    for(p_iter=P.begin(); p_iter!=P.end(); p_iter++)
    {
      if(p_iter->w.size()==1)
      {
        if(p_iter->w[0] == string(1,x[i-1]))
        VV[i][1].insert(p_iter->V); // link this variable  2)
      }
    }
  }

  if(verbose>=3)
  {
    cout << "Finished first row of VV table" << endl;
    for(i=1; i<=n; i++)
    {
      cout << "VV(" << i << ",1)= ";
      for(v_iter=VV[i][1].begin(); v_iter!=VV[i][1].end(); v_iter++)
      {
        cout << *v_iter << " ";
      }
      cout << endl;
    }
  }

  // build remainder of rows of VV

  for(j=2; j<=n; j++) // move down the VV matrix rows  3)
  {
    for(i=1; i<=n-j+1; i++) // move across VV          4)
    {
      // VV[i][j] = 0; automatic, initialized set      5)
      for (k=1; k<=j-1; k++) //                        6)
      {
        for(p_iter=P.begin(); p_iter!=P.end(); p_iter++) // productions
        {
          B_OK = false;
          C_OK = false;
          if(p_iter->w.size()==2)
          {
            if(VV[i][k].find(p_iter->w[0])!=VV[i][k].end()) B_OK = true;
            if(VV[i+k][j-k].find(p_iter->w[1])!=VV[i+k][j-k].end()) C_OK = true;
          }
          if (B_OK && C_OK)
            VV[i][j].insert(p_iter->V); // link this production
        }
      }
    }

    if(verbose>=3)
    {
      cout << "Finished " << j << " row of VV table" << endl;
      for(i=1; i<=n; i++)
      {
        cout << "VV(" << i << "," << j << ")= ";
        for(v_iter=VV[i][j].begin(); v_iter!=VV[i][j].end(); v_iter++)
        {
          cout << *v_iter << " ";
        }
        cout << endl;
      }
    }
  }

  // finished building VV table

  if(verbose>=3)
  cout << "finish CYK algorithm, check for S in VV[1][n]and thus Accepted "
       << endl;


  if(VV[1][n].find(S)!=VV[1][n].end())
  {
    cout << "string accepted by G, string is in L(G)" << endl;
    return true;
  }
  else
  {
    cout << "string rejected by G, string is not in L(G)" << endl;
    return false;
  }
} // end cyk_parse