// cyk.cpp   Given a grammar, G, and a string, x, determine if x in L(G)
//
//           input string x of length n, n>0
//           CFG, context free grammar in Chomsky normal form
//           G = (V, T, P, S) where V is the set of variables 
//               T is the set of terminal symbols, symbols in the string x
//               P is the set of productions of the forms A -> a  and A -> B C
//               which is Chomsky normal form, when A, B and C are variables
//               in V and 'a' is a variable in T, with exactly these two forms.
//               S is the start symbol
//
//   P1[i] i=1..np1 is the A -> a productions
//   P2[i] i=1..np2 is the A -> B C productions
//   x[i]  i=0..n-1 is the input string
//   subscripting starts at 1


#include <iostream>
#include <cstdlib>
#include <fstream>
#include "cyk.h"

using namespace std;

void cyk(char x[], int n, Prod1 P1[], int np1, Prod2 P2[], int np2)
{
  int nvar;             // number of variables
  int nter;             // number of termo
  int i, j, k, ip;      // loop variables
  bool found;           // used in searching lists (sets)

  Variable Var[100];    // simple array for variables

  Terminal Ter[100];    // simple array for terminals

  class List
  {
    public:
      List(Variable v1, List * next1){ v=v1; next=next1;}
      Variable v;
      List * next;
  };

  List * V[60][60]; //  n+1 to make indexing nice
  List * Link;      // working variable
  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"

  cout << "CYK starting" << endl;
  cout << "Input string x=" << x << " of length " << n << endl << endl;
  if(n<2) exit(0);

  cout << "Productions of type A -> a" << endl;
  for (i=1; i<=np1; i++)  // print P1 productions
    cout << P1[i].A  << " -> " <<  P1[i].alpha << endl;
  cout << endl;

  cout << "Productions of type A -> B C" << endl;
  for (i=1; i<=np2; i++)   // print P2 productions
    cout << P2[i].A << " -> " << P2[i].B << "  " << P2[i].C << endl;
  cout << endl;

  // find all unique variables in P1 and P2
  nvar = 0; // increment before store, loop to <=nvar
  for (i=1; i<=np1; i++)  // search P1 productions
  {
    found = false;
    for (j=1; j<=nvar; j++) found = found || (P1[i].A == Var[j]);
    if (!found) { nvar++; Var[nvar] = P1[i].A;}
  }

  for (i=1; i<=np2; i++)   // search P2 productions
  {
    found = false;
    for (j=1; j<=nvar; j++) found = found || (P2[i].A == Var[j]);
    if (!found) { nvar++; Var[nvar] = P2[i].A;}

    found = false;
    for (j=1; j<=nvar; j++) found = found || (P2[i].B == Var[j]);
    if (!found) { nvar++; Var[nvar] = P2[i].B;}

    found = false;
    for (j=1; j<=nvar; j++) found = found || (P2[i].C == Var[j]);
    if (!found) { nvar++; Var[nvar] = P2[i].C;}
  }

  cout << "Var the set of variables" << endl;
  for (i=1; i<= nvar; i++)   // print variables
    cout << Var[i] << "   ";
  cout << endl << endl;

  // find all unique terminals in P1, none in P2
  nter = 0;     // increment before store, test <= in loops
  for (i=1; i<=np1; i++)  // search P1 productions
  {
    found = false;
    for (j=1; j<=nter; j++) found = found || (P1[i].alpha == Ter[j]);
    if (!found) { nter++; Ter[nter] = P1[i].alpha;} 
  }

  cout << "Ter the set of terminals" << endl;
  for (i=1; i<=nter; i++)   // print terminals
    cout << Ter[i] << "  ";
  cout << endl << endl;

  cout << "All data is in" << endl << endl;


  // be sure array is initialized to nulls
  for (i=0; i<=n; i++)
    for (j=0; j<=n; j++)
      V[i][j] = NULL;

  cout << "run CYK algorithm to build array" << endl;
  for (i=1; i<=n; i++) // loop through the symbols in x
  {
    cout << "i= " << i << " ,x[i-1]= " << x[i-1] << endl;
    for (ip=1; ip<=np1; ip++)    // loop through type 1 productions
    {
      if (P1[ip].alpha == x[i-1])
      {
        Link = V[i][1];      // check if already linked
        found = false;
        while (Link != NULL)
	{
          if (Link->v == P1[ip].A) found = true;
          Link = Link->next;
	}
        if (!found)
	{
          V[i][1] = new List(P1[ip].A, V[i][1]); // link this variable
        }
      }
    }
  }
  cout << "Finished first row of V table" << endl;

  for (i=1; i<=n; i++)
  {
    if (V[i][1] != NULL)
    {
      Link = V[i][1];
      while (Link != NULL)
      {
        cout << Link->v << " ";
        Link = Link->next;
      }
    }
    else
    {
      cout << "null ";
    }
    if (i==n) break;
    cout << ",";
  }
  cout << endl << endl;

  for (j=2; j<=n; j++)
  {
    for (i=1; i<=n-j+1; i++)
    {
      V[i][j] = NULL;
      for (k=1; k<=j-1; k++)
      {
        for (ip=1; ip<=np2; ip++)
        {
          B_OK = false;
          C_OK = false;
          if (V[i][k] != NULL)
	  {
            Link = V[i][k];
            while (Link != NULL)
	    {
              if (P2[ip].B == Link->v)
	      {
                B_OK = true;
                break;
	      }
              Link = Link->next;
            }
          }
          if (V[i+k][j-k] != NULL)
	  {
            Link = V[i+k][j-k];
            while (Link != NULL)
	    {
              if (P2[ip].C == Link->v)
	      {
                C_OK = true;
                break;
              }
              Link = Link->next;
            }
          }
          if (B_OK && C_OK)
	  {
            Link = V[i][j];      // check if already linked
            found = false;
            while (Link != NULL)
	    {
              if (Link->v == P2[ip].A) found = true;
              Link = Link->next;
	    }
            if (!found)
            {
              V[i][j] = new List(P2[ip].A, V[i][j]); // link this variable
            }
          }      
        }
      }
    }
    cout << "Finished " << j << " row of V table" << endl;

    for (i=1; i<=n; i++)
    {
      if (V[i][j] != NULL)
      {
        Link = V[i][j];
        while (Link != NULL)
	{
          cout << Link->v << " ";
          Link = Link->next;
        }
      }
      else
      {
        cout << "null ";
      }
      if (i==n) break;
      cout << ",";
    }
    cout << endl;
  }
  cout << endl;

  // finished building V table

  cout << "finish CYK algorithm, check for S and thus Accepted " << endl;
  cout << endl;
  Link = V[1][n];
  while (Link != NULL)
  {
    if (Link->v == 'S')
    {
      Accepted = true;
      break;
    }
    Link = Link->next;
  }
  if (Accepted)
    cout << "x accepted by G, x is in L(G)" << endl;
  else
    cout << "x rejected by G, x is not in L(G)" << endl;

} // end CYK