/*************************************** * * * 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, CalculsEffectues; extern numero NbElements, NbReelElements, NbIdempotents, DernierMot; extern unsigned long NbRelations, TailleTableDeHachage; extern element *Generateurs; extern numero *TableDeHachage; extern numero *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, numero *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 numero 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, numero *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; numero 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(); 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; 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; /* if ((NbElements %2000) == 0) Tous les 2000 elements, on affiche, pour faire patienter ... */ /* printf("%5lu\n", 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; } /******************************* * * On calcule maintenant au * *******************************/ u = u0; /* On reprend le premier mot de longueur courante */ while (Table[u].Longueur == LongueurCourante) { Table_u = &Table[u]; p = Table_u->Prefixe; Finale = Table_u->Finale; 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; } u = Table_u->Suivant; } u0 = u; LongueurCourante++; } 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 numero 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 numero 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) { numero 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 numero 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 */ } }