// aa.c

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

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

#define E(i,j)   e[((i) + 1)*(n + 1) + (j) +1]
#define T(i,j)   t[((i) + 1)*(n + 1) + (j) +1]

#define Del(a)   1
#define Ins(a)   1
#define Sub(a,b) (a == b ? 0 : 3)

void aa(int i, int j, Etat *e, int *t, Mot x, Mot y, Longueur n) {
   PaireAlignee paireAlignee;

   if (i != -1 && j != -1 && T(i, j) == T(i - 1, j - 1) + Sub(x[i], y[j])) {
      if (E(i - 1, j - 1) == NULL) {
         E(i - 1, j - 1) = nouvelEtat();
         aa(i - 1, j - 1, e, t, x, y, n);
      }
      paireAlignee.haut = x[i];
      paireAlignee.bas  = y[j];
      fixerCible(E(i - 1, j - 1), paireAlignee, E(i, j));
   }
   if (i != -1 && T(i, j) == T(i - 1, j) + Del(x[i])) {
      if (E(i - 1, j) == NULL) {
         E(i - 1, j) = nouvelEtat();
         aa(i - 1, j, e, t, x, y, n);
      }
      paireAlignee.haut = x[i];
      paireAlignee.bas  = '-';
      fixerCible(E(i - 1, j), paireAlignee, E(i, j));
   }
   if (j != -1 && T(i, j) == T(i, j - 1) + Ins(y[j])) {
      if (E(i, j - 1) == NULL) {
         E(i, j - 1) = nouvelEtat();
         aa(i, j - 1, e, t, x, y, n);
      }
      paireAlignee.haut = '-';
      paireAlignee.bas  = y[j];
      fixerCible(E(i, j - 1), paireAlignee, E(i, j));
   }
}