ProGAL.geom3d.complex.alphaComplex
Class UnionFind<E>

java.lang.Object
  ProGAL.geom3d.complex.alphaComplex.UnionFind<E>

All Implemented Interfaces:

java.io.Serializable

public class UnionFind<E>
extends java.lang.Object
implements java.io.Serializable

UnionFind is a datastructure for performing unification and lookup operations. It uses the path compression and union-by-rank heuristics to achieve O(m * alpha(m, n)) runtime, where m is the total number of operations, n is the total number of elements in the set, and alpha denotes the *extremely* slowly-growing inverse Ackermann function. The abstract state of the data structure at each moment is determined by the previously executed unifications (union(E, E)). Each element of the universe of discourse is part of exactly one equivalence class. Initially, each elements sits in its own equivalence class; each union(E, E) operation merges the equivalence classes for its arguments. Each look-up operation (find(E)) finds the representative of the equivalence class of its argument, i.e., one of the elements from that equivalence class.

Author:

C. Scott Ananian - cananian@alumni.princeton.edu, Alexandru Salcianu - salcianu@alum.mit.edu

See Also:

Serialized Form

Constructor Summary

UnionFind()
Creates a UnionFind.

Method Summary

java.util.Set<E>	allKnownElements() Returns an unmodifiable set containing all elements that this UnionFind structure has knowledge about.
boolean	areUnified(E e1, E e2) Checks whether the elements e1 and e2 are unified in this union-find structure.
java.util.Set<E>	equivalenceClass(E e) Returns the equivalence class that element e is part of, as an unmodifiable set containing all elements from that class (including e).
E	find(E e) Returns the representative of the equivalence class of e.
E	union(E e1, E e2) Unifies the elements e1 and e2 and returns the representative of the resulting equivalence class.
boolean	unUnified(E e) Returns true if the element e has not been unified yet with any DIFFERENT element.

Methods inherited from class java.lang.Object

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

Constructor Detail

UnionFind

public UnionFind()

Creates a UnionFind.

Method Detail

union

public E union(E e1,
               E e2)

Unifies the elements e1 and e2 and returns the representative of the resulting equivalence class.

find

public E find(E e)

Returns the representative of the equivalence class of e.

areUnified

public boolean areUnified(E e1,
                          E e2)

Checks whether the elements e1 and e2 are unified in this union-find structure.

unUnified

public boolean unUnified(E e)

Returns true if the element e has not been unified yet with any DIFFERENT element. Complexity: O(1).

equivalenceClass

public java.util.Set<E> equivalenceClass(E e)

Returns the equivalence class that element e is part of, as an unmodifiable set containing all elements from that class (including e).

This method is quite slow: its execution time is at least linear in the size of the underlying forest!

allKnownElements

public java.util.Set<E> allKnownElements()

Returns an unmodifiable set containing all elements that this UnionFind structure has knowledge about. It is important to understand that this structure knows only the elements that it was asked to unify via calls to union; it doesn't know the other elements of the universe of discourse.