// alp-complet.c

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

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

Automate alpComplet(Ensemble X) {
   Automate M;
   Couple couple;
   Etat p, q, q0, r, s;
   File F;
   Lettre a;

   M = arbre(X);
   q0 = initial(M);
   F = fileVide();
   for (a = PREMIERELETTRE; a <= DERNIERELETTRE; ++a) {
      q = cible(q0, a);
      if (q == NULL)
         fixerCible(q0, a, q0);
      else
         enfiler(F, nouveauCouple(q, q0));
   }
   while (!fileEstVide(F)) {
      couple = (Couple)defilement(F);
      p = (Etat)(couple->comp1);
      r = (Etat)(couple->comp2);
      if (terminal(r))
         terminal(p) = VRAI;
      for (a = PREMIERELETTRE; a <= DERNIERELETTRE; ++a) {
         q = cible(p, a);
         s = cible(r, a);
         if (q == NULL)
            fixerCible(p, a, s);
         else
            enfiler(F, nouveauCouple(q, s));
      }
   }
   return(M);
}