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