TUM CCSM Commons

edu.tum.cs.commons.algo
Class UnionFindWithSize

java.lang.Object
  extended by edu.tum.cs.commons.collections.ManagedIntArray
      extended by edu.tum.cs.commons.algo.UnionFind
          extended by edu.tum.cs.commons.algo.UnionFindWithSize

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.

Version:
$Rev: 26283 $
Author:
hummelb, $Author: juergens $
Rating:
GREEN Hash: 71910668F1546351D03C7BCCEED97CB6

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

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.


TUM CCSM Commons

TUM CCSM Commons - 2.7