//package DisjointSet;

import java.util.HashMap;
import java.util.Vector;
import java.util.Iterator;
/**
 * Title:        Disjoint Set
 * Description:  Implementazione dell'adt disjoint set mediante foreste di alberi.
 * In questa implementazione si utilizzano le euristiche "union by rank" e
 * "path compression" per aumentare le prestazioni.
 * Copyright:    Copyright (c) 2000
 * Company:      Università degli Studi di Verona
 * @author Roberto Posenato
 * @version 1.0
 */

 /**
  * Un insieme disgiunto è rappresentato da un HashMap of Node.
  * Si utilizza HashMap in quanto è possibile inserire/ricercare gli oggetti
  * utilizzandoli come key della hash table.
  * Volendo implementare la classe mediante foreste di alberi, la classe Node
  * contiene l'oggetto, l'oggetto padre (è un albero particolare) e il rank.
  * Il rank approssima il logaritmo della dimensione del sottoalbero ed è un upper
  * bound all'altezza del nodo nell'albero.
  */
public class ForestDisjointSet implements DisjointSet {

  //
  HashMap insiemi;
  int nInsiemi;

  public ForestDisjointSet() {
    insiemi = new HashMap();
    nInsiemi = 0;
  }

  public int size() {
    return nInsiemi;
  }

  /**
   * makeSet(Object x) crea un nuovo insieme singleton.
   * Il rank della radice è 0, mentre poniamo il padre uguale a se stesso.
   * Ricordarsi che tutti gli elementi devono essere inseriti la prima volta
   * come insiemi singoletti.
   */
  public void makeSet(Object x) {
    if (!insiemi.containsKey(x)) {
      Node nodo = new Node(x, 0);
      insiemi.put(x, nodo);
      nInsiemi++;
    }
  }

  /**
   * findSet(Object x) restituisce il rappresentante dell'insieme che contiene
   * l'oggetto x. Questa procedura implementa l'euristica "path compression" che
   * modifica (durante la ricerca) il padre di ciascun nodo di un albero, in modo
   * tale che punti direttamente alla radice dell'albero. In questo modo si può
   * dimostrare che il tempo di computazione per n operazioni di findSet & union
   * si riduce considerevolmente.
   */
  public Object findSet(Object x) {

    Node nodo = (Node) insiemi.get(x);//recupero il nodo nell'insieme

    if (nodo != null) {
      if (x != nodo.padre)
        nodo.padre = findSet(nodo.padre);
      return nodo.padre;
    } else
      return null;
  }

  /**
   * union(Object x, Object y) esegue l'unione dei due insiemi che contengono
   * gli oggetti x e y.
   *
   */
  public void union(Object x, Object y) {
    link(findSet(x),findSet(y));
  }

  /**
   * link(x, y) fonde i due alberi con radice x e y. La fusione è realizzata
   * secondo l'euristica "union by rank".
   * L'idea è far diventare l'albero con meno nodi figlio della radice dell'altro.
   * Il rank deve essere aggiustato solo nel caso in cui i due alberi hanno il
   * medesimo rank (in questo caso infatti l'albero risultante è più alto di 1)
   */
  private void link(Object x, Object y) {

    if (x != null && y != null) {
      Node nodoX = (Node) insiemi.get(x);
      Node nodoY = (Node) insiemi.get(y);
      if ( ! nodoX.padre.equals(nodoY.padre) ) {
        if (nodoX.rank > nodoY.rank)
          nodoY.padre = x;
        else {
          nodoX.padre = y;
          if (nodoX.rank == nodoY.rank)
            nodoY.rank += 1;
        }
        nInsiemi--;
      }
    }
  }

  public String toString() {
    Object key;
    Node nodo;
    int i;
    Vector listaRapp = new Vector();
    Vector listaMembri = new Vector();
    Iterator chiave = insiemi.keySet().iterator();

    while (chiave.hasNext()) {
      nodo = (Node) insiemi.get( key = chiave.next());
      i = listaRapp.indexOf(nodo.padre);
      if (i != -1) { //già inserito
        listaMembri.setElementAt(
          (String) listaMembri.get(i) + ", " + key.toString(),
          i
        );
      } else {
        listaRapp.addElement(nodo.padre);
        listaMembri.addElement(key.toString());
      }
    }

    StringBuffer out = new StringBuffer();
    for (i=0;(i<listaRapp.size()); i++)
      out.append(listaRapp.get(i).toString() + "\t:\t" + listaMembri.get(i).toString() + "\n");

    return out.toString();
  }
}