// cykp.h  CYK Parser  header file
#ifndef CYKP_H
#define CYKP_H

#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
using namespace std;

// Primary type definitions

typedef string variable;
typedef set<variable> var_type;
typedef string terminal;
typedef set<terminal> ter_type;
typedef vector<string> alpha; // terminals and variables

class production // an entry in P 
{
  public:
    production(variable from_var)
              { V = from_var; /* w.clear() */ ; color = 0; }
    static bool smaller(production a, production b)
                       { if(a.V < b.V) return true;
                         if(a.V > b.V) return false;
                         alpha::const_iterator a_iter, b_iter=b.w.begin();
                         for(a_iter=a.w.begin(); a_iter!=a.w.end(); a_iter++)
                         {
                           if(b_iter == b.w.end()) return false;
                           if(*a_iter < *b_iter) return true;
                           if(*a_iter > *b_iter) return false;
                           b_iter++;
                         }
                         return false;
                       }
    bool operator ==(const production &b)
                    { if(b.V != V) return false;
                      alpha::const_iterator a_iter, b_iter=b.w.begin();
                      for(a_iter=w.begin(); a_iter!=w.end(); a_iter++)
                      {
                        if(b_iter == b.w.end()) return false;
                        if(*a_iter != *b_iter) return false;
                        b_iter++;
                      }
                      if(b_iter!=b.w.end()) return false;
                      return true;
                    }
    friend ostream &operator<<(ostream &stream, production p);
    variable V;
    alpha    w;
    int      color;
};

typedef vector<production> prod_type;  

// function prototypes
void cyk_eliminate(var_type &V, ter_type &T, prod_type &P, variable &S);
void cyk_chomsky(var_type &V, ter_type &T, prod_type &P, variable &S);
void cyk_greibach(var_type V, ter_type T, prod_type P, variable S);
bool cyk_parse(var_type &V, ter_type &T, prod_type &P, variable &S,
               string input_string);

extern int verbose; // verbose printout 0=none, greater than 3 is for debug
extern bool accept_null; // true if grammar accepts null string

#endif // CYKP_H