goldman.partition
Class UnionFindNode<T>

java.lang.Object
  extended by goldman.partition.UnionFindNode<T>
All Implemented Interfaces:
PartitionElement<T>

public class UnionFindNode<T>
extends Object
implements PartitionElement<T>

The UnionFindNode class provides an implementation of the PartitionElement ADT using the union-find data structure.


Constructor Summary
UnionFindNode(T data)
          It creates a new component holding a single union-find node associated with the given application data.
 
Method Summary
 UnionFindNode<T> findRepresentative()
          Returns the representative element for the component that includes this partition element.
 T get()
          Returns the data associated with this partition element.
 boolean sameComponent(PartitionElement<T> x)
          Returns true if and only if this partition element and x are in the same component.
 void set(T data)
          Resets the application data to the given value.
 String toString()
           
 PartitionElement<T> union(PartitionElement<T> x)
          Combines the components of x and this partition element into one component If x and the node on which this method is called are in the same component then no change is made, and the root of their component is returned.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

UnionFindNode

public UnionFindNode(T data)
It creates a new component holding a single union-find node associated with the given application data.

Parameters:
data - the application data,
Method Detail

toString

public String toString()
Specified by:
toString in interface PartitionElement<T>
Overrides:
toString in class Object
Returns:
a String that shows the application data held within the node.

get

public T get()
Description copied from interface: PartitionElement
Returns the data associated with this partition element.

Specified by:
get in interface PartitionElement<T>
Returns:
the application data held within the node.

set

public void set(T data)
Resets the application data to the given value.

Specified by:
set in interface PartitionElement<T>
Parameters:
data - the new value for the application data

findRepresentative

public UnionFindNode<T> findRepresentative()
Description copied from interface: PartitionElement
Returns the representative element for the component that includes this partition element.

Specified by:
findRepresentative in interface PartitionElement<T>
Returns:
the representative node for the component containing this node.

sameComponent

public boolean sameComponent(PartitionElement<T> x)
Description copied from interface: PartitionElement
Returns true if and only if this partition element and x are in the same component.

Specified by:
sameComponent in interface PartitionElement<T>
Parameters:
x - a union-find node,
Returns:
true if and only if x and the node on which this method is called are in the same component.

union

public PartitionElement<T> union(PartitionElement<T> x)
Combines the components of x and this partition element into one component If x and the node on which this method is called are in the same component then no change is made, and the root of their component is returned.

Specified by:
union in interface PartitionElement<T>
Parameters:
x - a node whose component is to be combined with the component of this partition element.
Returns:
the representative element of the resulting component.
Throws:
IllegalArgumentException - x is not a union-find node