edu.uci.ics.dillenco.datastruct
Class UnionFind<T>

java.lang.Object
  edu.uci.ics.dillenco.datastruct.UnionFind<T>

public class UnionFind<T>
extends Object

This class implements the standard union-find algorithm, with weight balancing and path compression

Constructor Summary

UnionFind()
Construct an empty union-find structure with an expected capacity of 100.

UnionFind(int size)
Construct an empty union-find structure with the given expected capacity.

Method Summary

void	add(T data) Add the given data item as a singleton set.
T	find(T data) Return the label of the set containing the given data item.
T	merge(T data1, T data2) Merge the sets containing the two given data items.
void	reset() Reset the structure so every element is in its own equivalent class.
void	setAsLabel(T data) Set the indicated data item as the label (root) of its equivalence class.
void	verify() Verify internal consistency of data structures.

Methods inherited from class java.lang.Object

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

Constructor Detail

UnionFind

public UnionFind()

Construct an empty union-find structure with an expected capacity of 100.

UnionFind

public UnionFind(int size)

Construct an empty union-find structure with the given expected capacity.

Parameters:

size - the expected capacity

Method Detail

reset

public void reset()

Reset the structure so every element is in its own equivalent class.

add

public void add(T data)

Add the given data item as a singleton set.

Parameters:

data - the data item to be added.

find

public T find(T data)

Return the label of the set containing the given data item.

Parameters:

data - the data item whose set label is to be returned.

Returns:

the label of the set containing the given data item. If the parameter data is null, the returned value is null.

merge

public T merge(T data1,
               T data2)

Merge the sets containing the two given data items. The two items can be arbitrary set elements, they do not have to be the set labels. But they must be in different sets. If the two items are in the same set, an IllegalArgumentException is thrown.

Parameters:

data1 - the first data item

data2 - the second data item

Returns:

the label (root) of the new merged set. If either data1 or data2 is null, the root of the other set is returned.

setAsLabel

public void setAsLabel(T data)

Set the indicated data item as the label (root) of its equivalence class. This does not affect the UnionFind tree, but it does alter the association between UnionFind tree elements and data items.

Parameters:

data - the data item to be made the label.

verify

public void verify()

Verify internal consistency of data structures. If the verification fails,an IllegalArgumentException is thrown.