/* ========================================================================
   Implementações dos algoritmos de conjuntos disjuntos

   Todas as rotinas recebem como primeiro parametro
   uma colecao de conjuntos disjuntos, por referencia.

   DICA: use sempre o comando make para compilar seu
   codigo.  Ele contem a importante diretiva -wall
   (warn all = mostre todos os erros e avisos).

   DICA2: Implemente as funcoes na ordem dada abaixo, e
   submeta seu programa a cada funcao terminada (exceto
   que as duas primeiras tem que ser feitas juntas).


   ===================================================================== */

#include "cdisj.h"
#include <stdlib.h>

/*==================================================

  Makeset recebe um parametro totalelems e inicializa
  uma colecao de conjuntos disjuntos com n conjuntos
  unitarios, cada um contendo um inteiro diferente
  de 0 a totalelems-1.

  Makeset deve tambem fazer outras inicializaoes
  necessarias para manter a colecao.

  Makeset deve retornar 1 se tudo foi bem e 0
  caso contrario.

  Obs: totalelems <= 0 e' considerado "nao tudo bem", 
  entao deve retornar 0.

  ================================================*/

int  Makeset(Colecao *C, int totalelems) {
  int i;

  if (C == NULL)
    return 0;
  
  C->totalelems = totalelems;
  C->nsets = totalelems;

  if ( (C->element = (Node *) calloc(totalelems, sizeof(Node))) == NULL )
    return 0;


  for (i=0; i < totalelems; i++) {
    (C->element[i]).pai    = i;
    (C->element[i]).rank   = 0;
    (C->element[i]).nelems = 1;
  }

  return 1;
}

/*==================================================

  Libera: libera toda a area de memoria alocada para 
  a colecao C.

  ==================================================*/

void Libera(Colecao *C) {

  if (C != NULL)
    if (C->element != NULL)
      free(C->element);

  return;
}

/*==================================================

  Find recebe um parametro i e deve retornar o indice 
  da raiz do conjunto que contem i.  Se algo der errado, 
  retorna -1.

  Obs.: Nao e' preciso fazer compressao de caminhos
  neste codigo.  Basta achar a raiz.

  ==================================================*/

int  Find(Colecao *C, int i) {
  int j=-1;

  if (C == NULL)
    return -1;
  
  if (i < 0 || i >= C->totalelems ) 
    return -1;

  if ( C->element[i].pai == i )
    j = i;
  else
    j = Find(C,C->element[i].pai);

  return j;
}

/*==================================================

  NSets retorna o numero de conjuntos na colecao, ou
  -1 se algo der errado (ponteiro == NULL, por exemplo)

  ==================================================*/

int  NSets(Colecao *C) {

  if ( C == NULL)
    return -1;
  
  return C->nsets;

}

/*==================================================

  NElems recebe uma raiz r e retorna o numero de
  elementos no conjunto cuja raiz e' r.  Se algo
  der errado, retorna -1.

  ==================================================*/

int  NElems(Colecao *C, int r) {
  if (C == NULL )
    return -1;

  if (r < 0 || r >= C->totalelems )
    return -1;

  return C->element[r].nelems;
}



/*==================================================

  Union recebe dois inteiros r1 e r2 , que necessariamente
  devem correpondes a raizes da colecao (ou seja,
  representantes de conjuntos), e unir os dois
  conjuntos dados num unico conjunto.

  Aquele que tiver maior posto entre r1 e r2 devera'
  ser a raiz do novo conjunto; caso haja empate, a nova
  raiz sera' o MENOR entre r1 e r2, e a nova raiz tera'
  seu posto aumentado de uma unidade.

  Union deve ainda atualizar contadores globais sobre
  o numero total de conjuntos e sobre o numero de
  elementos de cada conjunto.

  Union deve retornar 1 se tudo foi bem e 0
  caso contrario.

  Se r1 = r2 retorna 1 mas nao faz mais nada.

  ==================================================*/

int  Union(Colecao *C, int r1, int r2) {
  int raiz, outra;

  if (C == NULL)
    return 0;

  if (0 > r1 || 0 > r2 || r1 >= C->totalelems || r2 >= C->totalelems )
    return 0;

  if (r1 == r2)
    return 1;

  if ( C->element[r1].rank == C->element[r2].rank ) {
    if (r1 < r2) {
      raiz  = r1;
      outra = r2;
    } else {
      raiz  = r2;
      outra = r1;
    }
    C->element[raiz].rank ++;
  } else {
    if ( C->element[r1].rank > C->element[r2].rank ) {
      raiz  = r1;
      outra = r2;
    } else {
      raiz = r2;
      outra = r1;
    }
    
  }
  C->element[raiz].nelems += C->element[outra].nelems;
  C->element[outra].pai = raiz;
  C->nsets --;
  
  return 1;

}















/* author: Gustavo Sverzut Barbieri (http://www.gustavobarbieri.com.br) */