cc.kave.repackaged.jayes.internal.util

Class UnionFind

java.lang.Object

cc.kave.repackaged.jayes.internal.util.UnionFind

public class UnionFind
extends Object

Disjoint Set Datastructure, uses Union by Rank and Path Compression heuristics. See "Efficiency of a Good But Not Linear Set Union Algorithm" (Tarjan, 1975)

Constructor Summary

Constructors

Constructor and Description
UnionFind()

Method Summary

Modifier and Type	Method and Description
static UnionFind[]	createArray(int size)
UnionFind	find()
void	merge(UnionFind other) Unites the sets.
int	rank()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

UnionFind

public UnionFind()

Method Detail

find

public UnionFind find()

Returns:

the set that contains this element

merge

public void merge(UnionFind other)

Unites the sets. In equal rank case, the other set is chosen as the new root.

Parameters:

other - set to unite with

rank

public int rank()

Returns:

upper bound for the height of the tree rooted at this element

createArray

public static UnionFind[] createArray(int size)