smithers.util
Class AlternatingUnionFindNode

java.lang.Object
  smithers.util.AlternatingUnionFindNode

public class AlternatingUnionFindNode
extends java.lang.Object

A modified disjoint-set data structure which also partitions each set into two parts. The typical usage can be described as follows. A collection of objects are to be partitioned into two disjoint parts. To start with, there is no information about whether any two objects are in the same part. Periodically it is discovered (or decided) that two objects are, or are not, in the same part. A collection of objects of this class can keep track of this information.

See Also:

UnionFindNode

Constructor Summary

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

Method Summary

boolean	samePart(AlternatingUnionFindNode node) Tests whether this node and the given node are in the same part of a set.
boolean	sameSet(AlternatingUnionFindNode node) Tests whether this node and the given node are in the same set.
void	union(AlternatingUnionFindNode node, boolean same) 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

AlternatingUnionFindNode

public AlternatingUnionFindNode()

Creates a new node in a set of its own.

Method Detail

sameSet

public boolean sameSet(AlternatingUnionFindNode 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

samePart

public boolean samePart(AlternatingUnionFindNode node)

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

Parameters:

node - the node to test against this one

Returns:

true iff both nodes are in the same part of the same set

union

public void union(AlternatingUnionFindNode node,
                  boolean same)

Merges the set containing this node and the set containing the given node. The two nodes given (this and node) can be placed in the same part of the new set, or different parts, all other nodes in the set are organised according to this. If the two nodes are already in the same set, and the same parameter contradicts the existing data, then the behaviour of samePart(AlternatingUnionFindNode) is undefined for this set.

Parameters:

node - a node in the set to merge with

same - true if this and node should be placed in the same part of the new set