// interdits.c

// << Algorithmique du texte >>
// Maxime Crochemore, Christophe Hancart et Thierry Lecroq
// Vuibert, 2001.

#include <stdio.h>
#include "chl.h"
#include "cellule.h"
#include "fifo.h"
#include "automate.h"
#include "couple.h"


Automate interdits(Automate Sy) {
   Automate M;
   Couple couple;
   Etat p, pp, qp;
   File L;
   Lettre a;
   int *visite;

   visite = (int *)calloc(dernier(Sy)->nom + 1, sizeof(int));
   if (visite == NULL) error("interdits");

   M = nouvelAutomate();
   L = fileVide();
   visite[initial(Sy)->nom] = VRAI;
   enfiler(L, nouveauCouple(initial(Sy), initial(M)));
   while (!fileEstVide(L)) {
      couple = (Couple)defilement(L);
      p = couple->comp1;
      pp = couple->comp2;
      for (a = PREMIERELETTRE; a <= DERNIERELETTRE; ++a)
         if (cible(p, a) == NULL &&
             (p == initial(Sy) || cible(F(p), a) != NULL)) {
            qp = nouvelEtat();
            terminal(qp) = VRAI;
            fixerCible(pp, a, qp);
         }
         else
            if (cible(p, a) != NULL && !visite[cible(p, a)->nom]){
               qp = nouvelEtat();
               fixerCible(pp, a, qp);
               visite[cible(p, a)->nom] = VRAI;
               enfiler(L, nouveauCouple(cible(p, a), qp));
            }
   }
   free(visite);
   return(M);
}