#include <stdio.h>

#include "defs.h"

short *itemset;
short *itemsetend;
unsigned *ruleset;

static unsigned *first_derives;
static unsigned *EFF;


void set_EFF(void)
{
unsigned *row;
int symbol;
short *sp;
int rowsize;
int i;
int rule;

  rowsize = WORDSIZE(nvars);
  EFF = NEW2(nvars * rowsize, unsigned);

  row = EFF;
  for (i = start_symbol; i < nsyms; i++)
    {
	 sp = derives[i];
	 for (rule = *sp; rule > 0; rule = *++sp)
	   {
	   symbol = ritem[rrhs[rule]];
	   if (ISVAR(symbol))
	     {
		  symbol -= start_symbol;
		  SETBIT(row, symbol);
	     }
	   }
	row += rowsize;
   }

  reflexive_transitive_closure(EFF, nvars);

#ifdef	DEBUG
  print_EFF();
#endif
}


void set_first_derives(void)
{
unsigned *rrow;
unsigned *vrow;
int j;
unsigned mask;
unsigned cword;
short *rp;

int rule;
int i;
int rulesetsize;
int varsetsize;

  rulesetsize = WORDSIZE(nrules);
  varsetsize = WORDSIZE(nvars);
  first_derives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize;

  set_EFF();

  rrow = first_derives + ntokens * rulesetsize;
  for (i = start_symbol; i < nsyms; i++)
    {
    vrow = EFF + ((i - ntokens) * varsetsize);
    cword = *vrow++;
    mask = 1;
    for (j = start_symbol; j < nsyms; j++)
	   {
	   if (cword & mask)
	     {
	     rp = derives[j];
	     while ((rule = *rp++) >= 0)
		    {
		    SETBIT(rrow, rule);
		    }
	     }

	  mask <<= 1;
	  if (mask == 0)
	    {
       cword = *vrow++;
	    mask = 1;
	    }
	  }

    vrow += varsetsize;
    rrow += rulesetsize;
    }

#ifdef	DEBUG
  print_first_derives();
#endif

  FREE(EFF);
}


void closure(short *nucleus,int n)
{
int ruleno;
unsigned word;
unsigned mask;
short *csp;
unsigned *dsp;
unsigned *rsp;
int rulesetsize;

short *csend;
unsigned *rsend;
int symbol;
int itemno;

  rulesetsize = WORDSIZE(nrules);
  rsp = ruleset;
  rsend = ruleset + rulesetsize;
  for (rsp = ruleset; rsp < rsend; rsp++)
	 *rsp = 0;

  csend = nucleus + n;
  for (csp = nucleus; csp < csend; ++csp)
    {
	 symbol = ritem[*csp];
	 if (ISVAR(symbol))
	   {
	   dsp = first_derives + symbol * rulesetsize;
	   rsp = ruleset;
	   while (rsp < rsend)
		  *rsp++ |= *dsp++;
	   }
    }

  ruleno = 0;
  itemsetend = itemset;
  csp = nucleus;
  for (rsp = ruleset; rsp < rsend; ++rsp)
    {
	 word = *rsp;
	 if (word == 0) ruleno += BITS_PER_WORD;
	 else
	   {
	   mask = 1;
	   while (mask)
	     {
		  if (word & mask)
		    {
		    itemno = rrhs[ruleno];
		    while (csp < csend && *csp < itemno)
			    *itemsetend++ = *csp++;
		    *itemsetend++ = itemno;
		    while (csp < csend && *csp == itemno)
			    ++csp;
		    }

       mask <<= 1;
		 ++ruleno;
	    }
	   }
    }

  while (csp < csend)
	 *itemsetend++ = *csp++;

#ifdef	DEBUG
  print_closure(n);
#endif
}



void finalize_closure(void)
{
  FREE(itemset);
  FREE(ruleset);
  FREE(first_derives + ntokens * WORDSIZE(nrules));
}


#ifdef	DEBUG

void print_closure(int n)
{
int isp;

  printf("\n\nn = %d\n\n", n);
  for (isp = itemset; isp < itemsetend; isp++)
    printf("   %d\n", *isp);
}


void print_EFF(void)
{
int i, j, k;
unsigned *rowp;
unsigned word;
unsigned mask;

  printf("\n\nEpsilon Free Firsts\n");

  for (i = start_symbol; i < nsyms; i++)
    {
	 printf("\n%s", symbol_name[i]);
	 rowp = EFF + ((i - start_symbol) * WORDSIZE(nvars));
	 word = *rowp++;

	 mask = 1;
  for (j = 0; j < nvars; j++)
	 {
	 if (word & mask) printf("  %s", symbol_name[start_symbol + j]);

    mask <<= 1;
	 if (mask == 0)
	   {
	   word = *rowp++;
		mask = 1;
	   }
	}
  }
}


void print_first_derives(void)
{
int i;
int j;
unsigned *rp;
unsigned cword;
unsigned mask;

  printf("\n\n\nFirst Derives\n");

  for (i = start_symbol; i < nsyms; i++)
    {
    printf("\n%s derives\n", symbol_name[i]);
    rp = first_derives + i * WORDSIZE(nrules);
    cword = *rp++;
    mask = 1;
    for (j = 0; j <= nrules; j++)
      {
	   if (cword & mask) printf("   %d\n", j);
	   mask <<= 1;
	   if (mask == 0)
	     {
	     cword = *rp++;
	     mask = 1;
	    }
	  }
   }
  fflush(stdout);
}

#endif