/***************************************
* *
* Copyright (c) 1998 Jean-Eric Pin *
* All rights reserved. *
* *
* TAB = 2 spaces *
* *
***************************************/
/*-------------------------------------------------------------------
* MatricesBooleennes.c Jean-Eric Pin 07/12/96
*-------------------------------------------------------------------
*/
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#include "Globales.h"
#include "Main.h"
#include "InitiauxFinaux.h"
#include "MatricesBooleennes.h"
#include "Memoire.h"
#include "Utilitaires.h"
#ifdef DEBUG
extern long ElementsAlloues;
#endif /* DEBUG */
extern unsigned short NbEtats, NbLettres, PartiePointee,
InitiauxDejaSpecifies, FinauxDejaSpecifies;
extern unsigned long Periode, Seuil;
extern unsigned long TailleElement;
extern element *Generateurs, *TableDesValeurs;
extern unsigned long TailleTableDeHachage, TailleTableDeHachageMoinsUn;
extern unsigned long TailleMaxi, NbElements;
extern char **Messages;
extern unsigned short *EtatsInitiaux, *EtatsFinaux;
extern info *Table; /* La table contenant les informations sur les elements */
/************************************************************************
*
* CopieMatricesBooleennes : copie x dans y
*
************************************************************************/
void CopieMatricesBooleennes(element x, element y)
{
register short i, j;
for (i = 0; i < NbEtats; i++)
for (j = 0; j < NbEtats; j++)
((MatriceBooleenne)y)[i][j] = ((MatriceBooleenne)x)[i][j];
}
/************************************************************************
*
* EstEgalMatricesBooleennes : Teste l'egalite de deux matrices booleennes
*
************************************************************************/
short EstEgalMatricesBooleennes(element x, element y)
{
register short i, j;
for (i = 0; i < NbEtats; i++)
for (j = 0; j < NbEtats; j++)
if (((MatriceBooleenne)x)[i][j] != ((MatriceBooleenne)y)[i][j])
return(0);
return(1);
}
/************************************
*
* ProduitMatricesBooleennes
*
************************************/
void ProduitMatricesBooleennes(element x, element y, element xy)
{
register short p, q, r;
for (p = 0; p < NbEtats; p++)
for (q = 0; q < NbEtats; q++)
{
for (r = 0; r < NbEtats; r++)
if (((MatriceBooleenne)x)[p][r] && ((MatriceBooleenne)y)[r][q])
break;
((MatriceBooleenne)xy)[p][q] = (boolean)(r < NbEtats) ;
}
}
/************************************************************
*
* HachageMatricesBooleennes
*
************************************************************/
unsigned long HachageMatricesBooleennes(element x)
{
register short i, j;
register unsigned long h;
h = 0;
for (i = 0; i < NbEtats; i++)
for (j = 0; j < NbEtats; j++)
h = ((h << 1) + ((MatriceBooleenne)x)[i][j]) % TailleTableDeHachage;
return(h);
}
/************************************************************
*
* HachageSecondaireMatricesBooleennes
*
************************************************************/
unsigned long HachageSecondaireMatricesBooleennes(element x)
{
register short i, j;
register unsigned long h;
h = 0;
for (i = 0; i < NbEtats; i++)
for (j = 0; j < NbEtats; j++)
h = ((h << 1) + ((MatriceBooleenne)x)[i][j]) % TailleTableDeHachageMoinsUn;
return(1+h); /* Il faut eviter la valeur 0 ! */
}
/********************************************************
*
* FaireIdentiteMatricesBooleennes : Initialisation de l'identite
*
********************************************************/
void FaireIdentiteMatricesBooleennes(element x)
{
short p, q;
for (p = 0; p < NbEtats; p++)
for (q = 0; q < NbEtats; q++)
((MatriceBooleenne)x)[p][q] = (p != q) ? '\0' : '\1';
}
/****************************************************
*
* SauvegardeMatricesBooleennes. OK
*
****************************************************/
void SauvegardeMatricesBooleennes(FILE *MyFile)
{
short p, q;
lettre a;
fprintf(MyFile, "%8hu %% Taille des matrices\n", NbEtats);
fprintf(MyFile, "%8lu %% Seuil\n", 0UL);
fprintf(MyFile, "%8lu %% Periode\n", 1UL);
for (a = 0; a < NbLettres; a++)
{
for (p = 0; p < NbEtats; p++)
{
for (q = 0; q < NbEtats; q++)
fprintf(MyFile, "%u ", ((MatriceBooleenne)Generateurs[a])[p][q]);
fprintf(MyFile, "\n");
}
fprintf(MyFile, "\n");
}
if (PartiePointee && InitiauxDejaSpecifies)
SauvegardeInitiaux(MyFile);
if (PartiePointee && FinauxDejaSpecifies)
SauvegardeFinaux(MyFile);
}
/****************************************************
*
* LectureMatricesBooleennes. OK
*
****************************************************/
void LectureMatricesBooleennes(FILE *MyFile)
{
short p, q;
lettre a;
if (fscanf(MyFile, "%hu %% Taille des matrices", &NbEtats) != 1)
{
printf("scanf error\n");
exit(1);
}
if (fscanf(MyFile, "%lu %% Seuil", &Seuil) != 1)
{
printf("scanf error\n");
exit(1);
}
if (fscanf(MyFile, "%lu %% Periode", &Periode) != 1)
{
printf("scanf error\n");
exit(1);
}
AlloueMemoireGenerateurs();
for (a = 0; a < NbLettres; a++)
for (p = 0; p < NbEtats; p++)
for (q = 0; q < NbEtats; q++)
{
if (fscanf(MyFile, "%1s", &((MatriceBooleenne)Generateurs[a])[p][q]) != 1)
{
printf("scanf error\n");
exit(1);
}
((MatriceBooleenne)Generateurs[a])[p][q] -= '0';
}
if (!InitiauxDejaSpecifies)
LectureInitiaux(MyFile);
if (!FinauxDejaSpecifies)
LectureFinaux(MyFile);
}
/****************************************************
*
* EntreeMatricesBooleennes. Les matrices booleennes sont
* des matrices ayant NbEtats lignes et NbEtats colonnes,
* on comprimera peut etre un jour les booleens...
*
****************************************************/
void EntreeMatricesBooleennes(void)
{
short p, q, n;
lettre a;
printf("%s ", Messages[M_Size_Boolean_matrices]);
if (scanf("%hu", &NbEtats) != 1)
{
printf("scanf error\n");
exit(1);
}
printf("\n");
TailleElement = NbEtats * NbEtats * sizeof(boolean);
AlloueMemoireGenerateurs();
for (a = 0; a < NbLettres; a++)
{
for (p = 0; p < NbEtats; p++)
{
for (q = 0; q < NbEtats; q++)
{
do
{
printf("%c[%d,%d] = ", a + 97, p + 1, q + 1);
if (scanf("%hd", &n) != 1)
{
printf("scanf error\n");
exit(1);
}
}
while (!((n == 0) || (n == 1)));
((MatriceBooleenne)Generateurs[a])[p][q] = (boolean)n;
}
}
printf("\n");
}
if (PartiePointee && (!FinauxDejaSpecifies))
EntreeEtatsInitiauxFinaux();
}
/****************************************************
*
* SortieMatricesBooleennes. Sortie d'un element. OK
*
****************************************************/
void SortieMatricesBooleennes(element x)
{
short p, q;
for (p = 0; p < NbEtats; p++)
{
for (q = 0; q < NbEtats; q++)
printf("%2c ", ((MatriceBooleenne)x)[p][q] + '0');
printf("|");
}
printf("\n");
}
/****************************************************
*
* SortieLaTeXMatricesBooleennes. Sortie d'un element. OK
*
****************************************************/
void SortieLaTeXMatricesBooleennes(element x, FILE *MyFile)
{
short p, q;
for (p = 0; p < NbEtats; p++)
for (q = 0; q < NbEtats; q++)
fprintf(MyFile, "&%d ", ((MatriceBooleenne)x)[p][q]);
fprintf(MyFile, "\n");
}
/****************************************************
*
* AlloueMemoireMatricesBooleennes. OK
*
****************************************************/
element AlloueMemoireMatricesBooleennes(void)
{
element Element;
short j;
Element = (void *)ALLOC(boolean *, NbEtats);
if (Element == NULL)
{
printf("%s %s\n", Messages[M_Pb_memory], Messages[M_Pb_matrix]); /* Probleme lors de l'allocation memoire d'une matrice ! */
exit(1);
}
for (j = 0; j < NbEtats; j++)
{
((MatriceBooleenne)Element)[j] = (boolean *)ALLOC(boolean, NbEtats);
if (((MatriceBooleenne)Element)[j] == NULL)
{
printf("%s %s\n", Messages[M_Pb_memory], Messages[M_Pb_matrix]); /* Probleme lors de l'allocation memoire d'une matrice ! */
exit(1);
}
}
#ifdef DEBUG
ElementsAlloues++;
#endif /* DEBUG */
return Element;
}
/****************************************************
*
* LibereMemoireMatricesBooleennes. OK
*
****************************************************/
void LibereMemoireMatricesBooleennes(element Element)
{
short j;
for (j = 0; j < NbEtats; j++)
free(((MatriceBooleenne)Element)[j]);
free(Element);
#ifdef DEBUG
ElementsAlloues--;
#endif /* DEBUG */
}
/****************************************************************************
*
* EntreePartieMatricesBooleennes. OK
* Definit la partie pointee P a partir des ensembles I (etats initiaux) et F
* (etats finaux).
* P = { u | il existe i dans I et f dans F tels que u_{i,f} = 1 }
*
****************************************************************************/
void EntreePartieMatricesBooleennes(void)
{
unsigned long u;
short i, j = 0;
if (InitiauxDejaSpecifies && FinauxDejaSpecifies) /* Etat initiaux et finaux specifies */
{
for (u = IDENTITE; u <= NbElements; u++)
{
for (i = 0; i < NbEtats; i++)
{
if (EtatsInitiaux[i]) /* i etat initial */
for (j = 0; j < NbEtats; j++)
if ((EtatsFinaux[j]) && (((MatriceBooleenne)TableDesValeurs[u])[i][j]))
break; /* j etat final et M_{i,j} = 1 */
if (j != NbEtats) /* x est dans P, inutile de poursuivre. */
break;
}
if (i != NbEtats)
Table[u].Statut |= EST_DANS_P;
else
Table[u].Statut &= ~EST_DANS_P;
}
}
else /* Pas d'etats initiaux ni finaux specifies */
EntreePartieStandard();
}