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

/*-------------------------------------------------------------------
 * Inverses.c   Jean-Eric Pin 13/04/97
 * On cree les tableaux Inverses et InversesFaibles. Pour chaque element s,
 * Inverses[s] contient la liste des inverses de s et InversesFaibles[s]
 * contient la liste des inverses faibles qui ne sont pas inverses de s.
 * L'algorithme ci-dessous devra etre ameliore pour eviter de faire un
 * parcours pour CHAQUE t dans S.
 * Algorithme : pour chaque t dans S, on fait un parcours en profondeur
 * du graphe du preordre <=J issu de t. Pour chaque s sur ce parcours,
 * on a s <=J t par construction et on teste si
 *  (1) st est idempotent
 *  (2) st R s
 * (3) s J t
 * Si (1) et (2) sont remplies, on a st = e, e R s, d'ou es = s
 * et donc sts = s. Donc s est un inverse faible de t. La reciproque
 * est immediate. Si de plus (3) est vraie, s est inverse de t.
 *-------------------------------------------------------------------
 */     

#include <stdlib.h>
#include <stdio.h>
#include "Main.h"
#include "Calcul.h"
#include "DclassesIteratif.h"
#include "Globales.h"
#include "Memoire.h"
#include "Reduction.h"
#include "Sortie.h"
#include "SortieLaTeX.h"
#include "TableDeS.h"
#include "Utilitaires.h"
#include "Varietes.h"
#include "Inverses.h"

extern unsigned long NbElements, NbIdempotents;
extern unsigned short NbLettres, PossedeUnNeutre;
extern unsigned long TestsEffectues, Varietes, CalculsEffectues;
extern char **Messages;
extern info *Table;     /* La table contenant les informations sur les elements */
extern info2 *Table2;     /* La table contenant les autres informations sur les elements */
extern unsigned long *TableIdempotents;  /* La table des idempotents */
extern unsigned long **TableDeS;  /* La table de multiplication du semigroupe */

struct NumeroEtLettre *PileInverses;
ListeNumero *Inverses, *InversesFaibles;
static unsigned long NbGenerateursKS, TailleCourante;
static unsigned long *TableKS, *TableGenerateursKS;


/***************************************************************************
*
*  MiseAJour
*
***************************************************************************/

void MiseAJour(unsigned long s, unsigned long t)
{
  unsigned long st;
  ListeNumero Temporaire;
  
  st = ProduitParReduction(s, t);
  if ((Table[st].Statut & IDEMPOTENT) && (Table2[st].Rclasse == Table2[s].Rclasse))    /* s inverse faible de t */
  {
    Temporaire = AlloueMemoireWagonNumero();
    Temporaire->t = s;
    if ((Table2[s].Dclasse == Table2[t].Dclasse))    /* s inverse de t */
    {
      Temporaire->suivant = Inverses[t];
      Inverses[t] = Temporaire;
    }
    else                                          /* s inverse faible de t */
    {
      Temporaire->suivant = InversesFaibles[t];
      InversesFaibles[t] = Temporaire;
    }
  }
}

/***************************************************************************
*
* ParcoursGrapheJ. Parcours en profondeur du graphe de l'ordre <=J
* a partir d'un sommet t.
*
***************************************************************************/

void ParcoursGrapheJ(unsigned long t)
{
  register lettre a;
  register long i;
  register unsigned long s, u;
  
  for (i = IDENTITE; i <= NbElements; i++)
    Table2[i].Statut &= ~D_VISITE;        /* Initialisation des drapeaux */
  i = 0;
  PileInverses[0].Numero = t;
  do
  {
    s = PileInverses[i].Numero;
    a = PileInverses[i].Lettre;
    if ((Table2[s].Statut & D_VISITE) == 0)  /* Premiere visite dans s */
    {
      MiseAJour(s, t);
      Table2[s].Statut |= D_VISITE;
    }
    u = (a < NbLettres) ? Table[s].Produits[a].D & ~EST_REDUIT : Table[s].Produits[a - NbLettres].G;
    if ((Table2[u].Statut & D_VISITE) == 0)  /* Si possible, on descend en profondeur. */
      PileInverses[++i].Numero = u;
    else if (a < (2 * NbLettres - 1))        /* Sinon, on explore les autres branches */
      PileInverses[i].Lettre++;
    else                            /* Plus rien a explorer a ce niveau : on remonte */ 
      PileInverses[i--].Lettre = 0;
  }
  while (i != -1);  
}

/***************************************************************************
*
* Inverses. 
*
***************************************************************************/

void CalculInverses(void)
{
  unsigned long t;
  ListeNumero Temporaire;
  
  if (!(CalculsEffectues & CALCUL_INVERSES))
  {
    CalculIdempotents();
    CalculDclasses();
    Inverses = AlloueMemoireTableListeNumero();
    InversesFaibles = AlloueMemoireTableListeNumero();
    if (NbLettres == 0)    /* Cas du monoide trivial */
    {
      Temporaire = AlloueMemoireWagonNumero();
      Temporaire->t = IDENTITE;
      Temporaire->suivant = NULL;
      Inverses[IDENTITE] = Temporaire;
      return;
    }
    PileInverses = AlloueMemoirePileNumeroEtLettre();
    for (t = IDENTITE; t <= NbElements; t++)
      ParcoursGrapheJ(t);
    CalculsEffectues |= CALCUL_INVERSES;    /* On prend note : le calcul des inverses est termine */
  }
}

/***************************************************************************
*
* ProduitsDroits. Prend en argument un element u et calcule les elements ut et tu
* ou t parcourt l'ensemble des generateurs de K(S). 
*
***************************************************************************/

void ProduitsDroits(unsigned long u)
{
  unsigned long i, t, ut;
  
  for (i = 0; i < NbGenerateursKS; i++)                /* Calcul de ut et de tu */
  {
    t = TableGenerateursKS[i];
    ut = TableDeS[u][t];
    if ((Table[ut].Statut & EST_DANS_KS) == 0)  /* Si ut n'est pas deja dans K(S) */
    {
      TableKS[TailleCourante++] = ut;
      Table[ut].Statut |= EST_DANS_KS;
    }
  }
}

/***************************************************************************
*
* ProduitsGauches. Prend en argument un element u et calcule les elements tu
* ou t parcourt les K premiers de generateurs de K(S). 
*
***************************************************************************/

void ProduitsGauches(unsigned long u)
{
  unsigned long i, t, tu;
  
  for (i = 0; i < NbGenerateursKS; i++)                /* Calcul de tu */
  {
    t = TableGenerateursKS[i];
    tu = TableDeS[t][u];
    if ((Table[tu].Statut & EST_DANS_KS) == 0)  /* Si tu n'est pas deja dans K(S) */
    {
      TableKS[TailleCourante++] = tu;
      Table[tu].Statut |= EST_DANS_KS;
    }
  }
}

/***************************************************************************
*
* Conjugue. Prend en argument des elements u et s et calcule les elements
* de la forme v = sut, ou t est un inverse de s. Pour chaque element v ainsi
* trouve, on calcule les produits 
*
***************************************************************************/

void Conjugue(unsigned long i, unsigned long s)
{
  unsigned long j, t, sut, u, v;
  ListeNumero Liste;

  u = TableKS[i];
  Liste = Inverses[s];
  while (Liste != NULL)
  {
    t = Liste->t;
    sut = TableDeS[TableDeS[s][u]][t];
    if ((Table[sut].Statut & EST_DANS_KS) == 0)    /* Si sut n'est pas dans K(S) */
    {
      TableKS[TailleCourante++] = TableGenerateursKS[NbGenerateursKS++] = sut;
      Table[sut].Statut |= EST_DANS_KS;
      for (j = 0; j < i; j++)
      {
        v = TableKS[j];
        ProduitsGauches(v);
      }
    }
    Liste = Liste->suivant;
  }
}
  
/***************************************************************************
*
* ConjugueFaiblement. Prend en argument des elements u et s et calcule les
* elements de la forme sut et tus, ou t est un inverse faible de s.
*
***************************************************************************/

void ConjugueFaiblement(unsigned long i, unsigned long s)
{
  unsigned long j, t, sut, tus, u, v;
  ListeNumero Liste;

  u = TableKS[i];
  Liste = InversesFaibles[s];
  while (Liste != NULL)
  {
    t = Liste->t;
    sut = TableDeS[TableDeS[s][u]][t];
    if ((Table[sut].Statut & EST_DANS_KS) == 0)    /* Si sut n'est pas dans K(S) */
    {
      TableKS[TailleCourante++] = TableGenerateursKS[NbGenerateursKS++] = sut;
      Table[sut].Statut |= EST_DANS_KS;
      for (j = 0; j < i; j++)
      {
        v = TableKS[j];
        ProduitsGauches(v);
      }
    }
    tus = TableDeS[TableDeS[t][u]][s];
    if ((Table[tus].Statut & EST_DANS_KS) == 0)    /* Si tus n'est pas dans K(S) */
    {
      TableKS[TailleCourante++] = TableGenerateursKS[NbGenerateursKS++] = tus;
      Table[tus].Statut |= EST_DANS_KS;
      for (j = 0; j < i; j++)
      {
        v = TableKS[j];
        ProduitsGauches(v);
      }
    }
    Liste = Liste->suivant;
  }
}

/***************************************************************************
*
* Calcul du noyau.
* K(S) est l'intersection des \tau^{-1}(1), prise sur tous les morphismes
* relationnels \tau de M dans un groupe G. D'apres le theoreme de Ash, on a
* K(S) = D(S), ou D(S) est le plus petit sous-semigroupe de S ferme par
* conjugaison faible. Comme D(S) contient E(S), on part de E(S) et on fait
* for each u in D(S)
*   for each weakly conjugate pair (s, t)
*      add sut and tus to D(S)
*    add D(S)u to D(S)
* Si les idempotents commutent, K(S) = E(S)
*
***************************************************************************/

void CalculKS(void)
{
  unsigned long i, s;
  
  if (!(CalculsEffectues & CALCUL_KS))
  {
    TestECom();
    if (Varietes & SEM_ECOM)    /* Le semigroupe est dans Ecom, K(S) = E(S) */
    {
      for (i = 0; i < NbIdempotents; i++)
        Table[TableIdempotents[i]].Statut |= EST_DANS_KS;
      return;
    }
    CalculListeIdempotents();    /* Calculs preliminaires */
    CalculInverses();
    CalculTableDeS();
    TableKS = AlloueMemoireTableau(NbElements);
    TableGenerateursKS = AlloueMemoireTableau(NbElements);
    
    for (i = 0; i < NbIdempotents; i++)                        /* Au depart, K(S) = E(S) */
    {
      TableKS[i] = TableGenerateursKS[i] = TableIdempotents[i];
      Table[TableIdempotents[i]].Statut |= EST_DANS_KS;
    }
    
    NbGenerateursKS = TailleCourante = NbIdempotents;
    i = 0;
    while (i < TailleCourante)
    {
      for (s = IDENTITE + !PossedeUnNeutre; s <= NbElements; s++)      /* Calcul de sut */
      {
        Conjugue(i, s);
        ConjugueFaiblement(i, s); 
      }
      ProduitsDroits(TableKS[i]);
      i++;
    }
    free(TableKS);
    free(TableGenerateursKS);
    CalculsEffectues |= CALCUL_KS;    /* On prend note : le calcul de K(S) est termine */
  }
}