|
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.collections.ManagedIntArray
edu.tum.cs.commons.algo.UnionFind
edu.tum.cs.commons.algo.UnionFindWithSize
public class UnionFindWithSize
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.
Field Summary |
---|
Fields inherited from class edu.tum.cs.commons.collections.ManagedIntArray |
---|
array, size |
Constructor Summary | |
---|---|
UnionFindWithSize()
|
Method Summary | |
---|---|
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 edu.tum.cs.commons.algo.UnionFind |
---|
find, union |
Methods inherited from class edu.tum.cs.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 |
---|
public UnionFindWithSize()
Method Detail |
---|
public int addElement()
addElement
in class UnionFind
protected void connectToRepresentative(int element, int representative)
connectToRepresentative
in class UnionFind
public int getClusterSize(int element)
|
TUM CCSM Commons | |||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |