TUM CCSM Commons

edu.tum.cs.commons.algo
Class ObjectUnionFind<T>

java.lang.Object
  extended by edu.tum.cs.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.

Version:
$Rev: 26283 $
Author:
hummelb, $Author: juergens $
Rating:
GREEN Hash: 91B639154846D7F1249747DF97FF5A44

Constructor Summary
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
 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.


TUM CCSM Commons

TUM CCSM Commons - 2.7