/*************************************** * * * Copyright (c) 1998 Jean-Eric Pin * * All rights reserved. * * * * TAB = 2 spaces * * * ***************************************/ /*------------------------------------------------------------------- * Transitions.c Jean-Eric Pin 07/12/96 *------------------------------------------------------------------- */ #include <stdlib.h> #include <stdio.h> #include <errno.h> #include <fcntl.h> #include "Erreurs.h" #include "FichierUnix.h" #include "Globales.h" #include "InitiauxFinaux.h" #include "Main.h" #include "Initialisation.h" #include "Memoire.h" #include "Sortie.h" #include "Transitions.h" #include "Utilitaires.h" #if SYSTEME == MAC #include <unix.h> #endif #ifdef DEBUG extern long ElementsAlloues; #endif /* DEBUG */ extern unsigned short NbEtats, NbLettres, EtatInitial1, PartiePointee, InitiauxDejaSpecifies, FinauxDejaSpecifies; extern unsigned long TailleElement; extern element *Generateurs, *TableDesValeurs; extern unsigned long TailleTableDeHachage, TailleTableDeHachageMoinsUn, CalculsEffectues; extern unsigned long NbElements, TailleMaxi; extern char **Messages; extern info *Table; /* La table contenant les informations sur les elements */ extern char s[TAILLE_CHAINE_MAX]; extern unsigned short *EtatsInitiaux, *EtatsFinaux; extern Sortie_ SortieElement; /************************************************************************ * * CopieTransitions : copie x dans y * ************************************************************************/ void CopieTransitions(element x, element y) { register short q; for (q = 1; q <= NbEtats; q++) ((Transitions)y)[q] = ((Transitions)x)[q]; } /************************************************************************ * * EstEgalTransitions : Teste l'egalite de deux transformations * ************************************************************************/ short EstEgalTransitions(element x, element y) { register short q; for (q = 1; q <= NbEtats; q++) if (((Transitions)x)[q] != ((Transitions)y)[q]) return(0); return(1); } /************************************ * * ProduitTransitions * ************************************/ void ProduitTransitions(element x, element y, element xy) { register short q; for (q = 1; q <= NbEtats; q++) ((Transitions)xy)[q] = ((Transitions)y)[((Transitions)x)[q]]; } /************************************ * * ProduitParTransitionsPartielles * ************************************/ void ProduitTransitionsPartielles(element x, element y, element xy) { register short q; ((Transitions)xy)[0] = 0; for (q = 1; q <= NbEtats; q++) ((Transitions)xy)[q] = ((Transitions)y)[((Transitions)x)[q]]; } /************************************************************ * * HachageTransitions. Meilleure version apres test par le * Profiler, car les collisions coutent tres cher. * ************************************************************/ unsigned long HachageTransitions(element x) { register short i; register unsigned long h; h = 0; for (i = 1; i <= NbEtats; i++) h = (h * (NbEtats + 1) + ((Transitions)x)[i]) % TailleTableDeHachage; return(h); } /************************************************************ * * HachageUneLettreTransitions, un seul generateur. A modifier ! * ************************************************************/ unsigned long HachageUneLettreTransitions(element x) { return(((Transitions)x)[1] % TailleTableDeHachage); } /************************************************************ * * HachageSecondaireTransitions. * ************************************************************/ unsigned long HachageSecondaireTransitions(element x) { register short i; register unsigned long h; h = 0; for (i = 1; i <= NbEtats; i++) h = (h * (NbEtats + 1) + ((Transitions)x)[i]) % TailleTableDeHachageMoinsUn; return(1+h); /* Il faut eviter la valeur 0 ! */ } /************************************************************ * * HachageSecondaireUneLettreTransitions, un seul generateur. A modifier ! * ************************************************************/ unsigned long HachageSecondaireUneLettreTransitions(element x) { return(1 + ((Transitions)x)[1] % TailleTableDeHachageMoinsUn); } /******************************************************** * * FaireIdentiteTransitions : Initialisation de l'identite * ********************************************************/ void FaireIdentiteTransitions(element x) { short q; for (q = 0; q <= NbEtats; q++) ((Transitions)x)[q] = q; } /**************************************************** * * SauvegardeTransitions. OK * ****************************************************/ void SauvegardeTransitions(FILE *fichier) { short q; lettre a; int erreur; if (fprintf(fichier, "%8u %% Nombre d'etats\n", NbEtats) < 0) { erreur = errno; printf("fprintf %8u %% Nombre d'etats failed!\n", NbEtats); Erreur_printf(erreur); return; } for (a = 0; a < NbLettres; a++) { for (q = 1; q <= NbEtats; q++) if (fprintf(fichier, "%u ", ((Transitions)Generateurs[a])[q]) < 0) { erreur = errno; printf("fprintf %u failed!\n", ((Transitions)Generateurs[a])[q]); Erreur_printf(erreur); return; } if (fprintf(fichier, "\n") < 0) { erreur = errno; printf("fprintf %s failed!\n", "\\n"); Erreur_printf(erreur); return; } } if (PartiePointee && InitiauxDejaSpecifies) SauvegardeInitiaux(fichier); if (PartiePointee && FinauxDejaSpecifies) SauvegardeFinaux(fichier); } /**************************************************** * * LectureTransitions. OK * ****************************************************/ void LectureTransitions(FILE *fichier) { unsigned short q; lettre a; if (fscanf(fichier, "%hu %% Nombre d'etats", &NbEtats) != 1) { printf("scanf error\n"); exit(1); } AlloueMemoireGenerateurs(); for (a = 0; a < NbLettres; a++) { for (q = 1; q <= NbEtats; q++) if (fscanf(fichier, "%hu", &((Transitions)Generateurs[a])[q]) != 1) { printf("scanf error: Generateurs\n"); exit(1); } } fscanf(fichier, "\n"); fscanf(fichier, "%% Etats initiaux"); fscanf(fichier, "\n"); if (InitiauxDejaSpecifies) LectureInitiaux(fichier); fscanf(fichier, "\n"); fscanf(fichier, "%% Etats finaux"); fscanf(fichier, "\n"); if (FinauxDejaSpecifies) LectureFinaux(fichier); } /**************************************************** * * EntreeTransitions. OK * ****************************************************/ void EntreeTransitions(void) { unsigned short q, n; lettre a; printf("%s ", Messages[M_Number_of_states]); /* Nombre d'etats de l'automate ? */ if (scanf("%hu", &NbEtats) != 1) { printf("scanf error\n"); exit(1); } printf("\n"); TailleElement = (1 + NbEtats) * sizeof(short); AlloueMemoireGenerateurs(); for (a = 0; a < NbLettres; a++) { ((Transitions)Generateurs[a])[0] = 0; for (q = 1; q <= NbEtats; q++) { do { printf("%d.%c = ", q, a + 97); if (scanf("%hu", &n) != 1) { printf("scanf error\n"); exit(1); } } while (!(n <= NbEtats)); ((Transitions)Generateurs[a])[q] = n; } printf("\n"); } EntreeEtatsInitiauxFinaux(); } /**************************************************** * * SortieTransitions. Sortie d'un element. OK * ****************************************************/ void SortieTransitions(element x) { short q; for (q = 1; q <= NbEtats; q++) printf("%2d ", ((Transitions)x)[q]); printf("\n"); } /**************************************************** * * SortieLaTeXTransitions. Sortie d'un element. OK * ****************************************************/ void SortieLaTeXTransitions(element x, FILE *fichier) { short q; for (q = 1; q <= NbEtats; q++) fprintf(fichier, "&%d ", ((Transitions)x)[q]); } /**************************************************** * * AlloueMemoireTransitions. OK * ****************************************************/ element AlloueMemoireTransitions(void) { register element Element; Element = (void *)ALLOC(unsigned short, (1 + NbEtats)); if (Element == NULL) { printf("%s %s\n", Messages[M_Pb_memory], Messages[M_Pb_transitions]); exit(1); } #ifdef DEBUG ElementsAlloues++; #endif /* DEBUG */ return Element; } /**************************************************** * * LibereMemoireTransitions. OK * ****************************************************/ void LibereMemoireTransitions(element Element) { free(Element); #ifdef DEBUG ElementsAlloues--; #endif /* DEBUG */ } /**************************************************************************** * * EntreePartieTransitions. OK * Definit la partie pointee P a partir des ensembles I (etats initiaux) et F * (etats finaux). * P = { u | 1.u est dans F} lorsqu'il y a un seul etat initial 1 * P = { u | il existe i dans I et f dans F tels que u_{i,f} = 1 } * ****************************************************************************/ void EntreePartieTransitions(void) { unsigned long u; short i; if (FinauxDejaSpecifies && EtatInitial1) /* Etat initial 1, etats finaux specifies */ { for (u = IDENTITE; u <= NbElements; u++) if (EtatsFinaux[((Transitions)TableDesValeurs[u])[1]] == 1) Table[u].Statut |= EST_DANS_P; else Table[u].Statut &= ~EST_DANS_P; } else if (FinauxDejaSpecifies && InitiauxDejaSpecifies) /* Etat initiaux et finaux specifies */ { for (u = IDENTITE; u <= NbElements; u++) { for (i = 0; i < NbEtats; i++) { if ((EtatsInitiaux[i]) && (EtatsFinaux[((Transitions)TableDesValeurs[u])[1]] == 1)) /* i etat initial */ break; /* i est initial et i.u est un etat final */ } if (i != NbEtats) Table[u].Statut |= EST_DANS_P; else Table[u].Statut &= ~EST_DANS_P; } } else /* Pas d'etats initiaux ni finaux specifies */ EntreePartieStandard(); CalculsEffectues |= CALCUL_P; /* On prend note : le calcul de P est termine */ #ifdef DEBUG for (u = IDENTITE; u <= NbElements; u++) { SortieMotFormate(u, 1); printf(" "); SortieElement(TableDesValeurs[u]); if (Table[u].Statut & EST_DANS_P) printf(" In P\n"); else printf(" Not in P\n"); } #endif /* DEBUG */ }