15 #ifndef GEOS_OPERATION_CLUSTER_UNIONFIND
16 #define GEOS_OPERATION_CLUSTER_UNIONFIND
22 #include <geos/export.h>
23 #include <geos/operation/cluster/Clusters.h>
44 std::iota(clusters.begin(), clusters.end(), 0);
45 std::fill(sizes.begin(), sizes.end(), 1);
49 bool same(
size_t i,
size_t j) {
50 return i == j || (find(i) == find(j));
54 bool different(
size_t i,
size_t j) {
66 while(clusters[root] != root) {
67 root = clusters[root];
71 size_t next = clusters[i];
84 void join(
size_t i,
size_t j) {
92 if ((sizes[b] > sizes[a]) || (sizes[a] == sizes[b] && b <= a)) {
96 clusters[a] = clusters[b];
103 size_t getNumClusters()
const {
108 void sortByCluster(T begin, T end) {
109 std::sort(begin, end, [
this](
size_t a,
size_t b) {
110 return find(a) < find(b);
128 std::vector<size_t> clusters;
129 std::vector<size_t> sizes;
Definition: UnionFind.h:33
Clusters getClusters(std::vector< size_t > elems)
UnionFind(size_t n)
Definition: UnionFind.h:40
size_t find(size_t i)
Definition: UnionFind.h:63
void join(size_t i, size_t j)
Definition: UnionFind.h:84
Basic namespace for all GEOS functionalities.
Definition: Angle.h:25