dk.brics.xact.analysis.util
Class UnionFindForest<Key,NodeData>

java.lang.Object
  dk.brics.xact.analysis.util.UnionFindForest<Key,NodeData>

Type Parameters:

Key -

NodeData -

public abstract class UnionFindForest<Key,NodeData>
extends Object

Maintains a set of disjoint sets (called components). A node belongs to exactly one component, and components can be merged into larger components. Each component is associated with some user data that can be accessed with getData(Object).

Constructor Summary

UnionFindForest()

Method Summary

boolean	containsKey(Key key)
protected abstract NodeData	defaultNodeData()
NodeData	getData(Key key) Returns the data associated with the specified key's component.
Set<Key>	getKeys()
Key	getRepresentativeKey(Key key) Returns the key representing the given key's component.
NodeData	merge(Key a, Key b)
protected abstract NodeData	mergeNodeData(NodeData a, NodeData b) Merges the data associated with two components when they are merged into one.
void	setData(Key key, NodeData data) Sets the data associated with the specified key's component.

Methods inherited from class java.lang.Object

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

Constructor Detail

UnionFindForest

public UnionFindForest()

Method Detail

containsKey

public boolean containsKey(Key key)

defaultNodeData

protected abstract NodeData defaultNodeData()

getData

public NodeData getData(Key key)

Returns the data associated with the specified key's component. The data may be modified if wanted.

getKeys

public Set<Key> getKeys()

getRepresentativeKey

public Key getRepresentativeKey(Key key)

Returns the key representing the given key's component. This is the same for all keys in the same component.

merge

public NodeData merge(Key a,
                      Key b)

mergeNodeData

protected abstract NodeData mergeNodeData(NodeData a,
                                          NodeData b)

Merges the data associated with two components when they are merged into one. Both arguments may be modified if wanted and the returned value may either be one of the arguments or a new instance.

Parameters:

a - data from one component

b - data from another component

Returns:

new node for their joined component

setData

public void setData(Key key,
                    NodeData data)

Sets the data associated with the specified key's component.