// cyk_greibach.cpp  CYK reduce grammar to Greiback Normal Form
//                   and output it to file  greibach.pda
//                   for use in a PDA
// corrections 4/3/01 JSS

#include "cykp.h"

void cyk_greibach(var_type V, ter_type T, prod_type P, variable S)
                  // parameters are input only, not modified
{
  vector<string> A; // the A[k] in pseudo code
  vector<string> B; // the B[k] in pseudo code
  var_type::const_iterator iter;
  int m = V.size();            // loop limit in pseudo code
  int k;                       // loop variable in pseudo code
  int j;                       // loop variable in pseudo code
  int i;                       // misc loop variable
  prod_type P1;                // swaping temporary for productions
  prod_type P2;                // the other swap temporary
                               // (can't remove in loop)
  prod_type::iterator p1_iter; // for loop through productions
  prod_type::iterator p2_iter; // for loop within loop through productions
  production tp("");           // temporary production
  alpha::iterator a_iter;      // for loop through right side of production
  int kk;                      // additional loop variable

  if(verbose>=3) cout << "generating greiback.pda" << endl;

  // the variables are ordered, arbitrarily, yet fixed, A and B pairs
  // no requirement on ordering productions, sorted at end for checking
  if(verbose>=4) cout << "k  A[k]     B[k]" << endl;
  k = 0;
  for(iter=V.begin(); iter!=V.end(); iter++)
  {
    A.push_back(*iter);
    B.push_back("G_"+ *iter);
    if(verbose>=4) cout << k++ << "  " << *iter << "   "
                        << "G_"+ *iter << endl;
  }
  P1 = P;
  
  for(kk=0; kk<m; kk++) {  // must repeat
    P2.clear();
    for(k = 0; k < m; k++) {  // pseudo code 1)
      if(verbose>=5) cout << "kk=" << kk << ", k=" << k << endl;
      if(verbose>=5) cout << "A[k]=" << A[k] << endl;
      for(p1_iter=P1.begin(); p1_iter!=P1.end(); p1_iter++)
        p1_iter->color = 0; // later a 1 will mean delete
      for(j = 0; j < k; j++) {  // pseudo code 2)
        if(verbose>=6) {
			cout << "kk=" << kk << ", k=" << k << ", j=" << j << endl;
        	cout << "A[j]=" << A[j] << endl;
		}
        for(p1_iter=P1.begin(); p1_iter!=P1.end(); p1_iter++) { //pseudo code 3)
          if(p1_iter->V==A[k] && p1_iter->w[0]==A[j] && p1_iter->color==0) {
            if(verbose>=4) 
				cout << "found 3 " << A[k] << " -> " << A[j] << endl;
            for(p2_iter=P1.begin(); p2_iter!=P1.end(); p2_iter++) { // pscode 4)
              if(p2_iter->V==A[j] && p2_iter->color==0) {
                tp = *p2_iter;
                tp.V = A[k];
                for(i=1; i<p1_iter->w.size(); i++)
                  tp.w.push_back(p1_iter->w[i]); // pseudo code 5)
                P2.push_back(tp);
                if(verbose>=4) {
                  cout << "adding 5 " << tp.V << " ->";
                  for(a_iter=tp.w.begin(); a_iter!=tp.w.end(); a_iter++)
                    cout << "  " << *a_iter;
                  cout << endl;
                }
              }
            }
            p1_iter->color = 1; // delete later  pseudo code 6)
            if(verbose>=4) {
              cout << "deleting 6 " << p1_iter->V << " ->";
              for(a_iter=p1_iter->w.begin(); a_iter!=p1_iter->w.end(); a_iter++)
                cout << "  " << *a_iter;
              cout << endl;
            }
          }
        }
      } // end  for(j=

      // fix up P1 for next section
      for(p1_iter=P1.begin(); p1_iter!=P1.end(); p1_iter++)
                       if(p1_iter->color==0) P2.push_back(*p1_iter);
      P1 = P2;
      P2.clear();
      // sort, delete duplicates and print productions
      tp = production("");
      sort(P1.begin(), P1.end(), production::smaller );
      for(p1_iter=P1.begin(); p1_iter!=P1.end(); p1_iter++)
      {
        if(tp == *p1_iter) continue; // delete
        if(verbose>2) cout << *p1_iter << endl;
        tp = *p1_iter;
        P2.push_back(tp);
      }
      P1 = P2;
      P2.clear();

      for(p1_iter=P1.begin(); p1_iter!=P1.end(); p1_iter++) { // pseudo code 7)
        if(p1_iter->V==A[k] && p1_iter->w[0]==A[k] && p1_iter->color==0) {
          if(verbose>=4) 
			cout << "found 7 " << A[k] << " -> " << A[k] << endl;
          tp = production(B[k]);
          for(i=1; i<p1_iter->w.size(); i++)
            tp.w.push_back(p1_iter->w[i]);
          P2.push_back(tp); // pseudo code 8)
          if(verbose>=4) {
            cout << "adding 8 " << tp.V << " ->";
            for(a_iter=tp.w.begin(); a_iter!=tp.w.end(); a_iter++)
              cout << "  " << *a_iter;
            cout << endl;
          }
          tp.w.push_back(B[k]);
          P2.push_back(tp); // also pseudo code 8)
          if(verbose>=4) {
            cout << "adding 8 " << tp.V << " ->";
            for(a_iter=tp.w.begin(); a_iter!=tp.w.end(); a_iter++)
              cout << "  " << *a_iter;
            cout << endl;
          }
          p1_iter->color = 1; // delete later  pseudo code 9)
          if(verbose>=4) {
            cout << "deleting 9 " << p1_iter->V << " ->";
            for(a_iter=p1_iter->w.begin(); a_iter!=p1_iter->w.end(); a_iter++)
              cout << "  " << *a_iter;
            cout << endl;
          }

          for(p2_iter=P1.begin(); p2_iter!=P1.end(); p2_iter++) {// pscode 10)
            if(p2_iter->V==A[k] && p2_iter->w[0]!=A[k] && p2_iter->color==0) {
              if(verbose>=4) 
			    cout << "found 10 " << A[k] << " -> !=" << endl;
              tp = *p2_iter;
              tp.w.push_back(B[k]);
              P2.push_back(tp); // also pseudo code 11)
              if(verbose>=4) {
                cout << "adding 11 " << tp.V << " ->";
                for(a_iter=tp.w.begin(); a_iter!=tp.w.end(); a_iter++)
                  cout << "  " << *a_iter;
                cout << endl;
              }
            }
          }
        }
      }
      // fix up P1 for next section
      for(p1_iter=P1.begin(); p1_iter!=P1.end(); p1_iter++)
                       if(p1_iter->color==0) P2.push_back(*p1_iter);
      P1 = P2;
      P2.clear();
      // sort, delete duplicates and print productions
      tp = production("");
      sort(P1.begin(), P1.end(), production::smaller );
      for(p1_iter=P1.begin(); p1_iter!=P1.end(); p1_iter++)
      {
        if(tp == *p1_iter) continue; // delete
        if(verbose>2) cout << *p1_iter << endl;
        tp = *p1_iter;
        P2.push_back(tp);
      }
      P1 = P2;
      P2.clear();


      if(verbose>=6) cout << "fix up deletes in P1" << endl;
      // fix up P1 for next iteration
      for(p1_iter=P1.begin(); p1_iter!=P1.end(); p1_iter++)
      {
        if(p1_iter->color==0) P2.push_back(*p1_iter);
      }
      P1 = P2;
      P2.clear();
      // sort, delete duplicates and print productions
      tp = production("");
      sort(P1.begin(), P1.end(), production::smaller );
      for(p1_iter=P1.begin(); p1_iter!=P1.end(); p1_iter++)
      {
        if(tp == *p1_iter) continue; // delete
        if(verbose>2) cout << *p1_iter << endl;
        tp = *p1_iter;
        P2.push_back(tp);
      }
      P1 = P2;
      P2.clear();

      if(verbose>=6) // detailed printout
      {
        cout << "productions are now:" << endl;
        for(p1_iter=P1.begin(); p1_iter!=P1.end(); p1_iter++)
        {
          cout << p1_iter->V << " ->" ;
          for(a_iter=p1_iter->w.begin(); a_iter!=p1_iter->w.end(); a_iter++)
          {
            cout << "  " << *a_iter ;
          }
          cout << endl;
        }
      }
    } // end  for(k=

    // sort, delete duplicates and print productions
    tp = production("");
    sort(P1.begin(), P1.end(), production::smaller );
    for(p1_iter=P1.begin(); p1_iter!=P1.end(); p1_iter++)
    {
      if(tp == *p1_iter) continue; // delete
      if(verbose>2) cout << *p1_iter << endl;
      tp = *p1_iter;
      P2.push_back(tp);
    }
    P1 = P2;
    P2.clear();

  } // end  for(kk=
  if(verbose>=4) cout << "Greibach pass 1 complete" << endl;  



  // Pass2 of Greibach  A[k] -> A[kk] gamma gets all A[kk] replaced
  for(kk=m-1; kk>0; kk--)
  {
    for(k=kk-1; k>=0; k--)
    {
      if(verbose>=4) cout << "Greiback Pass2 kk=" << kk << ", k=" << k << endl;
      if(verbose>=4) cout << "A[kk]=" << A[kk] << ", A[k]=" << A[k] << endl;
      for(p1_iter=P1.begin(); p1_iter!=P1.end(); p1_iter++) // through productions
      {
        if(p1_iter->V==A[k] && p1_iter->w[0]==A[kk] && p1_iter->color==0)
        {
          if(verbose>=4) cout << "found sub " << A[k] << " -> " << A[kk] << " gamma" << endl;
          for(p2_iter=P1.begin(); p2_iter!=P1.end(); p2_iter++) // substitute
          {
            if(p2_iter->V==A[kk])
            {
              tp = *p2_iter;
              tp.V = A[k];
              for(i=1; i<p1_iter->w.size(); i++)
              {
                tp.w.push_back(p1_iter->w[i]); // keep gamma
              }
              P2.push_back(tp);
              if(verbose>=4)
              {
                cout << "adding substitute " << tp.V << " ->";
                for(a_iter=tp.w.begin(); a_iter!=tp.w.end(); a_iter++)
                {
                  cout << "  " << *a_iter;
                }
                cout << endl;
              }
            }
          }
          p1_iter->color = 1; // delete later
          if(verbose>=4)
          {
            cout << "deleting in pass2 " << p1_iter->V << " ->";
            for(a_iter=p1_iter->w.begin(); a_iter!=p1_iter->w.end(); a_iter++)
            {
              cout << "  " << *a_iter;
            }
            cout << endl;
          }
        }
      }
    }
    if(verbose>=6) cout << "fix up deletes in P1" << endl;
    // fix up P1 for next iteration
    for(p1_iter=P1.begin(); p1_iter!=P1.end(); p1_iter++)
    {
      if(p1_iter->color==0) P2.push_back(*p1_iter);
    }
    P1 = P2;
    P2.clear();

    if(verbose>=6) // detailed printout
    {
      cout << "Pass2 productions are now:" << endl;
      for(p1_iter=P1.begin(); p1_iter!=P1.end(); p1_iter++)
      {
        cout << p1_iter->V << " ->" ;
        for(a_iter=p1_iter->w.begin(); a_iter!=p1_iter->w.end(); a_iter++)
        {
          cout << "  " << *a_iter ;
        }
        cout << endl;
      }
    }    
  }

  if(verbose>=4) cout << "Greibach pass 2 complete, sort and delete duplicates" << endl;  

  // sort, delete duplicates and print productions
  tp = production("");
  sort(P1.begin(), P1.end(), production::smaller );
  for(p1_iter=P1.begin(); p1_iter!=P1.end(); p1_iter++)
  {
    if(tp == *p1_iter) continue; // delete
    if(verbose>2) cout << *p1_iter << endl;
    tp = *p1_iter;
    P2.push_back(tp);
  }
  P1 = P2;
  P2.clear();

  if(verbose>=4) cout << "Greibach Pass3, G_* -> A* substitute" << endl;
  for(k=0; k<m; k++)
  {
    for(p1_iter=P1.begin(); p1_iter!=P1.end(); p1_iter++) // through productions
    {
      if(p1_iter->w[0]==A[k] && p1_iter->color==0)
      {
        if(verbose>=4) cout << "found sub 3 " << p1_iter->V << " -> " << A[k] << " gamma" << endl;
        for(p2_iter=P1.begin(); p2_iter!=P1.end(); p2_iter++) // substitute
        {
          if(p2_iter->V==A[k])
          {
            tp = *p2_iter;
            tp.V = p1_iter->V;
            for(i=1; i<p1_iter->w.size(); i++)
            {
              tp.w.push_back(p1_iter->w[i]); // keep gamma
            }
            P2.push_back(tp);
            if(verbose>=4)
            {
              cout << "adding substitute 3 " << tp.V << " ->";
              for(a_iter=tp.w.begin(); a_iter!=tp.w.end(); a_iter++)
              {
                cout << "  " << *a_iter;
              }
              cout << endl;
            }
          }
        }
        p1_iter->color = 1; // delete later
        if(verbose>=4)
        {
          cout << "deleting in pass3 " << p1_iter->V << " ->";
          for(a_iter=p1_iter->w.begin(); a_iter!=p1_iter->w.end(); a_iter++)
          {
            cout << "  " << *a_iter;
          }
          cout << endl;
        }
      }
    }
  }
  if(verbose>=6) cout << "fix up deletes in P1" << endl;
  // fix up P1 for next iteration
  for(p1_iter=P1.begin(); p1_iter!=P1.end(); p1_iter++)
  {
    if(p1_iter->color==0) P2.push_back(*p1_iter);
  }
  P1 = P2;
  P2.clear();

  if(verbose>=4) cout << "Greibach pass 3 complete, sort and delete duplicates" << endl;  

  // sort, delete duplicates and print productions
  tp = production("");
  sort(P1.begin(), P1.end(), production::smaller );
  for(p1_iter=P1.begin(); p1_iter!=P1.end(); p1_iter++)
  {
    if(tp == *p1_iter) continue; // delete
    if(verbose>0) cout << *p1_iter << endl;
    tp = *p1_iter;
    P2.push_back(tp);
  }
  P1 = P2;
  P2.clear();

  // Clean out some redundant stuff that may have created
  cyk_eliminate(V, T, P1, S);

  // open output file and write
  ofstream file_out;
  file_out.open("greibach.pda");
  if(!file_out)
  {
    cout << "can not open greibach.pda for writing. bye!" << endl;
    return;
  }
  file_out << "// greibach.pda from cykp" << endl;
  file_out << endl;
  file_out << "start " << S << endl;
  file_out << endl;
  
  for(iter=T.begin(); iter!=T.end(); iter++) // output terminals
  {
    file_out << "terminal " << *iter << " ;" << endl;
  }
  file_out << endl;
  
  for(iter=V.begin(); iter!=V.end(); iter++) // output variables
  {
    file_out << "variable " << *iter << " ;" << endl;
  }
  file_out << endl;
  
  for(p1_iter=P1.begin(); p1_iter!=P1.end(); p1_iter++) // output productions
  {
    file_out << p1_iter->V << " ->" ;
    for(a_iter=p1_iter->w.begin(); a_iter!=p1_iter->w.end(); a_iter++)
    {
      file_out << "  " << *a_iter ;
    }
    file_out << " ;" << endl;
  }
  file_out << "enddef" << endl;
  file_out.close();
  if(verbose>=4) cout << "greibach finished" << endl << endl;
  return;
}