|
TUM CCSM Commons | |||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectedu.tum.cs.commons.algo.ObjectUnionFind<T>
public class ObjectUnionFind<T>
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.
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 |
---|
public ObjectUnionFind()
public ObjectUnionFind(java.util.HashMap<T,java.lang.Integer> lookup)
lookup
- the map being used for lookup (e.g. for providing a
IdentityHashMap
. This map should not be used outside
afterwards!Method Detail |
---|
public T find(T element)
public void union(T element1, T element2)
public void addElement(T element)
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.
public boolean containsElement(T element)
addElement(Object)
or union(Object, Object)
. Note that
all methods will also work for elements for which this method returns
false,
public int getClusterSize(T element)
|
TUM CCSM Commons | |||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |