java.lang.Object
org.cicirello.ds.DisjointIntegerSetForest
 All Implemented Interfaces:
Copyable<DisjointIntegerSetForest>
public final class DisjointIntegerSetForest
extends Object
implements Copyable<DisjointIntegerSetForest>
Disjoint sets of integers from [0, n) implemented with a disjoint set forest. An instance of this
class represents a set of disjoint sets of the n integers: {0, 1, ..., n1}. Initially each
integer is in a set by itself, and the class provides methods for combining sets and checking if
elements are in the same 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 objects, see the DisjointSetForest
class.

Constructor Summary
ConstructorDescriptionDisjointIntegerSetForest
(int n) Initializes a disjoint set forest containing the integers from 0 through n1, each initially in a set by itself. 
Method Summary
Modifier and TypeMethodDescriptioncopy()
Creates an identical copy of this object.boolean
Checks if this DisjointIntegerSetForest is equal to another.int
findSet
(int element) Finds the id of the set currently containing the element.int
hashCode()
Computes a hashCode for the DisjointIntegerSetForest.boolean
sameSet
(int element1, int element2) Checks whether or not two elements are in the same set.int
size()
Gets the size of the DisjointIntegerSetForest in total number of elements.void
union
(int element1, int element2) Merges two sets into one, where the sets are chosen by specifying a representative member of each.

Constructor Details

DisjointIntegerSetForest
public DisjointIntegerSetForest(int n) Initializes a disjoint set forest containing the integers from 0 through n1, each initially in a set by itself. Parameters:
n
 The number of integers in the disjoint set forest.


Method Details

copy
Description copied from interface:Copyable
Creates an identical copy of this object. Specified by:
copy
in interfaceCopyable<DisjointIntegerSetForest>
 Returns:
 an identical copy of this object.

equals
Checks if this DisjointIntegerSetForest is equal to another. This test of equality is true if and only if the two DisjointIntegerSetForest are structurally the same (i.e., not just same set of disjoint sets, but also exact same internal structure). 
hashCode
public int hashCode()Computes a hashCode for the DisjointIntegerSetForest. 
findSet
public int findSet(int element) 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, which must be in [0,n). Returns:
 the id of the set that currently contains the element, where the id is a representative member of that set.
 Throws:
ArrayIndexOutOfBoundsException
 if element is less than 0 or if element is greater than or equal to n.

sameSet
public boolean sameSet(int element1, int element2) Checks whether or not two elements are in the same set. Parameters:
element1
 The first element, which must be in [0,n).element2
 The second element, which must be in [0,n). Returns:
 true if and only if element1 and element2 are elements in the same set of the disjoint set forest.
 Throws:
ArrayIndexOutOfBoundsException
 if element1 or element2 is less than 0 or if element1 or element2 is greater than or equal to n.

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

union
public void union(int element1, int element2) 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, which must be in [0,n).element2
 A representative member of the other set, which must be in [0,n). Throws:
ArrayIndexOutOfBoundsException
 if either element1 or element2 is less than 0 or if element1 ot element2 is greater than or equal to n.
