edu.tum.cs.commons.algo
Class UnionFindWithSize

java.lang.Object
  edu.tum.cs.commons.collections.ManagedIntArray
      edu.tum.cs.commons.algo.UnionFind
          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.