/*
----------------------------------------------------------------
Y. CIURLIK & A. DUCHENE - Projet Compil - M1GMI
-------------------------------------------------------------------
*/
#include "matrice.h"

#define SIZE_BUFFER 512
#define SIZE_LISTE_TRANSITION 500

/* matrice de transition*/
int** matrice;
/*tableau de suppleant*/
int* suppleant;
/*nombre total d'etat*/
int nombre_etat;
/*notre alphabet*/
char* alphabet;
/*nom du fichier a ouvrir*/
char filename[256];
/*taille de l'alphabet*/
int taille_alphabet;

typedef struct {
	int etat_dep;
	char lettre;
	int etat_arr;
} transition;

// Listes de toutes les transitions
transition listeTransition[SIZE_LISTE_TRANSITION];	

int nb_etat = 0;

char **sortie = NULL;

/*Ajoute une lettre a l'alphabet*/
void addLetterInAlphabet(char lettre) {
   if(lettre != '\0') 
		printf("Ajout de la lettre %c dans l'alphabet\n",lettre);
	if (alphabet == NULL) {
		alphabet = (char*) malloc(sizeof(char));
		alphabet[0] = lettre;
	} else {
		alphabet = (char*) realloc(alphabet, sizeof(char) * (taille_alphabet+1));
        if (alphabet == NULL) {
            printf("erreur de realloc dans fixe_alphabet, strlen : %d taille alphabet : %d\n",taille_alphabet,sizeof(alphabet));
        }
   		alphabet[taille_alphabet] = lettre;
	}
	if(lettre!='\0')
		taille_alphabet++;
}

/*ajoute les lettres d'un mot dans l'alphabet si elles n'y sont pas*/
void addWordInAlphabet(char* mot) {
	int i;
	//printf("Ajout du mot %s dans l'alphabet\n",mot);
	if(alphabet==NULL)
		addLetterInAlphabet(mot[0]);
	for(i=0;i<strlen(mot);i++){
		if(!isInAlphabet(mot[i]))
			addLetterInAlphabet(mot[i]);
	}
}

/*permet de savoir si une lettre se trouve dans l'alphabet*/
boolean isInAlphabet(char lettre) {
	int i;
	for(i=0;i<taille_alphabet;i++){
		if(alphabet[i]==lettre)
			return TRUE;
	}
	return FALSE;
}

void createMatrix() {
	int i;
	//printf("je suis dans creer \n");
	matrice = (int**) malloc(sizeof(int*)*taille_alphabet);
	for (i=0;i<taille_alphabet;i++) {
		matrice[i] = (int*) malloc(sizeof(int)*10000);
	}
	//printf("longueur de matrice : %d\n", strlen(matrice[0]));
}

void createState() {
	int i;
	for (i=0;i<taille_alphabet;i++) {
		//matrice[i] = (int*) realloc(matrice[i],sizeof(int)*(nombre_etat+1));
		matrice[i][nombre_etat] = -1;
	}
	nombre_etat++;
}

/*Fonction qui recherche une lettre dans l'alphabet et retourne sa position*/	
int searchPosition(char lettre) {
	int i;
	for(i = 0; i < taille_alphabet; i++) {
		if (alphabet[i] == lettre) {
			return i;
		}
	}
	return -1;
}

/*Ajoute une transition entre etat_depart et etat_arr par la lettre donnee*/
void addTransition(int etat_depart, int etat_arr, char lettre) {
	int pos = searchPosition(lettre);
	
	/* on ajoute une transition entre deux etats */
	if (pos > -1) {	
		matrice[pos][etat_depart] = etat_arr;
	} else {
		printf("La lettre %c n'existe pas dans l alphabet \n",lettre);
	}
}

/*Affichage de la matrice ligne par ligne*/
void postMatrix() {
	int j,i;
	
	printf("---------- MATRICE -----------\n\n");
	
	for (i = 0; i < nombre_etat; i++) {
		for (j = 0;j < taille_alphabet;j++) {
			printf("%d ",matrice[j][i]);
		}
		printf("\n");
	}
}

/*Creer le tableau qui represente les suppleants.Initialise chaque case par 0*/
void createSubstitute() {
	int i;
	suppleant = (int*) malloc(sizeof(int)*nombre_etat);
	for (i = 0; i < nombre_etat; i++) {
		suppleant[i] = 0;
	}
}

void setSubstitute(int etat_dep, int etat_arr) { /*etat inverse debug*/
	suppleant[etat_dep] = etat_arr;
}

void postSubstitute() {
	int i;
	for (i = 0; i < nombre_etat; i++) {
		printf("suppleant[%d] = %d \n",i,suppleant[i]);
	}
}

void postOut() {
	int i;
	char *separateur = { ";" };
	char *mots_trouves;
	
	printf("---------- SORTIE -----------\n\n");
	
	for (i = 0; i < nombre_etat; i++) {
		mots_trouves = strtok(sortie[i], separateur);
		printf("sortie[%d] : %s", i, mots_trouves);
		while (mots_trouves != NULL) {
			mots_trouves = strtok(NULL, separateur);
			if (mots_trouves != NULL) {
					printf(";");
					printf("%s\n", mots_trouves);
			}
		}
		printf("\n");
	}
}


void setOut(int depart_initialisation, char *un_mot) {
	int i;
	
	if (depart_initialisation == 1) {
		depart_initialisation = 0;
	}
	for (i = depart_initialisation; i < nombre_etat-1; i++) {
		
		sortie[i] = (char*) malloc(sizeof(char));
		strcpy(sortie[i], "");
	}
	
	sortie[i] = (char*) malloc(sizeof(char) * strlen(un_mot));
	strcpy(sortie[i], un_mot);
}

transition suivant(int etat_dep, char lettre) {
	transition suivant;
	int i;
	
	i = searchPosition(lettre);
	i++;
	// On commence a rechercher a partir de i
	while (matrice[i-1][etat_dep] == -1) {
		i++;
	}
	suivant.etat_dep = etat_dep;
	suivant.lettre = alphabet[i];
	suivant.etat_arr = matrice[i-1][etat_dep];
	return suivant;	
}

/*Retourne la premiere transition �partir de l'�at etat_dep*/
transition premier(int etat_dep) {
	transition premier;
	int i = 0;
	
	while (matrice[i][etat_dep] == -1) {
		i++;
	}
	
	premier.etat_dep = etat_dep;
	premier.lettre = alphabet[i];
	premier.etat_arr = matrice[i][etat_dep];
	return premier;	
}

/*Calcul des suppl�nts*/
void completer(int etat) {
	int i = 0, pos;
	int r;
	int s;	// Suppl�nt
	int nb_transition;
	int nouvelle_taille;
	transition prem;
	char valeur_sortie[SIZE_BUFFER];
	char valeur_suppleant_sortie[SIZE_BUFFER];
	file_vide();
	// Liste de toutes les transitions (0, a, p) telles que p != 0
	nb_transition = getListOfTransition(0);
	prem = premier(etat);
	while (i < nb_transition){
		enfiler(prem.etat_arr);
		setSubstitute(prem.etat_arr, prem.etat_dep);
		prem = suivant(prem.etat_dep, prem.lettre);
		i++;
	}
	// Tant que la file n'est pas vide
	while (!isEmpty()) {
		r = defiler();
		nb_transition = getListOfTransition(r);
		//printf("nb Transition %d\n",nb_transition);
		if (nb_transition > 0) {
			prem = premier(r);
		}
		i = 0;
		while (i < nb_transition) {
			enfiler(prem.etat_arr);
			s = suppleant[prem.etat_dep];
			
			pos = searchPosition(prem.lettre);
			// Tant que la transition (s, prem.lettre) est non definie
			while (matrice[pos][s] == -1) {
				//printf("pos %d s %d suppleant %d\n",pos,s,suppleant[s]);
				s = suppleant[s];
			}
			
			if(matrice[pos][s]==296){ //YC debug
				postMatrix();
			}	
			setSubstitute(prem.etat_arr, matrice[pos][s]);
			
			if ((i+1) < nb_transition) {
				//printf("suivant\n");
				prem = suivant(prem.etat_dep, prem.lettre);
			}
			// On recupere la sortie de prem.etat_arr
			strcpy(valeur_sortie, sortie[prem.etat_arr]);
			// On recupere la sortie de suppleant(prem.etat_arr);
			strcpy(valeur_suppleant_sortie, sortie[suppleant[prem.etat_arr]]);
			
			// Si la valeur de la sortie du suppleant est non vide
			if (strcmp(valeur_suppleant_sortie, "") != 0) {
				nouvelle_taille = strlen(valeur_sortie)+strlen(valeur_suppleant_sortie)+1;
				sortie[prem.etat_arr] = (char*)realloc(sortie[prem.etat_arr], sizeof(char) * (strlen(valeur_sortie)+strlen(valeur_suppleant_sortie)+1));
				strcpy(sortie[prem.etat_arr], "");
				if (strlen(valeur_sortie) > 0) {
					strcpy(sortie[prem.etat_arr], valeur_sortie);
					
					strcat(sortie[prem.etat_arr], ";");
				}
				strcat(sortie[prem.etat_arr], valeur_suppleant_sortie);
			}
			i++;
		}
	}
}

/* Renvoie la liste de toutes les transitions (etat_depart, a, p).*/
int getListOfTransition(int etat_depart) {
	int i = 0;
	int nb_transition_definie = 0;
	
	// On parcourt une ligne de la matrice
	while (i < taille_alphabet) {
		// S'il y a une transition de d�inie
		if (matrice[i][etat_depart] != 0 && matrice[i][etat_depart] != -1) {
			// On initialise la nouvelle transition
			listeTransition[nb_transition_definie].etat_dep = etat_depart;
			listeTransition[nb_transition_definie].lettre = alphabet[i];
			listeTransition[nb_transition_definie].etat_arr = matrice[i][etat_depart];
			nb_transition_definie++;
		}
		i++;
	}
	return nb_transition_definie;
}

/*Entre les transitions dans la matrice selon un mot donn�*/
void entrer(char *un_mot) {
	int i = 0;
	int etat_de_depart;
	int etat_suivant = 0, save_etat_suivant;
	int pos;
	int save_premier_etat = -1;
	char lettre;	// lettre du mot donn�	int pos;
	int taille_du_mot;
	taille_du_mot = strlen(un_mot);		// La longueur du mot a entrer dans la matrice
	boolean premier_tour_de_boucle = TRUE;

	lettre = un_mot[i];					// La premiere lettre du mot
	pos = searchPosition(lettre);		// On recupere la colonne qui correspond �la lettre suivante
	etat_suivant = matrice[pos][i];
	while (i < taille_du_mot-1 && i < nombre_etat && etat_suivant != -1) {
		lettre = un_mot[i+1];			// La lettre suivante dans le mot
		pos = searchPosition(lettre);	// On recupere la colonne qui correspond �la lettre suivante
		save_etat_suivant = etat_suivant;	// On sauvegarde la valeur de l'etat suivant
		etat_suivant = matrice[pos][etat_suivant];
		i++;
	}
	if (i > 0) {
		// La nouvelle transition commence �partir de "etat_de_depart"
		etat_de_depart = save_etat_suivant;
	} else {
		etat_de_depart = 0;
	}
	while (i < taille_du_mot) {
	// On cree un etat
		createState();
		nb_etat++;
		if (premier_tour_de_boucle) {
			// On sauvegarde le premier etat cree pour ensuite initialiser la sortie
			save_premier_etat = nb_etat;
			premier_tour_de_boucle = FALSE;
		}
		addTransition(etat_de_depart, nb_etat, un_mot[i]);
		etat_de_depart = nb_etat;
		
		i++;
	}
	// On enregistre dans le tableau "sortie" le nouveau mot entr�dans la matrice
   // sortie = (char**)realloc(sortie, sizeof(char*) * (nombre_etat));
    if (save_premier_etat != -1) {
		setOut(save_premier_etat, un_mot);
	} else {
		sortie[i] = (char*) malloc(sizeof(char) * strlen(un_mot));
		strcpy(sortie[i], un_mot);
	}
}

/*Algorithme de pr�aitement*/
int pre_ac(char** ensemble_mot, int nb_mot) {
	int i;
	
	createMatrix();
	createState();	// Creer l'etat q0
	for (i = 0; i < nb_mot; i++) {
		entrer(ensemble_mot[i]);
	}
	for (i = 0; i < taille_alphabet; i++) {
		if (matrice[i][0] == -1) {
			// Boucle sur l'etat initial
			matrice[i][0] = 0;
		}
	}
	createSubstitute(); //createSubstitute(nombre_etat);
	completer(0);	// Calcul des suppleants
	return 0;
}

/*Fonction principale*/
void aho_corasick(char** ensemble_mot, int nb_mot) {
	int etat;
	int j;
	int taille_du_texte;
	int pos;
	char lettre_lue;	// lettre lue dans le texte
	char *separateur = { ";" };
	char *mots_trouves;
	
	int fd_source;	// Descripteur du fichier
	int caractere_lu = -1;
	int nb_caractere_lu = 0;
	char texte[SIZEBUF];
	
	etat = pre_ac(ensemble_mot, nb_mot);
	printf("Ouverture du fichier\n");
	// On ouvre le fichier en lecture
	fd_source = open(filename, O_RDONLY);
	if (fd_source == -1) {
		perror("Erreur d'ouverture du fichier source\n");
		exit(3);
	}
	// On lit ligne par ligne dans le fichier
	while (caractere_lu != 0) {
		caractere_lu = read(fd_source, texte, SIZEBUF);
		if (caractere_lu == -1) {
			perror("Erreur dans la lecture du fichier\n");
			exit(5);
		}

		taille_du_texte = caractere_lu;
		for (j = 0; j < taille_du_texte; j++) {
			lettre_lue = texte[j];
			pos = searchPosition(lettre_lue);
			if (pos > -1) {
				while (matrice[pos][etat] == -1) {
					etat = suppleant[etat];
				}
				etat = matrice[pos][etat];
				if (strcmp(sortie[etat], "") != 0) {
					// On a trouve une occurence dans le texte
					mots_trouves = strtok(sortie[etat], separateur);
					printf("Le mot %s apparait a la position %d dans le texte\n", mots_trouves, (j+1-strlen(mots_trouves)+nb_caractere_lu));
					
                    while (mots_trouves != NULL) {
						mots_trouves = strtok(NULL, separateur);
						if (mots_trouves != NULL) {
							printf("Le mot %s apparait a la position %d dans le texte.\n", mots_trouves, (j+1-strlen(mots_trouves)+nb_caractere_lu));
						}
					}
				}
			} else {
				etat = 0;
			}
		}
		nb_caractere_lu = nb_caractere_lu + caractere_lu;
	}
	close(fd_source);
}

int main(int argc,char *argv[]) {
	int alpha;
	nombre_etat = 0;
	alphabet = NULL;
	char **mots;		// Ensemble de mots a chercher
	char buffer[SIZE_BUFFER];
	int nombre_mot; // = 4;	
	time_t debut, fin;     // permet de calculer la différence de temps
	
	taille_alphabet = 0;

	if(argc<3) {
		printf("Recherche (v1) de motif dans le fichier fic.txt\n");
		printf("Usage : %s fic.txt motif1 [motif2] [motif3] ...\n",argv[0]);
		exit(1);
	}	

    strcpy(filename, argv[1]);	
	nombre_mot = argc-2;

	printf("Recherche (v1) de %d mot(s) dans le fichier %s\n",nombre_mot,filename);
	
	mots = (char**) malloc(sizeof(char*)*nombre_mot);
	sortie = (char**)realloc(sortie, sizeof(char*) * (500));

	for(alpha=2;alpha<argc;alpha++){
		strcpy(buffer,argv[alpha]);
		printf("Ajout et etude du mot %s\n",buffer);
		mots[alpha-2] = (char*) malloc(sizeof(char)*(1+strlen(buffer)));
		strcpy(mots[alpha-2], buffer);
	}
	
	for(alpha=0;alpha<nombre_mot;alpha++) {
		addWordInAlphabet(mots[alpha]);
	}
	addLetterInAlphabet('\0');
	
	time(&debut);
	aho_corasick(mots, nombre_mot);
	time(&fin);
	
	printf("Le programme a mis %.0f secondes pour effectuer la recherche\n", difftime(fin, debut));
	return 1;
}
