com.mhhe.clrs2e
Class DisjointSetLinkedList

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

All Implemented Interfaces:

DisjointSetUnion

public class DisjointSetLinkedList

extends java.lang.Object

implements DisjointSetUnion

Linked-list implementation of disjoint-set union, using the weighted-union heuristic, as given on pages 502-503 of Introduction to Algorithms, Second edition.

The representative pointer is different here from in the book. In order to be able to get to the information for a set, the representative here references the set, rather than the first node in the set's list.

Nested Class Summary

private static class	DisjointSetLinkedList.DisjointSet Private inner class for each disjoint set.
static class	DisjointSetLinkedList.DisjointSetUnionException Inner class for an exception that occurs if either set to be united is empty.
private static class	DisjointSetLinkedList.Node Private inner class for nodes of the list.

Constructor Summary

DisjointSetLinkedList()

Method Summary

private void	append(DisjointSetLinkedList.DisjointSet first, DisjointSetLinkedList.DisjointSet second) Appends one set's list to another set's list.
java.lang.Object	findSet(java.lang.Object x) Returns the object that serves as the representative of the set containing an object.
java.lang.Object	makeSet(java.lang.Object x) Makes a singleton set containing an object.
java.lang.String	printSet(java.lang.Object x) Returns the String representation of the set containing a given 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

DisjointSetLinkedList

public DisjointSetLinkedList()

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 DisjointSet object.

append

private void append(DisjointSetLinkedList.DisjointSet first,
                    DisjointSetLinkedList.DisjointSet second)

Appends one set's list to another set's list.

Parameters:

first - The set to which the other will be appended.

second - The set that will be appended to the other.

Throws:

DisjointSetLinkedList.DisjointSetUnionException - if either set is empty.

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.

printSet

public java.lang.String printSet(java.lang.Object x)

Returns the String representation of the set containing a given object.

Parameters:

x - The object whose set's String representation is returned.