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

struct _trans{
  int orig;
  int dest;
  char read;
  char write;
  char dir;
};
typedef struct _trans trans;

struct _mt{
  int init;
  int accept;
  int reject;
  trans **t_trans;
  int nb_trans;
  int nb_states;
  int size_t_trans;
};
typedef struct _mt mt;

mt *allocate_mt(void)
{
  mt *a = malloc(sizeof(mt));
  if(a == NULL){
    fprintf(stderr, "allocation problem\n");
    exit(1);
  }
  a->init = -1;
  a->accept = -1;
  a->reject = -1;
  a->nb_trans = 0;
  a->nb_states = 0;
  a->size_t_trans = 0;
  a->t_trans = NULL;
  return a;
}


trans *allocate_trans(int orig, int dest, char read, char write, char dir)
{
  trans *t = malloc(sizeof(trans));
  if(t == NULL){
    fprintf(stderr, "allocation problem\n");
    exit(1);
  }
  t->orig = orig;
  t->dest = dest;
  t->read = read;
  t->write = write;
  t->dir = dir;
  return t;
}

void add_trans(mt *a, int orig, int dest, char read, char write, char dir)
{
  if(a->nb_trans == a->size_t_trans){
    a->size_t_trans = 2 * (a->size_t_trans + 1);
    a->t_trans = realloc(a->t_trans, a->size_t_trans * sizeof(trans *)); 

  }
  a->t_trans[a->nb_trans] = allocate_trans(orig, dest, read, write, dir);
  a->nb_trans++;
}

void print_mt(mt *a)
{
  int i,j;
  printf("init = %d\n", a->init);
  printf("accept = %d\n", a->accept);
  printf("reject = %d\n", a->reject);
  for(i=0; i < a->nb_states; i++){
    for(j = 0 ; j < a->nb_trans; j++){
      if(a->t_trans[j]->orig == i){
	printf("%d %d %c %c %c\n", a->t_trans[j]->orig, a->t_trans[j]->dest, a->t_trans[j]->read, a->t_trans[j]->write, a->t_trans[j]->dir);
      }
    }
  }
}

void generate_introduction(void)
{
printf("#include<stdio.h>\n");
printf("#include<stdlib.h>\n");
printf("#include<string.h>\n");
printf("int i;\n");
printf("char tape[1000];\n");
/*printf("void gauche(void){i--;}\n");*/
/*printf("void droite(void){i++;}\n");*/
printf("void print_tape(char *state)\n");
printf("{\n");
printf("  int j;\n");
printf("  int l = strlen(tape);\n");
printf("  printf(\"%%s \", state);\n");
printf("  for(j=0; j < i; j++)\n");
printf("    printf(\"%%c\", tape[j]);\n");
printf("  printf(\"[%%c]\", tape[i]);\n");
printf("  for(j=i+1; j < l; j++)\n");
printf("    printf(\"%%c\", tape[j]);\n");
printf("  printf(\"\\n\");\n");
printf("}\n");
}

void generate_conclusion(void)
{
printf("int main(int argc, char *argv[])\n");
printf("{\n");
printf("  strcpy(tape, \"$\");\n");
printf("  strcat(tape, argv[1]);\n");
printf("  strcat(tape, \"$\");\n");
    
/* printf("  printf(\"tape = %%s\\n\", tape);\n"); */
printf("  reco(tape);\n");
printf("  return 0;\n");
printf("}\n");

}

void generate_mt(mt *a)
{
  int i,j;

  printf("int reco(char *tape)\n{\ni=1;\n");
  for(i=0; i <= a->nb_states; i++){
    if(i != a->reject){
      if(i == a->accept){printf("accept: {printf(\"ACCEPT\\n\");  exit(1);}\n");}
      else{
	printf("e%d: {print_tape(\"e%d\");\n", i, i); 
	for(j = 0 ; j < a->nb_trans; j++){
	  if(a->t_trans[j]->orig == i){
	    printf("  if(tape[i] == '%c'){tape[i] = '%c';", a->t_trans[j]->read, a->t_trans[j]->write);
	    if(a->t_trans[j]->dir == 'D') printf(" i++;");
	    else printf(" i--;");
	    if(a->t_trans[j]->dest == a->accept) printf(" goto accept;}\n");
	    else if(a->t_trans[j]->dest == a->reject) printf(" goto reject;}\n");
	    else printf(" goto e%d;}\n", a->t_trans[j]->dest);
	  }
	}
	printf(" goto reject;\n}\n");
      }
    }
  }
  printf("reject: {printf(\"REJECT\\n\");  exit(1);}\n");
  printf("}\n");
}

void generate_code(mt *a){
  generate_introduction();
  generate_mt(a);
  generate_conclusion();
}



mt *read_mt(char *filename)
{
  FILE *f = fopen(filename, "r");
  char buffer[1000];
  int orig, dest;
  char read, write, dir;
  mt *a;
  int r;

  if(f == NULL){
    fprintf(stderr, "cannot open file %s\n", filename);
    exit(1);
  }

  a = allocate_mt();
  while(!feof(f)){
    fgets(buffer, 1000, f);
    if(buffer[0] != '#'){
      r = sscanf(buffer, "%d %d %c %c %c", &orig, &dest, &read, &write, &dir);
      if(r == 5){
	/* printf("%d %d %c %c %c\n", orig, dest, read, write, dir); */
	if(a->nb_trans==0) a->init = orig;
	if(orig > a->nb_states) a->nb_states = orig;
	if(dest > a->nb_states) a->nb_states = dest;
	add_trans(a, orig, dest, read, write, dir);
      }
      if(r == 2){
	if(orig == 1) a->accept = dest;
	if(orig == 0) a->reject = dest;
      }
    }
  }
  fclose(f);
  return a;
}


int main(int argc, char *argv[])
{
  FILE *f = fopen(argv[1], "r");
  char buffer[1000];
  int orig, dest, read, write, dir;
  mt *a;
  
  a= read_mt(argv[1]);
  /* print_mt(a);  */
  generate_code(a); 
  
}