com.oracle.graal.graph

Class NodeUnionFind

java.lang.Object

com.oracle.graal.graph.NodeIdAccessor

com.oracle.graal.graph.NodeUnionFind

public class NodeUnionFind
extends NodeIdAccessor

Union-find data structure for Nodes. All operations have an accumulated worst-case complexity of O(a(n)), where a(n) is the inverse of the Ackermann function A(n,n).

Field Summary

Fields

Modifier and Type	Field and Description
private int[]	parent
private int[]	rank

Fields inherited from class com.oracle.graal.graph.NodeIdAccessor

epoch, graph

Constructor Summary

Constructors

Constructor and Description
NodeUnionFind(Graph graph) Create a new union-find data structure for a Graph.

Method Summary

Modifier and Type	Method and Description
boolean	equiv(Node a, Node b)
private int	find(int a)
Node	find(Node a) Get a representative element of the equivalence set of a node.
private void	union(int a, int b)
void	union(Node a, Node b) Merge the equivalence sets of two nodes.

Methods inherited from class com.oracle.graal.graph.NodeIdAccessor

getGraph, getNodeId, verifyIdsAreStable

Methods inherited from class java.lang.Object

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

Field Detail

rank

private int[] rank

parent

private int[] parent

Constructor Detail

NodeUnionFind

public NodeUnionFind(Graph graph)

Create a new union-find data structure for a Graph. Initially, all nodes are in their own equivalence set.

Method Detail

union

public void union(Node a,
                  Node b)

Merge the equivalence sets of two nodes. After calling this function, find(a) == find(b).

find

public Node find(Node a)

Get a representative element of the equivalence set of a node. This function returns the same representative element for all members of the same equivalence set, i.e., find(a) == find(b) if and only if a and b are in the same set.

equiv

public boolean equiv(Node a,
                     Node b)

union

private void union(int a,
                   int b)

find

private int find(int a)