/***************************************
* *
* Copyright (c) 1998 Jean-Eric Pin *
* All rights reserved. *
* *
* TAB = 2 spaces *
* *
***************************************/
/*-------------------------------------------------------------------
* Main.h Jean-Eric Pin 07/12/96
*-------------------------------------------------------------------
*/
/************************************************
*
* Choix du systeme : MAC, UNIX, WINDOWS, DOS
*
************************************************/
#define MAC 1
#define UNIX 2
#define WINDOWS 3
#define DOS 4
#define SYSTEME UNIX
/************************************************
*
* Number of bits (machine dependent) 32 or 64
*
************************************************/
#define BITS 64
#ifndef CLOCKS_PER_SEC
#define CLOCKS_PER_SEC CLK_TCK
#endif
/********************************************************************
*
* PROFILER : si on l'utilise, il faut desactiver "strictement ANSI"
* et "Mots-cles ANSI uniquement". En revanche, activer "Emettre des
* appels du Profiler".
*
********************************************************************/
#undef PROFIL
/****************
*
* Debogage
*
****************/
/* #define DEBUG */
#ifdef DEBUG
#define TRACE(s) printf s
#else
#define TRACE(ignore)
#endif /* DEBUG */
/*****************
*
* Constantes
*
*****************/
#define TAILLE_BUFFER 128
#define SIZE_BUFFER_TEXT 200
#define IDENTITE 1UL
#define IDEMPOTENT 0x1UL
#define DANS_UN_GROUPE 0x2UL
#define REGULIER 0x4UL
#define OMEGA_CALCULE 0x8UL
#define EST_CALCUL_DROIT 0x10UL /* Bit d'etat : vaut 1 si u provient du calcul d'un produit droit */
#define R_VISITE 0x20UL
#define R_DEJA_CALCULE 0x40UL
#define R_PARCOURS 0x80UL
#define L_VISITE 0x100UL
#define L_DEJA_CALCULE 0x200UL
#define L_PARCOURS 0x400UL
#define D_VISITE 0x800UL
#define D_DEJA_VISITE 0x1000UL
#define D_PARCOURS 0x2000UL
#define EST_D_MINIMAL 0x4000UL /* Dans l'ideal minimum */
#define EST_DANS_P 0x8000UL
#define EST_ELEMENT_LOCAL 0x10000UL
#define EST_DANS_IDEAL_DROIT 0x20000UL
#define EST_DANS_IDEAL_GAUCHE 0x40000UL
#define EST_DANS_KS 0x80000UL
#define EST_DANS_AM 0x100000UL
#define EST_DANS_AN 0x200000UL
#define EST_DANS_T 0x400000UL
#define EST_REDUIT (1UL << (BITS - 1)) /* Les parentheses sont indispensables, car c'est une macro... */
#define NumeroDeParcours xOmega
#define PointDAttache Hclasse
enum LeTypeSemigroupe {ParTransitions = 1, ParTransitionsPartielles, MatricesBooleennes,
MatricesMaxPlus, MatricesMinPlus, MatricesMaxPlusTropicales, MatricesMinPlusTropicales,
MatricesMaxPlusProjectives, MatricesEntieres, Presentation, FreeIdempotent};
enum LeTypeCalcul {Semigroupe = 1, Monoide, SemigroupeSyntactique, MonoideSyntactique, Exemple,
Fichier, Prefs};
typedef unsigned char boolean;
/* typedef unsigned long unsigned long; */
/* En pratique, la taille maximum d'un semigroupe sera d'environ 429 000 000 */
/* En effet, le premier bit est reserve dans ProduitsDG.D et il faut
diviser par 5 puisqu'on prend une table de hachage 5 fois plus grande */
typedef unsigned char lettre; /* Limite la taille de l'alphabet a 255. On conserve le caractere 255 comme marqueur. */
typedef void *element;
typedef struct
{
unsigned long D; /* Le bit de plus grand poids de numeroD sert de drapeau : */
unsigned long G; /* il vaut 0 si ua est reductible, 1 si ua est irreductible */
}ProduitsDG; /* Taille actuelle : 8 */
typedef struct /* Decrit un element x */
{
unsigned long Statut;
unsigned short Longueur; /* La longueur n du mot */
lettre Initiale; /* La premiere lettre du mot */
lettre Finale; /* La derniere lettre du mot */
ProduitsDG *Produits; /* Les elements de la forme ua et au, ou a est une lettre */
unsigned long Prefixe; /* L'adresse dans la table du prefixe de longueur n-1 */
unsigned long Suffixe; /* L'adresse dans la table du suffixe de longueur n-1 */
unsigned long Suivant; /* L'adresse du mot suivant dans l'ordre militaire */
}info; /* Taille actuelle : 24 */
/*****************************************************************************
* *
* Value of sizeof: *
* char: 1, short: 2, int: 4, long: 8, info: 48 *
* unsigned char: 1, unsigned short: 2, unsigned int: 4, unsigned long: 8 *
* *
*****************************************************************************/
typedef struct /* Decrit un element x */
{
unsigned long Statut;
unsigned long Rclasse;
unsigned long Lclasse;
unsigned long Dclasse;
unsigned long Hclasse;
unsigned long xOmega; /* L'adresse dans la table de l'idempotent puissance de l'element */
}info2; /* Taille actuelle : 24 */
#define TYPE_RENVERSE '\001'
#define UNIVERS_TRANSITIONS '\001'
#define UNIVERS_TRANSITIONS_PARTIELLES '\002'
#define UNIVERS_MATRICES_ENTIERES '\003'
#define UNIVERS_MATRICES '\004'
#define MEMOIRE_IDENTITE 0x1U
#define MEMOIRE_GENERATEURS 0x2U
#define MEMOIRE_NOMEXEMPLE 0x4U
#define MEMOIRE_TABLE_VALEURS 0x8U
#define MEMOIRE_PILE 0x10U
#define MEMOIRE_TABLEAU_LONGUEUR_MOTS 0x20U
#define CALCUL_ELEMENTS 0x1UL
#define CALCUL_ZERO 0x2UL
#define CALCUL_IDEMPOTENTS 0x4UL
#define CALCUL_LISTE_IDEMPOTENTS 0x8UL
#define CALCUL_X_OMEGA 0x10UL
#define CALCUL_R_CLASSES 0x20UL
#define CALCUL_D_CLASSES 0x40UL
#define CALCUL_H_CLASSES 0x80UL
#define CALCUL_BLOCS 0x100UL
#define CALCUL_REGULIERS 0x200UL
#define CALCUL_DANS_UN_GROUPE 0x400UL
#define CALCUL_INVERSES 0x800UL
#define CALCUL_TABLE_DE_S 0x1000UL
#define CALCUL_P 0x2000UL
#define CALCUL_SYNTACTIQUE 0x4000UL
#define CALCUL_KS 0x8000UL
#define CALCUL_O CALCUL_P
#define SEM_COMMUTATIF 0x1UL
#define SEM_IDEMPOTENT 0x2UL
#define SEM_APERIODIQUE 0x4UL
#define SEM_GROUPE 0x8UL
#define SEM_R_TRIVIAL 0x10UL
#define SEM_L_TRIVIAL 0x20UL
#define SEM_D_TRIVIAL 0x40UL
#define SEM_NILPOTENT 0x80UL
#define SEM_ECOM 0x100UL
#define SEM_BG 0x200UL
#define SEM_DA 0x400UL
#define SEM_DS 0x800UL
#define SEM_RvL 0x1000UL
#define SEM_LI 0x2000UL
#define SEM_LG 0x4000UL
#define SEM_B_UN 0x8000UL
#define SEM_B_UN_PLUS 0x10000UL
#define SEM_REGULIER 0x20000UL
#define SEM_A_UN_ZERO 0x40000UL
/************************************************************
*
* Liste des adresses des contre-exemples.
* Par exemple, commutatif_1 et commutatif_2 sont les adresses
* de deux lettres qui ne commutent pas.
*
************************************************************/
typedef struct
{
lettre *commutatif_1, *commutatif_2;
unsigned long *idempotent;
unsigned long *aperiodique;
unsigned long *DA_x, *DA_y;
unsigned long *DS_x, *DS_y;
unsigned long *RvL_x, *RvL_y, *RvL_z;
unsigned long *L1_e, *L1_s;
unsigned long *LG_e, *LG_s;
unsigned long *B1_p, *B1_q, *B1_r, *B1_s, *B1_e, *B1_f;
unsigned long *B1Plus_e, *B1Plus_s;
unsigned long *ECom_e, *ECom_f;
unsigned long *BG_e, *BG_f;
}adresses;
typedef struct
{
unsigned char TypeCalcul; /* Semigroupe, Monoide */
unsigned char Univers; /* Univers du semigroupe */
unsigned long CalculsEffectues; /* Drapeaux des calculs (effectue = 1, non effectue = 0) */
unsigned long ProprietesTestees; /* Drapeaux des proprietes (testees = 1, non testees = 0) */
adresses *AdressesContreExemples; /* Adresses des contre-exemples */
unsigned long Proprietes; /* Drapeaux des proprietes du semigroupe (vraie 1, fausse 0) */
element *Generateurs; /* Les generateurs du semigroupe */
element *TableDesValeurs; /* Les valeurs des elements du semigroupe dans l'univers. */
/* unsigned long *TableDeHachage; La table de l'adresse des elements. On y accede par hachage et adressage ouvert. */
info *Table; /* La table contenant les informations sur les elements */
}semigroupe;
typedef info *pointeurInfo;
typedef struct
{
unsigned long Adresse;
lettre Lettre;
} elementpile;
struct WagonNumero /* Liste d'elements de S */
{
unsigned long t;
struct WagonNumero *suivant; /* Donne l'adresse du suivant dans la liste */
};
typedef struct WagonNumero *ListeNumero;
struct NumeroEtLettre
{
unsigned long Numero;
lettre Lettre;
};
struct Wagon2Numeros /* Liste de sommets du graphe syntactique M x M */
{
unsigned long u;
unsigned long v;
struct Wagon2Numeros *suivant; /* Adresse du suivant dans la liste */
};
typedef struct Wagon2Numeros *Liste2Numeros;
typedef struct
{
Liste2Numeros Aretes; /* Successeurs (ua, va) -> (u, v) ou bien (au, av) -> (u, v) */
char Label;
}infoSommet;