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

#define TRUE 1
#define FALSE 0
#define ALPHABET 1
#define NON_ALPHABET 0
#define INSIDE 1
#define OUTSIDE 0
#define MAX 48

/*Global variable declarations */

int count = 1,flag = 0,important_states[MAX],important_states_count=0,last_char = NON_ALPHABET;
char current_char='0',epsilon_states[MAX];
char * important_states_str, * set_of_input_symbols;
struct automata * nfa, * dfa;

/* Functions are defined below this. */

struct state {
	char *state_number;
	struct state *transition1;
	char value_on_edge1;
	struct state *transition2;
	char value_on_edge2;
};

struct automata {
	struct state *start;
	struct state *final;
};

int createNewState (struct state **ptr) {

	struct state *tmp_st;
	tmp_st =(struct state *) malloc(sizeof(struct state));
	if(tmp_st != (struct state *)NULL) {
		tmp_st->state_number = (char *)NULL;
		tmp_st->transition1 = (struct state *)NULL;
		tmp_st->value_on_edge1='$';
		tmp_st->transition2 = (struct state *)NULL;
		tmp_st->value_on_edge2='$';
		*ptr = tmp_st;
		return TRUE;
	}
	else {
		printf("Unable to create a state");
		return FALSE;
	}
}

int createAutomata (struct automata **ptr) {

	struct automata *tmp_automata;
	tmp_automata = (struct automata *)malloc(sizeof(struct automata));
	if(tmp_automata != (struct automata *)NULL) {
		tmp_automata->start = (struct state *)NULL;
		tmp_automata->final = (struct state *)NULL;
		*ptr = tmp_automata;
		return TRUE;
	}
	else {
		printf("Unable to allocate memory for automata");
		return FALSE;
	}
}

struct automata * applyAnd (struct automata * nfa, struct automata * nfa1) {

	if(nfa != (struct automata *)NULL && nfa1 != (struct automata *)NULL) {
		printf("\n State : %s -- epsilon --> %s",nfa->final->state_number,nfa1->start->state_number);
		nfa->final->transition1 = nfa1->start;
		nfa->final->value_on_edge1 = '#';
		nfa->final = nfa1->final;
		return (nfa);
	}
	else {
		printf("\nUnable to Apply the 'and' operation on the nfa");
		exit(1);
	}
}

struct automata * applyOr (struct automata * nfa, struct automata * nfa1) {

	if(nfa != (struct automata *)NULL && nfa1 != (struct automata *)NULL) {

		struct state *tmp1 = (struct state *)NULL;
		struct state *tmp2 = (struct state *)NULL;
		if(createNewState(&tmp1) && createNewState(&tmp2)) {
			tmp1->state_number = (char *) malloc(MAX);
			itoa(count++,tmp1->state_number,10);
			tmp2->state_number = (char *) malloc(MAX);
			itoa(count++,tmp2->state_number,10);

			tmp1->transition1 = nfa->start;
			tmp1->value_on_edge1 = '#';
			tmp1->transition2 = nfa1->start;
			tmp1->value_on_edge2 = '#';
			printf("\n State : %s -- epsilon --> %s",tmp1->state_number,tmp1->transition1->state_number);
			printf("\n State : %s -- epsilon --> %s",tmp1->state_number,tmp1->transition2->state_number);

			nfa->final->transition1 = tmp2;
			nfa->final->value_on_edge1 = '#';
			nfa1->final->transition1 = tmp2;
			nfa1->final->value_on_edge1 = '#';
			printf("\n State : %s -- epsilon --> %s",nfa->final->state_number,nfa->final->transition1->state_number);
			printf("\n State : %s -- epsilon --> %s",nfa1->final->state_number,nfa1->final->transition1->state_number);

			nfa->start = tmp1;
			nfa->final = tmp2;
			nfa->final->transition1 = (struct state *)NULL;
            nfa->final->transition2 = (struct state *)NULL;
			return (nfa);
		}
		else {
			printf("\nProbs in creating new states");
			exit(1);
		}
	}
	else {
		printf("\nUnable to Apply the Or operation on the nfa");
		exit(1);
	}
}

struct automata * applyStar (struct automata * nfa) {

	struct state *tmp1 = (struct state *)NULL;
	struct state *tmp2 = (struct state *)NULL;
	if(createNewState(&tmp1) && createNewState(&tmp2)) {
		tmp1->state_number = (char *) malloc(MAX);
		itoa(count++,tmp1->state_number,10);
		tmp1->transition1 = nfa->start;
		tmp1->value_on_edge1 = '#';
		tmp1->transition2 = tmp2;
		tmp1->value_on_edge2 = '#';
		tmp2->state_number = (char *) malloc(MAX);
		itoa(count++,tmp2->state_number,10);

		nfa->final->transition1 = nfa->start;
		nfa->final->value_on_edge1 = '#';
		nfa->final->transition2 = tmp2;
		nfa->final->value_on_edge2 = '#';

		printf("\n State : %s -- epsilon --> %s",nfa->final->state_number,nfa->final->transition1->state_number);
		printf("\n State : %s -- epsilon --> %s",nfa->final->state_number,nfa->final->transition2->state_number);

		printf("\n State : %s -- epsilon --> %s",tmp1->state_number,nfa->start->state_number);
		printf("\n State : %s -- epsilon --> %s",tmp1->state_number,tmp2->state_number);

		nfa->start = tmp1;
		nfa->final = tmp2;
		nfa->final->transition1 = (struct state *)NULL;
        nfa->final->transition2 = (struct state *)NULL;
		return (nfa);
	}
	else {
		printf("\nUnable to Apply the star operation on the nfa");
		exit(1);
	}
}

void add_to_inputsymbols (char input) {
	 char *temp;
	 temp = (char *)malloc(8);
	 *temp = input;
     *(temp+1) = '\0';
	 if(strchr(set_of_input_symbols,input) == (char *)NULL) {
		  strcat(set_of_input_symbols,temp);
	 }
}

char * find_Epsilon_Closure (struct state * nfa_start) {

	 epsilon_states[count_of_states] = nfa_start->state_number;

	 if (nfa_start->value_on_edge1 == '#') {
		  find_Epsilon_Closure(nfa_start->transition1);
	 }
	 if (nfa_start->value_on_edge2 == '#') {
		  find_Epsilon_Closure(nfa_start->transition2);
	 }
	 return epsilon_states;
}

struct state * get_state (char *state_number, struct state * temp_head) {

    int loop_count = 0;

    if (temp_head == (struct state *)NULL) {
        return (struct state *)NULL;
    }
    else if (strcmp(temp_head->state_number,state_number) == 0) {
        return temp_head;
    }
    else {
        temp_head = get_state(state_number,temp_head->transition1);
        if (temp_head == (struct state *)NULL) {

            temp_head = get_state(state_number,temp_head->transition2);
            if (temp_head == (struct state *)NULL)
                return (struct state *)NULL;
            else {
                return temp_head;
            }
        }
        else {
            return temp_head;
        }
    }
}

char * del_cap (struct state * dfa_state, char input) {

    char *output_states,*temp,*states;
    int loop_count =0,flag=OUTSIDE;
    struct state * state, * head = nfa->start;
    char temp_state_number[2];
    temp = (char *) malloc(MAX);
    output_states = (char *)malloc(MAX);
    strcpy(output_states,"`");
    strcpy(states,"");

    for (loop_count = 0; dfa_state->state_number[loop_count] != '\0';loop_count++) {
        if (dfa_state->state_number[loop_count] != '`') {
            if (flag == INSIDE) {

                temp_state_number[0] = dfa_state->state_number[loop_count-1];
                temp_state_number[1] = dfa_state->state_number[loop_count];
                state = get_state(temp_state_number,head);
                strcat(states,delta(state,input));
            }
            else if(dfa_state->state_number[loop_count+1] == '`') {
                temp_state_number[0] = dfa_state->state_number[loop_count];
                temp_state_number[1] = '\0';
                state = get_state(temp_state_number,head);
                strcat(states = delta(state,input));
            }
            flag = INSIDE;
        }
        else
            flag = OUTSIDE;
    }
    for(loop_count = 0; states[loop_count] != '\0';loop_count++) {
        state = get_state(states[loop_count],head);
        strcat(output_states, find_Epsilon_Closure(state));
    }
    printf("\n[%s] -- %c --> [%s]\n ",dfa_state->state_number,input,output_states);
    return output_states;
}