Class DisjointSets
java.lang.Object
org.locationtech.jts.operation.union.DisjointSets
A data structure that represents a partition of a set
into disjoint subsets, and allows merging subsets.
Set items are represented by integer indices
(which will typically be an index into an array
of the objects actually being partitioned).
Initially each item is in its own subset.
Client code can merge subsets of items as required for the
algorithm being performed (e.g. set partitioning or clustering).
The current partitioning can be computed at any time,
and subset items accessed
using the
DisjointSets.Subsets
accessor.
See the Wikipedia article on disjoint set data structures.
- Author:
- Martin Davis
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionclass
A representation of a partition of a set of items into disjoint subsets. -
Constructor Summary
ConstructorsConstructorDescriptionDisjointSets
(int size) Creates a new set containing a given number of items. -
Method Summary
Modifier and TypeMethodDescriptionboolean
isInSameSubset
(int i, int j) Tests if two items are in the same subset.void
merge
(int i, int j) Merges two subsets containing the given items.subsets()
Gets a representation of the current partitioning.
-
Constructor Details
-
DisjointSets
public DisjointSets(int size) Creates a new set containing a given number of items.- Parameters:
size
- the number of items contained in the set
-
-
Method Details
-
isInSameSubset
public boolean isInSameSubset(int i, int j) Tests if two items are in the same subset.- Parameters:
i
- an item indexj
- another item index- Returns:
- true if items are in the same subset
-
merge
public void merge(int i, int j) Merges two subsets containing the given items. Note that the items do not have to be the roots of their respective subsets. If the items are in the same subset the partitioning does not change.- Parameters:
i
- an item indexj
- another item index
-
subsets
Gets a representation of the current partitioning. This creates a snapshot of the partitioning; the set can be merged further after this call.- Returns:
- an representation of the current subset partitioning.
-