/***************************************
* *
* Copyright (c) 1998 Jean-Eric Pin *
* All rights reserved. *
* *
* TAB = 2 spaces *
* *
***************************************/
/*-------------------------------------------------------------------
* Initialisation.c Jean-Eric Pin 07/12/96
*-------------------------------------------------------------------
*/
#include <stdlib.h>
#include <stdio.h>
#include "Main.h"
#include "Globales.h"
#include "Calcul.h"
#include "Initialisation.h"
#include "InitiauxFinaux.h"
#include "Matrices.h"
#include "MatricesBooleennes.h"
#include "MatricesMaxPlus.h"
#include "Memoire.h"
#include "Reduction.h"
#include "SortieLaTeX.h"
#include "Transitions.h"
extern unsigned short NbEtats, NbLettres, LongueurMax, TypeCalcul, PossedeUnNeutre,
PossedeUnZero, TypeSemigroupe, SemigroupeRenverse, MemoireInitiauxAllouee,
MemoireFinauxAllouee, MemoireAllouee, SortieLaTeX, SemiReduit, AvecNumero,
FichierExempleOuvert, FichierLaTeXOuvert, InitiauxDejaSpecifies, FinauxDejaSpecifies;
extern unsigned long NbRelations, TailleTableDeHachage, TestsEffectues,
CalculsEffectues, Varietes;
extern element Identite;
extern unsigned long NbElements, NbIdempotents, DernierMot, nZero;
extern info *Table;
extern info2 *Table2;
extern element *Generateurs;
extern unsigned long *TableDeHachage;
extern element *TableDesValeurs; /* Les valeurs des elements du semigroupe dans l'univers. */
extern Copie_ Copie;
extern Hachage_ Hachage;
extern Hachage_ HachageSecondaire;
extern Produit_ ProduitNormal;
extern ProduitRapide_ ProduitRapide;
extern EstEgal_ EstEgal;
extern FaireIdentite_ FaireIdentite;
extern Entree_ Entree;
extern Sortie_ SortieElement;
extern SortieLaTeX_ SortieLaTeXElement;
extern Sauvegarde_ Sauvegarde;
extern Lecture_ LectureFichier;
extern Alloue_ AlloueMemoireElement, AlloueMemoireGenerateur;
extern Libere_ LibereMemoireElement, LibereMemoireGenerateur;
extern EntreePartie_ EntreePartie;
extern char **Messages;
extern float Version;
/****************************************************
*
* Baniere. OK
*
****************************************************/
void Baniere(void)
{
printf("%s %f %s %s\n\n", Messages[M_Version], Version, Messages[M_Author], Messages[M_Date]);
}
/************************************************************
*
* ProduitRenverse
*
************************************************************/
void ProduitRenverse(element x, element y, element xy)
{
ProduitNormal(y, x, xy);
}
/************************************************************
*
* Choix
*
************************************************************/
void Choix(void)
{
switch (TypeSemigroupe)
{
case ParTransitions:
if (NbLettres != 1)
{
Hachage = HachageTransitions;
HachageSecondaire = HachageSecondaireTransitions;
}
else
{
Hachage = HachageUneLettreTransitions;
HachageSecondaire = HachageSecondaireUneLettreTransitions;
}
Copie = CopieTransitions;
ProduitNormal = ProduitTransitions;
EstEgal = EstEgalTransitions;
FaireIdentite = FaireIdentiteTransitions;
Entree = EntreeTransitions;
SortieElement = SortieTransitions;
SortieLaTeXElement = SortieLaTeXTransitions;
LectureFichier = LectureTransitions;
Sauvegarde = SauvegardeTransitions;
AlloueMemoireGenerateur = AlloueMemoireTransitions;
AlloueMemoireElement = AlloueMemoireTransitions;
LibereMemoireElement = LibereMemoireTransitions;
LibereMemoireGenerateur = LibereMemoireTransitions;
EntreePartie = EntreePartieTransitions;
break;
case ParTransitionsPartielles :
if (NbLettres != 1)
{
Hachage = HachageTransitions;
HachageSecondaire = HachageSecondaireTransitions;
}
else
{
Hachage = HachageUneLettreTransitions;
HachageSecondaire = HachageSecondaireUneLettreTransitions;
}
Copie = CopieTransitions;
ProduitNormal = ProduitTransitionsPartielles;
EstEgal = EstEgalTransitions;
FaireIdentite = FaireIdentiteTransitions;
Entree = EntreeTransitions;
SortieElement = SortieTransitions;
SortieLaTeXElement = SortieLaTeXTransitions;
LectureFichier = LectureTransitions;
Sauvegarde = SauvegardeTransitions;
AlloueMemoireGenerateur = AlloueMemoireTransitions;
AlloueMemoireElement = AlloueMemoireTransitions;
LibereMemoireElement = LibereMemoireTransitions;
LibereMemoireGenerateur = LibereMemoireTransitions;
EntreePartie = EntreePartieTransitions;
break;
case MatricesBooleennes:
Copie = CopieMatricesBooleennes;
Hachage = HachageMatricesBooleennes;
HachageSecondaire = HachageSecondaireMatricesBooleennes;
ProduitNormal = ProduitMatricesBooleennes;
EstEgal = EstEgalMatricesBooleennes;
FaireIdentite = FaireIdentiteMatricesBooleennes;
Entree = EntreeMatricesBooleennes;
SortieElement = SortieMatricesBooleennes;
SortieLaTeXElement = SortieLaTeXMatricesBooleennes;
LectureFichier = LectureMatricesBooleennes;
Sauvegarde = SauvegardeMatricesBooleennes;
AlloueMemoireGenerateur = AlloueMemoireMatricesBooleennes;
AlloueMemoireElement = AlloueMemoireMatricesBooleennes;
LibereMemoireElement = LibereMemoireMatricesBooleennes;
LibereMemoireGenerateur = LibereMemoireMatricesBooleennes;
EntreePartie = EntreePartieMatricesBooleennes;
break;
case MatricesMaxPlus:
Copie = CopieMatrices;
Hachage = HachageMatrices;
HachageSecondaire = HachageSecondaireMatrices;
ProduitNormal = ProduitMatricesMaxPlus;
EstEgal = EstEgalMatrices;
FaireIdentite = FaireIdentiteMatricesMaxPlus;
Entree = EntreeMatricesMaxPlus;
SortieElement = SortieMatricesMaxPlus;
SortieLaTeXElement = SortieLaTeXMatricesMaxPlus;
Sauvegarde = SauvegardeMatrices;
LectureFichier = LectureMatrices;
AlloueMemoireGenerateur = AlloueMemoireMatrice;
AlloueMemoireElement = AlloueMemoireMatrice;
LibereMemoireElement = LibereMemoireMatrice;
LibereMemoireGenerateur = LibereMemoireMatrice;
EntreePartie = EntreePartieStandard;
break;
case MatricesMinPlus:
Copie = CopieMatrices;
Hachage = HachageMatrices;
HachageSecondaire = HachageSecondaireMatrices;
ProduitNormal = ProduitMatricesMinPlus;
EstEgal = EstEgalMatrices;
FaireIdentite = FaireIdentiteMatricesMinPlus;
Entree = EntreeMatricesMinPlus;
SortieElement = SortieMatricesMinPlus;
SortieLaTeXElement = SortieLaTeXMatricesMinPlus;
Sauvegarde = SauvegardeMatrices;
LectureFichier = LectureMatrices;
AlloueMemoireGenerateur = AlloueMemoireMatrice;
AlloueMemoireElement = AlloueMemoireMatrice;
LibereMemoireElement = LibereMemoireMatrice;
LibereMemoireGenerateur = LibereMemoireMatrice;
EntreePartie = EntreePartieStandard;
break;
case MatricesMaxPlusTropicales:
Copie = CopieMatrices;
Hachage = HachageMatrices;
HachageSecondaire = HachageSecondaireMatrices;
ProduitNormal = ProduitMatricesMaxPlusTropicales;
EstEgal = EstEgalMatrices;
FaireIdentite = FaireIdentiteMatricesMaxPlus;
Entree = EntreeMatricesMaxPlusTropicales;
SortieElement = SortieMatricesMaxPlusTropicales;
SortieLaTeXElement = SortieLaTeXMatricesMaxPlusTropicales;
Sauvegarde = SauvegardeMatrices;
LectureFichier = LectureMatrices;
AlloueMemoireGenerateur = AlloueMemoireMatrice;
AlloueMemoireElement = AlloueMemoireMatrice;
LibereMemoireElement = LibereMemoireMatrice;
LibereMemoireGenerateur = LibereMemoireMatrice;
EntreePartie = EntreePartieStandard;
break;
case MatricesMinPlusTropicales:
Copie = CopieMatrices;
Hachage = HachageMatrices;
HachageSecondaire = HachageSecondaireMatrices;
ProduitNormal = ProduitMatricesMinPlusTropicales;
EstEgal = EstEgalMatrices;
FaireIdentite = FaireIdentiteMatricesMinPlus;
Entree = EntreeMatricesMinPlusTropicales;
SortieElement = SortieMatricesMinPlusTropicales;
SortieLaTeXElement = SortieLaTeXMatricesMinPlusTropicales;
Sauvegarde = SauvegardeMatrices;
LectureFichier = LectureMatrices;
AlloueMemoireGenerateur = AlloueMemoireMatrice;
AlloueMemoireElement = AlloueMemoireMatrice;
LibereMemoireElement = LibereMemoireMatrice;
LibereMemoireGenerateur = LibereMemoireMatrice;
EntreePartie = EntreePartieStandard;
break;
case MatricesMaxPlusProjectives:
Copie = CopieMatrices;
Hachage = HachageMatrices;
HachageSecondaire = HachageSecondaireMatrices;
ProduitNormal = ProduitMatMaxPlusProjectives;
EstEgal = EstEgalMatrices;
FaireIdentite = FaireIdentiteMatricesMaxPlus;
Entree = EntreeMatricesMaxPlus;
SortieElement = SortieMatricesMaxPlus;
SortieLaTeXElement = SortieLaTeXMatricesMaxPlus;
Sauvegarde = SauvegardeMatrices;
LectureFichier = LectureMatrices;
AlloueMemoireGenerateur = AlloueMemoireMatrice;
AlloueMemoireElement = AlloueMemoireMatrice;
LibereMemoireElement = LibereMemoireMatrice;
LibereMemoireGenerateur = LibereMemoireMatrice;
EntreePartie = EntreePartieStandard;
break;
case MatricesEntieres:
Copie = CopieMatrices;
Hachage = HachageMatrices;
HachageSecondaire = HachageSecondaireMatrices;
ProduitNormal = ProduitMatricesEntieres;
EstEgal = EstEgalMatrices;
FaireIdentite = FaireIdentiteMatricesEntieres;
Entree = EntreeMatricesEntieres;
SortieElement = SortieMatricesEntieres;
SortieLaTeXElement = SortieLaTeXMatricesEntieres;
Sauvegarde = SauvegardeMatrices;
LectureFichier = LectureMatrices;
AlloueMemoireGenerateur = AlloueMemoireMatrice;
AlloueMemoireElement = AlloueMemoireMatrice;
LibereMemoireElement = LibereMemoireMatrice;
LibereMemoireGenerateur = LibereMemoireMatrice;
EntreePartie = EntreePartieStandard;
break;
default:
printf("Not yet defined !\n");
exit(0);
}
}
/************************************
*
* Initialisation du mot vide
*
************************************/
void InitIdentite(void)
{
Identite = AlloueMemoireElement();
TableDesValeurs[IDENTITE] = Identite;
FaireIdentite(Identite);
TableDeHachage[Hachage(Identite)] = IDENTITE;
Table[IDENTITE].Statut |= IDEMPOTENT | OMEGA_CALCULE | ((TypeCalcul == Monoide) * EST_CALCUL_DROIT);
NbElements++;
DernierMot = IDENTITE;
MemoireAllouee |= MEMOIRE_IDENTITE; /* On prend note : on a alloue la memoire pour l'identite. */
}
/************************************
*
* Initialisation des generateurs.
*
************************************/
void InitGenerateurs(void)
{
lettre a;
unsigned long u = IDENTITE; /* u est le numero du mot courant */
long h;
element x;
for (a = 0; a < NbLettres; a++)
{
x = Generateurs[a]; /* x est l'element courant */
h = Range(x, &u);
if (u == 0) /* Nouvel element, i.e. si a est different de 1 ou d'un autre generateur */
{
TableDeHachage[h] = u = ++NbElements;
Table[u].Produits = AlloueMemoireProduits(); /* Necessite de connaitre le nombre de lettres */
Table[u].Statut |= EST_CALCUL_DROIT;
TableDesValeurs[NbElements] = AlloueMemoireElement();
Copie(x, TableDesValeurs[NbElements]);
Table[u].Longueur = 1;
Table[u].Initiale = a;
Table[u].Finale = a;
Table[u].Prefixe = IDENTITE;
Table[u].Suffixe = IDENTITE;
Table[IDENTITE].Produits[a].D = Table[IDENTITE].Produits[a].G = u;
Table[IDENTITE].Produits[a].D |= EST_REDUIT; /* Ne pas oublier ce drapeau ! */
Table[DernierMot].Suivant = u;
DernierMot = u;
}
else if (u == IDENTITE) /* a = 1 */
{
Table[IDENTITE].Produits[a].D = Table[IDENTITE].Produits[a].G = IDENTITE;
Table[IDENTITE].Produits[a].D &= ~(EST_REDUIT);
if (TypeCalcul == Semigroupe)
PossedeUnNeutre = 1;
else
NbRelations++;
}
else /* a = un autre generateur deja present */
{
Table[IDENTITE].Produits[a].D = Table[IDENTITE].Produits[a].G = u;
Table[IDENTITE].Produits[a].D &= ~(EST_REDUIT);
NbRelations++;
}
}
}
/*******************************************
*
* Elimination des generateurs redondants.
*
*******************************************/
void ElimineGenerateurs(void)
{
lettre a, b;
unsigned long u = IDENTITE; /* u est le numero du mot courant */
long h;
element x;
a = 0;
while (a < NbLettres)
{
x = Generateurs[a]; /* x est l'element courant */
h = Range(x, &u);
if (u != 0) /* Si a est egal a 1 ou a un autre generateur, a est retire de la liste des generateurs */
{
NbLettres--;
for (b = a; b < NbLettres; b++)
Generateurs[b] = (element *)Generateurs[b+1];
if (MemoireAllouee & MEMOIRE_GENERATEURS)
LibereMemoireElement(Generateurs[NbLettres]);
if ((u == IDENTITE) && (TypeCalcul == Semigroupe)) /* Si a = 1, on met quand meme a jour dans le cas d'un semigroupe. */
PossedeUnNeutre = 1;
}
else
a++;
}
}
/**********************
*
* InitCalcul.
*
**********************/
void InitCalcul(void)
{
PossedeUnNeutre = (TypeCalcul == Monoide);
ProduitRapide = ProduitParReduction;
TableDeHachage = AlloueMemoireTableau(TailleTableDeHachage);
Table = AlloueMemoireTable();
AlloueMemoireTableDesValeurs(); /* Necessairement appelee AVANT InitIdentite() et InitGenerateurs() */
InitIdentite();
/* ElimineGenerateurs(); */
Table[IDENTITE].Produits = AlloueMemoireProduits(); /* Necessite de connaitre le nombre de lettres */
Table[0].Produits = AlloueMemoireProduits(); /* Necessite de connaitre le nombre de lettres */
InitGenerateurs();
AlloueMemoireAdresses();
}
/**********************
*
* InitVariables.
*
**********************/
void InitVariables(void)
{
NbRelations = 0;
NbElements = 0;
NbIdempotents = 0;
PossedeUnZero = 0;
LongueurMax = 0;
nZero = 0;
CalculsEffectues = 0UL;
MemoireAllouee = 0;
MemoireInitiauxAllouee = 0;
MemoireFinauxAllouee = 0;
TestsEffectues = 0UL;
Varietes = 0UL;
InitiauxDejaSpecifies = 0;
FinauxDejaSpecifies = 0;
/* SortieLaTeX = 0; */
/* SemiReduit = 0; */
AvecNumero = 0;
FichierExempleOuvert = 0;
FichierLaTeXOuvert = 0;
}
/**********************
*
* InitDrapeaux.
*
**********************/
void InitDrapeaux(void)
{
unsigned long n;
for (n = IDENTITE; n <= NbElements; n++)
{
Table[n].Statut &= ~(EST_ELEMENT_LOCAL | EST_DANS_IDEAL_DROIT | EST_DANS_IDEAL_GAUCHE );
Table2[n].Statut &= ~(R_VISITE | R_DEJA_CALCULE | R_PARCOURS | L_VISITE | L_DEJA_CALCULE
| L_PARCOURS | EST_D_MINIMAL | D_VISITE | D_DEJA_VISITE | D_PARCOURS);
}
}
/**********************
*
* InitPile.
*
**********************/
void InitPile(elementpile *Pile)
{
unsigned long n;
for (n = 0; n < NbElements; n++)
{
Pile[n].Lettre = 0;
Pile[n].Adresse = 0;
}
}