/***************************************
*                                      *
*   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"); */
}