#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "efc_structs.h"

extern int tok_high;
extern int wd_len;
extern int new_wd;
extern float wd_cur_match;
extern float wd_occ;
extern float WDS;
extern float matching_tok[];
extern float real_tok[];
extern struct stats wd_info[];

char sswd[50];

/**************************************************************************

Subroutine: init_stats

Purpose: Initialize global data structure to start-up values.  The
	structures are used to gather statistics on the functioning of the
	EFC simulations.

Inputs: pointer to such a data structure.

Outputs: none.

Other Side Effects: none.

**************************************************************************/

void init_stats(st_str)
struct stats *st_str;
{
	int i;

	st_str->mismatches = 0.0;
	st_str->subtot = 0;
	for (i = 0; i < TOK_NO; i++) {
		real_tok[i+1] = 0.0;
		st_str->toks_used[i] = 0;
	}
	for (i=0; i < 5*TOK_NO; i++)
		matching_tok[i+1] = 0.0;
	for (i=0; i < 4; i++)
		st_str->errs[i] = 0;
}

/**************************************************************************

Subroutine: error

Purpose: Quick exit from program upon irrecoverable error condition.

Inputs: s1 can be a string constant or a printf formatting string.
	s2 must be a string constant.

Outputs: none.

Other Side Effects: Program execution halted with no data saved.

**************************************************************************/
void error(s1, s2)
char *s1, *s2;
{
	fprintf(stderr, s1, s2);
	fprintf(stderr, "\n");
	exit(1);
}

/**************************************************************************

Subroutine: salloc

Purpose: To allocate memory to be used for representation of a state
	in the EFC error tolerance state machine.

Inputs: none.

Outputs: none.

Returns: pointer to newly allocated memory.

Other Side Effects: none.

**************************************************************************/

struct state *salloc()
{
	return((struct state *) malloc(sizeof(struct state)));
}

/**************************************************************************

Subroutine: nalloc

Purpose: To allocate memory to be used for representation of state transitions in the EFC error tolerance state machine.

Inputs: none.

Outputs: none.

Returns: pointer to newly allocated memory.

Other Side Effects: none.

**************************************************************************/

struct new_state *nalloc()
{
	return((struct new_state *) malloc(sizeof(struct new_state)));
}

struct new_state *init_new_state(trans, sptr, tss)
int trans;
struct state *sptr;
struct new_state *tss;
{
	struct new_state *ns_ptr;

	ns_ptr = nalloc();
	ns_ptr->transition = trans;
	ns_ptr->next_state = sptr;
	ns_ptr->next = tss;
	return(ns_ptr);
}

/**************************************************************************

Subroutine: init_state

Purpose: Initialize a new_state being added to the state machine.

Inputs: no	- this state's number in the state machine.
	actions	- binary pattern representing state actions to be taken.
	sts	- points to another state in state machine state table.

Outputs: none.

Other Side Effects: memory is allocated for the state.

Returns: pointer to newly created and initialized state.

**************************************************************************/

struct state *init_state(no, actions, sts)
int no;
int actions;
struct state *sts;
{
	struct state *st_ptr;

	st_ptr = salloc();
	st_ptr->state_no = no;
	st_ptr->actions = actions;
	st_ptr->trans_lst = NULL;
	st_ptr->next = sts;
	return(st_ptr);
}

/**************************************************************************

Subroutine: make_state_table

Purpose: Generate the EFC error tolerance state machine representation.

Inputs: none.

Outputs: none.

Returns: pointer to the state machine table.

Other Side Effects: memory allocated for table generation.

**************************************************************************/

struct state *make_state_table()
{
	struct state *tmps[8];
	struct new_state *tmpns, *tmpns2, *common;

	/* create the seven states */
	tmps[7] = init_state(7, 012, NULL);
	tmps[6] = init_state(6, 010, tmps[7]);
	tmps[5] = init_state(5, 06, tmps[6]);
	tmps[4] = init_state(4, 026, tmps[5]);
	tmps[3] = init_state(3, 0, tmps[4]);
	tmps[2] = init_state(2, 01, tmps[3]);
	tmps[1] = init_state(1, 040, tmps[2]);

	/*create fransition list for each state */
	tmpns  = init_new_state(034, tmps[6], NULL);
	tmpns2 = init_new_state(014, tmps[4], tmpns);
	tmpns  = init_new_state(010, tmps[4], tmpns2);
	tmpns2 = init_new_state(04,  tmps[1], tmpns);
	tmpns  = init_new_state(0,   tmps[1], tmpns2);

	tmps[7]->trans_lst = tmpns;
	tmps[6]->trans_lst = tmpns;
	tmps[5]->trans_lst = tmpns;
	tmps[3]->trans_lst = tmpns;
	tmps[2]->trans_lst = tmpns;

	tmpns  = init_new_state(035, tmps[6], NULL);
	tmpns2 = init_new_state(011, tmps[5], tmpns);
	tmpns  = init_new_state(015, tmps[3], tmpns2);
	tmpns2 = init_new_state(05,  tmps[3], tmpns);
	tmpns  = init_new_state(01,  tmps[1], tmpns2);
	tmps[4]->trans_lst = tmpns;

	tmpns  = init_new_state(036, tmps[7], NULL);
	tmpns2 = init_new_state(016, tmps[5], tmpns);
	tmpns  = init_new_state(012, tmps[5], tmpns2);
	tmpns2 = init_new_state(06,  tmps[2], tmpns);
	tmpns  = init_new_state(02,  tmps[2], tmpns2);
	tmps[1]->trans_lst = tmpns;

	return(tmps[1]);
}

/**************************************************************************

Subroutine: get_next_state

Purpose: Given the current inputs and current, transit to the next state.

Inputs: cur_st	- pointer into state table representing current_state.
	input 	- character matcher outputs during current_state.

Outputs: none.

Returns: pointer into state table to next state.

Other Side Effects: none.

**************************************************************************/

struct state *get_next_state(cur_st, input)
struct state *cur_st;	/* current_state number */
int input;		/* current input from character matcher */
{
	struct state *ps;
	struct new_state *pns;

	pns = cur_st->trans_lst;
	input = (input & 020) ? (input | 034) : input;	/* mask don't cares */
	while (pns->transition != input && pns != NULL)
		pns = pns->next;
	if (pns == NULL)
		error("Unknown_token transition %d", input);
	return(pns->next_state);
}

/**************************************************************************

Subroutine: do_state_actions

Purpose: Execute actions for current_state as stored in state machine table.

Inputs: pointer to an active_token follower.

Outputs: none.

Other Side Effects: the error flags, error counter, and_token pointer (ss_cell) in the_token follower may be updated depending on the state actions performed.

**************************************************************************/

void do_state_actions(tok)
struct tok_follow *tok;	/* token follower moving through state machine */
{
	struct state *ps;
	struct new_state *pns;

	tok->ref = (tok->current_st->actions & 040) ? 1 : 0;
	tok->ef = (tok->current_st->actions & 020) ? 1 : 0;
	if (tok->current_st->actions & 010)
		tok->ss_cell++;
	if (tok->current_st->actions & 04)
		tok->ss_cell += 2;
	if (tok->current_st->actions & 02)
		tok->err_cnt++;
	tok->abort = (tok->current_st->actions & 01) ? 1 : 0;
}

/**************************************************************************

Subroutine: init_ch_matcher

Purpose: Initialize a character matcher with a character group.

Inputs: em chlst pointer to character matcher to be initialized.

-character group to initialize matcher with.

Outputs: none.

Other Side Effects: none.

**************************************************************************/

void init_ch_matcher(cm, chlst)
struct ch_matcher *cm;
char *chlst;
{
	cm->ch_lst = chlst;
}

/**************************************************************************

Subroutine: init_ss_matcher

Purpose: Initialize string matcher with_token or string to be searched for.
	This_token is gotten from a data base of target words.

Inputs: fname	- pointer to data base of words to search for.
	sm	- pointer to string matcher to be initialized.

Outputs: none.

Other Side Effects: all token followers in string matcher deactivated,
	pointer into target word data base incremented,
	program execution halted when end of data base is reached.

**************************************************************************/

void init_ss_matcher(fname, sm)	/* initialize substring matcher */
char *fname;
struct str_matcher *sm;
{
	static char chlst[16][50];
	static short int first = 1;
	char wd[50];
	int i, j;
	FILE *fopen();
	static FILE *dbptr;
	void print_stats(), deactivate_toks();
	char *strcpy();

	if (first) { 
		first = 0;
		if ((dbptr= fopen(fname, "r")) == NULL)
			error("init_ss_matcher: can't open %s", fname);
	}
	j = getwd(dbptr, wd, &wd_occ, 0);
/* strcpy(sswd, wd);*/
	if (j == EOF) {
		fclose(dbptr);
		print_stats();
		error("\nFinished.", NULL);
	}
	WDS += wd_occ;	/* accumulate total words sampled, per efc.c's own
			   doc comment: WDS = sum of all word frequencies
			   in the target database */
	wd_info[wd_len].mismatches -= wd_occ * wd_occ;
	deactivate_toks(sm);
	sm->str_len = strlen(wd) - 1;
	sm->enabled = 1;
	for (i = 0; i <= sm->str_len; i++) {
		chlst[i][0] = wd[i];
		chlst[i][1] = '\0';
		init_ch_matcher(&(sm->reg_matcher[i]), chlst[i]);
	}
}

/**************************************************************************

Subroutine: ch_match

Purpose: Match an incoming character with what is loaded in character matcher.

Inputs: cm	- pointer to a character matcher.
	c	- character to match against what is stored in matcher.

Outputs: none.

Returns: 1 if match is made, 0 if not.

**************************************************************************/

int ch_match(cm, c)
struct ch_matcher *cm;
char c;
{
	int i, found;

	found = 0;
/*****
	for (i = 0; i < strlen(cm->ch_lst) && !found; i++)
		if (cm->ch_lst[i] == c)
			found = 1;
*****/

	if (cm->ch_lst[0] == c)
		found = 1;

	return(found);
}

/**************************************************************************

Subroutine: ss_match

Purpose: Look at three character matcher outputs for the expected character,
	the next expected chatacter, and the second expected character.

Inputs: sm	- pointer to a string matcher.
	c	- current incoming character in input stream.
	tok	- pointer to one of the string matcher's active token followers.

Outputs: none.

Returns: integer where lower order three bits represent, respectively, the
	character matcher outputs for second previous, current, and next
	expected chatacters.

Other Side Effects: none.

**************************************************************************/

int ss_match(sm, c, tok)
struct str_matcher *sm;	/* a substring matcher */
char c;			/* current character in input stream */
struct tok_follow *tok;	/* token follower */
{
	int val;

	val = 0;

	if (ch_match(&(sm->reg_matcher[tok->ss_cell]), c ) == 1)
		val = val | 020;
	if (tok->ss_cell < (sm->str_len) &&
		(ch_match(&(sm->reg_matcher[(tok->ss_cell)+1]), c) == 1))
		val = val | 010;
	if (tok->ss_cell > 1 &&
		(ch_match(&(sm->reg_matcher[(tok->ss_cell)-2]), c) == 1))
		val = val | 04;
	if (tok->ref == 1)
		val = val | 02;
	if (tok->ef == 1)
		val = val | 01;
	return(val);
}

/**************************************************************************

Subroutine: activate_tok

Purpose: Try to activate a new token follower for a newly arrived
	character in the imput stream.

Inputs: st_tbl	- pointer to the error tolerance state machine table.
	ss	- pointer to a string matcher.
	newest_tok -	integer representing what order this token follower
			is being activated in th sequence of token followers
			trying to match the current incoming word with the
			target.

Outputs: newest_tok is incremented only if a token follower is available
	for activation.

Returns: 1 if a token follower is activated, 0 if not.

Other Side Effects: none.

**************************************************************************/

int activate_tok(st_tbl, ss, newest_tok)
struct state *st_tbl;
struct str_matcher *ss;
int *newest_tok;
{
	int i;

	i = 0;
	while (ss->tok[i].active == 1 && i < TOK_NO)
		i++;
	if (i != TOK_NO) {
		if (i > tok_high)
			tok_high = i;
		ss->tok[i].current_st = st_tbl->next->next;
		ss->tok[i].err_cnt = 0;
		ss->tok[i].ss_cell = 0;
		ss->tok[i].ref = 0;
		ss->tok[i].ef = 0;
		ss->tok[i].abort = 0;
		ss->tok[i].active = 1;
		ss->tok[i].number = ++(*newest_tok);
	}
	return((i == TOK_NO) ? 0: 1);
}

/**************************************************************************

Subroutine: deactivate_toks

Purpose: Deactivate all token followers in a string matcher.

Inputs: pointer to a string matcher.

Outputs: none.

Returns: none.

Other Side Effects: none.

**************************************************************************/

void deactivate_toks(ss)
struct str_matcher *ss;
{
	int i;

	tok_high = -1;
	wd_cur_match = 0;
	for (i = 0; i < TOK_NO; i++)
		ss->tok[i].active = 0;
}

/**************************************************************************

Subroutine: check_tok

Purpose: Check to see if token follower should be deactivated because
	either a match or abort condition has occurred.  If so, gather
	appropriate statistics.

Inputs: tok	- pointer to a token follower.
	len	- length of the target string being searched for.
	occ	- relative frequency of occurrence of current word in
			input stream.
	wd	- current word in imput stream.
	tok_ind	- number of physical token follower (not activation order).

Outputs: none.

Returns: 1 if a match condition exists, 0 if not.

Other Side Effects: Abort signal in token follower may be set if number
	of errors encountered exceeds maximum nummber allowed. Token follower
	will be deactivated if a match or abort condition exists.

**************************************************************************/

int check_tok(tok, len, occ, wd, tok_ind)
struct tok_follow *tok;
int len;
float occ;
char *wd;
int tok_ind;
{
	int res;

	res = 0;
#ifdef EFC_MODIFIED_TOLERANCE
	/* Length-dependent error tolerance table (thesis Table 2.1),
	   derived AFTER analyzing the original Figure 2.5 results.
	   This is the "Modified EFC" configuration -- produces
	   plot6.png-plot9.png, NOT Figure 2.5 (mismatches vs word length). */
	if (len <= 6 && tok->err_cnt == 1)
		tok->abort = 1;
	else if ((len == 7 || len == 8) && tok->err_cnt == 2)
		tok->abort = 1;
	else if ((len == 9 || len == 10) && tok->err_cnt == 3)
		tok->abort = 1;
	else if (tok->err_cnt == 4)
		tok->abort = 1;
#else
	/* Original, flat error tolerance: up to 3 non-consecutive errors
	   regardless of word length. This is the configuration used for
	   Figure 2.5 (Mismatches versus Word Length), Figure 2.6 (Peak
	   Token Usage), and Figures for one/two/three-error probability
	   -- per chap2.tex: "up to three non-consecutive errors... are
	   permitted when searching for the target string [regardless of
	   word length]." */
	if (tok->err_cnt == 4)
		tok->abort = 1;
#endif
	else if (tok->ss_cell == 15 || tok->ss_cell >= len+1) {
		if (new_wd)
			wd_cur_match += occ;
		res = 1 ;
/*printf("target '%s' matched %s\n", sswd, wd);*/
		wd_info[wd_len].errs[tok->err_cnt] += wd_occ * occ;
		matching_tok[tok->number] += wd_occ * occ;
		real_tok[tok_ind+1] += wd_occ;
		tok->active = 0;
		new_wd = 0;
	}
	if (tok->abort == 1) /* abort search */
		tok->active = 0;
	return(res);
}

/**************************************************************************

Subroutine: print_stats

Purpose: Make final computations on statistics gathered in many of the
	subroutines and print the results.

Inputs: none.

Outputs: none.

Returns: none.

Other Side Effects: All global data structures used in gathering
	statistics are altered to put data in its final form.

**************************************************************************/

void print_stats()
{
	float mm_tot, avg_wd, avg_tot;
	float tmp_tottoks, tmp_wdtot, tokerrs[4], allerrs;
	float toks_subtot[TOK_NO], toks_tot, wdtot, match_tok_tot, real_tok_tot;
	int i, j, mst_tok;

	printf("\nTotal words sampled (WDS): %.0f\n", WDS);

	real_tok_tot = match_tok_tot = 0.0;
	wdtot = toks_tot = allerrs = mm_tot = avg_tot = 0.0;
	for (j = 0; j < TOK_NO; j++)
		toks_subtot[j] = 0.0;
	for (j = 0; j < 4; j++)
		tokerrs[j] = 0.0;
	mst_tok = 0;
	for (i = 3; i < 17; i++) {
		tmp_tottoks = tmp_wdtot = avg_wd = 0.0;
		wd_info[i].mismatches /= WDS;
		wd_info[i].mismatches /= WDS;	/* CONFIRMED by thesis Eqn 2.x:
					   Prob(mismatch) = foc(target)*foc(input)
					   / [sum foc(word_x)]^2 -- denominator
					   is WDS squared. Not a guess anymore. */
		printf("\n%d letter target string:\n\n", i);
		if (wd_info[i].mismatches)
			printf("  %1.8f mismatches.\n\n",
				wd_info[i].mismatches);
		mm_tot += wd_info[i].mismatches;
	for(j = 0; j < TOK_NO; j++)
		if (wd_info[i].toks_used[j]) {
			avg_wd += wd_info[i].toks_used[j] * (j+1);
			avg_tot += wd_info[i].toks_used[j] * (j+1);
			toks_subtot[j] += wd_info[i].toks_used[j];
			toks_tot += wd_info[i].toks_used[j];
			tmp_wdtot += wd_info[i].toks_used[j];
			wdtot += wd_info[i].toks_used[j];
		}
	for (j = 0; j < TOK_NO; j++)
		if (wd_info[i].toks_used[j]) {
			if (j > mst_tok)
				mst_tok = j;
			printf("  %1.8f used %d tokens.\n",
				wd_info[i].toks_used[j]/tmp_wdtot, j+1);
		}
	for(j = 0; j < 4; j++) {
		tmp_tottoks += wd_info[i].errs[j];
		tokerrs[j] += wd_info[i].errs[j];
		allerrs += wd_info[i].errs[j];
	}
	printf("\n");
	for (j = 0; j < 4; j++)
		if (wd_info[i].errs[j])
			printf("  %1.8f of matching tokens had %d errors.\n",
				wd_info[i].errs[j]/tmp_tottoks, j);
	if (avg_wd)
		printf("\n Average: %1.8f tokens per %d-letter word.\n",
			avg_wd/tmp_wdtot, i);
	}
	printf("\n%1.8f total mismatches.\n\n", mm_tot);
	for(j=0; j < TOK_NO; j++)
		printf("%1.8f used %d tokens.\n", toks_subtot[j]/toks_tot, j+1);
	printf("\nAverage: %1.8f tokens per word.\n", avg_tot/wdtot);
	printf("Most:    %d tokens.\n\n", mst_tok+1);

	for (j = 0; j < 4; j++)
		printf("%1.8f had %d errors.\n", tokerrs[j]/allerrs, j);
	for (j = 1; j <= 5*TOK_NO; j++)
		match_tok_tot += matching_tok[j];
	for (j = 1; j <= 5*TOK_NO; j++)
		matching_tok[j] /= match_tok_tot;
	for (j = 1; j <= TOK_NO; j++)
		real_tok_tot += real_tok[j];
	for (j = 1; j <= TOK_NO; j++)
		real_tok[j] /= real_tok_tot;
	printf("\n");
	for(j = 1; j < 5*TOK_NO+1; j++)
		if (matching_tok[j])
			printf("%1.8f words were matched with activated token %d\n",
				matching_tok[j], j);
	printf("\n");
	for (j = 1; j<= TOK_NO; j++)
		if (real_tok[j])
			printf("%1.8f words were matched with the real token %d\n",
				real_tok[j], j);
}