/*************************************************************************************************************************************/
/*                                                                                                                                   */
/*        T R A N S F O R M A T I O N   D E   B U R R O W S - W H E E L E R   E T   I N V E R S E  :                                 */
/*                                                                                                                                   */
/*                                                                                                                                   */
/*        Author of '$xtc/BurrowsWheeler.11$vv$I' :                                                                                  */
/*                                                                                                                                   */
/*                    Jean-Francois Colonna (LACTAMME, 20151223080447).                                                              */
/*                                                                                                                                   */
/*************************************************************************************************************************************/

/*************************************************************************************************************************************/
/*                                                                                                                                   */
/*        D E F I N I T I O N   G E N E R A L E S  :                                                                                 */
/*                                                                                                                                   */
/*************************************************************************************************************************************/
int       TransformationDeBurrowsWheeler_EditeLaMatrice=FAUX;
int       TransformationDeBurrowsWheeler_EditerLesChaines=VRAI;
int       TransformationDeBurrowsWheeler_EditionsHexaDecimalesDesChaines=FAUX;
                                        /* Indicateurs de controle des editions...                                                   */

#ifndef   CHAR
#         define    CHAR                                                                                                                \
                              unsigned  char                                                                                            \
                                        /* Afin que tous les tests effectues fonctionnent correctement et que les relations          */ \
                                        /* d'odre soient bien celles que l'on attend, il est a priori necessaire que les             */ \
                                        /* caracteres soient non signes...                                                           */
#else
#endif

#ifndef   FORMAT_CARACTERE
#         define    FORMAT_CARACTERE                                                                                                    \
                              COND((TransformationDeBurrowsWheeler_EditionsHexaDecimalesDesChaines == VRAI),"%02x ","%c")               \
                                        /* Format d'edition des caracteres des chaines et de la matrice...                           */
#else
#endif

#define   BurrowsWheeler_INDEXN                                                                                                         \
                    NombreVersIndex(TransformationDeBurrowsWheeler_LongueurDeToutesLesChaines)
int       TransformationDeBurrowsWheeler_LongueurDeToutesLesChaines;
                                        /* On notera qu'a priori, aucune des chaines utilisees n'a de caractere de fin. Cela         */
                                        /* vient du fait que ces chaines peuvent contenir 256 codes differents et qu'alors le        */
                                        /* code '0x00' habituel ne peut etre utilise. La fin d'une chaine est donc reperee via       */
                                        /* son dernier caractere d'index 'INDEXN'...                                                 */

#ifndef   ACCES_CHAINE
#         define    ACCES_CHAINE(Chaine,IndexCaractere)                                                                                 \
                              *(Chaine+IndexCaractere)                                                                                  \
                                        /* Acces a une chaine quelconque...                                                          */
#else
#endif

CHAR      *TransformationDeBurrowsWheeler_ChaineAPermuter;
#define   SIZE_IndexDeLaChaineAPermuterDansLaMatrice                                                                                    \
                    (sizeof(TransformationDeBurrowsWheeler_IndexDeLaChaineAPermuterDansLaMatrice)*NBITOC)
int       TransformationDeBurrowsWheeler_IndexDeLaChaineAPermuterDansLaMatrice;
                                        /* Definition de la chaine Argument a permuter...                                            */
CHAR      *TransformationDeBurrowsWheeler_ChainePermutee;
                                        /* Definition de la version permutee de 'ChaineAPermuter'...                                 */
CHAR      *TransformationDeBurrowsWheeler_ChainePermuteeTriee;
int       *TransformationDeBurrowsWheeler_CaracteresNombreOccurence;
                                        /* Definition de la version permutee et triee de 'ChaineAPermuter'...                        */
CHAR      *TransformationDeBurrowsWheeler_ChaineRetablie;
                                        /* Definition de la chaine "depermutee" qui doit donc etre identique a 'ChaineAPermuter'...  */

#define   MATRICE(IndexLigne,IndexColonne)                                                                                              \
                    *(TransformationDeBurrowsWheeler_Matrice                                                                            \
                     +((IndexLigne*TransformationDeBurrowsWheeler_LongueurDeToutesLesChaines)+IndexColonne)                             \
                      )
CHAR      *TransformationDeBurrowsWheeler_Matrice;
                                        /* Definition de la matrice contenant 'ChaineAPermuter' et toutes ses permutations           */
                                        /* circulaires possibles.                                                                    */

#define   PERMUTATION_DES_LIGNES_DE_LA_MATRICE(IndexLigne)                                                                              \
                    *(TransformationDeBurrowsWheeler_PermutationDesLignesDeLaMatrice+IndexLigne)
int       *TransformationDeBurrowsWheeler_PermutationDesLignesDeLaMatrice;
                                        /* Definition du tri par ordre croissant des differentes lignes de 'Matrice' via cette       */
                                        /* liste de permutation...                                                                   */

/*************************************************************************************************************************************/
/*                                                                                                                                   */
/*        T R I S   E N   ' N . L O G ( N ) '   D E   C H A I N E S   Q U E L C O N Q U E S  :                                       */
/*                                                                                                                                   */
/*************************************************************************************************************************************/
enum      RelationsDOrdre
          {
           INFERIEUR=-1
          ,EGAL
          ,SUPERIEUR
          };
                                        /* Liste des trois relations d'ordre possibles.                                              */

int       TransformationDeBurrowsWheeler_ComparaisonDeDeuxChaines(int IndexLigne_1
                                                                 ,int IndexLigne_2
                                                                 ,int IndexColonneMinimal
                                                                 ,int IndexColonneMaximal
                                                                  )
          {
          int       IndexColonne=IndexColonneMinimal;
          int       PoursuivreLaComparaison=VRAI;
          int       ResultatDeLaComparaisonDeDeuxChaines;

          while     (PoursuivreLaComparaison == VRAI)
                    {
                    if        (MATRICE(PERMUTATION_DES_LIGNES_DE_LA_MATRICE(IndexLigne_1),IndexColonne)
                              < MATRICE(PERMUTATION_DES_LIGNES_DE_LA_MATRICE(IndexLigne_2),IndexColonne)
                               )
                              {
                              ResultatDeLaComparaisonDeDeuxChaines = INFERIEUR;
                              PoursuivreLaComparaison = FAUX;
                              }
                    else
                              {
                              if        (MATRICE(PERMUTATION_DES_LIGNES_DE_LA_MATRICE(IndexLigne_1),IndexColonne)
                                        == MATRICE(PERMUTATION_DES_LIGNES_DE_LA_MATRICE(IndexLigne_2),IndexColonne)
                                         )
                                        {
                                        ResultatDeLaComparaisonDeDeuxChaines = EGAL;
                                        }
                              else
                                        {
                                        ResultatDeLaComparaisonDeDeuxChaines = SUPERIEUR;
                                        PoursuivreLaComparaison = FAUX;
                                        }
                              }

                    if        (PoursuivreLaComparaison == VRAI)
                              {
                              if        (IndexColonne < IndexColonneMaximal)
                                        {
                                        IndexColonne++;
                                        }
                              else
                                        {
                                        PoursuivreLaComparaison = FAUX;
                                        }
                              }
                    else
                              {
                              }
                    }

          return(ResultatDeLaComparaisonDeDeuxChaines);
          }

#define   ECHANGE_DE_DEUX_CHAINES(IndexLigne_1,IndexLigne_2)                                                                            \
                    {                                                                                                                   \
                    int       VariableDeManoeuvre=PERMUTATION_DES_LIGNES_DE_LA_MATRICE(IndexLigne_1);                                   \
                    PERMUTATION_DES_LIGNES_DE_LA_MATRICE(IndexLigne_1) = PERMUTATION_DES_LIGNES_DE_LA_MATRICE(IndexLigne_2);            \
                    PERMUTATION_DES_LIGNES_DE_LA_MATRICE(IndexLigne_2) = VariableDeManoeuvre;                                           \
                                        /* Permutation "virtuelle" des lignes de la matrice...                                       */ \
                    }

int       TransformationDeBurrowsWheeler_Reorganisation(int IndexLigneDebut
                                                       ,int IndexLigneFin
                                                       ,int IndexColonneMinimal
                                                       ,int IndexColonneMaximal
                                                        )
          {
          int       IndexLigne=IndexLigneDebut;
          int       ItererLaReorganisation=VRAI;

          while     (ItererLaReorganisation == VRAI)
                    {
                    int       IndexLigneGauche=2*IndexLigne;

                    if        (IndexLigneGauche > IndexLigneFin)
                              {
                              ItererLaReorganisation = FAUX;
                              }
                    else
                              {
                              int       IndexMaximal=IndexLigneGauche;
                              int       IndexLigneDroite=IndexLigneGauche+1;

                              if        (IndexLigneDroite > IndexLigneFin)
                                        {
                                        }
                              else
                                        {
                                        if        (TransformationDeBurrowsWheeler_ComparaisonDeDeuxChaines(IndexLigneGauche
                                                                                                          ,IndexLigneDroite
                                                                                                          ,IndexColonneMinimal
                                                                                                          ,IndexColonneMaximal
                                                                                                           )
                                                  < 0
                                                   )
                                                  {
                                                  IndexMaximal = IndexLigneDroite;
                                                  }
                                        else
                                                  {
                                                  }
                                        }

                              if        (TransformationDeBurrowsWheeler_ComparaisonDeDeuxChaines(IndexMaximal
                                                                                                ,IndexLigne
                                                                                                ,IndexColonneMinimal
                                                                                                ,IndexColonneMaximal
                                                                                                 )
                                        <= 0
                                         )
                                        {
                                        ItererLaReorganisation = FAUX;
                                        }
                              else
                                        {
                                        ECHANGE_DE_DEUX_CHAINES(IndexLigne,IndexMaximal);

                                        IndexLigne = IndexMaximal;
                                        }
                              }
                    }

          return(VRAI);
          }

void      TransformationDeBurrowsWheeler_TriRapideDeLEnsembleDesChaines(int IndexLigneDebut
                                                                       ,int IndexLigneFin
                                                                       ,int IndexColonneMinimal
                                                                       ,int IndexColonneMaximal
                                                                        )
          {
          int       IndexLigne=IndexLigneFin/2;

          while     (IndexLigne >= IndexLigneDebut)
                    {
                    TransformationDeBurrowsWheeler_Reorganisation(IndexLigne,IndexLigneFin,IndexColonneMinimal,IndexColonneMaximal);
                    IndexLigne = IndexLigne-1;
                    }

          IndexLigne = IndexLigneFin;

          while     (IndexLigne > IndexLigneDebut)
                    {
                    ECHANGE_DE_DEUX_CHAINES(IndexLigneDebut,IndexLigne);

                    IndexLigne = IndexLigne-1;
                    TransformationDeBurrowsWheeler_Reorganisation(IndexLigneDebut,IndexLigne,IndexColonneMinimal,IndexColonneMaximal);
                    }
          }

/*************************************************************************************************************************************/
/*                                                                                                                                   */
/*        E D I T I O N S   D I V E R S E S  :                                                                                       */
/*                                                                                                                                   */
/*************************************************************************************************************************************/
#define   BurrowsWheeler_EDITION_D_UNE_CHAINE(EditionPreliminaire,ChaineA)                                                              \
                    {                                                                                                                   \
                    if        (TransformationDeBurrowsWheeler_EditerLesChaines == VRAI)                                                 \
                              {                                                                                                         \
                              int       IndexCaractere;                                                                                 \
                                                                                                                                        \
                              EditionPreliminaire;                                                                                      \
                                                                                                                                        \
                              for       (IndexCaractere=INDEX0 ; IndexCaractere <= BurrowsWheeler_INDEXN ; IndexCaractere++)            \
                                        {                                                                                               \
                                        printf(FORMAT_CARACTERE,ACCES_CHAINE(ChaineA,IndexCaractere));                                  \
                                        }                                                                                               \
                                                                                                                                        \
                              printf("\n");                                                                                             \
                              }                                                                                                         \
                    else                                                                                                                \
                              {                                                                                                         \
                              }                                                                                                         \
                    }

#define   EDITION_DE_LA_MATRICE(operateur)                                                                                              \
                    {                                                                                                                   \
                    if        (TransformationDeBurrowsWheeler_EditeLaMatrice == VRAI)                                                   \
                              {                                                                                                         \
                              int       IndexLigne;                                                                                     \
                                                                                                                                        \
                              printf("\n");                                                                                             \
                                                                                                                                        \
                              for       (IndexLigne=INDEX0 ; IndexLigne <= BurrowsWheeler_INDEXN ; IndexLigne++)                        \
                                        {                                                                                               \
                                        int       IndexColonne;                                                                         \
                                                                                                                                        \
                                        for       (IndexColonne=0 ; IndexColonne <= BurrowsWheeler_INDEXN ; IndexColonne++)             \
                                                  {                                                                                     \
                                                  printf(FORMAT_CARACTERE,MATRICE(operateur(IndexLigne),IndexColonne));                 \
                                                  }                                                                                     \
                                                                                                                                        \
                                        printf("\n");                                                                                   \
                                        }                                                                                               \
                                                                                                                                        \
                              printf("\n");                                                                                             \
                              }                                                                                                         \
                    else                                                                                                                \
                              {                                                                                                         \
                              }                                                                                                         \
                    }

/*************************************************************************************************************************************/
/*                                                                                                                                   */
/*        I N I T I A L I S A T I O N   D E   L A   C H A I N E   A   T R A I T E R  :                                               */
/*                                                                                                                                   */
/*************************************************************************************************************************************/
#define   TransformationDeBurrowsWheeler_InitialisationChaineATraiter(ChaineR,ChaineA,LongueurChaineA)                                  \
                    {                                                                                                                   \
                    int       IndexCaractere;                                                                                           \
                                                                                                                                        \
                    TransformationDeBurrowsWheeler_LongueurDeToutesLesChaines = LongueurChaineA;                                        \
                                        /* ATTENTION : en toute generalite dans 'ChaineA' les 256 codes possibles peuvent            */ \
                                        /* etre presents et donc 'strlen(...)' ne peut pas fonctionner systematiquement. C'est       */ \
                                        /* pourquoi un pramatre de longueur 'LongueurChaineA' doit apparaitre explicitement...       */ \
                                                                                                                                        \
                    ChaineR = malloc(TransformationDeBurrowsWheeler_LongueurDeToutesLesChaines);                                        \
                                                                                                                                        \
                    for       (IndexCaractere=INDEX0 ; IndexCaractere <= BurrowsWheeler_INDEXN ; IndexCaractere++)                      \
                              {                                                                                                         \
                              ACCES_CHAINE(ChaineR,IndexCaractere) = ChaineA[IndexCaractere];                                           \
                              }                                                                                                         \
                    }

#define   TransformationDeBurrowsWheeler_DesinitialisationChaineATraiter(ChaineA)                                                       \
                    {                                                                                                                   \
                    free(ChaineA);                                                                                                      \
                    }

/*************************************************************************************************************************************/
/*                                                                                                                                   */
/*        T R A N S F O R M A T I O N   D E   B U R R O W S - W H E E L E R   D I R E C T E  :                                       */
/*                                                                                                                                   */
/*************************************************************************************************************************************/
#define   GenerationDeLaChainePermutee(ChaineR)                                                                                         \
                    {                                                                                                                   \
                    int       IndexLigne;                                                                                               \
                                                                                                                                        \
                    for       (IndexLigne=INDEX0 ; IndexLigne <= BurrowsWheeler_INDEXN ; IndexLigne++)                                  \
                              {                                                                                                         \
                              ACCES_CHAINE(ChaineR,IndexLigne)                                                                          \
                              = MATRICE(PERMUTATION_DES_LIGNES_DE_LA_MATRICE(IndexLigne),BurrowsWheeler_INDEXN);                        \
                                        /* Version permutee de la chaine initiale 'ChaineAPermuter'. Elle est en fait constituee     */ \
                                        /* de la derniere colonne ('INDEXN') de la matrice 'Matrice'...                              */ \
                                                                                                                                        \
                              if        (PERMUTATION_DES_LIGNES_DE_LA_MATRICE(IndexLigne) == INDEX0)                                    \
                                        {                                                                                               \
                                        TransformationDeBurrowsWheeler_IndexDeLaChaineAPermuterDansLaMatrice = IndexLigne;              \
                                        /* Memorisation de l'index de la ligne de la matrice 'Matrice' contenant dans le bon         */ \
                                        /* ordre la chaine Argument...                                                               */ \
                                        }                                                                                               \
                              else                                                                                                      \
                                        {                                                                                               \
                                        }                                                                                               \
                              }                                                                                                         \
                                                                                                                                        \
                    BurrowsWheeler_EDITION_D_UNE_CHAINE({                                                                               \
                                                        printf("%08d "                                                                  \
                                                              ,TransformationDeBurrowsWheeler_IndexDeLaChaineAPermuterDansLaMatrice     \
                                                               );                                                                       \
                                                        }                                                                               \
                                                       ,ChaineR                                                                         \
                                                        );                                                                              \
                    }

#define   TransformationDeBurrowsWheeler_InitialisationTransformationDirecte(ChaineA)                                                   \
                    {                                                                                                                   \
                    TransformationDeBurrowsWheeler_Matrice                                                                              \
                    = malloc(TransformationDeBurrowsWheeler_LongueurDeToutesLesChaines                                                  \
                            *TransformationDeBurrowsWheeler_LongueurDeToutesLesChaines                                                  \
                             );                                                                                                         \
                    TransformationDeBurrowsWheeler_PermutationDesLignesDeLaMatrice                                                      \
                    = malloc(TransformationDeBurrowsWheeler_LongueurDeToutesLesChaines*sizeof(int));                                    \
                    ChaineA = malloc(TransformationDeBurrowsWheeler_LongueurDeToutesLesChaines);                                        \
                                        /* Allocations memoire diverses...                                                           */ \
                    }

#define   TransformationDeBurrowsWheeler_TransformationDirecte(ChaineR,ChaineA)                                                         \
                    {                                                                                                                   \
                    int       IndexLigne;                                                                                               \
                                                                                                                                        \
                    for       (IndexLigne=INDEX0 ; IndexLigne <= BurrowsWheeler_INDEXN ; IndexLigne++)                                  \
                              {                                                                                                         \
                              int       IndexColonne;                                                                                   \
                                                                                                                                        \
                              PERMUTATION_DES_LIGNES_DE_LA_MATRICE(IndexLigne) = IndexLigne;                                            \
                                        /* Initialisation neutre a priori du tri de toutes les chaines...                            */ \
                                                                                                                                        \
                              for       (IndexColonne=0 ; IndexColonne <= BurrowsWheeler_INDEXN ; IndexColonne++)                       \
                                        {                                                                                               \
                                        int       IndexCaractere=IndexColonne-IndexLigne;                                               \
                                                                                                                                        \
                                        if        (IndexCaractere < 0)                                                                  \
                                                  {                                                                                     \
                                                  IndexCaractere = IndexCaractere                                                       \
                                                                   +TransformationDeBurrowsWheeler_LongueurDeToutesLesChaines;          \
                                                  }                                                                                     \
                                        else                                                                                            \
                                                  {                                                                                     \
                                                  }                                                                                     \
                                                                                                                                        \
                                        MATRICE(IndexLigne,IndexColonne) = ChaineA[IndexCaractere];                                     \
                                        /* Permutations circulaires de 'ChaineAPermuter'...                                          */ \
                                        }                                                                                               \
                              }                                                                                                         \
                                                                                                                                        \
                    EDITION_DE_LA_MATRICE(PERMUTATION_DES_LIGNES_DE_LA_MATRICE);                                                        \
                                                                                                                                        \
                    TransformationDeBurrowsWheeler_TriRapideDeLEnsembleDesChaines(INDEX0,BurrowsWheeler_INDEXN                          \
                                                                                 ,INDEX0,BurrowsWheeler_INDEXN                          \
                                                                                  );                                                    \
                                                                                                                                        \
                    EDITION_DE_LA_MATRICE(PERMUTATION_DES_LIGNES_DE_LA_MATRICE);                                                        \
                                                                                                                                        \
                    GenerationDeLaChainePermutee(ChaineR);                                                                              \
                    }

#define   TransformationDeBurrowsWheeler_DesinitialisationsTransformationDirecte()                                                      \
                    {                                                                                                                   \
                    free(TransformationDeBurrowsWheeler_PermutationDesLignesDeLaMatrice);                                               \
                    free(TransformationDeBurrowsWheeler_Matrice);                                                                       \
                    }

/*************************************************************************************************************************************/
/*                                                                                                                                   */
/*        T R A N S F O R M A T I O N   D E   B U R R O W S - W H E E L E R   I N V E R S E   ( V E R S I O N   01 )  :              */
/*                                                                                                                                   */
/*************************************************************************************************************************************/
#define   GenerationDeLaChaineRetablie(ChaineR)                                                                                         \
                    {                                                                                                                   \
                    int       IndexCaractere;                                                                                           \
                                                                                                                                        \
                    for       (IndexCaractere=INDEX0 ; IndexCaractere <= BurrowsWheeler_INDEXN ; IndexCaractere++)                      \
                              {                                                                                                         \
                              ACCES_CHAINE(ChaineR,IndexCaractere)                                                                      \
                              = MATRICE(PERMUTATION_DES_LIGNES_DE_LA_MATRICE                                                            \
                                        (TransformationDeBurrowsWheeler_IndexDeLaChaineAPermuterDansLaMatrice)                          \
                                       ,IndexCaractere                                                                                  \
                                        );                                                                                              \
                              }                                                                                                         \
                    }

#define   TransformationDeBurrowsWheeler_InitialisationTransformationInverse_01(ChaineR)                                                \
                    {                                                                                                                   \
                    TransformationDeBurrowsWheeler_Matrice                                                                              \
                    = malloc(TransformationDeBurrowsWheeler_LongueurDeToutesLesChaines                                                  \
                            *TransformationDeBurrowsWheeler_LongueurDeToutesLesChaines                                                  \
                             );                                                                                                         \
                    TransformationDeBurrowsWheeler_PermutationDesLignesDeLaMatrice                                                      \
                    = malloc(TransformationDeBurrowsWheeler_LongueurDeToutesLesChaines*sizeof(int));                                    \
                    ChaineR = malloc(TransformationDeBurrowsWheeler_LongueurDeToutesLesChaines);                                        \
                                        /* Allocations memoire diverses...                                                           */ \
                    }

#define   TransformationDeBurrowsWheeler_TransformationInverse_01(ChaineR,ChaineA)                                                      \
                    {                                                                                                                   \
                    int       IndexColonne;                                                                                             \
                                                                                                                                        \
                    for       (IndexColonne=INDEX0 ; IndexColonne <= BurrowsWheeler_INDEXN ; IndexColonne++)                            \
                              {                                                                                                         \
                              int       IndexLigne;                                                                                     \
                                                                                                                                        \
                              for       (IndexLigne=INDEX0 ; IndexLigne <= BurrowsWheeler_INDEXN ; IndexLigne++)                        \
                                        {                                                                                               \
                                        MATRICE(IndexLigne,IndexColonne) = 0;                                                           \
                                        /* Initialisation de la matrice : ceci est en fait inutile car cette derniere est remplie    */ \
                                        /* colonne par colonne (en partant de la colonne de droite 'INDEXN') et que n'est utilise    */ \
                                        /* que le sous-ensemble de colonnes qui ont ete remplies.                                    */ \
                                        }                                                                                               \
                              }                                                                                                         \
                                                                                                                                        \
                    for       (IndexColonne=BurrowsWheeler_INDEXN ; IndexColonne >= INDEX0 ; IndexColonne--)                            \
                              {                                                                                                         \
                              int       IndexLigne;                                                                                     \
                                                                                                                                        \
                              for       (IndexLigne=INDEX0 ; IndexLigne <= BurrowsWheeler_INDEXN ; IndexLigne++)                        \
                                        {                                                                                               \
                                        if        (IndexColonne == BurrowsWheeler_INDEXN)                                               \
                                                  {                                                                                     \
                                                  PERMUTATION_DES_LIGNES_DE_LA_MATRICE(IndexLigne) = IndexLigne;                        \
                                        /* Initialisation neutre a priori du tri de toutes les chaines...                            */ \
                                                  }                                                                                     \
                                        else                                                                                            \
                                                  {                                                                                     \
                                                  }                                                                                     \
                                                                                                                                        \
                                        MATRICE(PERMUTATION_DES_LIGNES_DE_LA_MATRICE(IndexLigne),IndexColonne)                          \
                                        = ACCES_CHAINE(ChaineA,IndexLigne);                                                             \
                                        /* La chaine permutee est introduite dans l'ordre du classement courant en tant que          */ \
                                        /* colonne courante de gauche ('IndexColonne').                                              */ \
                                        }                                                                                               \
                                                                                                                                        \
                              EDITION_DE_LA_MATRICE(PERMUTATION_DES_LIGNES_DE_LA_MATRICE);                                              \
                                                                                                                                        \
                              TransformationDeBurrowsWheeler_TriRapideDeLEnsembleDesChaines(INDEX0,BurrowsWheeler_INDEXN                \
                                                                                           ,IndexColonne,BurrowsWheeler_INDEXN          \
                                                                                            );                                          \
                                                                                                                                        \
                              EDITION_DE_LA_MATRICE(PERMUTATION_DES_LIGNES_DE_LA_MATRICE);                                              \
                              }                                                                                                         \
                                                                                                                                        \
                    GenerationDeLaChaineRetablie(ChaineR);                                                                              \
                                        /* La chaine Argment est retrouvee sur la ligne 'IndexDeLaChaineAPermuterDansLaMatrice'      */ \
                                        /* le la matrice 'Matrice'.                                                                  */ \
                                                                                                                                        \
                    BurrowsWheeler_EDITION_D_UNE_CHAINE({},ChaineR);                                                                    \
                    }

#define   TransformationDeBurrowsWheeler_DesinitialisationsTransformationInverse_01(ChaineA1,ChaineA2)                                  \
                    {                                                                                                                   \
                    free(ChaineA1);                                                                                                     \
                    free(ChaineA2);                                                                                                     \
                                                                                                                                        \
                    free(TransformationDeBurrowsWheeler_PermutationDesLignesDeLaMatrice);                                               \
                    free(TransformationDeBurrowsWheeler_Matrice);                                                                       \
                    }

/*************************************************************************************************************************************/
/*                                                                                                                                   */
/*        T R A N S F O R M A T I O N   D E   B U R R O W S - W H E E L E R   I N V E R S E   ( V E R S I O N   02 )  :              */
/*                                                                                                                                   */
/*************************************************************************************************************************************/
#define   TransformationDeBurrowsWheeler_InitialisationTransformationInverse_02(ChaineR)                                                \
                    {                                                                                                                   \
                    ChaineR = malloc(TransformationDeBurrowsWheeler_LongueurDeToutesLesChaines);                                        \
                                        /* Allocations memoire diverses...                                                           */ \
                    }

#define   TransformationDeBurrowsWheeler_echang(index1,index2)                                                                          \
                    {                                                                                                                   \
                    CHAR      tempo=ACCES_CHAINE(TransformationDeBurrowsWheeler_ChainePermuteeTriee,index1);                            \
                    ACCES_CHAINE(TransformationDeBurrowsWheeler_ChainePermuteeTriee,index1)                                             \
                    = ACCES_CHAINE(TransformationDeBurrowsWheeler_ChainePermuteeTriee,index2);                                          \
                    ACCES_CHAINE(TransformationDeBurrowsWheeler_ChainePermuteeTriee,index2) = tempo;                                    \
                    }

int       TransformationDeBurrowsWheeler_reorg(int debut,int fin)
          {
          int       j=debut;
          int       iter=VRAI;

          while     (iter==VRAI)
                    {
                    int       gauche=2*j;

                    if        (gauche>fin)
                              {
                              iter=FAUX;
                              }
                    else
                              {
                              int       indmax=gauche;
                              int       droite=gauche+1;

                              if        (droite>fin)
                                        {
                                        }
                              else
                                        {
                                        if        (ACCES_CHAINE(TransformationDeBurrowsWheeler_ChainePermuteeTriee,gauche)
                                                  < ACCES_CHAINE(TransformationDeBurrowsWheeler_ChainePermuteeTriee,droite)
                                                   )
                                                  {
                                                  indmax=droite;
                                                  }
                                        else
                                                  {
                                                  }
                                        }

                              if        (ACCES_CHAINE(TransformationDeBurrowsWheeler_ChainePermuteeTriee,indmax)
                                         <= ACCES_CHAINE(TransformationDeBurrowsWheeler_ChainePermuteeTriee,j)
                                         )
                                        {
                                        iter=FAUX;
                                        }
                              else
                                        {
                                        TransformationDeBurrowsWheeler_echang(j,indmax);
                                        j=indmax;
                                        }
                              }
                    }
          return(VRAI);
          }

int       TransformationDeBurrowsWheeler_tri(int debut,int fin)
          {
          int       index=fin/2;

          while     (index>=debut)
                    {
                    TransformationDeBurrowsWheeler_reorg(index,fin);
                    index=index-1;
                    }

          index=fin;

          while     (index>debut)
                    {
                    TransformationDeBurrowsWheeler_echang(debut,index);
                    index=index-1;
                    TransformationDeBurrowsWheeler_reorg(debut,index);
                    }

          return(VRAI);
          }

#define   TransformationDeBurrowsWheeler_TransformationInverse_02(ChaineR,ChaineA)                                                      \
                    {                                                                                                                   \
                    int       Index;                                                                                                    \
                                                                                                                                        \
                    TransformationDeBurrowsWheeler_ChainePermuteeTriee                                                                  \
                    = malloc(TransformationDeBurrowsWheeler_LongueurDeToutesLesChaines                                                  \
                             );                                                                                                         \
                    TransformationDeBurrowsWheeler_CaracteresNombreOccurence                                                            \
                    = malloc(TransformationDeBurrowsWheeler_LongueurDeToutesLesChaines*sizeof(int)                                      \
                             );                                                                                                         \
                                                                                                                                        \
                    for       (Index=INDEX0 ; Index <= BurrowsWheeler_INDEXN ; Index++)                                                 \
                              {                                                                                                         \
                              ACCES_CHAINE(TransformationDeBurrowsWheeler_ChainePermuteeTriee,Index)                                    \
                              = ACCES_CHAINE(ChaineA,Index);                                                                            \
                              }                                                                                                         \
                                                                                                                                        \
                    if        (FAUX)                                                                                                    \
                                        /* Cas du tri en N^2 :                                                                       */ \
                              {                                                                                                         \
                              int       index_de_fin;                                                                                   \
                                                                                                                                        \
                              for       (index_de_fin=(BurrowsWheeler_INDEXN-1) ; index_de_fin>=INDEX0 ; index_de_fin=index_de_fin-1)   \
                                        {                                                                                               \
                                        int       index_de_debut;                                                                       \
                                                                                                                                        \
                                        for       (index_de_debut=INDEX0                                                                \
                                                  ; index_de_debut<=index_de_fin                                                        \
                                                  ; index_de_debut=index_de_debut+1                                                     \
                                                   )                                                                                    \
                                                  {                                                                                     \
                                                  if        (ACCES_CHAINE(TransformationDeBurrowsWheeler_ChainePermuteeTriee            \
                                                                         ,index_de_debut                                                \
                                                                          )                                                             \
                                                            > ACCES_CHAINE(TransformationDeBurrowsWheeler_ChainePermuteeTriee           \
                                                                         ,index_de_debut+1                                              \
                                                                          )                                                             \
                                                             )                                                                          \
                                                            {                                                                           \
                                                            CHAR      caractere_manoeuvre;                                              \
                                                            caractere_manoeuvre                                                         \
                                                            = ACCES_CHAINE(TransformationDeBurrowsWheeler_ChainePermuteeTriee           \
                                                                         ,index_de_debut                                                \
                                                                          );                                                            \
                                                            ACCES_CHAINE(TransformationDeBurrowsWheeler_ChainePermuteeTriee             \
                                                                         ,index_de_debut                                                \
                                                                          )                                                             \
                                                            = ACCES_CHAINE(TransformationDeBurrowsWheeler_ChainePermuteeTriee           \
                                                                         ,index_de_debut+1                                              \
                                                                          );                                                            \
                                                            ACCES_CHAINE(TransformationDeBurrowsWheeler_ChainePermuteeTriee             \
                                                                         ,index_de_debut+1                                              \
                                                                          )                                                             \
                                                            = caractere_manoeuvre;                                                      \
                                        /* Tri en N^2 de la chaine permutee...                                                       */ \
                                                            }                                                                           \
                                                  else                                                                                  \
                                                            {                                                                           \
                                                            }                                                                           \
                                                  }                                                                                     \
                                        }                                                                                               \
                              }                                                                                                         \
                    else                                                                                                                \
                              {                                                                                                         \
                                        /* Cas du tri en N.log(N) :                                                                  */ \
                              TransformationDeBurrowsWheeler_tri(INDEX0,BurrowsWheeler_INDEXN);                                         \
                              }                                                                                                         \
                                                                                                                                        \
                    int       NombreOccurence=1;                                                                                        \
                                                                                                                                        \
                    ACCES_CHAINE(TransformationDeBurrowsWheeler_CaracteresNombreOccurence,INDEX0) = NombreOccurence;                    \
                                                                                                                                        \
                    for       (Index=INDEX0+1 ; Index <= BurrowsWheeler_INDEXN ; Index++)                                               \
                              {                                                                                                         \
                              if        (ACCES_CHAINE(TransformationDeBurrowsWheeler_ChainePermuteeTriee,Index-1)                       \
                                        == ACCES_CHAINE(TransformationDeBurrowsWheeler_ChainePermuteeTriee,Index)                       \
                                         )                                                                                              \
                                        {                                                                                               \
                                        NombreOccurence++;                                                                              \
                                        }                                                                                               \
                              else                                                                                                      \
                                        {                                                                                               \
                                        NombreOccurence=1;                                                                              \
                                        }                                                                                               \
                              ACCES_CHAINE(TransformationDeBurrowsWheeler_CaracteresNombreOccurence,Index)=NombreOccurence;             \
                              }                                                                                                         \
                                                                                                                                        \
                    int       index_caractere = TransformationDeBurrowsWheeler_IndexDeLaChaineAPermuterDansLaMatrice;                   \
                                                                                                                                        \
                    for       (Index=INDEX0 ; Index <= BurrowsWheeler_INDEXN ; Index++)                                                 \
                              {                                                                                                         \
                              CHAR      caractere_courant                                                                               \
                                        =ACCES_CHAINE(TransformationDeBurrowsWheeler_ChainePermuteeTriee,index_caractere);              \
                              int       NombreOccurenceCourant                                                                          \
                                        =ACCES_CHAINE(TransformationDeBurrowsWheeler_CaracteresNombreOccurence,index_caractere);        \
                                                                                                                                        \
                              ACCES_CHAINE(ChaineR,Index) = caractere_courant;                                                          \
                                                                                                                                        \
                              int       index_recherche=INDEX0;                                                                         \
                              int       iterer=VRAI;                                                                                    \
                                                                                                                                        \
                              NombreOccurence=1;                                                                                        \
                                                                                                                                        \
                              while     (iterer == VRAI)                                                                                \
                                        {                                                                                               \
                                        if        (ACCES_CHAINE(ChaineA,index_recherche) == caractere_courant)                          \
                                                  {                                                                                     \
                                                  if        (NombreOccurenceCourant == NombreOccurence)                                 \
                                                            {                                                                           \
                                                            index_caractere = index_recherche;                                          \
                                                            iterer = FAUX;                                                              \
                                                            }                                                                           \
                                                  else                                                                                  \
                                                            {                                                                           \
                                                            NombreOccurence++;                                                          \
                                                            }                                                                           \
                                                  }                                                                                     \
                                        else                                                                                            \
                                                  {                                                                                     \
                                                  }                                                                                     \
                                                                                                                                        \
                                        if        (index_recherche < BurrowsWheeler_INDEXN)                                             \
                                                  {                                                                                     \
                                                  index_recherche++;                                                                    \
                                                  }                                                                                     \
                                        else                                                                                            \
                                                  {                                                                                     \
                                                  iterer = FAUX;                                                                        \
                                                  }                                                                                     \
                                        }                                                                                               \
                              }                                                                                                         \
                                                                                                                                        \
                    free(TransformationDeBurrowsWheeler_CaracteresNombreOccurence);                                                     \
                    free(TransformationDeBurrowsWheeler_ChainePermuteeTriee);                                                           \
                    }

#define   TransformationDeBurrowsWheeler_DesinitialisationsTransformationInverse_02(ChaineA1,ChaineA2)                                  \
                    {                                                                                                                   \
                    }

/*************************************************************************************************************************************/
/*                                                                                                                                   */
/*        V E R I F I C A T I O N   D U   P R O C E S S U S   C O M P L E T  :                                                       */
/*                                                                                                                                   */
/*************************************************************************************************************************************/
void      TransformationDeBurrowsWheeler_Verifications(CHAR *ChaineA1,CHAR *ChaineA2)
          {
          int       IndexCaractere;

          for       (IndexCaractere=INDEX0 ; IndexCaractere <= BurrowsWheeler_INDEXN ; IndexCaractere++)
                    {
                    if        (ACCES_CHAINE(ChaineA1,IndexCaractere) != ACCES_CHAINE(ChaineA2,IndexCaractere))
                              {
                              fprintf(stderr
                                     ,"ERREUR(BurrowsWheeler) : chaine retablie ('0x%02x') # chaine a traiter ('0x%02x').\n"
                                     ,ACCES_CHAINE(ChaineA1,IndexCaractere)
                                     ,ACCES_CHAINE(ChaineA2,IndexCaractere)
                                      );
                              }
                    else
                              {
                              }
                    }
          }



Copyright © Jean-François Colonna, 2021-2021.
Copyright © CMAP (Centre de Mathématiques APpliquées) UMR CNRS 7641 / Ecole Polytechnique, 2021-2021.