#include <stdio.h>
#include <stdlib.h>
/*
 * A Turing machine simulator
 * 
 * ProgramName: turing.c
 * Author: Shinichi Asakawa <asakawa@twcu.ac.jp>
 */
/*
	IQ : inner state
	IA : index card
	OA : action 
	OQ : change state
 */

int  pretape = 10; 
#define maxtapelen 70
#define MAXRULE 100

int IQ[MAXRULE], OQ[MAXRULE];
char IA[MAXRULE], OA[MAXRULE]; 

char tape[maxtapelen];

int nrule = 0;
int state = 1;
int head = 0;
int step = 1;


void usage(void){
    fprintf(stderr, "Turing machine simulator\n");
    fprintf(stderr, "Usage: Turing <rule file> <tape contents>\n");
    exit (EXIT_FAILURE);
}

char read_tape(int pos)
{
  if (tape[pretape+pos] == '0')
    return 'B';
  else 
    return tape[pretape+pos];
}

void set_tape(int n, char str)
{
    tape[pretape+n] = str;
}

void check_tapelen(int pos)
{
    if (pos + pretape > maxtapelen){
	fprintf(stderr, "Tap over flow\n");
	exit (EXIT_FAILURE);
    }
}

void print_head(void)
{
    int i, pos;

    pos = 6 + pretape + head;
    for (i=0;i<pos;i++)
	printf(" ");
    printf("^");

}


void print_tape(int step)
{
    int i;

    printf("(%04d)", step);
    for (i=0;i<maxtapelen;i++){
	if (tape[i] == 'B' || tape[i] == '0') 
	    printf(".");
	else 
	    printf("%c", tape[i]);
    }
    printf("\n");
}

int match_rule(void)
{
    int i;

    for (i=0; i<nrule; i++){
	if ((IA[i]==read_tape(head)) && (state==IQ[i]))
	    return i;
    }
    return -1;
}


int calc_sum(void)
{
    int i, sum=0;

    for (i=0; i<maxtapelen; i++) {
	if (tape[i] == '1') 
	    sum++;
    }
    return sum;
}

void init_tape(char *str)
{
    int i, maxlen;
    char c;

    for (i=0;i<maxtapelen;i++) {
	tape[i] = 'B';
    }
    if ((maxlen = strlen(str)) > (maxtapelen-pretape)){
	fprintf(stderr, "Tape too long\n");
	exit (EXIT_FAILURE);
    }
    for (i=0; i<maxlen; i++){
	c = str[i];
	if (c == '0')
	    tape[i+pretape] = 'B';
	else 
	    tape[i+pretape] = c;
    }
}

int read_rule(char *file)
{
    FILE *fp;
    char strings[1024];
    int i;

    for (i=0; i<MAXRULE; i++) {
	IQ[i]=0; OQ[i]=0;
	IA[i]=' '; OA[i]=' ';
    }
    i=0;
    fp = fopen(file,"r");
    while ( fgets(strings, 1024, fp) != NULL) {
	strings[strlen(strings)-1]='\0';
	sscanf(strings, "%d %c %c %d", &IQ[i], &IA[i], &OA[i], &OQ[i]);
	i++;
    }
    fclose(fp);
    return i;
}


int main(int argc, char **argv)
{
    int rule;

    if ( argc != 3 ){
	usage();
    }    

    nrule = read_rule(argv[1]);
    init_tape(argv[2]);

    while (1){
	print_tape(step);
	print_head();
	rule = match_rule();
	if (rule >= 0) {
	    printf(" Rule %d(%d %c %c %d) matched.\n",
		   rule, IQ[rule], IA[rule], OA[rule], OQ[rule]);
	    if (OA[rule] == 'R') 
		head++;
	    else if (OA[rule] == 'L') 
		head--;
	    else 
		set_tape(head, OA[rule]);
	    state = OQ[rule];
	    check_tapelen(head);
	} else {
	    printf(" HALT: No rule matched.\n");
	    printf("Result = %d\n", calc_sum());
	    exit (EXIT_FAILURE);
	}
	step++;
    } 
}