/* construct by thompson's algorithm from a parse tree a nfa state table */

/* the e symbol will be 0 */

/* thompson's algorithm : for every leaf node construct the 2 states with a transition on the
 * leaf's symbol.
 *
 * for interior nodes, 
 *
 * alternation : construct the a hexagon state graph, where there is a new initial and new final state,
 * and the top and bottom of the hexagon is made of the initial and final states of the child nodes.
 *
 * star : construct a surrounding new initial and final state for the child node's initial and final states.
 *  place an e transition from the new initial to new final state to represent a zero iteration.
 *  place an e transition from the child's final state to the child's initial state to represent 1 or more iterations.
 *
 *  concatenation : the final state of the first child becomes the start state of the second child, with no e transition.
 *  this may require searching the state table 
 */

#include "nfa.h"
#include "parsenode.h"
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
int init_state_transition_table();
int fill_state_trans(node_p node);
int make_state_trans(node_p root);
int make_nfa_node_attrib( node_p node, int init_state, int final_state) ;
nfa_node_attrib_t*  get_node_states( node_p node) ;

int nextstate = 0;
int start_state = 0;

int state_stack1[MAX_STATES];
int state_stack2[MAX_STATES];
int* examined_stack = state_stack1;
int* next_stack  = state_stack2;
int stack2_sz = 0;
int stack1_sz = 0;

/**
 * sets the attrib void pointer of node_p to a nfa_node_attrib_t  pointer,
 * so the node is tagged with the init and final states of the node
 */
int make_nfa_node_attrib( node_p node, int init_state, int final_state) {
	nfa_node_attrib_t * node_states = malloc( sizeof( nfa_node_attrib_t) );
	node_states->init_state = init_state;
	node_states->final_state = final_state;
	node->attribs = node_states;
	return 1;
}


int show_trans_table() {

	int i, j;

	for (i = 0; i < nextstate; ++i) {
		for ( j = 0; j < MAX_INOUT; ++j ) {
			int symbol = state_trans[i][j].symbol;
			if (!symbol) 
				break;
			printf("state-from %d\t state-to%d symbol %d %c\n", i,  state_trans[i][j].next, symbol, symbol);
			
		}
	}
	
	return 1;
}

int make_trans_table(node_p root) {
	init_state_transition_table();
	fill_state_trans( root);

	start_state = get_node_states(root)->init_state;

	return 1;
}

int make_transition( int state, int next_state, int symbol) {
	int i =0;

	for (i = 0; i < MAX_INOUT; ++i ) {
		if (state_trans[state][i].symbol == 0) {
			state_trans[state][i].symbol = symbol;
			state_trans[state][i].next = next_state;
			return 1;
		}
	}

	fprintf (stderr, "too many state transitions for state %d\n" , state);
	return 0;
}

int change_state_targets ( int old, int newstate) {
	int i,j ;

	for (i = 0; i < nextstate; ++i) {
		for (j = 0; j < MAX_INOUT; ++i) {
			if ( ! state_trans[i][j].symbol)
				break;
			if ( state_trans[i][j].next == old) {
				state_trans[i][j].next = newstate;
			}
		}
	}
	return 1;
}

int fill_state_trans( node_p node) {
	
	if (node == NULL) {
		return 1;
	}
	fill_state_trans(node->left);
	fill_state_trans(node->right);
	make_state_trans(node);
	
	return 1;
}


int make_state_trans(node_p node) {
	
	nfa_node_attrib_t *left_states, *right_states;

#ifdef DEBUG
	fprintf(stderr, "Looking at node with value %c %d\n", node->value, node->value);

#endif

	if (node->left == NULL && node->right == NULL) {
		make_transition( nextstate, nextstate+1, node->value);
		make_nfa_node_attrib( node, nextstate, nextstate +1);
		nextstate += 2;
	} 
	else switch (node->value)  {
			case CONCAT:
				left_states = (nfa_node_attrib_t*)  node->left->attribs;
				right_states = (nfa_node_attrib_t*)  node->right->attribs;
				change_state_targets( left_states->final_state, right_states->init_state);
				left_states->final_state = right_states->init_state;
				make_nfa_node_attrib( node, left_states->init_state, right_states->final_state);
				break;

			case STAR:
				left_states = (nfa_node_attrib_t*)  node->left->attribs;
				make_transition( nextstate, nextstate+1, E);
				make_transition( nextstate, left_states->init_state, E);
				make_transition( left_states->final_state, nextstate+1, E);
				make_transition ( left_states->final_state, left_states->init_state, E);
				make_nfa_node_attrib( node, nextstate, nextstate+1);
				nextstate += 2;
				break;

			case UNIFY:
				
				left_states = (nfa_node_attrib_t*)  node->left->attribs;
				right_states = (nfa_node_attrib_t*)  node->right->attribs;
				
				make_transition( nextstate, left_states->init_state, E);
				make_transition( nextstate, right_states->init_state, E);
				make_transition( left_states->final_state, nextstate+1, E);
				make_transition( right_states->final_state, nextstate+1, E);
				make_nfa_node_attrib( node, nextstate, nextstate+1);

				nextstate += 2;
				

				break;

			default:
				error("unrecognized symbol\n");
				exit(-1);
	}		

	return 0;

		
}

int init_state_transition_table() {
	memset( state_trans, 0, MAX_STATES * MAX_INOUT * sizeof(nfa_trans_t ) ); 
	return 0;
}

nfa_node_attrib_t*  get_node_states( node_p node) {
	if ( node == NULL) {
		return NULL;
	}
	return (nfa_node_attrib_t*) node->attribs;
}


/** gets the e-closure of start_states, which will be returned in e_trans_list
 * and the e-closure list size returned 
 */
int get_e-closure_of ( int* start_states, int sz_list, int* e_trans_list) {
	int i, j, k;
	k = 0;

	/** add the zero transitions to the e-closure list */
	for (i = 0; i < sz_list; ++i ) {
		e_trans_list[k++] = start_states;	
	}

	/** find the immediate E transitions from the start_states list */
	for (i = 0; i < sz_list; ++i ) {
		int state = start_states[i];
	 	for ( j = 0; j < MAX_INOUT; ++j) {
			if(! state_trans[state][j].symbol) 
				break;
			if (state_trans[state][j].symbol == E) {
				e_trans_list[k++] = state_trans[state][j].next;
			}
		}
	}

	/** expand the e_trans_list until no more states with E transitions
	 */
	for (i = 0; i < k ; ++i) {
		int state = e_trans_list[i];
		for (j = 0; j < MAX_INOUT; ++j) {
			if(! state_trans[state][j].symbol)
		              break;
			if (state_trans[state][j].symbol == E) {
				  int l, found = 0;
				  for (l = 0; l < k && !found; ++l) {
					  if(  e_trans_list[l] == state_trans[state][j].next) {
						  found = 1;
						  /* filter out states already in list to avoid a possible cycle */	
					  }
			      }
				  if (!found) {
					  e_trans_list[k++] = state_trans[state][j].next;
				  }
			}
		}
	}
	return k;

}

int symbol_match( int osymbol, int symbol) {
		switch (osymbol) {

			case DOT:
					return 1;
			default:
					return osymbol == symbol;
		};			
}


int move ( int * states, int sz_list, int symbol, int* next_states) {
		int i,j ,k;
		k = 0;

		for (i = 0; i < sz_list; ++i ) {
			int state = states[i];
			for (j = 0; j < MAX_INOUT; ++j) {
				int osymbol = state_trans[state][j].symbol;

				if ( !osymbol)
					break;
				if ( symbol_match( osymbol, symbol) ) {
					next_states[k++] = state_trans[state][j].next;
				}
			}
		}
		return k;
}

int nfa_accept( char* test_str) {
	int i,k, j , l,  curr_state;
	i = l = 0;
	int states1[MAX_STATES], states2[MAX_STATES];
	int sz_origin, sz_next;
	int * origin, *next;
	origin = states2;
	next = states1;

	next[0] = start_states;
	sz_next = 1;
	
	sz_origin = get_e-closure_of( next,  sz_next, origin);

	
	l = strlen( test_str);

	for (i = 0; i < l ; ++i ) {
		sz_next = get_e-closure_of( move( origin, sz_origin,  test_str[l] , next) );
		sz_origin = sz_next;
		origin = next;
	}
	

	
	
		
}



#ifdef NFA_MAIN
int main(int argc, char* argv[]) {
	node_p root;
	nfa_node_attrib_t *states;
	start();
	root = pop();
	shownode(root , 0);
	make_trans_table(root);
	show_trans_table();

	fprintf(stdout, "init at root is %d\n", get_node_states(root)->init_state);
#define MAXBUF 1000
	while (1) {
		char test_str[MAXBUF];
		fprintf(stdout, "\nenter a test string or <enter> to exit:\n")
		fscanf( stdin, "%s", test_str);
		if (strlen(test_str) == 0)
			break;
		if ( nfa_accept( test_str) ) {
			fprintf(stdout, "The string was accepted \n");
		} else {
			fprintf(stdout, "The string was not accepted \n");
		}
	}
	return 0;
}
#endif