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

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

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "Globales.h"
#include "Main.h"
#include "Initialisation.h"
#include "Sortie.h"
#include "Reduction.h"

extern unsigned short NbLettres;
extern unsigned long NbElements; 
extern info *Table; 
extern info2 *Table2; 
extern char **Messages;

static unsigned long sa, as;
  

/****************************************************
*
* Reduction. OK
*
****************************************************/

unsigned long Reduction(lettre *Mot)
{
  unsigned short LongueurMot;
  unsigned long n = IDENTITE;
  short i;
  
  LongueurMot = strlen((char *)Mot);    /* A changer si lettre = short !! */
  if (Mot[0] != '1')
    for (i = 0; i < LongueurMot; i++)
      n = Table[n].Produits[Mot[i] - 'a'].D;   /* Pas tres stable, a revoir */
  return n;
}

/****************************************************
*
* ProduitParReduction. OK
*
****************************************************/

unsigned long ProduitParReduction(unsigned long n1, unsigned long n2)
{  
  if (Table[n1].Longueur <= Table[n2].Longueur)
  {
    while (n1 != IDENTITE) 
    {
      n2 = Table[n2].Produits[Table[n1].Finale].G; 
      n1 = Table[n1].Prefixe;
    }
    return(n2);
  }
  while (n2 != IDENTITE) 
  {
    n1 = Table[n1].Produits[Table[n2].Initiale].D  & ~EST_REDUIT; 
    n2 = Table[n2].Suffixe;
  }
  return(n1);
}

/****************************************************
*
* ProduitParReductionRecursif. OK
*
****************************************************/

unsigned long ProduitParReductionRecursif(unsigned long n1, unsigned long n2)
{  
  if (Table[n1].Longueur <= Table[n2].Longueur)
  {
    if (n1 != IDENTITE) 
      return(ProduitParReductionRecursif(Table[n1].Prefixe, Table[n2].Produits[Table[n1].Finale].G));
    return(n2);
  }
  if (n2 != IDENTITE) 
    return(ProduitParReductionRecursif(Table[n1].Produits[Table[n2].Initiale].D  & ~EST_REDUIT, Table[n2].Suffixe));
  return(n1);
}

/****************************************************
*
* ProduitParReductionInfo. OK
*
****************************************************/

info *ProduitParReductionInfo(info *n1, info *n2)
{  
  if (n1->Longueur <= n2->Longueur)
  {
    while (n1 != &Table[IDENTITE]) 
    {
      n2 = &Table[n2->Produits[n1->Finale].G]; 
      n1 = &Table[n1->Prefixe];
    }
    return(n2);
  }
  while (n2 != &Table[IDENTITE]) 
  {
    n1 = &Table[n1->Produits[n2->Initiale].D  & ~EST_REDUIT]; 
    n2 = &Table[n2->Suffixe];
  }
  return(n1);
}

/****************************************************
*
* xOmega. OK
*
****************************************************/

unsigned long xOmega(unsigned long x)
{
  register unsigned long n;
  
  n = x;
  while ((Table2[n].xOmega == 0))
    n = ProduitParReduction(n, x);   /* A accelerer lorsqu'on saura si n est regulier */   
  return(n);
}

/****************************************************
*
* Calcul_eSe_Brutal. OK
*
****************************************************/

void Calcul_eSe_Brutal(unsigned long e)   /* Par force brute ! A modifier */
{
  unsigned long n;

  if ((Table[e].Statut & IDEMPOTENT) == 0)
    printf("%s\n", Messages[M_Is_not_idempotent]);  /* Cet element n'est pas idempotent ! */
  else
  {
    for (n = IDENTITE; n <= NbElements; n++)
      Table[n].Statut &= ~EST_ELEMENT_LOCAL;
    for (n = IDENTITE; n <= NbElements; n++)
      Table[ProduitParReduction(ProduitParReduction(e, n),e)].Statut |= EST_ELEMENT_LOCAL;
  }
}

/****************************************************
*
* ParcoursGauche. OK
*
****************************************************/

void ParcoursGauche(unsigned long s)   /* Parcours en profondeur du graphe gauche */
{
  lettre a;

  for (a = 0; a < NbLettres; a++)
  {
    as = Table[s].Produits[a].G;
    if ((Table[as].Statut & EST_DANS_IDEAL_GAUCHE) == 0)
    {
      Table[as].Statut |= EST_DANS_IDEAL_GAUCHE;
      ParcoursGauche(as);
    }
  }
}

/****************************************************
*
* ParcoursDroit. OK
*
****************************************************/

void ParcoursDroit(unsigned long s)   /* Parcours en profondeur du graphe droit */
{
  lettre a;

  for (a = 0; a < NbLettres; a++)
  {
    sa = Table[s].Produits[a].D;
    if ((Table[sa].Statut & EST_DANS_IDEAL_DROIT) == 0)
    {
      Table[sa].Statut |= EST_DANS_IDEAL_DROIT;
      ParcoursDroit(sa);
    }
  }
}

/****************************************************
*
* CalculIdealDroit. OK
*
****************************************************/

void CalculIdealDroit(unsigned long s)   /* Ideal a droite engendre par s */
{
  unsigned long n;

  for (n = IDENTITE; n <= NbElements; n++)
    Table[n].Statut &= ~EST_DANS_IDEAL_DROIT;
  ParcoursDroit(s);
}

/****************************************************
*
* CalculIdealGauche. OK
*
****************************************************/

void CalculIdealGauche(unsigned long s)   /* Ideal a gauche engendre par s */
{
  unsigned long n;

  for (n = IDENTITE; n <= NbElements; n++)
    Table[n].Statut &= ~EST_DANS_IDEAL_GAUCHE;
  ParcoursGauche(s);
}

/****************************************************
*
* CalculMonoideLocal. OK
*
****************************************************/

void CalculMonoideLocal(unsigned long e)   
{
  InitDrapeaux();
  if (Table[e].Statut & IDEMPOTENT)
  {
    Table[e].Statut |= EST_DANS_IDEAL_DROIT | EST_DANS_IDEAL_GAUCHE;    /* Necessaire lorsque e = 1 */
    ParcoursDroit(e);
    ParcoursGauche(e);
  }
}

/****************************************************
*
* CalculMonoideLocalMot. OK
*
****************************************************/

void CalculMonoideLocalMot(lettre *Mot)
{
  CalculMonoideLocal(Reduction(Mot));
}