Package net.automatalib.common.util
Class UnionFind
- java.lang.Object
-
- net.automatalib.common.util.UnionFind
-
- All Implemented Interfaces:
IntDisjointSets
public final class UnionFind extends Object implements IntDisjointSets
The well-known disjoint-set forest data structure for dealing with partitions on a fixed-range integer domain.
-
-
Constructor Summary
Constructors Constructor Description UnionFind(int n)
Initializes the disjoint-set data structure.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description int
find(int x)
Finds the set of a given element, and compresses the path to the root node.int
link(int x, int y)
Unites two given sets.int
size()
Returns the size of the universe.-
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
-
Methods inherited from interface net.automatalib.common.util.IntDisjointSets
equivalent, union
-
-
-
-
Method Detail
-
size
public int size()
Description copied from interface:IntDisjointSets
Returns the size of the universe. The elements of the universe are the integers between0
(inclusive) andsize()
(exclusive).- Specified by:
size
in interfaceIntDisjointSets
- Returns:
- the size of the universe
-
find
public int find(int x)
Finds the set of a given element, and compresses the path to the root node.- Specified by:
find
in interfaceIntDisjointSets
- Parameters:
x
- the element- Returns:
- the identifier of the set which contains the given element
-
link
public int link(int x, int y)
Unites two given sets. Note that the behavior of this method is not specified if the given parameters are normal elements and no set identifiers.- Specified by:
link
in interfaceIntDisjointSets
- Parameters:
x
- the first sety
- the second set- Returns:
- the identifier of the resulting set (either
x
ory
)
-
-