br.usp.ime.klava.segmentit.structures
Class UnionFind

java.lang.Object
  br.usp.ime.klava.segmentit.structures.UnionFind

public class UnionFind
extends java.lang.Object

Implements the union/find operations over disjoint sets, using the union by rank and path compression heuristics.

Author:

Bruno Klava

Constructor Summary

UnionFind(int numElements)
Creates an UnionFind structure with numElements elements (unitary disjoint sets) given by keys ranging from 0 to numElements - 1.

Method Summary

int	findSet(int key) Returns the representative of the set where the element given by key belongs.
void	reset() Undoes all the operations done so far, restoring the structure to its initial state (numElements - 1 unitary disjoint sets).
java.lang.String	toString()
int	union(int key1, int key2) Merges the sets where the elements given by the keys key1 and key2 belong.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

UnionFind

public UnionFind(int numElements)

Creates an UnionFind structure with numElements elements (unitary disjoint sets) given by keys ranging from 0 to numElements - 1.

Parameters:

numElements - the number of elements to be created

Method Detail

reset

public void reset()

Undoes all the operations done so far, restoring the structure to its initial state (numElements - 1 unitary disjoint sets).

findSet

public int findSet(int key)

Returns the representative of the set where the element given by key belongs.

Parameters:

key - the key to the element to be localized

Returns:

the representative of the class where the element given by key belongs

union

public int union(int key1,
                 int key2)

Merges the sets where the elements given by the keys key1 and key2 belong.

Parameters:

key1 - a key of an element from the first set to be merged

key2 - a key of an element from the second set to be merged

Returns:

the representative of the new merged set

toString

public java.lang.String toString()

Overrides:

toString in class java.lang.Object