E
- element typepublic final class StandardUnionFind<E> extends java.lang.Object implements java.io.Serializable, UnionFind<E>
This class implements Union-Find algorithm with rank and path compression.
See algorithmist for more detail.
Modifier and Type | Class and Description |
---|---|
private static class |
StandardUnionFind.Node<E>
The internal node representation.
|
Modifier and Type | Field and Description |
---|---|
private java.util.Map<E,StandardUnionFind.Node<E>> |
elmap
All values with the same root node are in the same equivalence set.
|
private static long |
serialVersionUID |
Constructor and Description |
---|
StandardUnionFind()
Creates an empty UnionFind structure.
|
StandardUnionFind(UnionFind<E> other)
Creates an UnionFind structure being a copy of other structure.
|
Modifier and Type | Method and Description |
---|---|
void |
add(E e)
Adds the given element to a new set if it is not already in a set.
|
java.util.Collection<java.util.Set<E>> |
allEquivalenceClasses()
Returns an immutable collection containing all equivalence classes.
|
boolean |
areEquivalent(E a,
E b)
Returns true if
a and b belong to the same equivalence
class. |
java.util.Set<E> |
elements()
Returns an unmodifiable set of all elements added to the UnionFind.
|
E |
find(E e)
Returns the representative of the equivalence class of
e . |
java.util.Set<E> |
findAll(E value)
Returns the elements in the same equivalence class as
value . |
private StandardUnionFind.Node<E> |
findRoot(StandardUnionFind.Node<E> node)
Given a
StandardUnionFind.Node , walk the parent field as far as possible, until
reaching the root, which is the StandardUnionFind.Node for the current
representative of this equivalence class. |
private StandardUnionFind.Node<E> |
findRootOrCreateNode(E e)
If e is already in a non-trivial equivalence class, that is, a class with
more than two elements, then return the
StandardUnionFind.Node corresponding to the
representative element. |
E |
union(E a,
E b)
Unions the equivalence classes of
a and b and returns the
representative of the resulting equivalence class. |
private static final long serialVersionUID
private final java.util.Map<E,StandardUnionFind.Node<E>> elmap
public StandardUnionFind()
public void add(E e)
UnionFind
public E union(E a, E b)
UnionFind
a
and b
and returns the
representative of the resulting equivalence class. The elements will be
added if they are not already present.public E find(E e)
UnionFind
e
.public boolean areEquivalent(E a, E b)
UnionFind
a
and b
belong to the same equivalence
class.areEquivalent
in interface UnionFind<E>
public java.util.Set<E> elements()
UnionFind
public java.util.Collection<java.util.Set<E>> allEquivalenceClasses()
UnionFind
allEquivalenceClasses
in interface UnionFind<E>
private StandardUnionFind.Node<E> findRootOrCreateNode(E e)
StandardUnionFind.Node
corresponding to the
representative element. Otherwise, if e sits in an equivalence class by
itself, then create a StandardUnionFind.Node
, put it into elmap and return it.private StandardUnionFind.Node<E> findRoot(StandardUnionFind.Node<E> node)
StandardUnionFind.Node
, walk the parent field as far as possible, until
reaching the root, which is the StandardUnionFind.Node
for the current
representative of this equivalence class. To achieve low runtime
complexity, also compress the path, by making each node a direct child of
the root.