org.conqat.lib.commons.algo

Class UnionFindWithSize

java.lang.Object

org.conqat.lib.commons.collections.ManagedIntArray

org.conqat.lib.commons.algo.UnionFind

org.conqat.lib.commons.algo.UnionFindWithSize

All Implemented Interfaces:

java.io.Serializable

public class UnionFindWithSize
extends UnionFind

Implementation of a simple union find data structure. It implements the "partial path compression" heuristic but does not use "union by size" but instead uses randomization. Additionally the size of union clusters is managed.

Author:

hummelb

See Also:

Serialized Form

Field Summary

Fields inherited from class org.conqat.lib.commons.collections.ManagedIntArray

array, size

Constructor Summary

Constructors

Constructor and Description
UnionFindWithSize()

Method Summary

Modifier and Type	Method and Description
int	addElement() Adds a new element to this union find structure and returns its index.
protected void	connectToRepresentative(int element, int representative) Connects the given element (must also be representative) to the given representative.
int	getClusterSize(int element) Returns the size of the union cluster containing the given element.

Methods inherited from class org.conqat.lib.commons.algo.UnionFind

find, union

Methods inherited from class org.conqat.lib.commons.collections.ManagedIntArray

addArrayElement, addArrayElements

Methods inherited from class java.lang.Object

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

Constructor Detail

UnionFindWithSize

public UnionFindWithSize()

Method Detail

addElement

public int addElement()

Adds a new element to this union find structure and returns its index.

Overrides:

addElement in class UnionFind

connectToRepresentative

protected void connectToRepresentative(int element,
                                       int representative)

Connects the given element (must also be representative) to the given representative.

Overrides:

connectToRepresentative in class UnionFind

getClusterSize

public int getClusterSize(int element)

Returns the size of the union cluster containing the given element.