smithers.util
Class UnionFindNode

java.lang.Object
  smithers.util.UnionFindNode

public class UnionFindNode
extends java.lang.Object

Implementation of a disjoint-set data structure and union-find algorithm. This class represents an individual node in a disjoint-set forest. The forest is optimised by path compression on each method call.

Constructor Summary

UnionFindNode()
Creates a new node in a set of its own.

Method Summary

boolean	sameSet(UnionFindNode node) Tests whether this node and the given node are in the same set.
void	union(UnionFindNode node) Merges the set containing this node and the set containing the given node.

Methods inherited from class java.lang.Object

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

Constructor Detail

UnionFindNode

public UnionFindNode()

Creates a new node in a set of its own.

Method Detail

sameSet

public boolean sameSet(UnionFindNode node)

Tests whether this node and the given node are in the same set.

Parameters:

node - the node to test against this one

Returns:

true iff both nodes are in the same set

union

public void union(UnionFindNode node)

Merges the set containing this node and the set containing the given node.

Parameters:

node - a node in the set to merge with