org.eclipse.incquery.runtime.base.itc.alg.incscc

Class UnionFind<V>

java.lang.Object

org.eclipse.incquery.runtime.base.itc.alg.incscc.UnionFind<V>

Type Parameters:

V - the type parameter of the element's stored in the union-find data structure

public class UnionFind<V>
extends java.lang.Object

Union-find data structure implementation. Note that the implementation relies on the correct implementation of the equals method of the type parameter's class.

Author:

Tamas Szabo

Constructor Summary

Constructors

Constructor and Description
UnionFind() Instantiate a new union-find data structure.
UnionFind(java.lang.Iterable<V> elements) Instantiate a new union-find data structure with the given elements as separate sets.

Method Summary

Modifier and Type	Method and Description
void	deleteSet(V root) Delete the set whose root is the given node.
V	find(V node) Find method with path compression.
java.util.Set<V>	getPartition(V element) Returns the partition in which the given element can be found, or null otherwise.
java.util.Collection<java.util.Set<V>>	getPartitions() Returns all partitions.
boolean	isSameUnion(java.util.Set<V> elements) Returns if all given elements are in the same partition.
V	makeSet(java.util.Collection<V> nodes) Creates a new union set from a collection of elements.
V	makeSet(V node) This method creates a single set containing the given node.
V	union(V x, V y) Union by rank implementation of the two sets which contain x and y; x and/or y can be a single element from the universe.
void	unite(java.util.Set<V> elements) Places the given elements in to the same partition.

Methods inherited from class java.lang.Object

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

Constructor Detail

UnionFind

public UnionFind()

Instantiate a new union-find data structure.

UnionFind

public UnionFind(java.lang.Iterable<V> elements)

Instantiate a new union-find data structure with the given elements as separate sets.

Method Detail

makeSet

public V makeSet(java.util.Collection<V> nodes)

Creates a new union set from a collection of elements.

Parameters:

nodes - the collection of elements

Returns:

the root element

makeSet

public V makeSet(V node)

This method creates a single set containing the given node.

Parameters:

node - the root node of the set

Returns:

the root element

find

public V find(V node)

Find method with path compression.

Parameters:

node - the node to find

Returns:

the root node of the set in which the given node can be found

union

public V union(V x,
               V y)

Union by rank implementation of the two sets which contain x and y; x and/or y can be a single element from the universe.

Parameters:

x - set or single element of the universe

y - set or single element of the universe

Returns:

the new root of the two sets

unite

public void unite(java.util.Set<V> elements)

Places the given elements in to the same partition.

deleteSet

public void deleteSet(V root)

Delete the set whose root is the given node.

Parameters:

root - the root node

isSameUnion

public boolean isSameUnion(java.util.Set<V> elements)

Returns if all given elements are in the same partition.

getPartition

public java.util.Set<V> getPartition(V element)

Returns the partition in which the given element can be found, or null otherwise.

getPartitions

public java.util.Collection<java.util.Set<V>> getPartitions()

Returns all partitions.