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().

{
        size_t i;
        uint32_t** cluster_id_ptr_by_elem_id = lwalloc(uf->N * sizeof (uint32_t*));
        uint32_t* ordered_ids = lwalloc(uf->N * sizeof (uint32_t));

        for (i = 0; i < uf->N; i++)
        {
                /* Make sure each value in uf->clusters is pointing to the
                 * root of the cluster.
                 * */
                UF_find(uf, i);
                cluster_id_ptr_by_elem_id[i] = &(uf->clusters[i]);
        }

        /* Sort the array of cluster id pointers, so that pointers to the
         * same cluster id are grouped together.
         * */
        qsort(cluster_id_ptr_by_elem_id, uf->N, sizeof (uint32_t*), &cmp_int_ptr);

        /* Recover the input element ids from the cluster id pointers, so
         * we can return element ids grouped by cluster id.
         * */
        for (i = 0; i < uf-> N; i++)
        {
                ordered_ids[i] = (cluster_id_ptr_by_elem_id[i] - uf->clusters);
        }

        lwfree(cluster_id_ptr_by_elem_id);
        return ordered_ids;
}

Here is the call graph for this function:

Here is the caller graph for this function: