soot.jimple.spark.ondemand.genericutil

Class DisjointSets

java.lang.Object

soot.jimple.spark.ondemand.genericutil.DisjointSets

public final class DisjointSets
extends java.lang.Object

Constructor Summary

Constructors

Constructor and Description
DisjointSets(int numElements) Construct a disjoint sets object.

Method Summary

Modifier and Type	Method and Description
int	find(int x) find() finds the (int) name of the set containing a given element.
void	union(int root1, int root2) union() unites two disjoint sets into a single set.

Methods inherited from class java.lang.Object

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

Constructor Detail

DisjointSets

public DisjointSets(int numElements)

Construct a disjoint sets object.

Parameters:

numElements - the initial number of elements--also the initial number of disjoint sets, since every element is initially in its own set.

Method Detail

union

public void union(int root1,
                  int root2)

union() unites two disjoint sets into a single set. A union-by-size heuristic is used to choose the new root. This method will corrupt the data structure if root1 and root2 are not roots of their respective sets, or if they're identical.

Parameters:

root1 - the root of the first set.

root2 - the root of the other set.

find

public int find(int x)

find() finds the (int) name of the set containing a given element. Performs path compression along the way.

Parameters:

x - the element sought.

Returns:

the set containing x.