// les-alignements.c

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

#include <stdio.h>
#include "chl.h"
#include "alignement.h"
#include "les-alignements.h"

#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 lesAlignements(Mot x, Longueur m, Mot y, Longueur n, int *t) {
   Alignement z;

   z = NULL;
   la(m - 1, n - 1, z, x, y, n, t);
}


void la(int i, int j, Alignement z, Mot x, Mot y, Longueur n, int *t) {

   if (i != -1 && j != -1 && T(i, j) == T(i - 1, j - 1) + Sub(x[i], y[j])) {
      z = ajouterAuDebutAlignement(z, x[i], y[j]);
      la(i - 1, j - 1, z, x, y, n, t);
      z = retirerAuDebutAlignement(z);
   }
   if (i != -1 && T(i, j) == T(i - 1, j) + Del(x[i])) {
      z = ajouterAuDebutAlignement(z, x[i], '-');
      la(i - 1, j, z, x, y, n, t);
      z = retirerAuDebutAlignement(z);
   }
   if (j != -1 && T(i, j) == T(i, j - 1) + Ins(y[j])) {
      z = ajouterAuDebutAlignement(z, '-', y[j]);
      la(i, j - 1, z, x, y, n, t);
      z = retirerAuDebutAlignement(z);
   }
   if (i == -1 && j == -1)
      ecrireAlignement(z);
}