polyglot.ext.ibex.lr
Class UnionFind

java.lang.Object
  extended bypolyglot.ext.ibex.lr.UnionFind

public class UnionFind
extends java.lang.Object

Implementation of Tarjan's union-find data structure. Elements are integers. A good description of union-find can be found in [Cormen, et. al. 1990].


Constructor Summary
UnionFind()
           
UnionFind(int size)
           
 
Method Summary
 int find(int a)
          Returns the integer value associated with the first Node in a set.
 polyglot.ext.ibex.lr.UnionFind.Node findNode(int a)
          Searches the disjoint sets for a given integer.
 boolean isEquiv(int a, int b)
          Returns true if a and b are in the same set.
 void union(int a, int b)
          Combines the set that contains a with the set that contains b.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

UnionFind

public UnionFind()

UnionFind

public UnionFind(int size)
Method Detail

findNode

public polyglot.ext.ibex.lr.UnionFind.Node findNode(int a)
Searches the disjoint sets for a given integer. Returns the set containing the integer a. Sets are represented by a local class Node.


find

public int find(int a)
Returns the integer value associated with the first Node in a set.


isEquiv

public boolean isEquiv(int a,
                       int b)
Returns true if a and b are in the same set.


union

public void union(int a,
                  int b)
Combines the set that contains a with the set that contains b.