/***************************************
*                                      *
*   Copyright (c) 1998 Jean-Eric Pin   *
*   All rights reserved.               *
*                                      *
*   TAB = 2 spaces                     *
*                                      *
***************************************/

/*-------------------------------------------------------------------
 * MatricesMaxPlus.c    Jean-Eric Pin 07/12/96
 *-------------------------------------------------------------------
 */     

#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#include <limits.h>
#include "Globales.h"
#include "Main.h"
#include "InitiauxFinaux.h"
#include "Matrices.h"
#include "MatricesMaxPlus.h"
#include "Memoire.h"
#include "Utilitaires.h"

extern unsigned short NbEtats, NbLettres, PartiePointee,
                      InitiauxDejaSpecifies, FinauxDejaSpecifies;
extern unsigned long Periode, Seuil;
extern element *Generateurs;
extern unsigned long TailleElement;
extern char **Messages;

/******************
*  
*  Ecrete. OK  
*  
******************/

long Ecrete(long x)
{
  if (x > Seuil)
    x = Seuil;
  return(x);
}

/******************
*  
*  PlusMinMax. OK  
*  
******************/

long PlusMinMax(long x, long y)
{
  if ((x == LONG_MAX) || (y == LONG_MAX))
    return(LONG_MAX);
  if ((x == LONG_MIN) || (y == LONG_MIN))
    return(LONG_MIN);
  return(x + y);
}

/****************************************************
*
* EntreeSemiAnneauMaxPlusTropical. OK
*
****************************************************/

void EntreeSemiAnneauMaxPlusTropical(void)
{
    printf("%s\n", Messages[M_Semiring_minus_infinity]);  /* Semianneau {-infini, 0, 1, ..., s} ou s est le seuil */
    EntreeSeuil();
    Periode = 0;
}

/****************************************************
*
* EntreeSemiAnneauMaxPlusTropical. OK
*
****************************************************/

void EntreeSemiAnneauMinPlusTropical(void)
{
      printf("%s\n", Messages[M_Semiring_plus_infinity]);  /* Semianneau {0, 1, ..., s, +infini} ou s est le seuil */
      EntreeSeuil();
      Periode = 0;
}

/****************************************************
*
* EntreeMatricesMaxPlus. OK
*
****************************************************/

void EntreeMatricesMaxPlus(void)
{
  short p, q;
  lettre a;
  static char s[] = "        ";

  printf("%s ", Messages[M_Size_matrices_question_mark]);  /* Taille des matrices ? */
  if (scanf("%hu", &NbEtats) != 1)
  {
    printf("scanf error\n");
    exit(1);
  }
  TailleElement = NbEtats * NbEtats * sizeof(short);
  AlloueMemoireGenerateurs();
  printf("%s\n", Messages[M_Type_minus]);  /* Taper % pour "- infini" */
  for (a = 0; a < NbLettres; a++)
  {
    for (p = 0; p < NbEtats; p++)
      for (q = 0; q < NbEtats; q++)
      {
        printf("%c[%d,%d] = ", a + 97, p + 1, q + 1);        
        if (scanf("%s", s) != 1)
        {
          printf("scanf error\n");
          exit(1);
        }
        if (s[0] == '%')
          ((Matrice)Generateurs[a])[p][q] = LONG_MIN;
        else
          ((Matrice)Generateurs[a])[p][q] = atol(s);
      }
    printf("\n");
  }
  if (PartiePointee && (!FinauxDejaSpecifies))
    EntreeEtatsInitiauxFinaux();
}

/****************************************************
*
* EntreeMatricesMinPlus. OK
*
****************************************************/

void EntreeMatricesMinPlus(void)
{
  short p, q;
  lettre a;
  static char s[] = "        ";

  printf("%s ", Messages[M_Size_matrices_question_mark]);  /*  printf("Taille des matrices ? ");  */
  if (scanf("%hu", &NbEtats) != 1)
  {
    printf("scanf error\n");
    exit(1);
  }
  TailleElement = NbEtats * NbEtats * sizeof(short);
  AlloueMemoireGenerateurs();
  printf("%s\n", Messages[M_Type_plus]);  /* Taper % pour "+ infini" */
  for (a = 0; a < NbLettres; a++)
  {
    for (p = 0; p < NbEtats; p++)
      for (q = 0; q < NbEtats; q++)
      {
        printf("%c[%d,%d] = ", a + 97, p + 1, q + 1);        
        if (scanf("%s", s) != 1)
        {
          printf("scanf error\n");
          exit(1);
        }
        if (s[0] != '%')
          ((Matrice)Generateurs[a])[p][q] = atol(s);
        else
          ((Matrice)Generateurs[a])[p][q] = LONG_MAX;
      }
    printf("\n");
  }
  if (PartiePointee && (!FinauxDejaSpecifies))
    EntreeEtatsInitiauxFinaux();
}

/****************************************************
*
* EntreeMatricesMaxPlusTropicales. OK
*
****************************************************/

void EntreeMatricesMaxPlusTropicales(void)
{
  short p, q;
  lettre a;
  static char s[] = "        ";

  EntreeSemiAnneauMaxPlusTropical();  
  printf("%s ", Messages[M_Size_matrices_question_mark]);  /* Taille des matrices ? */
  if (scanf("%hu", &NbEtats) != 1)
  {
    printf("scanf error\n");
    exit(1);
  }
  TailleElement = NbEtats * NbEtats * sizeof(short);
  AlloueMemoireGenerateurs();
  printf("%s\n", Messages[M_Type_minus]);  /* Taper % pour "- infini" */
  for (a = 0; a < NbLettres; a++)
  {
    for (p = 0; p < NbEtats; p++)
      for (q = 0; q < NbEtats; q++)
      {
        printf("%c[%d,%d] = ", a + 97, p + 1, q + 1);        
        if (scanf("%s", s) != 1)
        {
          printf("scanf error\n");
          exit(1);
        }
        if (s[0] == '%')
          ((Matrice)Generateurs[a])[p][q] = LONG_MIN;
        else
          ((Matrice)Generateurs[a])[p][q] = Ecrete(atol(s));
      }
    printf("\n");
  }
  if (PartiePointee && (!FinauxDejaSpecifies))
    EntreeEtatsInitiauxFinaux();
}

/****************************************************
*
* EntreeMatricesMinPlusTropicales. OK
*
****************************************************/

void EntreeMatricesMinPlusTropicales(void)
{
  short p, q;
  lettre a;
  static char s[] = "        ";

  EntreeSemiAnneauMinPlusTropical();
  printf("%s ", Messages[M_Size_matrices_question_mark]);  /*  printf("Taille des matrices ? ");  */
  if (scanf("%hu", &NbEtats) != 1)
  {
    printf("scanf error\n");
    exit(1);
  }
  TailleElement = NbEtats * NbEtats * sizeof(short);
  AlloueMemoireGenerateurs();
  printf("%s\n", Messages[M_Type_plus]);  /* Taper % pour "+ infini" */
  for (a = 0; a < NbLettres; a++)
  {
    for (p = 0; p < NbEtats; p++)
      for (q = 0; q < NbEtats; q++)
      {
        printf("%c[%d,%d] = ", a + 97, p + 1, q + 1);        
        if (scanf("%s", s) != 1)
        {
          printf("scanf error\n");
          exit(1);
        }
        if (s[0] != '%')
          ((Matrice)Generateurs[a])[p][q] = Ecrete(atol(s));
        else
          ((Matrice)Generateurs[a])[p][q] = LONG_MAX;
      }
    printf("\n");
  }
  if (PartiePointee && (!FinauxDejaSpecifies))
    EntreeEtatsInitiauxFinaux();
}

/************************************
*  
*  NormeMatricesMaxPlus (calcule le Max des coefficients) 
*  
************************************/

long NormeMatricesMaxPlus(Matrice x)
{
  register short p, q;
  long Max = LONG_MIN;

  for (p = 0; p < NbEtats; p++)
    for (q = 0; q < NbEtats; q++)
      if (Max < x[p][q])
        Max = x[p][q];
  return Max;
}

/************************************
*  
*  ProduitMatricesMaxPlus
*  
************************************/

void ProduitMatricesMaxPlus(element x, element y, element xy)
{
  register short p, q, r;
  long v;

  for (p = 0; p < NbEtats; p++)
    for (q = 0; q < NbEtats; q++)
    {
      v = LONG_MIN;
      for (r = 0; r < NbEtats; r++)
        v = Max(v, PlusMinMax(((Matrice)x)[p][r], ((Matrice)y)[r][q]));
      ((Matrice)xy)[p][q] = v ;
    }
}

/************************************
*  
*  ProduitMatricesMinPlus  
*  
************************************/

void ProduitMatricesMinPlus(element x, element y, element xy)
{
  register short p, q, r;
  long v;

  for (p = 0; p < NbEtats; p++)
    for (q = 0; q < NbEtats; q++)
    {
      v = LONG_MAX;
      for (r = 0; r < NbEtats; r++)
        v = Min(v, PlusMinMax(((Matrice)x)[p][r], ((Matrice)y)[r][q]));
      ((Matrice)xy)[p][q] = v;  
    }
}

/************************************
*  
*  ProduitMatricesMaxPlusTropicales
*  
************************************/

void ProduitMatricesMaxPlusTropicales(element x, element y, element xy)
{
  register short p, q, r;
  long v;

  for (p = 0; p < NbEtats; p++)
    for (q = 0; q < NbEtats; q++)
    {
      v = LONG_MIN;
      for (r = 0; r < NbEtats; r++)
        v = Max(v, PlusMinMax(((Matrice)x)[p][r], ((Matrice)y)[r][q]));
      ((Matrice)xy)[p][q] = Ecrete(v) ;
    }
}

/************************************
*  
*  ProduitMatricesMinPlusTropicales  
*  
************************************/

void ProduitMatricesMinPlusTropicales(element x, element y, element xy)
{
  register short p, q, r;
  long v;

  for (p = 0; p < NbEtats; p++)
    for (q = 0; q < NbEtats; q++)
    {
      v = LONG_MAX;
      for (r = 0; r < NbEtats; r++)
        v = Min(v, PlusMinMax(((Matrice)x)[p][r], ((Matrice)y)[r][q]));
      ((Matrice)xy)[p][q] = Ecrete(v) ;  
    }
}

/************************************
*  
*  ProduitMatProjectivesMaxPlus
*  
************************************/

void ProduitMatMaxPlusProjectives(element x, element y, element xy)
{
  register short p, q, r;
  long v, Norme;

  for (p = 0; p < NbEtats; p++)
    for (q = 0; q < NbEtats; q++)
    {
      v = LONG_MIN;
      for (r = 0; r < NbEtats; r++)
        v = Max(v, PlusMinMax(((Matrice)x)[p][r], ((Matrice)y)[r][q]));
      ((Matrice)xy)[p][q] = v;
    }
  Norme = NormeMatricesMaxPlus((Matrice)xy);
  for (p = 0; p < NbEtats; p++)
    for (q = 0; q < NbEtats; q++)
      if (((Matrice)xy)[p][q] != LONG_MIN)
        ((Matrice)xy)[p][q] -= Norme;
}

/********************************************************
*            
* FaireIdentiteMatricesMaxPlus : Initialisation de l'identite  
*            
********************************************************/

void FaireIdentiteMatricesMaxPlus(element x)
{
  short p, q;

  for (p = 0; p < NbEtats; p++)
    for (q = 0; q < NbEtats; q++)
      ((Matrice)x)[p][q] = LONG_MIN;  
  for (p = 0; p < NbEtats; p++)
      ((Matrice)x)[p][p] = 0;  
}
    
/********************************************************
*            
* FaireIdentiteMatricesMinPlus : Initialisation de l'identite  
*            
********************************************************/

void FaireIdentiteMatricesMinPlus(element x)
{
  short p, q;

  for (p = 0; p < NbEtats; p++)
    for (q = 0; q < NbEtats; q++)
      ((Matrice)x)[p][q] = LONG_MAX;  
  for (p = 0; p < NbEtats; p++)
      ((Matrice)x)[p][p] = 0;  
}

/****************************************************
*
* SortieMatricesMaxPlus : Sortie d'un element. OK
*
****************************************************/

void SortieMatricesMaxPlus(element x)
{
  short p, q;

  for (p = 0; p < NbEtats; p++)
  {
    for (q = 0; q < NbEtats; q++)
      if (((Matrice)x)[p][q] == LONG_MIN) 
        printf(" -%% ");
      else
        printf("%3ld ", ((Matrice)x)[p][q]);
    printf("|");
  }
  printf("\n");
}

/****************************************************
*
* SortieMatricesMaxPlusTropicales : Sortie d'un element. OK
*
****************************************************/

void SortieMatricesMaxPlusTropicales(element x)
{
  short p, q;

  for (p = 0; p < NbEtats; p++)
  {
    for (q = 0; q < NbEtats; q++)
      if (((Matrice)x)[p][q] == LONG_MIN) 
        printf(" -%% ");
      else
        printf("%3ld ", ((Matrice)x)[p][q]);
    printf("|");
  }
  printf("\n");
}

/****************************************************
*
* SortieMatricesMinPlus : Sortie d'un element. OK
*
****************************************************/

void SortieMatricesMinPlus(element x)
{
  short p, q;

  for (p = 0; p < NbEtats; p++)
  {
    for (q = 0; q < NbEtats; q++)
      if (((Matrice)x)[p][q] == LONG_MAX) 
        printf(" +%% ");
      else
        printf("%3ld ", ((Matrice)x)[p][q]);
    printf("|");
  }
  printf("\n");
}

/****************************************************
*
* SortieMatricesMinPlusTropicales : Sortie d'un element. OK
*
****************************************************/

void SortieMatricesMinPlusTropicales(element x)
{
  short p, q;

  for (p = 0; p < NbEtats; p++)
  {
    for (q = 0; q < NbEtats; q++)
      if (((Matrice)x)[p][q] >= Seuil) 
        printf("%3ld ", Seuil);
      else
        printf("%3ld ", ((Matrice)x)[p][q]);
    printf("|");
  }
  printf("\n");
}

/****************************************************
*
* SortieLaTeXMatricesMaxPlus : Sortie d'un element. OK
*
****************************************************/

void SortieLaTeXMatricesMaxPlus(element x, FILE *MyFile)
{
  short p, q;

  for (p = 0; p < NbEtats; p++)
  {
    for (q = 0; q < NbEtats; q++)
      if (((Matrice)x)[p][q] == LONG_MIN) 
        fprintf(MyFile, "&$-\\infty$ ");
      else
        fprintf(MyFile, "&%ld ", ((Matrice)x)[p][q]);
  }
  fprintf(MyFile, "\n");
}

/****************************************************
*
* SortieLaTeXMatricesMaxPlusTropicales : Sortie d'un element. OK
*
****************************************************/

void SortieLaTeXMatricesMaxPlusTropicales(element x, FILE *MyFile)
{
  short p, q;

  for (p = 0; p < NbEtats; p++)
  {
    for (q = 0; q < NbEtats; q++)
      if (((Matrice)x)[p][q] == LONG_MIN) 
        fprintf(MyFile, "&$-\\infty$ ");
      else
        fprintf(MyFile, "&%ld ", ((Matrice)x)[p][q]);
  }
  fseek(MyFile, -2, SEEK_CUR);
  fprintf(MyFile, "\n");
}

/****************************************************
*
* SortieLaTeXMatricesMinPlus : Sortie d'un element. OK
*
****************************************************/

void SortieLaTeXMatricesMinPlus(element x, FILE *MyFile)
{
  short p, q;

  for (p = 0; p < NbEtats; p++)
  {
    for (q = 0; q < NbEtats; q++)
      if (((Matrice)x)[p][q] == LONG_MAX) 
        fprintf(MyFile, "&$+\\infty$ ");
      else
        fprintf(MyFile, "&%ld ", ((Matrice)x)[p][q]);
  }
  fseek(MyFile, -2, SEEK_CUR);
  fprintf(MyFile, "\n");
}

/****************************************************
*
* SortieLaTeXMatricesMinPlusTropicales : Sortie d'un element. OK
*
****************************************************/

void SortieLaTeXMatricesMinPlusTropicales(element x, FILE *MyFile)
{
  short p, q;

  for (p = 0; p < NbEtats; p++)
  {
    for (q = 0; q < NbEtats; q++)
      if (((Matrice)x)[p][q] >= Seuil) 
        fprintf(MyFile, "&$+\\infty$ ");
      else
        fprintf(MyFile, "&%ld ", ((Matrice)x)[p][q]);
  }
  fseek(MyFile, -2, SEEK_CUR);
  fprintf(MyFile, "\n");
}