/* grammar.c
 */

#include "grammar.h"
/* #include "ftree.h" */
#include "tree.h"
#include "hash-templates.h"
#include "mmm.h"
#include "svm_struct_api_types.h"
#include <stdio.h>
#include <ctype.h>
#include <math.h>

#define MAX(x,y)	((x) < (y) ? (y) : (x))

HASH_CODE_ADD(sihashst, si_index, size_t, IDENTITY, NEQ, IDENTITY, NO_OP, 0, NO_OP)

/*
static brule
make_brule(const FLOAT prob, const si_index parent, const si_index left, const si_index right, long weightid)
{
  brule br = MALLOC(sizeof(struct brule));
  br->prob = prob;
  br->parent = parent;
  br->left = left;
  br->right = right;
  br->weightid = weightid;
  return br;
}
*/

void
brules_free(brules brs)
{
  size_t i;
  for (i=0; i<brs.n; i++)
    FREE(brs.e[i]);
  FREE(brs.e);
}

static brules brules_empty = {NULL, 0, 0};

HASH_CODE(sihashbrs, si_index, brules, IDENTITY, NEQ, IDENTITY, NO_OP, brules_empty, brules_free)

typedef struct {
  si_index parent, left, right;
} brindex;

size_t brindex_hash(brindex bri)
{
  return (2*bri.parent+3*bri.left+5*bri.right);
}

int
brindex_neq(const brindex bri1, const brindex bri2)
{
  return ((bri1.parent != bri2.parent) || (bri1.left != bri2.left) || (bri1.right != bri2.right));
}

HASH_HEADER(brihashbr, brindex, brule)
HASH_CODE(brihashbr, brindex, brule, brindex_hash, brindex_neq, IDENTITY, NO_OP, NULL, NO_OP)

static void
add_brule(sihashbrs left_brules_ht, brihashbr brihtbr, 
	  const FLOAT prob, const si_index parent, const si_index left, const si_index right, long weightid)
{
  brindex bri;
  brule br;
  brules *brsp;

  bri.parent = parent;
  bri.left = left;
  bri.right = right;
  br = brihashbr_ref(brihtbr, bri);

  if (br) {			/* have we seen this rule before? */
    br->prob += prob;		/* yes */
    return;
  }
  
  br = MALLOC(sizeof(struct brule));	/* make new brule */
  br->prob = prob;
  br->parent = parent;
  br->left = left;
  br->right = right;
  br->weightid = weightid;
  
  brsp = sihashbrs_valuep(left_brules_ht, left);
  
  if (brsp->nsize <= brsp->n) {
    brsp->nsize = MAX(2*brsp->nsize, 8);
    brsp->e = REALLOC(brsp->e, brsp->nsize * sizeof(brsp->e[0]));
  }

  assert(brsp->n < brsp->nsize);
  brsp->e[(brsp->n)++] = br;
  brihashbr_set(brihtbr, bri, br);
}


static urule
make_urule(const FLOAT prob, const si_index parent, const si_index child, long weightid)
{
  urule ur = MALLOC(sizeof(struct urule));
  ur->prob = prob;
  ur->parent = parent;
  ur->child = child;
  ur->weightid = weightid;
  return ur;
}

static void
urules_free(urules urs)
{
  size_t i;
  for (i=0; i<urs.n; i++)
    FREE(urs.e[i]);
  FREE(urs.e);
}

static urules urules_empty = {NULL, 0, 0};

HASH_CODE(sihashurs, si_index, urules, IDENTITY, NEQ, IDENTITY, NO_OP, urules_empty, urules_free)

static void
push_urule(sihashurs child_urules_ht, const si_index key, const urule ur)
{
  urules *ursp = sihashurs_valuep(child_urules_ht, key);
  
  if (ursp->nsize <= ursp->n) {
    ursp->nsize = MAX(2*ursp->nsize, 8);
    ursp->e = REALLOC(ursp->e, ursp->nsize * sizeof(ursp->e[0]));
  }

  assert(ursp->n < ursp->nsize);
  ursp->e[(ursp->n)++] = ur;
}

si_index 
read_cat(FILE *fp, si_t si)
{
  char string[MAXLABELLEN];
  int    c;
  size_t i;

  while ((c = fgetc(fp)) && isspace(c) && (c != '\n'))		/* skip spaces */
    ;

  if ((c == '\n') || (c == EOF)) return(0);			/* line ended, return 0 */

  for (i = 0; (c != EOF) && (!isspace(c)) && (i < MAXLABELLEN); c = fgetc(fp)) 
    string[i++] = c;

  ungetc(c, fp);

  if (i >= MAXLABELLEN) {
    string[MAXLABELLEN-1] = '\0';
    fprintf(stderr, "read_cat() in grammar.c: Category label longer than MAXLABELLEN: %s\n", string);
    exit(EXIT_FAILURE);
  }

  string[i] = '\0';
  return(si_string_index(si, string));
}
  
  
grammar
read_grammar(FILE *fp, si_t si) 
{
  sihashbrs left_brules_ht = make_sihashbrs(NLABELS);
  sihashurs child_urules_ht = make_sihashurs(NLABELS);
  brihashbr brihtbr = make_brihashbr(NLABELS);
  int n;
  FLOAT value;
  urule ur;
  size_t  lhs, cat, rhs[MAXRHS];
  long id=0; 

  while ((n = fscanf(fp, "%lf ", &value)) == 1) {	/* read the value */
    lhs = read_cat(fp, si);
    assert(lhs);
    
    fscanf(fp, " " REWRITES);				/* read the rewrites symbol */

    for (n=0; n<MAXRHS; n++) {				/* read the rhs, n is length of rhs */
      cat = read_cat(fp, si);
      if (!cat)
	break;
      rhs[n] = cat;
    }

    if (n >= MAXRHS) {
      fprintf(stderr, "read_grammar() in grammar.c: rule rhs too long\n");
      exit(EXIT_FAILURE);
    }

    switch (n) {
    case 0: 
      fprintf(stderr, "read_grammar() in grammar.c: rule with empty rhs\n");
      exit(EXIT_FAILURE);
      break;
    case 1: 
      ur = make_urule(value, lhs, rhs[0],id++);
      push_urule(child_urules_ht, ur->child, ur);
      break;
    case 2:
      add_brule(left_brules_ht, brihtbr, value, lhs, rhs[0], rhs[1],id++);
      break;
    default: 
      { int start, i, j;
        char bcat[MAXBLABELLEN], *s;
	si_index bparent, left, right;

	right = rhs[n-1];		/* rightmost category */
	for (start=n-2; start>=1; start--) {
	  
	  i = 0;			/* i is index into bcat[] */
	  for (j=start; j<n; j++) {     /* j is index into rhs[] */
	    if (j!=start) {
	      bcat[i++] = BINSEP;
	      assert(i < MAXBLABELLEN);
	    }
	    
	    s = si_index_string(si, rhs[j]);
	    while (*s) {
	      bcat[i++] = *s++;
	      assert(i < MAXBLABELLEN);
	  }}

	  bcat[i] = '\0';
	  bparent = si_string_index(si, bcat);
	  left = rhs[start];
	  add_brule(left_brules_ht, brihtbr, 0.0, bparent, left, right,(long)-1);
	  right = bparent;
	}
	
	add_brule(left_brules_ht, brihtbr, value, lhs, rhs[0], right, id++);
      }}}
  
  free_brihashbr(brihtbr);	/* free brindex hash table */

  {
    grammar g;
    g.urs = child_urules_ht;
    g.brs = left_brules_ht;
    g.idMax=id;
    return g;
  }
}

void 
write_grammar(FILE *fp, grammar g, si_t si) 
{
  sihashbrsit	bhit;
  sihashursit	uhit;
  size_t	i;

  for (bhit=sihashbrsit_init(g.brs); sihashbrsit_ok(bhit); bhit=sihashbrsit_next(bhit)) 
    for (i=0; i<bhit.value.n; i++) 
      fprintf(fp, "%g	%s " REWRITES " %s %s\n", (double) bhit.value.e[i]->prob, 
	      si_index_string(si, bhit.value.e[i]->parent),
	      si_index_string(si, bhit.value.e[i]->left),
	      si_index_string(si, bhit.value.e[i]->right));

  for (uhit=sihashursit_init(g.urs); sihashursit_ok(uhit); uhit=sihashursit_next(uhit)) 
    for (i=0; i<uhit.value.n; i++) 
      fprintf(fp, "%g	%s " REWRITES " %s\n", (double) uhit.value.e[i]->prob, 
	      si_index_string(si, uhit.value.e[i]->parent),
	      si_index_string(si, uhit.value.e[i]->child));
}

void
free_grammar(grammar g)
{
  free_sihashurs(g.urs);
  free_sihashbrs(g.brs);
}


grammar
create_grammar(vihashl localtree_ht, vihashl weightid_ht, si_t si) 
{
  sihashbrs left_brules_ht = make_sihashbrs(NLABELS);
  sihashurs child_urules_ht = make_sihashurs(NLABELS);
  brihashbr brihtbr = make_brihashbr(NLABELS);
  int n, count;
  vihashlit hit;
  vindex  vi;
  urule ur;
  size_t  lhs, rhs[MAXRHS];
  long id=1;

  for (hit = vihashlit_init(localtree_ht); vihashlit_ok(hit); hit = vihashlit_next(hit)) {
    vi = (vindex) hit.key;
    assert(vi->n > 0);
    assert(vi->n <= MAXRHS);
    count = hit.value;
    lhs =  vi->e[0];

    for (n=0; n<(vi->n-1); n++) {     	/* read the rhs, n is length of rhs */
      rhs[n] = vi->e[n+1];
    }

    if (n >= MAXRHS) {
      fprintf(stderr, "read_grammar() in grammar.c: rule rhs too long\n");
      exit(EXIT_FAILURE);
    }

    switch (n) {
    case 0: 
      fprintf(stderr, "read_grammar() in grammar.c: rule with empty rhs\n");
      exit(EXIT_FAILURE);
      break;
    case 1: 
      ur = make_urule(count, lhs, rhs[0], id);
      push_urule(child_urules_ht, ur->child, ur);
      vihashl_set(weightid_ht,vi,id);
      id+=MAXFEAT;
      break;
    case 2:
      add_brule(left_brules_ht, brihtbr, count, lhs, rhs[0], rhs[1], id);
      vihashl_set(weightid_ht,vi,id);
      id+=MAXFEAT;
      break;
    default: 
      { int start, i, j;
        char bcat[MAXBLABELLEN], *s;
	si_index bparent, left, right;

	right = rhs[n-1];		/* rightmost category */
	for (start=n-2; start>=1; start--) {
	  
	  i = 0;			/* i is index into bcat[] */
	  for (j=start; j<n; j++) {     /* j is index into rhs[] */
	    if (j!=start) {
	      bcat[i++] = BINSEP;
	      assert(i < MAXBLABELLEN);
	    }
	    
	    s = si_index_string(si, rhs[j]);
	    while (*s) {
	      bcat[i++] = *s++;
	      assert(i < MAXBLABELLEN);
	  }}

	  bcat[i] = '\0';
	  bparent = si_string_index(si, bcat);
	  left = rhs[start];

	  vi=make_vindex(4); /* add index for new phi function */
	  vi->n=3;
	  vi->e[0]=bparent;
	  vi->e[1]=left;
	  vi->e[2]=right;
	  if(!vihashl_ref(weightid_ht,vi)) {
	    add_brule(left_brules_ht, brihtbr, count, bparent, left, right,
		      (long)id);
	    vihashl_set(weightid_ht,vi,id);	
	    id+=MAXFEAT;
	  }
	  vindex_free(vi);

	  right = bparent;
	}
	
	vi=make_vindex(4); /* add index for new phi function */
	vi->n=3;
	vi->e[0]=lhs;
	vi->e[1]=rhs[0];
	vi->e[2]=right;
	if(!vihashl_ref(weightid_ht,vi)) {
	  add_brule(left_brules_ht, brihtbr, count, lhs, rhs[0], right, id);
	  vihashl_set(weightid_ht,vi,id);
	  id+=MAXFEAT;
	}
	vindex_free(vi);
      }}}
  
  free_brihashbr(brihtbr);	/* free brindex hash table */
 
  {
    grammar g;
    g.urs = child_urules_ht;
    g.brs = left_brules_ht;
    g.idMax=id;
    return g;
  }
}