com.mhhe.clrs2e
Class DisjointSetForest

java.lang.Object
  |
  +--com.mhhe.clrs2e.DisjointSetForest

All Implemented Interfaces:

DisjointSetUnion

public class DisjointSetForest

extends java.lang.Object

implements DisjointSetUnion

Disjoint-set forest implementation of disjoint-set union, as given on page 508 of Introduction to Algorithms, Second edition.

Nested Class Summary

private static class

DisjointSetForest.Node Private inner class to serve as opaque handles.

Constructor Summary

DisjointSetForest()

Method Summary

java.lang.Object	findSet(java.lang.Object x) Returns the object that serves as the representative of the set containing an object.
private void	link(DisjointSetForest.Node x, DisjointSetForest.Node y) Links together two sets, given their root nodes.
java.lang.Object	makeSet(java.lang.Object x) Makes a singleton set containing an object.
void	union(java.lang.Object x, java.lang.Object y) Unites two sets, identified by handles to objects in the sets.

Methods inherited from class java.lang.Object

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

Constructor Detail

DisjointSetForest

public DisjointSetForest()

Method Detail

makeSet

public java.lang.Object makeSet(java.lang.Object x)

Makes a singleton set containing an object.

Specified by:

makeSet in interface DisjointSetUnion

Parameters:

x - The object in the singleton set.

Returns:

A handle that serves to identify the set in future operations.

union

public void union(java.lang.Object x,
                  java.lang.Object y)

Unites two sets, identified by handles to objects in the sets. The original sets are destroyed.

Specified by:

union in interface DisjointSetUnion

Parameters:

x - Handle to an object in one set.

y - Handle to an object in the other set.

Throws:

java.lang.ClassCastException - if either x or y does not reference a Node object.

findSet

public java.lang.Object findSet(java.lang.Object x)

Returns the object that serves as the representative of the set containing an object.

Specified by:

findSet in interface DisjointSetUnion

Parameters:

x - Handle to the object.

Returns:

A handle to the representative of the set containing x.

Throws:

java.lang.ClassCastException - if x is not a reference to a Node object.

link

private void link(DisjointSetForest.Node x,
                  DisjointSetForest.Node y)

Links together two sets, given their root nodes. The root with the larger rank becomes the parent of the root with the smaller rank. In case of a tie, we arbitrarily choose one root as the parent of the other.

Parameters:

x - The root node of one set.

y - The root node of the other set.