PostGIS  2.5.1dev-r@@SVN_REVISION@@

◆ UF_ordered_by_cluster()

uint32_t* UF_ordered_by_cluster ( UNIONFIND uf)

Definition at line 112 of file lwunionfind.c.

References UNIONFIND::clusters, cmp_int_ptr(), lwalloc(), lwfree(), UNIONFIND::N, and UF_find().

Referenced by combine_geometries(), test_unionfind_ordered_by_cluster(), and UF_get_collapsed_cluster_ids().

113 {
114  size_t i;
115  uint32_t** cluster_id_ptr_by_elem_id = lwalloc(uf->N * sizeof (uint32_t*));
116  uint32_t* ordered_ids = lwalloc(uf->N * sizeof (uint32_t));
117 
118  for (i = 0; i < uf->N; i++)
119  {
120  /* Make sure each value in uf->clusters is pointing to the
121  * root of the cluster.
122  * */
123  UF_find(uf, i);
124  cluster_id_ptr_by_elem_id[i] = &(uf->clusters[i]);
125  }
126 
127  /* Sort the array of cluster id pointers, so that pointers to the
128  * same cluster id are grouped together.
129  * */
130  qsort(cluster_id_ptr_by_elem_id, uf->N, sizeof (uint32_t*), &cmp_int_ptr);
131 
132  /* Recover the input element ids from the cluster id pointers, so
133  * we can return element ids grouped by cluster id.
134  * */
135  for (i = 0; i < uf-> N; i++)
136  {
137  ordered_ids[i] = (cluster_id_ptr_by_elem_id[i] - uf->clusters);
138  }
139 
140  lwfree(cluster_id_ptr_by_elem_id);
141  return ordered_ids;
142 }
void lwfree(void *mem)
Definition: lwutil.c:244
uint32_t * clusters
Definition: lwunionfind.h:33
static int cmp_int_ptr(const void *a, const void *b)
Definition: lwunionfind.c:196
uint32_t N
Definition: lwunionfind.h:36
unsigned int uint32_t
Definition: uthash.h:78
uint32_t UF_find(UNIONFIND *uf, uint32_t i)
Definition: lwunionfind.c:61
void * lwalloc(size_t size)
Definition: lwutil.c:229
Here is the call graph for this function:
Here is the caller graph for this function: