org.deri.iris.utils
Class DisjointSets<T>

java.lang.Object
  org.deri.iris.utils.DisjointSets<T>

public class DisjointSets<T>
extends Object

A data structure for representing and managing partitions, i.e. families of disjoint sets. Implemented as a disjoint-set data structure, which uses path compression and union by rank.

Note that the corresponding equals and hashCode methods of the type T are used to determine the equality of two representative elements of type T. Therefore, the equals and hashCode methods have to be implemented correctly.

Author:

Uwe Keller, Adrian Marte

See Also:

Object.equals(java.lang.Object), java.lang.Object#hashCode(java.lang.Object), Wikipedia article about Disjoint-set data structure

Constructor Summary

DisjointSets()
Creates a new empty equivalence relation.

Method Summary

boolean	add(T element) Adds a new element to the domain of the equivalence relation.
boolean	areInSameSet(T x, T y) Checks if the two specified objects are in the same set.
boolean	equals(Object obj)
T	find(T element) Retrieves the representative element of the set in which the given element resides.
int	getNumberOfSets() Returns the number of sets.
Set<T>	getSetOf(T element) Returns the set of elements in which the specified element resides.
Collection<Set<T>>	getSets() Returns a collection of all the sets of this disjoint-set.
int	hashCode()
T	putInSameSet(T x, T y) Merges the two sets of the two specified elements into a single set.
boolean	remove(T element) Removes an element from the disjoint-set.
String	toString()

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Constructor Detail

DisjointSets

public DisjointSets()

Creates a new empty equivalence relation.

Method Detail

add

public boolean add(T element)

Adds a new element to the domain of the equivalence relation. In fact the new element corresponds to a new singleton set consisting only of the given object.

Parameters:

element - The new element.

Returns:

true if this disjoint-set did not already contain the specified element, false otherwise.

remove

public boolean remove(T element)

Removes an element from the disjoint-set. The element is removed from all sets.

Parameters:

element - The element.

areInSameSet

public boolean areInSameSet(T x,
                            T y)

Checks if the two specified objects are in the same set. The corresponding equals method is used to determine the equality of elements of the given type.

Parameters:

x - The first object.

y - The second object.

Returns:

true if the two given objects are in the same set, false otherwise.

putInSameSet

public T putInSameSet(T x,
                      T y)

Merges the two sets of the two specified elements into a single set. Creates a new singleton set for elements which have not been added before.

Parameters:

x - The first element.

y - The second element.

Returns:

The representative object of the set that represents the merge of the element's sets.

find

public T find(T element)

Retrieves the representative element of the set in which the given element resides.

Parameters:

element - The element.

Returns:

The representative object for the set containing the specified element, or null if the specified element has not been added yet, i.e. there is no set containing the element.

getSets

public Collection<Set<T>> getSets()

Returns a collection of all the sets of this disjoint-set.

Returns:

A collection of all the sets of this disjoint-set.

getSetOf

public Set<T> getSetOf(T element)

Returns the set of elements in which the specified element resides.

Parameters:

element - The element.

Returns:

The set of elements in which the specified element resides or an empty set if has not been added to this disjoint-set yet.

getNumberOfSets

public int getNumberOfSets()

Returns the number of sets.

Returns:

The number of equivalence classes in the equivalence relation.

hashCode

public int hashCode()

Overrides:

hashCode in class Object

equals

public boolean equals(Object obj)

Overrides:

equals in class Object

toString

public String toString()

Overrides:

toString in class Object