/***************************************
* *
* Copyright (c) 1998 Jean-Eric Pin *
* All rights reserved. *
* *
* TAB = 2 spaces *
* *
***************************************/
/*-------------------------------------------------------------------
* Calcul.c Jean-Eric Pin 07/12/96
*-------------------------------------------------------------------
*/
#include <stdlib.h>
#include <stdio.h>
#include "Main.h"
#include "Calcul.h"
#include "Espace.h"
#include "Globales.h"
#include "Memoire.h"
#include "Initialisation.h"
#include "Reduction.h"
#ifdef PROFIL
#include <Profiler.h>
extern OSErr error;
#endif /* PROFIL */
extern unsigned short NbLettres, LongueurMax, TypeCalcul, PossedeUnNeutre,
PossedeUnZero;
extern unsigned long NbElements, NbReelElements, NbIdempotents, DernierMot;
extern unsigned long NbRelations, TailleTableDeHachage, CalculsEffectues;
extern element *Generateurs;
extern unsigned long *TableDeHachage;
extern unsigned long *TableIdempotents;
extern info *Table;
extern info2 *Table2;
extern element *TableDesValeurs; /* Les valeurs des elements du semigroupe dans l'univers. */
extern short TypeSemigroupe;
extern Produit_ Produit;
extern Hachage_ Hachage;
extern Hachage_ HachageSecondaire;
extern EstEgal_ EstEgal;
extern Alloue_ AlloueMemoireElement;
extern Libere_ LibereMemoireElement;
/****************************************************************************
*
* Range(element x, unsigned long *n).
*
* Recherche un element x dans la table. Retourne l'adresse de x dans la table de
* hachage en cas de succes et l'adresse d'une case vide en cas d'echec.
* Retourne dans *n le unsigned long de l'element x dans la table des valeurs (en cas de
* succes), ou 0 (en cas de nouvel element).
*
* Pour cela, on applique une premiere fonction de hachage a x, ce qui donne h.
* On examine l'entree T[h] :
* - Si l'entree T[h] est libre (valeur 0), n = 0;
* - Sinon, on compare la valeur de T[h] a x. En cas d'egalite, on a fini.
* Sinon, on applique une seconde fonction de hachage, ce qui donne h2, et
* on explore successivement les adresses h, h + h2, h + 2h2, etc., jusqu'a ce
* qu'on trouve une entree vide (n = 0) ou de valeur egale a x.
*
****************************************************************************/
unsigned long Range(element x, unsigned long *n)
{
unsigned long h, h2;
h = Hachage(x);
*n = TableDeHachage[h];
if ((*n != 0) && !EstEgal(x, TableDesValeurs[*n]))
{
h2 = HachageSecondaire(x);
do
{
h = (h + h2) % TailleTableDeHachage;
*n = TableDeHachage[h];
}
while ((*n != 0) && !EstEgal(x, TableDesValeurs[*n]));
}
return (h);
}
/************************************************************************
*
* Calcul du monoide de transition. Il y a trois variables importantes :
* u, qui donne l'adresse du mot courant u sur lequel on effectue les
* calculs ua et au (pour a dans A).
* DernierMot, qui donne l'adresse du dernier mot calcule par produit droit
* NbElements, qui donne le nombre total d'elements calcules.
*
************************************************************************/
void Calcul(void)
{
register lettre a, Initiale, Finale;
unsigned long h;
unsigned long u = IDENTITE, ap, sa, s, p, u0, ua; /* u0 est le premier mot de Longueur Courante */
element valeur_ua = 0;
register info *Table_u, *Table_ua;
short LongueurCourante;
short PasDeMemoireLibre = 1;
InitCalcul();
#ifdef DEBUG
printf("InitCalcul: successfull\n");
#endif /* DEBUG */
if (NbLettres != 0)
u = Table[IDENTITE].Suivant; /* On commence avec la premiere lettre */
else
{
NbReelElements = NbElements - (!PossedeUnNeutre && (TypeCalcul == Semigroupe));
return; /* S'il n'y a pas de generateurs, c'est termine */
}
LongueurCourante = 1;
u0 = u;
/***********************************************************************************
*
* Le calcul des elements. Soit u le mot courant, a la lettre courante,
* et soit v = ua. L'adresse du suffixe de longueur |u|-1 de u est s.
* On teste si s est un mot reduit.
* (1) S'il ne l'est pas, on met a jour et on passe a la lettre suivante.
* (2) S'il l'est, on procede au calcul de la valeur de ua.
*
* Le bit de poids fort de Table[u].Produits[a].D vaut 0 si ua est reductible,
* 1 si ua est irreductible.
*
************************************************************************************/
#ifdef PROFIL
if (!ProfilerInit(collectDetailed, PPCTimeBase, 10, 4))
{
#endif /* PROFIL */
while (u != 0)
{
while (Table[u].Longueur == LongueurCourante)
{
Table_u = &Table[u];
s = Table_u->Suffixe;
Initiale = Table_u->Initiale;
#ifdef DEBUG
printf("Calcul de au: u = %lu \n", u);
printf("Calcul de au: Initiale = %c \n", Initiale + 97);
printf("Calcul de au: s = %lu \n", s);
#endif /* DEBUG */
for (a = 0; a < NbLettres; a++)
{
if ((Table[s].Produits[a].D & EST_REDUIT) == 0) /* Si sa est reductible */
{
sa = Table[s].Produits[a].D & ~EST_REDUIT; /* Soit s le suffixe de longueur n-1. On calcule sa */
if (sa == IDENTITE)
{ /* sa = 1; dans ce cas, ua = initiale(u) */
PossedeUnNeutre = 1;
Table_u->Produits[a].D = Table[IDENTITE].Produits[Initiale].D & ~EST_REDUIT;
}
else
Table_u->Produits[a].D = Table[Table[Table[sa].Prefixe].Produits[Initiale].G].Produits[Table[sa].Finale].D & ~EST_REDUIT;
}
else /* sa est reduit */
{
if (PasDeMemoireLibre)
valeur_ua = AlloueMemoireElement(); /* On se decide au calcul de la valeur de ua et on note que sa est irreductible. */
Produit(TableDesValeurs[u], Generateurs[a], valeur_ua);
h = Range(valeur_ua, &ua); /* Desormais, la valeur de ua est connue */
PasDeMemoireLibre = (ua == 0);
if (PasDeMemoireLibre) /* Si cette valeur est nouvelle... */
{
TableDesValeurs[++NbElements] = valeur_ua;
TableDeHachage[h] = ua = NbElements;
Table[ua].Produits = AlloueMemoireProduits(); /* On alloue l'espace pour le nouvel element */
}
Table_u->Produits[a].D = ua; /* On peut maintenant calculer ua. */
Table_ua = &Table[ua];
if (((Table_ua->Statut & EST_CALCUL_DROIT) == 0) && (ua != IDENTITE))
Table_u->Produits[a].D |= EST_REDUIT;
else
Table_u->Produits[a].D &= ~EST_REDUIT;
if ((Table_ua->Statut & EST_CALCUL_DROIT) != 0) /* ua figure deja dans la table, a la case n */
{
NbRelations++;
Table_u->Produits[a].D &= ~(EST_REDUIT);
}
else /* En tant que produit droit, c'est nouveau */
{
Table_u->Produits[a].D |= EST_REDUIT;
Table_ua->Statut |= EST_CALCUL_DROIT;
Table_ua->Initiale = Initiale;
Table_ua->Finale = a;
Table_ua->Prefixe = u;
Table_ua->Suffixe = Table[s].Produits[a].D;
if (ua != IDENTITE)
{
Table_ua->Longueur = Table_u->Longueur + 1;
Table[DernierMot].Suivant = ua;
DernierMot = ua;
}
else /* Si on retombe sur 1 (cas d'un semigroupe), on n'ajoute rien. */
PossedeUnNeutre = 1;
}
}
}
if (u == DernierMot)
Table_u->Suivant = 0;
u = Table_u->Suivant;
}
#ifdef DEBUG
printf("Calcul: DernierMot = %lu \n", DernierMot);
#endif /* DEBUG */
/*******************************
*
* On calcule maintenant au
*
*******************************/
u = u0; /* On reprend le premier mot de longueur courante */
while (Table[u].Longueur == LongueurCourante)
{
#ifdef DEBUG
printf("Debut du calcul de au: LongueurCourante = %d \n", LongueurCourante);
printf("*** u = %lu \n", u);
#endif /* DEBUG */
Table_u = &Table[u];
p = Table_u->Prefixe;
#ifdef DEBUG
printf("Calcul de au: p = %lu \n", p);
#endif /* DEBUG */
Finale = Table_u->Finale;
#ifdef DEBUG
printf("Calcul de au: u = %lu \n", u);
printf("Calcul de au: Finale = %c \n", Finale + 97);
#endif /* DEBUG */
for (a = 0; a < NbLettres; a++)
{
ap = Table[p].Produits[a].G; /* Soit p le prefixe de longueur n-1. On calcule ap */
Table_u->Produits[a].G = Table[ap].Produits[Finale].D & ~EST_REDUIT;
#ifdef DEBUG
printf("Calcul de au: Table[p].Produits[a].G = %lu \n", ap);
#endif /* DEBUG */
}
u = Table_u->Suivant;
#ifdef DEBUG
printf("Calcul de au: u = %lu \n", u);
printf("Calcul de au: Table[u].Longueur = %d \n\n", Table[u].Longueur);
#endif /* DEBUG */
}
u0 = u;
#ifdef DEBUG
printf("Calcul de au: u0 = %lu \n", u0);
#endif /* DEBUG */
LongueurCourante++;
#ifdef DEBUG
printf("Calcul de au: LongueurCourante = %d \n", LongueurCourante);
printf("Calcul de au: Table[u].Longueur = %d \n\n", Table[u].Longueur);
#endif /* DEBUG */
} /* fin de la boucle while (u != 0) */
#ifdef DEBUG
printf("Calcul: successfull\n");
#endif /* DEBUG */
LongueurMax = Table[DernierMot].Longueur;
NbReelElements = NbElements - (!PossedeUnNeutre && (TypeCalcul == Semigroupe));
if (!PasDeMemoireLibre)
LibereMemoireElement(valeur_ua); /* On libere la memoire devenue inutile */
#ifdef PROFIL
}
error = ProfilerDump("\pProfilSemigroupe");
ProfilerTerm();
#endif /* PROFIL */
}
/************************************************************************
*
* CalculIdempotents
*
************************************************************************/
void CalculIdempotents(void)
{
register unsigned long n;
if ((CalculsEffectues & CALCUL_IDEMPOTENTS) == 0)
{
for (n = IDENTITE + 1; n <= NbElements; n++)
{
if (n == ProduitParReduction(n, n))
{
Table[n].Statut |= (IDEMPOTENT | OMEGA_CALCULE);
Table2[n].xOmega = n;
NbIdempotents++;
}
else
Table[n].Statut &= ~(IDEMPOTENT | OMEGA_CALCULE);
}
NbIdempotents = NbIdempotents + PossedeUnNeutre;
CalculsEffectues |= CALCUL_IDEMPOTENTS; /* On prend note : le calcul des idempotents est termine */
}
}
/************************************************************************
*
* CalculIdempotentsDirect
*
************************************************************************/
void CalculIdempotentsDirect(void)
{
register unsigned long n;
element x2 = 0;
if ((CalculsEffectues & CALCUL_IDEMPOTENTS) == 0)
{
x2 = AlloueMemoireElement();
for (n = IDENTITE + 1; n <= NbElements; n++)
{
Produit(TableDesValeurs[n], TableDesValeurs[n], x2);
if (EstEgal(TableDesValeurs[n], x2))
{
Table[n].Statut |= (IDEMPOTENT | OMEGA_CALCULE);
Table2[n].xOmega = n;
NbIdempotents++;
}
else
Table[n].Statut &= ~(IDEMPOTENT | OMEGA_CALCULE);
}
LibereMemoireElement(x2);
NbIdempotents = NbIdempotents + PossedeUnNeutre;
CalculsEffectues |= CALCUL_IDEMPOTENTS; /* On prend note : le calcul des idempotents est termine */
}
}
/************************************************************************
*
* CalculListeIdempotents
*
************************************************************************/
void CalculListeIdempotents(void)
{
unsigned long e;
unsigned long i = 0;
if (!(CalculsEffectues & CALCUL_LISTE_IDEMPOTENTS))
{
CalculIdempotents();
TableIdempotents = AlloueMemoireTableau(NbIdempotents);
for (e = IDENTITE + !PossedeUnNeutre; e != 0; e = Table[e].Suivant)
if (Table[e].Statut & IDEMPOTENT)
TableIdempotents[i++] = e;
CalculsEffectues |= CALCUL_LISTE_IDEMPOTENTS; /* On prend note : la liste des idempotents est creee */
}
}
/************************************************************************
*
* CalculxOmega OK
*
************************************************************************/
void CalculxOmega(void)
{
register unsigned long n, x;
if (!(CalculsEffectues & CALCUL_X_OMEGA))
{
for (n = IDENTITE; n <= NbElements; n++)
{
x = n;
while ((Table[x].Statut & OMEGA_CALCULE) == 0)
x = ProduitParReduction(x, n); /* A accelerer lorsqu'on saura si n est regulier */
Table2[n].xOmega = Table2[x].xOmega;
Table[n].Statut |= OMEGA_CALCULE;
}
CalculsEffectues |= CALCUL_X_OMEGA; /* On prend note : le calcul des x^ est termine */
}
}