PostGIS  2.2.8dev-r@@SVN_REVISION@@

◆ UF_ordered_by_cluster()

uint32_t* UF_ordered_by_cluster ( UNIONFIND uf)

Definition at line 93 of file lwunionfind.c.

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

Referenced by combine_geometries(), and test_unionfind_ordered_by_cluster().

94 {
95  size_t i;
96  uint32_t** cluster_id_ptr_by_elem_id = lwalloc(uf->N * sizeof (uint32_t*));
97  uint32_t* ordered_ids = lwalloc(uf->N * sizeof (uint32_t));
98 
99  for (i = 0; i < uf->N; i++)
100  {
101  /* Make sure each value in uf->clusters is pointing to the
102  * root of the cluster.
103  * */
104  UF_find(uf, i);
105  cluster_id_ptr_by_elem_id[i] = &(uf->clusters[i]);
106  }
107 
108  /* Sort the array of cluster id pointers, so that pointers to the
109  * same cluster id are grouped together.
110  * */
111  qsort(cluster_id_ptr_by_elem_id, uf->N, sizeof (uint32_t*), &cmp_int_ptr);
112 
113  /* Recover the input element ids from the cluster id pointers, so
114  * we can return element ids grouped by cluster id.
115  * */
116  for (i = 0; i < uf-> N; i++)
117  {
118  ordered_ids[i] = (cluster_id_ptr_by_elem_id[i] - uf->clusters);
119  }
120 
121  lwfree(cluster_id_ptr_by_elem_id);
122  return ordered_ids;
123 }
void lwfree(void *mem)
Definition: lwutil.c:214
uint32_t * clusters
Definition: lwunionfind.h:20
static int cmp_int_ptr(const void *a, const void *b)
Definition: lwunionfind.c:142
uint32_t N
Definition: lwunionfind.h:23
uint32_t UF_find(UNIONFIND *uf, uint32_t i)
Definition: lwunionfind.c:48
void * lwalloc(size_t size)
Definition: lwutil.c:199
Here is the call graph for this function:
Here is the caller graph for this function: