// arbre-c-suffixes.c

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

#include <stdio.h>
#include "chl.h"
#include "automate-suff.h"


void descLenteC(Etat p, int k, Etat *resp, int *resk, Mot y, Longueur n) {
   Etat r, q;
   Etiquette etiquette;
   int i, j, ell;

   while (k < n && cibleParUneLettre(p, y[k], y) != NULL) {
      q = cibleParUneLettre(p, y[k], y);
      etiquette = etiq(p, q);
      j = etiquette.position;
      ell = etiquette.longueur;
      i = j;
      do {
         ++i;
         ++k;
      }
      while (i < j + ell && k < n && y[i] == y[k]);
      if (i < j + ell) {
         oterCible(p, etiquette);
         r = nouvelEtat();
         etiquette.position = j;
         etiquette.longueur = i - j;
         fixerCible(p, etiquette, r);
         etiquette.position = i;
         etiquette.longueur = ell - i + j;
         fixerCible(r, etiquette, q);
         *resp = r;
         *resk = k;
         return;
      }
      p = q;
   }
   *resp = p;
   *resk = k;
}


Etat descRapide(Etat r, int j, int k, Mot y) {
   Etat p, q;
   Etiquette etiquette;
   int jp, ell;

   // Calcul de delta(r, y[j..k - 1])
   if (j >= k)
      return(r);
   else {
      q = cibleParUneLettre(r, y[j], y);
      etiquette = etiq(r, q);
      jp = etiquette.position;
      ell = etiquette.longueur;
      if (j + ell <= k)
         return(descRapide(q, j + ell, k, y));
      else {
         oterCible(r, etiquette);
         p = nouvelEtat();
         etiquette.position = j;
         etiquette.longueur = k - j;
         fixerCible(r, etiquette, p);
         etiquette.position = jp + k - j;
         etiquette.longueur = ell - k + j;
         fixerCible(p, etiquette, q);
         return(p);
      }
   }
}



Automate arbreCSuffixes(Mot y, Longueur n) {
   Automate M;
   Etat fourche, q, t;
   Etiquette etiquette;
   int i, j, k, ell;

   M = nouvelAutomate();
   ls(initial(M)) = initial(M);
   fourche = initial(M);
   k = 0;
   for (i = 0; i <= n - 1; ++i) {
      if (k < i)
         k = i;
      if (ls(fourche) == NULL) {
         t = parent(fourche);
         etiquette = etiq(t, fourche);
         j = etiquette.position;
         ell = etiquette.longueur;
         if (t == initial(M))
            --ell;
         ls(fourche) = descRapide(ls(t), k - ell, k, y);
      }
      descLenteC(ls(fourche), k, &fourche, &k, y, n);
      if (k < n) {
         q = nouvelEtat();
         etiquette.position = k;
         etiquette.longueur = n - k;
         fixerCible(fourche, etiquette, q);
         sortie(q) = i;
      }
      else
         sortie(fourche) = i;
   }
   return(M);
}