Class Forest

java.lang.Object
  |
  +--Forest

All Implemented Interfaces:

DisjointSetsOfInt

public class Forest

extends java.lang.Object

implements DisjointSetsOfInt

Classe per la realizzazione di gli insiemi disgiunti di interi, implementati come alberi di una foresta.
Vedi capitolo 22 del testo: Introduction to algorithms di T.H. Cormen, C.E. Leiserson, R.L. Rievest

Constructor Summary

Forest()
Genera una foresta vuota

Method Summary

int	Cardinality() ritorna la cardinalità della partizione corrente
void	Create(java.util.Set S) dato un insieme di interi S, genera la partizione discreta {{n} | n in S}
int	Find(int e) dato un elemento e in S ritorna il rappresentante della parte in S cui e appartiene
java.lang.String	toString() stampa la foresta come sequenza di coppie (etichetta nodo, indice del padre)
void	Union(int x, int y) modifica la partizione corrente sostituendo le parti cui appartengono x e y con la loro unione

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

Forest

public Forest()

Genera una foresta vuota

Method Detail

Create

public void Create(java.util.Set S)

Description copied from interface: DisjointSetsOfInt

dato un insieme di interi S, genera la partizione discreta {{n} | n in S}

Specified by:

Create in interface DisjointSetsOfInt

Parameters:

S - insieme di interi

Side effects: la foresta corrente rappresenta la partizione discreta di S realizzando ciascun elemento della partizione con un albero fatto della sola radice

Find

public int Find(int e)

Description copied from interface: DisjointSetsOfInt

dato un elemento e in S ritorna il rappresentante della parte in S cui e appartiene

Specified by:

Find in interface DisjointSetsOfInt

Parameters:

e - elemento dell'insieme su cui è costruita la partizione corrente

Returns:

l'indice della radice dell'albero cui appartiene e, ovvero del rappresentante canonico della classe d'equivalenza cui appartiene

Side effects: realizza la compressione del cammino

Union

public void Union(int x,
                  int y)

Description copied from interface: DisjointSetsOfInt

modifica la partizione corrente sostituendo le parti cui appartengono x e y con la loro unione

Specified by:

Union in interface DisjointSetsOfInt

Parameters:

x - intero di cui si considera la classe U cui appartiene

y - intero di cui si considera la classe V cui appartiene

Side effects: nella partizione corrente U e V sono rimpiazzati dalla loro unione (usando l'unione di alberi col criterio del minimo rango)

Cardinality

public int Cardinality()

Description copied from interface: DisjointSetsOfInt

ritorna la cardinalità della partizione corrente

Specified by:

Cardinality in interface DisjointSetsOfInt

toString

public java.lang.String toString()

stampa la foresta come sequenza di coppie (etichetta nodo, indice del padre)

Overrides:

toString in class java.lang.Object