/*************************************** * * * 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)); }