/*************************************** * * * Copyright (c) 1998 Jean-Eric Pin * * All rights reserved. * * * * TAB = 2 spaces * * * ***************************************/ /*------------------------------------------------------------------- * TriParTas.c Jean-Eric Pin 18/08/2006 *------------------------------------------------------------------- */ #include <stdlib.h> #include <stdio.h> #include <string.h> #include "Globales.h" #include "Main.h" #include "TriParTas.h" #include "Initialisation.h" #include "Memoire.h" #include "Reduction.h" #include "DclassesIteratif.h" #include "Blocs.h" #include "Utilitaires.h" extern unsigned short PossedeUnNeutre; extern unsigned long NbElements, NbRclasses, NbLclasses, NbDclasses; extern info *Table; extern info2 *Table2; extern unsigned long *B; unsigned long nTas, TailleTas; unsigned long *Tas; /************************************************************************** * * Precede(i,j). * * Retourne 1 si i < j dans l'ordre dans lequel les crietes suivants sont appliques: * - Le numero de D-classe de i est >= au numero de D-classe de j [c'est bien superieur ou egal !] * - Le numero de bloc de la R-classe de i est <= au numero de bloc de la R-classe de j * - Le numero de la R-classe de i est <= au numero de la R-classe de j * - Le numero de bloc de la L-classe de i est <= au numero de bloc de la L-classe de j * - Le numero de la L-classe de i est <= au numero de la L-classe de j * - Priorite aux idempotents: si [i est idempotent] ou * si [ni i, ni j, ne sont idempotents], i passe avant; * ***************************************************************************/ boolean Precede(unsigned long i, unsigned long j) { if (Table2[i].Dclasse > Table2[j].Dclasse) return(1); if (Table2[i].Dclasse == Table2[j].Dclasse) { if (B[Table2[i].Rclasse - 1] < B[Table2[j].Rclasse -1]) return(1); if (B[Table2[i].Rclasse - 1] == B[Table2[j].Rclasse - 1]) { if (Table2[i].Rclasse < Table2[j].Rclasse) return(1); if (Table2[i].Rclasse == Table2[j].Rclasse) { if (B[Table2[i].Lclasse + NbRclasses - 1] < B[Table2[j].Lclasse + NbRclasses - 1]) return(1); if (B[Table2[i].Lclasse + NbRclasses - 1] == B[Table2[j].Lclasse + NbRclasses - 1]) { if (Table2[i].Lclasse < Table2[j].Lclasse) return(1); if ((Table2[i].Lclasse == Table2[j].Lclasse) && ((Table[j].Statut & IDEMPOTENT) <= (Table[i].Statut & IDEMPOTENT)) ) return(1); } } } } return(0); } /**************************************************** * * Ajouter. Utilise pour le tri par tas. * ****************************************************/ void Ajouter(unsigned long n) { unsigned long i; i = nTas; ++nTas; while (i > 0 && Precede(Tas[(i-1)/2], n)) { Tas[i] = Tas[(i-1)/2]; i = (i-1)/2; } Tas[i] = n; } /**************************************************** * * Supprimer. Utilise pour le tri par tas. * ****************************************************/ void Supprimer(void) { unsigned long i, j, v; v = Tas[0] = Tas[--nTas]; i = 0; while (2*i + 1 < nTas) { j = 2*i + 1; if (j+1 < nTas && Precede(Tas[j], Tas[j+1])) ++j; if (Precede(Tas[j], v)) break; Tas[i] = Tas[j]; i = j; } Tas[i] = v; } /**************************************************** * * TriParTas * ****************************************************/ void TriParTas(void) { unsigned long n, v; Tas = AlloueMemoireTableau(NbElements + 1); nTas = 0; for (n = IDENTITE + !PossedeUnNeutre; n <= NbElements; n++) Ajouter(n); TailleTas = nTas; /* Dans la boucle for qui suit, n est "unsigned", ce qui interdit les tests >= 0 */ /* On remplace n >= 0 par n+1 > 0 */ for (n = TailleTas-1; n+1 > 0; --n) { v = Tas[0]; Supprimer(); Tas[n] = v; } /* for (n = 0; n < TailleTas; n++) printf("%d, ", Tas[n]); printf("\n"); */ }