PostGIS  2.2.8dev-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  * Copyright 2015 Daniel Baston <dbaston@gmail.com>
7  *
8  * This is free software; you can redistribute and/or modify it under
9  * the terms of the GNU General Public Licence. See the COPYING file.
10  *
11  **********************************************************************/
12 
13 #include "liblwgeom.h"
14 #include "lwunionfind.h"
15 #include <string.h>
16 
17 static int cmp_int(const void *a, const void *b);
18 static int cmp_int_ptr(const void *a, const void *b);
19 
20 UNIONFIND*
21 UF_create(uint32_t N)
22 {
23  size_t i;
24  UNIONFIND* uf = lwalloc(sizeof(UNIONFIND));
25  uf->N = N;
26  uf->num_clusters = N;
27  uf->clusters = lwalloc(N * sizeof(uint32_t));
28  uf->cluster_sizes = lwalloc(N * sizeof(uint32_t));
29 
30  for (i = 0; i < N; i++)
31  {
32  uf->clusters[i] = i;
33  uf->cluster_sizes[i] = 1;
34  }
35 
36  return uf;
37 }
38 
39 void
41 {
42  lwfree(uf->clusters);
43  lwfree(uf->cluster_sizes);
44  lwfree(uf);
45 }
46 
47 uint32_t
48 UF_find (UNIONFIND* uf, uint32_t i)
49 {
50  uint32_t base = i;
51  while (uf->clusters[base] != base) {
52  base = uf->clusters[base];
53  }
54 
55  while (i != base) {
56  uint32_t next = uf->clusters[i];
57  uf->clusters[i] = base;
58  i = next;
59  }
60 
61  return i;
62 }
63 
64 void
65 UF_union(UNIONFIND* uf, uint32_t i, uint32_t j)
66 {
67  uint32_t a = UF_find(uf, i);
68  uint32_t b = UF_find(uf, j);
69 
70  if (a == b)
71  {
72  return;
73  }
74 
75  if (uf->cluster_sizes[a] < uf->cluster_sizes[b] ||
76  (uf->cluster_sizes[a] == uf->cluster_sizes[b] && a > b))
77  {
78  uf->clusters[a] = uf->clusters[b];
79  uf->cluster_sizes[b] += uf->cluster_sizes[a];
80  uf->cluster_sizes[a] = 0;
81  }
82  else
83  {
84  uf->clusters[b] = uf->clusters[a];
85  uf->cluster_sizes[a] += uf->cluster_sizes[b];
86  uf->cluster_sizes[b] = 0;
87  }
88 
89  uf->num_clusters--;
90 }
91 
92 uint32_t*
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 }
124 static int
125 cmp_int(const void *a, const void *b)
126 {
127  if (*((uint32_t*) a) > *((uint32_t*) b))
128  {
129  return 1;
130  }
131  else if (*((uint32_t*) a) < *((uint32_t*) b))
132  {
133  return -1;
134  }
135  else
136  {
137  return 0;
138  }
139 }
140 
141 static int
142 cmp_int_ptr(const void *a, const void *b)
143 {
144  int val_cmp = cmp_int(*((uint32_t**) a), *((uint32_t**) b));
145  if (val_cmp != 0)
146  {
147  return val_cmp;
148  }
149  if (a > b)
150  {
151  return 1;
152  }
153  if (a < b)
154  {
155  return -1;
156  }
157  return 0;
158 }
void UF_destroy(UNIONFIND *uf)
Definition: lwunionfind.c:40
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 * cluster_sizes
Definition: lwunionfind.h:21
static int cmp_int(const void *a, const void *b)
Definition: lwunionfind.c:125
uint32_t N
Definition: lwunionfind.h:23
uint32_t UF_find(UNIONFIND *uf, uint32_t i)
Definition: lwunionfind.c:48
uint32_t * UF_ordered_by_cluster(UNIONFIND *uf)
Definition: lwunionfind.c:93
uint32_t num_clusters
Definition: lwunionfind.h:22
UNIONFIND * UF_create(uint32_t N)
Definition: lwunionfind.c:21
void UF_union(UNIONFIND *uf, uint32_t i, uint32_t j)
Definition: lwunionfind.c:65
void * lwalloc(size_t size)
Definition: lwutil.c:199
This library is the generic geometry handling section of PostGIS.