PostGIS  2.3.7dev-r@@SVN_REVISION@@
lwunionfind.c
Go to the documentation of this file.
1 /**********************************************************************
2  *
3  * PostGIS - Spatial Types for PostgreSQL
4  * http://postgis.net
5  *
6  * PostGIS is free software: you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License as published by
8  * the Free Software Foundation, either version 2 of the License, or
9  * (at your option) any later version.
10  *
11  * PostGIS is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with PostGIS. If not, see <http://www.gnu.org/licenses/>.
18  *
19  **********************************************************************
20  *
21  * Copyright 2015 Daniel Baston <dbaston@gmail.com>
22  *
23  **********************************************************************/
24 
25 
26 #include "liblwgeom.h"
27 #include "lwunionfind.h"
28 #include <string.h>
29 
30 static int cmp_int(const void *a, const void *b);
31 static int cmp_int_ptr(const void *a, const void *b);
32 
33 UNIONFIND*
34 UF_create(uint32_t N)
35 {
36  size_t i;
37  UNIONFIND* uf = lwalloc(sizeof(UNIONFIND));
38  uf->N = N;
39  uf->num_clusters = N;
40  uf->clusters = lwalloc(N * sizeof(uint32_t));
41  uf->cluster_sizes = lwalloc(N * sizeof(uint32_t));
42 
43  for (i = 0; i < N; i++)
44  {
45  uf->clusters[i] = i;
46  uf->cluster_sizes[i] = 1;
47  }
48 
49  return uf;
50 }
51 
52 void
54 {
55  lwfree(uf->clusters);
56  lwfree(uf->cluster_sizes);
57  lwfree(uf);
58 }
59 
60 uint32_t
61 UF_find (UNIONFIND* uf, uint32_t i)
62 {
63  uint32_t base = i;
64  while (uf->clusters[base] != base) {
65  base = uf->clusters[base];
66  }
67 
68  while (i != base) {
69  uint32_t next = uf->clusters[i];
70  uf->clusters[i] = base;
71  i = next;
72  }
73 
74  return i;
75 }
76 
77 uint32_t
78 UF_size (UNIONFIND* uf, uint32_t i)
79 {
80  return uf->cluster_sizes[UF_find(uf, i)];
81 }
82 
83 void
84 UF_union(UNIONFIND* uf, uint32_t i, uint32_t j)
85 {
86  uint32_t a = UF_find(uf, i);
87  uint32_t b = UF_find(uf, j);
88 
89  if (a == b)
90  {
91  return;
92  }
93 
94  if (uf->cluster_sizes[a] < uf->cluster_sizes[b] ||
95  (uf->cluster_sizes[a] == uf->cluster_sizes[b] && a > b))
96  {
97  uf->clusters[a] = uf->clusters[b];
98  uf->cluster_sizes[b] += uf->cluster_sizes[a];
99  uf->cluster_sizes[a] = 0;
100  }
101  else
102  {
103  uf->clusters[b] = uf->clusters[a];
104  uf->cluster_sizes[a] += uf->cluster_sizes[b];
105  uf->cluster_sizes[b] = 0;
106  }
107 
108  uf->num_clusters--;
109 }
110 
111 uint32_t*
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 }
143 
144 uint32_t*
145 UF_get_collapsed_cluster_ids(UNIONFIND* uf, const char* is_in_cluster)
146 {
147  uint32_t* ordered_components = UF_ordered_by_cluster(uf);
148  uint32_t* new_ids = lwalloc(uf->N * sizeof(uint32_t));
149  uint32_t last_old_id, current_new_id, i;
150  char encountered_cluster = LW_FALSE;
151 
152  current_new_id = 0;
153  for (i = 0; i < uf->N; i++)
154  {
155  uint32_t j = ordered_components[i];
156  if (!is_in_cluster || is_in_cluster[j])
157  {
158  uint32_t current_old_id = UF_find(uf, j);
159  if (!encountered_cluster)
160  {
161  encountered_cluster = LW_TRUE;
162  last_old_id = current_old_id;
163  }
164 
165  if (current_old_id != last_old_id)
166  current_new_id++;
167 
168  new_ids[j] = current_new_id;
169  last_old_id = current_old_id;
170  }
171  }
172 
173  lwfree(ordered_components);
174 
175  return new_ids;
176 }
177 
178 static int
179 cmp_int(const void *a, const void *b)
180 {
181  if (*((uint32_t*) a) > *((uint32_t*) b))
182  {
183  return 1;
184  }
185  else if (*((uint32_t*) a) < *((uint32_t*) b))
186  {
187  return -1;
188  }
189  else
190  {
191  return 0;
192  }
193 }
194 
195 static int
196 cmp_int_ptr(const void *a, const void *b)
197 {
198  int val_cmp = cmp_int(*((uint32_t**) a), *((uint32_t**) b));
199  if (val_cmp != 0)
200  {
201  return val_cmp;
202  }
203  if (a > b)
204  {
205  return 1;
206  }
207  if (a < b)
208  {
209  return -1;
210  }
211  return 0;
212 }
void UF_destroy(UNIONFIND *uf)
Definition: lwunionfind.c:53
void lwfree(void *mem)
Definition: lwutil.c:242
uint32_t * clusters
Definition: lwunionfind.h:33
static int cmp_int_ptr(const void *a, const void *b)
Definition: lwunionfind.c:196
uint32_t * cluster_sizes
Definition: lwunionfind.h:34
static int cmp_int(const void *a, const void *b)
Definition: lwunionfind.c:179
uint32_t N
Definition: lwunionfind.h:36
uint32_t UF_size(UNIONFIND *uf, uint32_t i)
Definition: lwunionfind.c:78
uint32_t UF_find(UNIONFIND *uf, uint32_t i)
Definition: lwunionfind.c:61
#define LW_FALSE
Definition: liblwgeom.h:76
uint32_t * UF_ordered_by_cluster(UNIONFIND *uf)
Definition: lwunionfind.c:112
#define LW_TRUE
Return types for functions with status returns.
Definition: liblwgeom.h:75
uint32_t num_clusters
Definition: lwunionfind.h:35
UNIONFIND * UF_create(uint32_t N)
Definition: lwunionfind.c:34
void UF_union(UNIONFIND *uf, uint32_t i, uint32_t j)
Definition: lwunionfind.c:84
void * lwalloc(size_t size)
Definition: lwutil.c:227
This library is the generic geometry handling section of PostGIS.
uint32_t * UF_get_collapsed_cluster_ids(UNIONFIND *uf, const char *is_in_cluster)
Definition: lwunionfind.c:145