org.conqat.lib.commons.algo

Class ObjectUnionFind<T>

java.lang.Object

org.conqat.lib.commons.algo.ObjectUnionFind<T>

public class ObjectUnionFind<T>
extends java.lang.Object

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

Author:

hummelb

Constructor Summary

Constructors

Constructor and Description
ObjectUnionFind() Constructor using a HashMap as underlying lookup storage.
ObjectUnionFind(java.util.HashMap<T,java.lang.Integer> lookup) Constructor through which the the underlying map can be set.

Method Summary

Modifier and Type	Method and Description
void	addElement(T element) Adds a new element to this union find structure.
boolean	containsElement(T element) Returns whether an element has been added to this stucture either by addElement(Object) or union(Object, Object).
T	find(T element) Finds and returns the representative for the given element.
int	getClusterSize(T element) Returns the size of the union cluster containing the given element.
void	union(T element1, T element2) Merges the classes in which element1 and element2 are, by giving them the same representative.

Methods inherited from class java.lang.Object

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

Constructor Detail

ObjectUnionFind

public ObjectUnionFind()

Constructor using a HashMap as underlying lookup storage.

ObjectUnionFind

public ObjectUnionFind(java.util.HashMap<T,java.lang.Integer> lookup)

Constructor through which the the underlying map can be set.

Parameters:

lookup - the map being used for lookup (e.g. for providing a IdentityHashMap. This map should not be used outside afterwards!

Method Detail

find

public T find(T element)

Finds and returns the representative for the given element.

union

public void union(T element1,
                  T element2)

Merges the classes in which element1 and element2 are, by giving them the same representative.

addElement

public void addElement(T element)

Adds a new element to this union find structure. Note that explicit adding is not required, as elements are dynamically added by union(Object, Object) and all other method work correctly even for objects not yet added. However this method makes sure, that no object can be added a second time.

containsElement

public boolean containsElement(T element)

Returns whether an element has been added to this stucture either by addElement(Object) or union(Object, Object). Note that all methods will also work for elements for which this method returns false,

getClusterSize

public int getClusterSize(T element)

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