/***************************************
*                                      *
*   Copyright (c) 2006 Jean-Eric Pin   *
*   All rights reserved.               *
*                                      *
*   TAB = 2 spaces                     *
*                                      *
***************************************/

/****************************************************
*
* Blocs.c   Jean-Eric Pin 21/08/2006
*
****************************************************/

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "Main.h"
#include "Memoire.h"
#include "Initialisation.h"
#include "DclassesIteratif.h"
#include "Sortie.h"
#include "Blocs.h"

extern info *Table;
extern info2 *Table2;
extern unsigned long *TableIdempotents;
extern unsigned short NbLettres, PossedeUnNeutre, TypeCalcul;
extern unsigned long CalculsEffectues;
extern unsigned long NbElements, NbRclasses, NbLclasses, NbDclasses, NbHclasses,
NbIdempotents, DernierMot;

unsigned long *B, *Taille;

/****************************************************
*
* CalculBlocs. OK    Aout 2006
*
****************************************************/

/********************************************************************************* 
* Ce calcul consiste a determiner les composantes connexes du graphe bipartite
* dont les sommets sont R U L (R = ensemble des R-classes, L = ensemble des L-classes)
* et dont les arcs sont donnes par les idempotents: arc (r,l) si l'intersection
* de r et l contient un idempotent.
* On utilise cette fois "Union-Find"
*********************************************************************************/

unsigned long Trouver(unsigned long x)
{
  unsigned long r;
  
  r = x;
  while (B[r] != r)
    r = B[r];  /* remonte l'arbre de x */
  while (B[x] != x)
  {
    B[x] = r;  /* x devient fils de r */
    x = B[x];
  }
  return r;
}

void Union(unsigned long x, unsigned long y)
{
  unsigned long r, s;
  
  r  = Trouver(x);
  s = Trouver(y);
  if (Taille[r] > Taille[s]) 
  {
    B[s] = r;
    Taille[r] = Taille[r] + Taille[s];
  } 
  else 
  {
    B[r] = s;
    Taille[s] = Taille[r] + Taille[s];
  }
}

void CalculBlocs(void)
{
  unsigned long i, r, l, n;
  unsigned long TailleTable = 0;
  unsigned short Longueur = 0;

  if (!(CalculsEffectues & CALCUL_BLOCS))
  {
    TailleTable = NbRclasses + NbLclasses;
    B = AlloueMemoireTableau(TailleTable);  
    Taille = AlloueMemoireTableau(TailleTable);
    for (i = 0; i < TailleTable; i++)
    {  
      B[i] = i;
      Taille[i] = 1;
    }
    if (CalculsEffectues & CALCUL_LISTE_IDEMPOTENTS)
      for (i = 0; i < NbIdempotents; i++)
      {
        r = Trouver(Table2[TableIdempotents[i]].Rclasse - 1);
        l = Trouver(NbRclasses + Table2[TableIdempotents[i]].Lclasse - 1);
        Union(r, l);
      }
    else  
      for (i = IDENTITE + !PossedeUnNeutre; i <= NbElements; i++)
      {
        if (Table[i].Statut & IDEMPOTENT)
        {
          r = Trouver(Table2[i].Rclasse - 1);
          l = Trouver(NbRclasses + Table2[i].Lclasse - 1);
          Union(r, l);
        }
      }
  }
  for (r = 0; r < TailleTable; r++)
    Trouver(r);
  for (n = IDENTITE; n != DernierMot; )
  {
    n = Table[n].Suivant;
    Longueur = Table[n].Longueur;
    r = Table2[n].Rclasse-1;
  }
  printf("\n"); 
  free(Taille);
  CalculsEffectues |= CALCUL_BLOCS;    /* On prend note : le calcul des blocs est termine */
}