#include <stdlib.h>
#include <stdio.h>
#include <strings.h>

int Alignment=0;
int MaxLen = 250;
int LenY = 0;
int LenX = 0;

typedef struct _w2p W2P;
struct _w2p
{ int w2w;
  int *p2x;
  int *p2y;
  int pa, pc;
};

#define IsWRD(w2p) (((w2p!=NULL)&&(w2p!=(W2P *)-1)&&(w2p->w2w==1))?1:0)
#define IsPHR(w2p) (((w2p!=NULL)&&(w2p!=(W2P *)-1)&&w2p->pc)?1:0)

void usage(char *prg, char *msg);
void PHsave(W2P ***XY, int x1, int x2, int y1, int y2);
int  PHmin (W2P ***XY, int *x1, int *x2, int *y1, int *y2);
int  PHnext(W2P ***XY, int *x1, int *x2, int *y1, int *y2);
void NoWRD(W2P ***XY, int y1, int y2, int x1, int x2);
int  WRDx(W2P ***XY, int y, int *x1, int *x2);
int  WRDy(W2P ***XY, int x, int *y1, int *y2);
int  PHRx(W2P ***XY, int x, int y);
void CnvP2W(W2P ***XY);
void CnvW2P(W2P ***XY, int lex);
int  PlotWW(W2P ***XY);
int  PlotPP(W2P ***XY);
int  PrintWW(W2P ***XY);
int  PrintPP(W2P ***XY);

int PrintLex(FILE *fe, FILE *ff, W2P ***XY)
{ char *BE[MaxLen], *BF[MaxLen], token[100], buf[1000];
  int x, y, i, j;
  int lenx, leny;
  int found;
 
  rewind(fe);
  found=0;
  while(fgets(buf, 1000, fe)) { 
    lenx=atoi(&buf[8]);
    if(lenx==Alignment) {found=1; break;}
  }

  if(found==0) {
    fprintf(stderr, "WARNING no alignment %d\n", Alignment);
    return 0;
  }
  lenx=1;
  i=14;
  while(buf[i]) {
    j=0;
    
    while(buf[i] && isspace(buf[i])) i++;
    while(buf[i] && !isspace(buf[i])) token[j++] = buf[i++];
    token[j] = '\0';
    if(!strcmp(token, "</s>")) break;

    while(buf[i] && !isspace(buf[i])) i++;
    BE[lenx++]=strdup(token);
  } 
  if(lenx <= LenX) {
    fprintf(stderr, "WARNING Alignment %d:%s%d %d\n", Alignment, buf, lenx, LenX);
    for(;lenx<=LenX; lenx++) BE[lenx]=strdup("@DUMMY");
  }
  BE[lenx] = NULL;

  rewind(ff);
  found=0;
  while(fgets(buf, 1000, ff)) { 
    leny=atoi(&buf[8]);
    if(leny==Alignment) {found=1; break;}
  }

  if(found==0) {
    fprintf(stderr, "WARNING no alignment %d\n", Alignment);
    return 0;
  }
  leny=1;
  i=14;

  while(buf[i]) {
    j=0;
    while(buf[i] && isspace(buf[i])) i++;
    while(buf[i] && !isspace(buf[i])) token[j++] = buf[i++];
    token[j] = '\0';
    if(!strcmp(token, "</s>"))  break;

    while(buf[i] && !isspace(buf[i])) i++;
    BF[leny++]=strdup(token);
  } 
  if(leny <= LenY) {
    fprintf(stderr, "WARNING Alignment %d:%s%d %d\n", Alignment, buf, leny, LenY);
    for(;leny<=LenY; leny++) BF[leny]=strdup("@DUMMY");
  }
  BF[leny] = NULL;


  fprintf(stdout, "@Alignment%d\t%d\t%d\n", Alignment, lenx-1, leny-1);

  for(y=1; y<=LenY; y++) {
    for(x=0; x<=LenX; x++) {
      if(IsPHR(XY[x][y])) {
        for(i=0; i< XY[x][y]->pc; i++) {
          for(j=x; j<=XY[x][y]->p2x[i];j++) {
            fprintf(stdout, "%s", BE[j]);
            if(j<XY[x][y]->p2x[i]) fprintf(stdout, "_");
          }
          fprintf(stdout, " <--> ");
          for(j=y; j<=XY[x][y]->p2y[i]; j++) {
            fprintf(stdout, "%s", BF[j]);
            if(j<XY[x][y]->p2y[i]) fprintf(stdout, "_");
          }
          fprintf(stdout, "\n");
          fflush(stdout);
        } 
      }
    }
  }

  i=1;
  while(BE[i]) free(BE[i++]);
  i=1;
  while(BF[i]) free(BF[i++]);
  return 1;
}

int PlotWW(W2P ***XY)
{ int x, y;

  fprintf(stderr, "Aln:%d LenX:%d LenY:%d\n", Alignment, LenX, LenY);
  fprintf(stderr, "   ");
  for(y=0; y<=LenY; y++) fprintf(stderr, "%d", y%10);
  fprintf(stderr, "\n");
  for(x=LenX; x>=0; x--) {
    fprintf(stderr, "%2.2d ", x);
    for(y=0; y<=LenY; y++) {
      if(IsWRD(XY[x][y])) fprintf(stderr, "x"); 
      else fprintf(stderr, " ");
    }
    fprintf(stderr, "\n");
  }
  fprintf(stderr, "   ");
  for(y=0; y<=LenY; y++) fprintf(stderr, "%d", y%10);
  fprintf(stderr, "\n");
}

int PlotPP(W2P ***XY)
{ int x, y;
 
  fprintf(stderr, "Aln:%d LenX:%d LenY:%d\n", Alignment, LenX, LenY);
  fprintf(stderr, "   ");
  fprintf(stderr, "\n");
  for(x=0; x<=LenX; x++) fprintf(stderr, "%d", x%10);
  for(y=LenY; y>=0; y--) {
    fprintf(stderr, "%2.2d ", y);
    for(x=0; x<=LenX; x++) {
      if(IsPHR(XY[x][y])) fprintf(stderr, "x");
      else fprintf(stderr, " ");
    }
    fprintf(stderr, "\n");
  }
  fprintf(stderr, "   ");
  for(x=0; x<=LenX; x++) fprintf(stderr, "%d", x%10);
  fprintf(stderr, "\n");
}
 
int PrintWW(W2P ***XY)
{ int x, y;
 
  for(x=0; x<=LenX; x++) {
    for(y=0; y<=LenY; y++) {
      if(IsWRD(XY[x][y])) fprintf(stdout, "%0.4d %d %d S\n", Alignment, x, y);
    }
  }
}
 
int PrintPP(W2P ***XY)
{ int i, x, y;
 
  for(y=1; y<=LenY; y++) {
    for(x=0; x<=LenX; x++) {
      if(IsPHR(XY[x][y])) {
       for(i=0; i< XY[x][y]->pc; i++)
         fprintf(stdout, "%0.4d %d-%d %d-%d S\n", Alignment, x, XY[x][y]->p2x[i], 
                                          y, XY[x][y]->p2y[i]);
    } }
  }
}




int PHmin(W2P ***XY, int *x1, int *x2, int *y1, int *y2)
{ int x, y, found=0;
 
  for(x=*x1; x<=*x2; x++) {
    for(y=1; y<=LenY; y++) {
      if(IsWRD(XY[x][y])) {
        if(y<*y1) {*y1=y; found=1;}
        if(y>*y2) {*y2=y; found=1;}
  } } }
  for(y=*y1; y<=*y2; y++) {
    for(x=1; x<=LenX; x++) {
      if(IsWRD(XY[x][y])) {
        if(x<*x1) {*x1=x; found=1;}
        if(x>*x2) {*x2=x; found=1;}
  } } }
  return found;
}

int PHnext(W2P ***XY, int *x1, int *x2, int *y1, int *y2)
{ int i, z1, z2, found=0;
 
  for(i=*y2+1; i<=LenY; i++) {
    if(WRDx(XY, i, &z1, &z2) == 0) continue;
    if(z1 < *x1) {*x1=z1; found=1;}
    if(z2 > *x2) {*x2=z2; found=1;}
    if(found) break;
  }
  return found;
}

void SetNoWord(W2P ***XY, int x, int y)
{

  if(XY[x][y]==(W2P *)-1) return;
  if(XY[x][y]==NULL) {
    XY[x][y]= (W2P *) -1;
    return;
  }
  XY[x][y]->w2w=2;
} 

void NoWRD(W2P ***XY, int x1, int x2, int y1, int y2)
{ int x, y;

  for(y=y1; y<=y2; y++) {
    for(x=x2+1; x<=LenX; x++) SetNoWord(XY, x, y);
    for(x=x1-1; x>0; x--)    SetNoWord(XY, x, y);
  }
  for(x=x1; x<=x2; x++) {
    for(y=y2+1; y<=LenY; y++) SetNoWord(XY, x, y);
    for(y=y1-1; y>0; y--)    SetNoWord(XY, x, y);
  }

  for(x=x1; x<=x2; x++) {
    for(y=y1; y<=y2; y++) {
      if(XY[x][y] == (W2P *) -1) continue;
      if(XY[x][y] == NULL)  XY[x][y] = calloc(1, sizeof(W2P));
      if(XY[x][y]->w2w==0) XY[x][y]->w2w=1;
  } }

}


int WRDy(W2P ***XY, int x, int *y1, int *y2)
{ int i, found=0;

  *y1=*y2=-1;
  for(i=1; i<=LenY; i++) {
    if(IsWRD(XY[x][i])) {
      if(*y1>=0) *y2=i;
      else *y1=*y2=i;
  } }
  return found;
}

int WRDx(W2P ***XY, int y, int *x1, int *x2)
{ int i, found=0;

  *x1=*x2=-1;
  for(i=1; i<=LenX; i++) {
    if(IsWRD(XY[i][y])) {
      if(*x1>=0) *x2=i;
      else *x1=*x2=i;
      found=1;
  } } 
  return found;
}


int PHRx(W2P ***XY, int x, int y)
{ int i;
 
  for(i=x+1; i<=LenX; i++) {
    if(IsPHR(XY[i][y])) return i;
  }
  return 0;
}
 

void CnvP2W(W2P ***XY)
{ int i, j, x, y;
  W2P *xy;
 
  for(y=1; y<=LenY; y++) {
    x=0;
    while(1) {
      x=PHRx(XY, x, y);
      if(x == 0) break;
 
      xy=XY[x][y];
      for(j=0; j<xy->pc; j++) {
        NoWRD(XY, x, xy->p2x[j], y, xy->p2y[j]);
      }
    } 
  }
}



void CnvW2P(W2P ***XY, int lex)
{ int i, j, x1, x2, y1, y2;
  int pc, save;
  W2P *xy;

  for(i=1; i<=LenY; i++) {
    if(WRDx(XY, i, &x1, &x2) == 0) continue;
    do {
      WRDy(XY, x1, &y1, &y2);
      while(PHmin(XY, &x1, &x2, &y1, &y2));
      PHsave(XY, x1, x2, y1, y2);
      if(lex) break;
    }while(PHnext(XY, &x1, &x2, &y1, &y2));

  }
}

void PHsave(W2P ***XY, int x1, int x2, int y1, int y2)
{ W2P *xy;
  int y, x, j, save=1;

  for(x=1; x<=LenX; x++) {
    for(y=1; y<=LenY; y++) {
      if(XY[x][y] == NULL) continue;
      xy=XY[x][y];
      for(j=0; j<xy->pc; j++) {
        if(
           ((x1 == x) && (x2 == xy->p2x[j])) ||
           ((y1 == y) && (y2 == xy->p2y[j]))) return;
        if(
           ((x1 <= x) && (x2 >= xy->p2x[j]) && 
            (y1 >= y) && (y2 <= xy->p2y[j])) ||
           ((x1 >= x) && (x2 <= xy->p2x[j]) && 
            (y1 <= y) && (y2 >= xy->p2y[j]))
          ) return;
      }
    }
  }


  if(XY[x1][y1] == NULL) XY[x1][y1]= calloc(1, sizeof(W2P));
  xy=XY[x1][y1];
 
  if(xy->pc == xy->pa) {
    xy->p2x = realloc(xy->p2x, (xy->pa+5)*sizeof(int));
    xy->p2y = realloc(xy->p2y, (xy->pa+5)*sizeof(int));
    xy->pa = xy->pa+5;
  }
  if(save) {
    xy->p2x[xy->pc]= x2;
    xy->p2y[xy->pc]= y2;
    xy->pc++;
  }
}

void XYfree(W2P ***XY)
{ int x, y;

  for(x=0; x<=LenX+1; x++) {
    for(y=0; y<=LenY+1; y++) {
      if(XY[x][y] == NULL) continue;
      if(XY[x][y] == (W2P *)-1) {XY[x][y]=NULL; continue;} 
      free(XY[x][y]->p2x);
      free(XY[x][y]->p2y);
      free(XY[x][y]);
      XY[x][y]=NULL;
} } }

int main(int argc,char *argv[])
{
  FILE *fi;
  FILE *fe, *ff;
  char fn[200], dummy[20], *stop, c, *lex=NULL, *in=NULL;
  char buf[100];
  char *lng1=NULL;
  char *lng2=NULL;
  int w2p=1, allex=0, print=0;
  int i, x, y, x2, y2;
  W2P ***XY;
 
  while((c=(char)getopt(argc, argv, "i:o:m:1:2:l:Ppeh")) != EOF) {
    switch(c) {
      case '1': lng1=strdup(optarg); break;
      case '2': lng2=strdup(optarg); break;
      case 'i': in=strdup(optarg); break;
      case 'm': MaxLen=atoi(optarg); break;
      case 'p': w2p=0; break;
      case 'l': lex=strdup(optarg); break;
      case 'e': allex=1; break;
      case 'P': print=1; break;
      case 'h': ;
      default: usage(argv[0], "Convert W1-W2 to P1-P2 Alignment");
  } }

 
  if(lex) {
    sprintf(fn, "%s.%s", lex, lng1==NULL?"e":lng1);
    if((fe  = fopen(fn, "r")) == NULL)
        usage("Cannot open for reading", lex);
    sprintf(fn, "%s.%s", lex, lng2==NULL?"f":lng2);
    if((ff  = fopen(fn, "r")) == NULL)
        usage("Cannot open for reading", lex);
  }
  if(in == NULL) fi = stdin;
  else {
    if((fi  = fopen(in, "r")) == NULL) 
        usage("Cannot open for reading", in);
  }

  XY= (W2P ***) calloc(MaxLen, sizeof(W2P **));
  for(i=0; i<MaxLen; i++) XY[i] = (W2P **) calloc(MaxLen, sizeof(W2P *));

  Alignment=-1;
  if(w2p) {
    while(1) {
      stop=fgets(buf, 100, fi);
      sscanf(buf, "%d %d %d %s", &i, &x, &y, dummy);

      if(Alignment == -1) Alignment=i;
      else if((i != Alignment) || (stop == NULL)) {
        if(print) PlotWW(XY);
        else {
          CnvW2P(XY, allex); 
          if(lex) PrintLex(fe, ff, XY);
          else PrintPP(XY);
        }
        XYfree(XY);
        LenX=LenY=0;
        Alignment=i;
      }
      if(stop == NULL) break;
      XY[x][y]= calloc(1, sizeof(W2P));
      XY[x][y]->w2w=1;
      if(x > LenX) LenX=x;
      if(y > LenY) LenY=y;
    }
  }
  else {
    while(1) {
      stop=fgets(buf, 100, fi);
      sscanf(buf, "%d %d-%d %d-%d %s", &i, &x, &x2, &y, &y2, dummy);

      if(Alignment == -1) Alignment=i;
      else if((i != Alignment) || (stop == NULL)) {
        if(print) PlotPP(XY);
        else {
          CnvP2W(XY); 
          PrintWW(XY);
        } 
        XYfree(XY);
        LenX=LenY=0;
        Alignment=i;
      }
      if(stop == NULL) break;
      PHsave(XY, x, x2, y, y2);
      if(x2 > LenX) LenX=x2;
      if(y2 > LenY) LenY=y2;
    }
  }
  fclose(fi);
  return 1;
}

void usage(char *prg, char *msg)
{  fprintf(stderr, "%s: %s\n", prg, msg);
   fprintf(stderr, "Options:\n");
   fprintf(stderr, "-i file \tinput alignment data\n");
   fprintf(stderr, "-m int  \tmax. len. alignment [%d]\n", MaxLen);
   fprintf(stderr, "-p      \tconvert P2P into W2W Alignment\n");
   fprintf(stderr, "-e      \tconvert minimal dictionary [exhaustive]\n");
   fprintf(stderr, "-P      \tplot W1-W2 Alignment\n");
   fprintf(stderr, "\nOptions to generate phrase dictionary\n");
   fprintf(stderr, "-l root \troot of test data\n");
   fprintf(stderr, "-1 str  \troot language 1 suffix [e]\n");
   fprintf(stderr, "-2 str  \troot language 2 suffix [f]\n");
  
   exit(0);
}