java.lang.Object
org.cicirello.ds.DisjointSetForest<T>
 Type Parameters:
T
 The type of object contained in the DisjointSetForest.
Represents disjoint sets of objects with a disjoint set forest. This class assumes that the
objects in the sets are of a class that has appropriately implemented the
Object.equals(java.lang.Object)
and Object.hashCode()
methods. If you rely on the default implementations of those methods
from the Object
class, then the disjoint set forest will treat two different objects
containing same data as different objects (i.e., the default behavior of equals and hashCode when
not overridden). Each object when first added to the DisjointSetForest is initially in a set by
itself. The class provides methods for combining sets and checking if elements are in the same
set, or in any set. It does not support splitting a set. It is implemented as Disjoint Set
Forests are described by Cormen, Leiserson, Rivest, and Stein describe in Introduction to
Algorithms, including the use of the union by rank heuristic and path compression.
For disjoint sets of integers, see the DisjointIntegerSetForest
class.

Constructor Summary

Method Summary
Modifier and TypeMethodDescriptionboolean
Checks if an element is in the disjoint set forest.int
Finds the id of the set currently containing the element.void
Adds a new set to the disjoint set forest containing only the new element.boolean
Checks whether or not two elements are in the same set.int
size()
Gets the size of the DisjointSetForest.void
Merges two sets into one, where the sets are chosen by specifying a representative member of each.

Constructor Details

DisjointSetForest
public DisjointSetForest()Initializes an empty DisjointSetForest.


Method Details

contains
Checks if an element is in the disjoint set forest. Parameters:
element
 The element to check Returns:
 true if and only if element is in the disjoint set forest.

findSet
Finds the id of the set currently containing the element. Calls to this method also apply path compression to make subsequent calls faster. Parameters:
element
 The element whose set is sought. Returns:
 the id of the set that currently contains the element.
 Throws:
IllegalArgumentException
 if element is not in the DisjointSetForest.

makeSet
Adds a new set to the disjoint set forest containing only the new element. Parameters:
element
 The new element to add to the disjoint set forest, which must not already exist within the DisjointSetForest. Throws:
IllegalArgumentException
 if element already exists in the DisjointSetForest.

sameSet
Checks whether or not two elements are in the same set. Parameters:
element1
 The first element.element2
 The second element. Returns:
 true if and only if element1 and element2 are elements in the same set of the disjoint set forest.

size
public int size()Gets the size of the DisjointSetForest. Returns:
 the number of elements in the DisjointSetForest.

union
Merges two sets into one, where the sets are chosen by specifying a representative member of each. If the two elements are already in the same set, then no merger takes place. Calls to this method also apply path compression while finding the sets containing each of the elements, and the union itself uses the union by rank heuristic. The combination of these two should improve cost of subsequent operations. Parameters:
element1
 A representative member of one of the sets.element2
 A representative member of the other set. Throws:
IllegalArgumentException
 if either of the elements doesn't exist in the DisjointSetForest.
