ProGAL.geom3d.complex.alphaComplex
Class DisjointSet

java.lang.Object
  ProGAL.geom3d.complex.alphaComplex.DisjointSet

public class DisjointSet
extends java.lang.Object

A class for maintaining disjoint sets using union-by-rank and path-compression. This gives an amortized runningtime of each union and find-operation of O(\alpha(n)). Except that a set is represented as an internal class that is associated with objects using a hash-map, this implementation follows the description in Cormen et. al 2001 and on http://en.wikipedia.org/wiki/Disjoint-set_data_structure (Jan. 2011).

Author:

R. Fonseca

Nested Class Summary

class

DisjointSet.Set A class representing a set.

Constructor Summary

DisjointSet()

Method Summary

DisjointSet.Set	find(DisjointSet.Set s) Determine which set a particular element is in.
DisjointSet.Set	find(java.lang.Object o) Determine which set a particular element is in.
DisjointSet.Set	makeSet(java.lang.Object o) Create a new set containing the element o
void	union(DisjointSet.Set x, DisjointSet.Set y) Merge two sets into a single set
void	union(java.lang.Object x, java.lang.Object y) Merge two sets into a single set.

Methods inherited from class java.lang.Object

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

Constructor Detail

DisjointSet

public DisjointSet()

Method Detail

union

public void union(java.lang.Object x,
                  java.lang.Object y)

Merge two sets into a single set. Warning: To associate objects with sets the set has to be looked up in a list which takes O(n) time.

union

public void union(DisjointSet.Set x,
                  DisjointSet.Set y)

Merge two sets into a single set

find

public DisjointSet.Set find(DisjointSet.Set s)

Determine which set a particular element is in. If one wishes to determine if two objects belong to the same set, the references returned by find can be compared by equality (i.e. "==" ).

find

public DisjointSet.Set find(java.lang.Object o)

Determine which set a particular element is in. If one wishes to determine if two objects belong to the same set, the references returned by find can be compared by equality (i.e. "==" ). Warning: To associate objects with sets the set has to be looked up in a list which takes O(n) time.

makeSet

public DisjointSet.Set makeSet(java.lang.Object o)

Create a new set containing the element o