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

char **sortie = NULL;
/*nom du fichier a ouvrir*/
char filename[256];

void postOut() {
	int i;
	
	printf("---------- SORTIE -----------\n\n");
	printf("Nb etat = %d\n",nombre_etat);
	for (i = 0; i <= nombre_etat; i++) {
		printf("sortie[%d] : %s\n",i, sortie[i]);
	}
}


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

/*Donne la transition suivante*/
trans* suivant(trans *liste) {
    trans *listeSuivante;
    
    listeSuivante = liste->suivant;
	return listeSuivante;
}

/*Donne la premiere transition a partir d un etat donne*/
trans* premier(int etat_dep) {
    trans *listePremiere;
    
    listePremiere = matrice[etat_dep];
	return listePremiere;
}

/*Entre les transitions dans la matrice selon un mot donne*/
void entrer(char *un_mot) {
    int i = 0;
    int taille_du_mot = strlen(un_mot);		// La longueur du mot a entrer dans la matrice
    //int etat = 0;
    int etat_de_depart, etat_arrivee;
    int save_etat_suivant;
    char lettre;	// lettre du mot donn�
    lettre = un_mot[i];
    
    int save_premier_etat;
    boolean premier_tour_de_boucle = TRUE;
    
    etat_arrivee = isDefinedTransition(0, lettre);
    while (i < taille_du_mot && etat_arrivee != -1) {
        lettre = un_mot[i+1];
        save_etat_suivant = etat_arrivee;
        etat_arrivee = isDefinedTransition(etat_arrivee, lettre);
        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) {
        lettre = un_mot[i];
        if (premier_tour_de_boucle) {
			// On sauvegarde le premier etat cree pour ensuite initialiser la sortie
			save_premier_etat = nombre_etat+1;
			premier_tour_de_boucle = FALSE;
		}
		matrice[etat_de_depart] = addTransition(etat_de_depart, nombre_etat+1, lettre);
        etat_de_depart = nombre_etat;
        i++;
    }
    // On enregistre dans le tableau "sortie" le nouveau mot entr�dans la matrice
	setOut(save_premier_etat, un_mot);
}

void calculateSubstitute(trans *prem, int r) {
    int s;
    int etat_arrivee;
    trans *transitionTemp;
    boolean trouve;
    int nouvelle_taille;
    char valeur_sortie[50];
	char valeur_suppleant_sortie[50];
    
    enfiler(prem->etat_arr);
    s = suppleant[r];
    //Tant que la transition (s, prem->lettre) est non definie
    while (isDefinedTransition(s, prem->lettre) == -1) {
        s = suppleant[s];
    }
    //On doit trouver l'etat d'arrivee de la transition (s, prem->lettre)
    transitionTemp = matrice[s];
    trouve = FALSE;
    while (transitionTemp->suivant != NULL && !trouve) {
        if (transitionTemp->lettre == prem->lettre) {
            etat_arrivee = transitionTemp->etat_arr;
            trouve = TRUE;
        }
        transitionTemp = transitionTemp->suivant;
    }
    if (transitionTemp->suivant == NULL && !trouve) {
        etat_arrivee = transitionTemp->etat_arr;
    }
    setSubstitute(prem->etat_arr, etat_arrivee);
    //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] = realloc(sortie[prem->etat_arr], sizeof(char) * nouvelle_taille);
		if (sortie[prem->etat_arr] == NULL) {
            printf("ERROR realloc : Allocation impossible\n");
            printf("Dans la fonction 'calculer_suppleant'\n");
            exit(10);
        }
		strcpy(sortie[prem->etat_arr], "");
		if (strlen(valeur_sortie) > 0) {
			// On separe chaque sortie par ;
			strcpy(sortie[prem->etat_arr], valeur_sortie);
			strcat(sortie[prem->etat_arr], ";");
		}
		strcat(sortie[prem->etat_arr], valeur_suppleant_sortie);
    }
}

void completer(int etat) {
    trans *prem;
    int r;

    file_vide();
    prem = premier(etat);
    //Liste de toutes les transitions (0, a, p) telles que p != 0
    while (prem->suivant != NULL) {
        if (prem->etat_arr != 0) {
            enfiler(prem->etat_arr);
            setSubstitute(prem->etat_arr, etat);
        }
        prem = prem->suivant;
    }
    if (prem != NULL) {
        if (prem->etat_arr != 0) {
            enfiler(prem->etat_arr);
            setSubstitute(prem->etat_arr, etat);
        }
    }
    //Tant que la file n'est pas vide
	while (!isEmpty()) {
		r = defiler();
		prem = premier(r);
		//s'il y a une transition qui existe
		if (prem != NULL) {
            //Tant qu'il y a une transition
            while (prem->suivant != NULL && prem->etat_arr != 0) {
                calculateSubstitute(prem, r);
                prem = prem->suivant;
            }
            //Il reste une transition
            calculateSubstitute(prem, r);
        }
    }
}



/*Algorithme de pretraitement*/
int pre_ac(char** ensemble_mot, int nb_mot) {
	int i;
	
	createMatrix();
	for (i = 0; i < nb_mot; i++) {
		entrer(ensemble_mot[i]);
	}
	//Pour toutes les lettres de l'alphabet
	for (i = 0; i < taille_alphabet; i++) {
		if (isDefinedTransition(0, alphabet[i]) == -1) {
			//Boucle sur l'etat initial
			matrice[0] = addTransition(0, 0, alphabet[i]);
			//printf("Ajout transition nb etat %d,alpha %d\n",nombre_etat,taille_alphabet);
		}
	}
	createSubstitute();
	completer(0);	//Calcul des suppleants
	return 0;
}

/*Renvoie true si la lettre donnee appartient a l'alphabet, false sinon*/
boolean letterIsInAlphabet(lettre) {
    int i;
    
    for (i = 0; i < taille_alphabet; i++) {
        if (alphabet[i] == lettre) {
            return TRUE;
        }
    }
    return FALSE;
}

/*Fonction principale*/
void aho_corasick(char** ensemble_mot, int nb_mot) {
	int etat;
	int j;
	int taille_du_texte;	
	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);   //Pretraitement

    //afficher_sortie();
	
	//exit(0);
	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++) {
            //On lit lettre par lettre
			lettre_lue = texte[j];
			//Si la lettre appartient a l'alphabet
			if (letterIsInAlphabet(lettre_lue)) {
                while (isDefinedTransition(etat, lettre_lue) == -1) {
				    etat = suppleant[etat];
                }
                etat = isDefinedTransition(etat, lettre_lue);
                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[]) {
    char **mots;		   //Ensemble de mots a chercher
	int nombre_mot = 4;    //Nombre de mots a chercher dans le texte
	time_t debut, fin;     //Date de depart et de fin de l'application
	int alpha;
	char buffer[512];
	taille_alphabet = 0;

	sortie = (char**)malloc(sizeof(char));

   if(argc<3) {
		printf("Recherche (v2) 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 (v2) de %d mot(s) dans le fichier %s\n",nombre_mot,filename);
	
	mots = (char**) malloc(sizeof(char*)*nombre_mot);
	sortie = malloc(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;
}
