1 // stb_connected_components - v0.95 - public domain connected components on grids
2 // http://github.com/nothings/stb
3 //
4 // Finds connected components on 2D grids for testing reachability between
5 // two points, with fast updates when changing reachability (e.g. on one machine
6 // it was typically 0.2ms w/ 1024x1024 grid). Each grid square must be "open" or
7 // "closed" (traversable or untraversable), and grid squares are only connected
8 // to their orthogonal neighbors, not diagonally.
9 //
10 // In one source file, create the implementation by doing something like this:
11 //
12 // #define STBCC_GRID_COUNT_X_LOG2 10
13 // #define STBCC_GRID_COUNT_Y_LOG2 10
14 // #define STB_CONNECTED_COMPONENTS_IMPLEMENTATION
15 // #include "stb_connected_components.h"
16 //
17 // The above creates an implementation that can run on maps up to 1024x1024.
18 // Map sizes must be a multiple of (1<<(LOG2/2)) on each axis (e.g. 32 if LOG2=10,
19 // 16 if LOG2=8, etc.) (You can just pad your map with untraversable space.)
20 //
21 // MEMORY USAGE
22 //
23 // Uses about 6-7 bytes per grid square (e.g. 7MB for a 1024x1024 grid).
24 // Uses a single worst-case allocation which you pass in.
25 //
26 // PERFORMANCE
27 //
28 // On a core i7-2700K at 3.5 Ghz, for a particular 1024x1024 map (map_03.png):
29 //
30 // Creating map : 44.85 ms
31 // Making one square traversable: 0.27 ms (average over 29,448 calls)
32 // Making one square untraversable: 0.23 ms (average over 30,123 calls)
33 // Reachability query: 0.00001 ms (average over 4,000,000 calls)
34 //
35 // On non-degenerate maps update time is O(N^0.5), but on degenerate maps like
36 // checkerboards or 50% random, update time is O(N^0.75) (~2ms on above machine).
37 //
38 // CHANGELOG
39 //
40 // 0.95 (2016-10-16) Bugfix if multiple clumps in one cluster connect to same clump in another
41 // 0.94 (2016-04-17) Bugfix & optimize worst case (checkerboard & random)
42 // 0.93 (2016-04-16) Reduce memory by 10x for 1Kx1K map; small speedup
43 // 0.92 (2016-04-16) Compute sqrt(N) cluster size by default
44 // 0.91 (2016-04-15) Initial release
45 //
46 // TODO:
47 // - better API documentation
48 // - more comments
49 // - try re-integrating naive algorithm & compare performance
50 // - more optimized batching (current approach still recomputes local clumps many times)
51 // - function for setting a grid of squares at once (just use batching)
52 //
53 // LICENSE
54 //
55 // See end of file for license information.
56 //
57 // ALGORITHM
58 //
59 // The NxN grid map is split into sqrt(N) x sqrt(N) blocks called
60 // "clusters". Each cluster independently computes a set of connected
61 // components within that cluster (ignoring all connectivity out of
62 // that cluster) using a union-find disjoint set forest. This produces a bunch
63 // of locally connected components called "clumps". Each clump is (a) connected
64 // within its cluster, (b) does not directly connect to any other clumps in the
65 // cluster (though it may connect to them by paths that lead outside the cluster,
66 // but those are ignored at this step), and (c) maintains an adjacency list of
67 // all clumps in adjacent clusters that it _is_ connected to. Then a second
68 // union-find disjoint set forest is used to compute connected clumps
69 // globally, across the whole map. Reachability is then computed by
70 // finding which clump each input point belongs to, and checking whether
71 // those clumps are in the same "global" connected component.
72 //
73 // The above data structure can be updated efficiently; on a change
74 // of a single grid square on the map, only one cluster changes its
75 // purely-local state, so only one cluster needs its clumps fully
76 // recomputed. Clumps in adjacent clusters need their adjacency lists
77 // updated: first to remove all references to the old clumps in the
78 // rebuilt cluster, then to add new references to the new clumps. Both
79 // of these operations can use the existing "find which clump each input
80 // point belongs to" query to compute that adjacency information rapidly.
81
82 #ifndef INCLUDE_STB_CONNECTED_COMPONENTS_H
83 #define INCLUDE_STB_CONNECTED_COMPONENTS_H
84
85 #include <stdlib.h>
86
87 typedef struct st_stbcc_grid stbcc_grid;
88
89 #ifdef __cplusplus
90 extern "C" {
91 #endif
92
93 //////////////////////////////////////////////////////////////////////////////////////////
94 //
95 // initialization
96 //
97
98 // you allocate the grid data structure to this size (note that it will be very big!!!)
99 extern size_t stbcc_grid_sizeof(void);
100
101 // initialize the grid, value of map[] is 0 = traversable, non-0 is solid
102 extern void stbcc_init_grid(stbcc_grid *g, unsigned char *map, int w, int h);
103
104
105 //////////////////////////////////////////////////////////////////////////////////////////
106 //
107 // main functionality
108 //
109
110 // update a grid square state, 0 = traversable, non-0 is solid
111 // i can add a batch-update if it's needed
112 extern void stbcc_update_grid(stbcc_grid *g, int x, int y, int solid);
113
114 // query if two grid squares are reachable from each other
115 extern int stbcc_query_grid_node_connection(stbcc_grid *g, int x1, int y1, int x2, int y2);
116
117
118 //////////////////////////////////////////////////////////////////////////////////////////
119 //
120 // bonus functions
121 //
122
123 // wrap multiple stbcc_update_grid calls in these function to compute
124 // multiple updates more efficiently; cannot make queries inside batch
125 extern void stbcc_update_batch_begin(stbcc_grid *g);
126 extern void stbcc_update_batch_end(stbcc_grid *g);
127
128 // query the grid data structure for whether a given square is open or not
129 extern int stbcc_query_grid_open(stbcc_grid *g, int x, int y);
130
131 // get a unique id for the connected component this is in; it's not necessarily
132 // small, you'll need a hash table or something to remap it (or just use
133 extern unsigned int stbcc_get_unique_id(stbcc_grid *g, int x, int y);
134 #define STBCC_NULL_UNIQUE_ID 0xffffffff // returned for closed map squares
135
136 #ifdef __cplusplus
137 }
138 #endif
139
140 #endif // INCLUDE_STB_CONNECTED_COMPONENTS_H
141
142 #ifdef STB_CONNECTED_COMPONENTS_IMPLEMENTATION
143
144 #include <assert.h>
145 #include <string.h> // memset
146
147 #if !defined(STBCC_GRID_COUNT_X_LOG2) || !defined(STBCC_GRID_COUNT_Y_LOG2)
148 #error "You must define STBCC_GRID_COUNT_X_LOG2 and STBCC_GRID_COUNT_Y_LOG2 to define the max grid supported."
149 #endif
150
151 #define STBCC__GRID_COUNT_X (1 << STBCC_GRID_COUNT_X_LOG2)
152 #define STBCC__GRID_COUNT_Y (1 << STBCC_GRID_COUNT_Y_LOG2)
153
154 #define STBCC__MAP_STRIDE (1 << (STBCC_GRID_COUNT_X_LOG2-3))
155
156 #ifndef STBCC_CLUSTER_SIZE_X_LOG2
157 #define STBCC_CLUSTER_SIZE_X_LOG2 (STBCC_GRID_COUNT_X_LOG2/2) // log2(sqrt(2^N)) = 1/2 * log2(2^N)) = 1/2 * N
158 #if STBCC_CLUSTER_SIZE_X_LOG2 > 6
159 #undef STBCC_CLUSTER_SIZE_X_LOG2
160 #define STBCC_CLUSTER_SIZE_X_LOG2 6
161 #endif
162 #endif
163
164 #ifndef STBCC_CLUSTER_SIZE_Y_LOG2
165 #define STBCC_CLUSTER_SIZE_Y_LOG2 (STBCC_GRID_COUNT_Y_LOG2/2)
166 #if STBCC_CLUSTER_SIZE_Y_LOG2 > 6
167 #undef STBCC_CLUSTER_SIZE_Y_LOG2
168 #define STBCC_CLUSTER_SIZE_Y_LOG2 6
169 #endif
170 #endif
171
172 #define STBCC__CLUSTER_SIZE_X (1 << STBCC_CLUSTER_SIZE_X_LOG2)
173 #define STBCC__CLUSTER_SIZE_Y (1 << STBCC_CLUSTER_SIZE_Y_LOG2)
174
175 #define STBCC__CLUSTER_COUNT_X_LOG2 (STBCC_GRID_COUNT_X_LOG2 - STBCC_CLUSTER_SIZE_X_LOG2)
176 #define STBCC__CLUSTER_COUNT_Y_LOG2 (STBCC_GRID_COUNT_Y_LOG2 - STBCC_CLUSTER_SIZE_Y_LOG2)
177
178 #define STBCC__CLUSTER_COUNT_X (1 << STBCC__CLUSTER_COUNT_X_LOG2)
179 #define STBCC__CLUSTER_COUNT_Y (1 << STBCC__CLUSTER_COUNT_Y_LOG2)
180
181 #if STBCC__CLUSTER_SIZE_X >= STBCC__GRID_COUNT_X || STBCC__CLUSTER_SIZE_Y >= STBCC__GRID_COUNT_Y
182 #error "STBCC_CLUSTER_SIZE_X/Y_LOG2 must be smaller than STBCC_GRID_COUNT_X/Y_LOG2"
183 #endif
184
185 // worst case # of clumps per cluster
186 #define STBCC__MAX_CLUMPS_PER_CLUSTER_LOG2 (STBCC_CLUSTER_SIZE_X_LOG2 + STBCC_CLUSTER_SIZE_Y_LOG2-1)
187 #define STBCC__MAX_CLUMPS_PER_CLUSTER (1 << STBCC__MAX_CLUMPS_PER_CLUSTER_LOG2)
188 #define STBCC__MAX_CLUMPS (STBCC__MAX_CLUMPS_PER_CLUSTER * STBCC__CLUSTER_COUNT_X * STBCC__CLUSTER_COUNT_Y)
189 #define STBCC__NULL_CLUMPID STBCC__MAX_CLUMPS_PER_CLUSTER
190
191 #define STBCC__CLUSTER_X_FOR_COORD_X(x) ((x) >> STBCC_CLUSTER_SIZE_X_LOG2)
192 #define STBCC__CLUSTER_Y_FOR_COORD_Y(y) ((y) >> STBCC_CLUSTER_SIZE_Y_LOG2)
193
194 #define STBCC__MAP_BYTE_MASK(x,y) (1 << ((x) & 7))
195 #define STBCC__MAP_BYTE(g,x,y) ((g)->map[y][(x) >> 3])
196 #define STBCC__MAP_OPEN(g,x,y) (STBCC__MAP_BYTE(g,x,y) & STBCC__MAP_BYTE_MASK(x,y))
197
198 typedef unsigned short stbcc__clumpid;
199 typedef unsigned char stbcc__verify_max_clumps[STBCC__MAX_CLUMPS_PER_CLUSTER < (1 << (8*sizeof(stbcc__clumpid))) ? 1 : -1];
200
201 #define STBCC__MAX_EXITS_PER_CLUSTER (STBCC__CLUSTER_SIZE_X + STBCC__CLUSTER_SIZE_Y) // 64 for 32x32
202 #define STBCC__MAX_EXITS_PER_CLUMP (STBCC__CLUSTER_SIZE_X + STBCC__CLUSTER_SIZE_Y) // 64 for 32x32
203 #define STBCC__MAX_EDGE_CLUMPS_PER_CLUSTER (STBCC__MAX_EXITS_PER_CLUMP)
204
205 // 2^19 * 2^6 => 2^25 exits => 2^26 => 64MB for 1024x1024
206
207 // Logic for above on 4x4 grid:
208 //
209 // Many clumps: One clump:
210 // + + + +
211 // +X.X. +XX.X+
212 // .X.X+ .XXX
213 // +X.X. XXX.
214 // .X.X+ +X.XX+
215 // + + + +
216 //
217 // 8 exits either way
218
219 typedef unsigned char stbcc__verify_max_exits[STBCC__MAX_EXITS_PER_CLUMP <= 256];
220
221 typedef struct
222 {
223 unsigned short clump_index:12;
224 signed short cluster_dx:2;
225 signed short cluster_dy:2;
226 } stbcc__relative_clumpid;
227
228 typedef union
229 {
230 struct {
231 unsigned int clump_index:12;
232 unsigned int cluster_x:10;
233 unsigned int cluster_y:10;
234 } f;
235 unsigned int c;
236 } stbcc__global_clumpid;
237
238 // rebuilt cluster 3,4
239
240 // what changes in cluster 2,4
241
242 typedef struct
243 {
244 stbcc__global_clumpid global_label; // 4
245 unsigned char num_adjacent; // 1
246 unsigned char max_adjacent; // 1
247 unsigned char adjacent_clump_list_index; // 1
248 unsigned char reserved;
249 } stbcc__clump; // 8
250
251 #define STBCC__CLUSTER_ADJACENCY_COUNT (STBCC__MAX_EXITS_PER_CLUSTER*2)
252 typedef struct
253 {
254 short num_clumps;
255 unsigned char num_edge_clumps;
256 unsigned char rebuild_adjacency;
257 stbcc__clump clump[STBCC__MAX_CLUMPS_PER_CLUSTER]; // 8 * 2^9 = 4KB
258 stbcc__relative_clumpid adjacency_storage[STBCC__CLUSTER_ADJACENCY_COUNT]; // 256 bytes
259 } stbcc__cluster;
260
261 struct st_stbcc_grid
262 {
263 int w,h,cw,ch;
264 int in_batched_update;
265 //unsigned char cluster_dirty[STBCC__CLUSTER_COUNT_Y][STBCC__CLUSTER_COUNT_X]; // could bitpack, but: 1K x 1K => 1KB
266 unsigned char map[STBCC__GRID_COUNT_Y][STBCC__MAP_STRIDE]; // 1K x 1K => 1K x 128 => 128KB
267 stbcc__clumpid clump_for_node[STBCC__GRID_COUNT_Y][STBCC__GRID_COUNT_X]; // 1K x 1K x 2 = 2MB
268 stbcc__cluster cluster[STBCC__CLUSTER_COUNT_Y][STBCC__CLUSTER_COUNT_X]; // 1K x 4.5KB = 4.5MB
269 };
270
stbcc_query_grid_node_connection(stbcc_grid * g,int x1,int y1,int x2,int y2)271 int stbcc_query_grid_node_connection(stbcc_grid *g, int x1, int y1, int x2, int y2)
272 {
273 stbcc__global_clumpid label1, label2;
274 stbcc__clumpid c1 = g->clump_for_node[y1][x1];
275 stbcc__clumpid c2 = g->clump_for_node[y2][x2];
276 int cx1 = STBCC__CLUSTER_X_FOR_COORD_X(x1);
277 int cy1 = STBCC__CLUSTER_Y_FOR_COORD_Y(y1);
278 int cx2 = STBCC__CLUSTER_X_FOR_COORD_X(x2);
279 int cy2 = STBCC__CLUSTER_Y_FOR_COORD_Y(y2);
280 assert(!g->in_batched_update);
281 if (c1 == STBCC__NULL_CLUMPID || c2 == STBCC__NULL_CLUMPID)
282 return 0;
283 label1 = g->cluster[cy1][cx1].clump[c1].global_label;
284 label2 = g->cluster[cy2][cx2].clump[c2].global_label;
285 if (label1.c == label2.c)
286 return 1;
287 return 0;
288 }
289
stbcc_query_grid_open(stbcc_grid * g,int x,int y)290 int stbcc_query_grid_open(stbcc_grid *g, int x, int y)
291 {
292 return STBCC__MAP_OPEN(g, x, y) != 0;
293 }
294
stbcc_get_unique_id(stbcc_grid * g,int x,int y)295 unsigned int stbcc_get_unique_id(stbcc_grid *g, int x, int y)
296 {
297 stbcc__clumpid c = g->clump_for_node[y][x];
298 int cx = STBCC__CLUSTER_X_FOR_COORD_X(x);
299 int cy = STBCC__CLUSTER_Y_FOR_COORD_Y(y);
300 assert(!g->in_batched_update);
301 if (c == STBCC__NULL_CLUMPID) return STBCC_NULL_UNIQUE_ID;
302 return g->cluster[cy][cx].clump[c].global_label.c;
303 }
304
305 typedef struct
306 {
307 unsigned char x,y;
308 } stbcc__tinypoint;
309
310 typedef struct
311 {
312 stbcc__tinypoint parent[STBCC__CLUSTER_SIZE_Y][STBCC__CLUSTER_SIZE_X]; // 32x32 => 2KB
313 stbcc__clumpid label[STBCC__CLUSTER_SIZE_Y][STBCC__CLUSTER_SIZE_X];
314 } stbcc__cluster_build_info;
315
316 static void stbcc__build_clumps_for_cluster(stbcc_grid *g, int cx, int cy);
317 static void stbcc__remove_connections_to_adjacent_cluster(stbcc_grid *g, int cx, int cy, int dx, int dy);
318 static void stbcc__add_connections_to_adjacent_cluster(stbcc_grid *g, int cx, int cy, int dx, int dy);
319
stbcc__clump_find(stbcc_grid * g,stbcc__global_clumpid n)320 static stbcc__global_clumpid stbcc__clump_find(stbcc_grid *g, stbcc__global_clumpid n)
321 {
322 stbcc__global_clumpid q;
323 stbcc__clump *c = &g->cluster[n.f.cluster_y][n.f.cluster_x].clump[n.f.clump_index];
324
325 if (c->global_label.c == n.c)
326 return n;
327
328 q = stbcc__clump_find(g, c->global_label);
329 c->global_label = q;
330 return q;
331 }
332
333 typedef struct
334 {
335 unsigned int cluster_x;
336 unsigned int cluster_y;
337 unsigned int clump_index;
338 } stbcc__unpacked_clumpid;
339
stbcc__clump_union(stbcc_grid * g,stbcc__unpacked_clumpid m,int x,int y,int idx)340 static void stbcc__clump_union(stbcc_grid *g, stbcc__unpacked_clumpid m, int x, int y, int idx)
341 {
342 stbcc__clump *mc = &g->cluster[m.cluster_y][m.cluster_x].clump[m.clump_index];
343 stbcc__clump *nc = &g->cluster[y][x].clump[idx];
344 stbcc__global_clumpid mp = stbcc__clump_find(g, mc->global_label);
345 stbcc__global_clumpid np = stbcc__clump_find(g, nc->global_label);
346
347 if (mp.c == np.c)
348 return;
349
350 g->cluster[mp.f.cluster_y][mp.f.cluster_x].clump[mp.f.clump_index].global_label = np;
351 }
352
stbcc__build_connected_components_for_clumps(stbcc_grid * g)353 static void stbcc__build_connected_components_for_clumps(stbcc_grid *g)
354 {
355 int i,j,k,h;
356
357 for (j=0; j < STBCC__CLUSTER_COUNT_Y; ++j) {
358 for (i=0; i < STBCC__CLUSTER_COUNT_X; ++i) {
359 stbcc__cluster *cluster = &g->cluster[j][i];
360 for (k=0; k < (int) cluster->num_edge_clumps; ++k) {
361 stbcc__global_clumpid m;
362 m.f.clump_index = k;
363 m.f.cluster_x = i;
364 m.f.cluster_y = j;
365 assert((int) m.f.clump_index == k && (int) m.f.cluster_x == i && (int) m.f.cluster_y == j);
366 cluster->clump[k].global_label = m;
367 }
368 }
369 }
370
371 for (j=0; j < STBCC__CLUSTER_COUNT_Y; ++j) {
372 for (i=0; i < STBCC__CLUSTER_COUNT_X; ++i) {
373 stbcc__cluster *cluster = &g->cluster[j][i];
374 for (k=0; k < (int) cluster->num_edge_clumps; ++k) {
375 stbcc__clump *clump = &cluster->clump[k];
376 stbcc__unpacked_clumpid m;
377 stbcc__relative_clumpid *adj;
378 m.clump_index = k;
379 m.cluster_x = i;
380 m.cluster_y = j;
381 adj = &cluster->adjacency_storage[clump->adjacent_clump_list_index];
382 for (h=0; h < clump->num_adjacent; ++h) {
383 unsigned int clump_index = adj[h].clump_index;
384 unsigned int x = adj[h].cluster_dx + i;
385 unsigned int y = adj[h].cluster_dy + j;
386 stbcc__clump_union(g, m, x, y, clump_index);
387 }
388 }
389 }
390 }
391
392 for (j=0; j < STBCC__CLUSTER_COUNT_Y; ++j) {
393 for (i=0; i < STBCC__CLUSTER_COUNT_X; ++i) {
394 stbcc__cluster *cluster = &g->cluster[j][i];
395 for (k=0; k < (int) cluster->num_edge_clumps; ++k) {
396 stbcc__global_clumpid m;
397 m.f.clump_index = k;
398 m.f.cluster_x = i;
399 m.f.cluster_y = j;
400 stbcc__clump_find(g, m);
401 }
402 }
403 }
404 }
405
stbcc__build_all_connections_for_cluster(stbcc_grid * g,int cx,int cy)406 static void stbcc__build_all_connections_for_cluster(stbcc_grid *g, int cx, int cy)
407 {
408 // in this particular case, we are fully non-incremental. that means we
409 // can discover the correct sizes for the arrays, but requires we build
410 // the data into temporary data structures, or just count the sizes, so
411 // for simplicity we do the latter
412 stbcc__cluster *cluster = &g->cluster[cy][cx];
413 unsigned char connected[STBCC__MAX_EDGE_CLUMPS_PER_CLUSTER][STBCC__MAX_EDGE_CLUMPS_PER_CLUSTER/8]; // 64 x 8 => 1KB
414 unsigned char num_adj[STBCC__MAX_CLUMPS_PER_CLUSTER] = { 0 };
415 int x = cx * STBCC__CLUSTER_SIZE_X;
416 int y = cy * STBCC__CLUSTER_SIZE_Y;
417 int step_x, step_y=0, i, j, k, n, m, dx, dy, total;
418 int extra;
419
420 g->cluster[cy][cx].rebuild_adjacency = 0;
421
422 total = 0;
423 for (m=0; m < 4; ++m) {
424 switch (m) {
425 case 0:
426 dx = 1, dy = 0;
427 step_x = 0, step_y = 1;
428 i = STBCC__CLUSTER_SIZE_X-1;
429 j = 0;
430 n = STBCC__CLUSTER_SIZE_Y;
431 break;
432 case 1:
433 dx = -1, dy = 0;
434 i = 0;
435 j = 0;
436 step_x = 0;
437 step_y = 1;
438 n = STBCC__CLUSTER_SIZE_Y;
439 break;
440 case 2:
441 dy = -1, dx = 0;
442 i = 0;
443 j = 0;
444 step_x = 1;
445 step_y = 0;
446 n = STBCC__CLUSTER_SIZE_X;
447 break;
448 case 3:
449 dy = 1, dx = 0;
450 i = 0;
451 j = STBCC__CLUSTER_SIZE_Y-1;
452 step_x = 1;
453 step_y = 0;
454 n = STBCC__CLUSTER_SIZE_X;
455 break;
456 }
457
458 if (cx+dx < 0 || cx+dx >= g->cw || cy+dy < 0 || cy+dy >= g->ch)
459 continue;
460
461 memset(connected, 0, sizeof(connected));
462 for (k=0; k < n; ++k) {
463 if (STBCC__MAP_OPEN(g, x+i, y+j) && STBCC__MAP_OPEN(g, x+i+dx, y+j+dy)) {
464 stbcc__clumpid src = g->clump_for_node[y+j][x+i];
465 stbcc__clumpid dest = g->clump_for_node[y+j+dy][x+i+dx];
466 if (0 == (connected[src][dest>>3] & (1 << (dest & 7)))) {
467 connected[src][dest>>3] |= 1 << (dest & 7);
468 ++num_adj[src];
469 ++total;
470 }
471 }
472 i += step_x;
473 j += step_y;
474 }
475 }
476
477 assert(total <= STBCC__CLUSTER_ADJACENCY_COUNT);
478
479 // decide how to apportion unused adjacency slots; only clumps that lie
480 // on the edges of the cluster need adjacency slots, so divide them up
481 // evenly between those clumps
482
483 // we want:
484 // extra = (STBCC__CLUSTER_ADJACENCY_COUNT - total) / cluster->num_edge_clumps;
485 // but we efficiently approximate this without a divide, because
486 // ignoring edge-vs-non-edge with 'num_adj[i]*2' was faster than
487 // 'num_adj[i]+extra' with the divide
488 if (total + (cluster->num_edge_clumps<<2) <= STBCC__CLUSTER_ADJACENCY_COUNT)
489 extra = 4;
490 else if (total + (cluster->num_edge_clumps<<1) <= STBCC__CLUSTER_ADJACENCY_COUNT)
491 extra = 2;
492 else if (total + (cluster->num_edge_clumps<<0) <= STBCC__CLUSTER_ADJACENCY_COUNT)
493 extra = 1;
494 else
495 extra = 0;
496
497 total = 0;
498 for (i=0; i < (int) cluster->num_edge_clumps; ++i) {
499 int alloc = num_adj[i]+extra;
500 if (alloc > STBCC__MAX_EXITS_PER_CLUSTER)
501 alloc = STBCC__MAX_EXITS_PER_CLUSTER;
502 assert(total < 256); // must fit in byte
503 cluster->clump[i].adjacent_clump_list_index = (unsigned char) total;
504 cluster->clump[i].max_adjacent = alloc;
505 cluster->clump[i].num_adjacent = 0;
506 total += alloc;
507 }
508 assert(total <= STBCC__CLUSTER_ADJACENCY_COUNT);
509
510 stbcc__add_connections_to_adjacent_cluster(g, cx, cy, -1, 0);
511 stbcc__add_connections_to_adjacent_cluster(g, cx, cy, 1, 0);
512 stbcc__add_connections_to_adjacent_cluster(g, cx, cy, 0,-1);
513 stbcc__add_connections_to_adjacent_cluster(g, cx, cy, 0, 1);
514 // make sure all of the above succeeded.
515 assert(g->cluster[cy][cx].rebuild_adjacency == 0);
516 }
517
stbcc__add_connections_to_adjacent_cluster_with_rebuild(stbcc_grid * g,int cx,int cy,int dx,int dy)518 static void stbcc__add_connections_to_adjacent_cluster_with_rebuild(stbcc_grid *g, int cx, int cy, int dx, int dy)
519 {
520 if (cx >= 0 && cx < g->cw && cy >= 0 && cy < g->ch) {
521 stbcc__add_connections_to_adjacent_cluster(g, cx, cy, dx, dy);
522 if (g->cluster[cy][cx].rebuild_adjacency)
523 stbcc__build_all_connections_for_cluster(g, cx, cy);
524 }
525 }
526
stbcc_update_grid(stbcc_grid * g,int x,int y,int solid)527 void stbcc_update_grid(stbcc_grid *g, int x, int y, int solid)
528 {
529 int cx,cy;
530
531 if (!solid) {
532 if (STBCC__MAP_OPEN(g,x,y))
533 return;
534 } else {
535 if (!STBCC__MAP_OPEN(g,x,y))
536 return;
537 }
538
539 cx = STBCC__CLUSTER_X_FOR_COORD_X(x);
540 cy = STBCC__CLUSTER_Y_FOR_COORD_Y(y);
541
542 stbcc__remove_connections_to_adjacent_cluster(g, cx-1, cy, 1, 0);
543 stbcc__remove_connections_to_adjacent_cluster(g, cx+1, cy, -1, 0);
544 stbcc__remove_connections_to_adjacent_cluster(g, cx, cy-1, 0, 1);
545 stbcc__remove_connections_to_adjacent_cluster(g, cx, cy+1, 0,-1);
546
547 if (!solid)
548 STBCC__MAP_BYTE(g,x,y) |= STBCC__MAP_BYTE_MASK(x,y);
549 else
550 STBCC__MAP_BYTE(g,x,y) &= ~STBCC__MAP_BYTE_MASK(x,y);
551
552 stbcc__build_clumps_for_cluster(g, cx, cy);
553 stbcc__build_all_connections_for_cluster(g, cx, cy);
554
555 stbcc__add_connections_to_adjacent_cluster_with_rebuild(g, cx-1, cy, 1, 0);
556 stbcc__add_connections_to_adjacent_cluster_with_rebuild(g, cx+1, cy, -1, 0);
557 stbcc__add_connections_to_adjacent_cluster_with_rebuild(g, cx, cy-1, 0, 1);
558 stbcc__add_connections_to_adjacent_cluster_with_rebuild(g, cx, cy+1, 0,-1);
559
560 if (!g->in_batched_update)
561 stbcc__build_connected_components_for_clumps(g);
562 #if 0
563 else
564 g->cluster_dirty[cy][cx] = 1;
565 #endif
566 }
567
stbcc_update_batch_begin(stbcc_grid * g)568 void stbcc_update_batch_begin(stbcc_grid *g)
569 {
570 assert(!g->in_batched_update);
571 g->in_batched_update = 1;
572 }
573
stbcc_update_batch_end(stbcc_grid * g)574 void stbcc_update_batch_end(stbcc_grid *g)
575 {
576 assert(g->in_batched_update);
577 g->in_batched_update = 0;
578 stbcc__build_connected_components_for_clumps(g); // @OPTIMIZE: only do this if update was non-empty
579 }
580
stbcc_grid_sizeof(void)581 size_t stbcc_grid_sizeof(void)
582 {
583 return sizeof(stbcc_grid);
584 }
585
stbcc_init_grid(stbcc_grid * g,unsigned char * map,int w,int h)586 void stbcc_init_grid(stbcc_grid *g, unsigned char *map, int w, int h)
587 {
588 int i,j,k;
589 assert(w % STBCC__CLUSTER_SIZE_X == 0);
590 assert(h % STBCC__CLUSTER_SIZE_Y == 0);
591 assert(w % 8 == 0);
592
593 g->w = w;
594 g->h = h;
595 g->cw = w >> STBCC_CLUSTER_SIZE_X_LOG2;
596 g->ch = h >> STBCC_CLUSTER_SIZE_Y_LOG2;
597 g->in_batched_update = 0;
598
599 #if 0
600 for (j=0; j < STBCC__CLUSTER_COUNT_Y; ++j)
601 for (i=0; i < STBCC__CLUSTER_COUNT_X; ++i)
602 g->cluster_dirty[j][i] = 0;
603 #endif
604
605 for (j=0; j < h; ++j) {
606 for (i=0; i < w; i += 8) {
607 unsigned char c = 0;
608 for (k=0; k < 8; ++k)
609 if (map[j*w + (i+k)] == 0)
610 c |= (1 << k);
611 g->map[j][i>>3] = c;
612 }
613 }
614
615 for (j=0; j < g->ch; ++j)
616 for (i=0; i < g->cw; ++i)
617 stbcc__build_clumps_for_cluster(g, i, j);
618
619 for (j=0; j < g->ch; ++j)
620 for (i=0; i < g->cw; ++i)
621 stbcc__build_all_connections_for_cluster(g, i, j);
622
623 stbcc__build_connected_components_for_clumps(g);
624
625 for (j=0; j < g->h; ++j)
626 for (i=0; i < g->w; ++i)
627 assert(g->clump_for_node[j][i] <= STBCC__NULL_CLUMPID);
628 }
629
630
stbcc__add_clump_connection(stbcc_grid * g,int x1,int y1,int x2,int y2)631 static void stbcc__add_clump_connection(stbcc_grid *g, int x1, int y1, int x2, int y2)
632 {
633 stbcc__cluster *cluster;
634 stbcc__clump *clump;
635
636 int cx1 = STBCC__CLUSTER_X_FOR_COORD_X(x1);
637 int cy1 = STBCC__CLUSTER_Y_FOR_COORD_Y(y1);
638 int cx2 = STBCC__CLUSTER_X_FOR_COORD_X(x2);
639 int cy2 = STBCC__CLUSTER_Y_FOR_COORD_Y(y2);
640
641 stbcc__clumpid c1 = g->clump_for_node[y1][x1];
642 stbcc__clumpid c2 = g->clump_for_node[y2][x2];
643
644 stbcc__relative_clumpid rc;
645
646 assert(cx1 != cx2 || cy1 != cy2);
647 assert(abs(cx1-cx2) + abs(cy1-cy2) == 1);
648
649 // add connection to c2 in c1
650
651 rc.clump_index = c2;
652 rc.cluster_dx = x2-x1;
653 rc.cluster_dy = y2-y1;
654
655 cluster = &g->cluster[cy1][cx1];
656 clump = &cluster->clump[c1];
657 assert(clump->num_adjacent <= clump->max_adjacent);
658 if (clump->num_adjacent == clump->max_adjacent)
659 g->cluster[cy1][cx1].rebuild_adjacency = 1;
660 else {
661 stbcc__relative_clumpid *adj = &cluster->adjacency_storage[clump->adjacent_clump_list_index];
662 assert(clump->num_adjacent < STBCC__MAX_EXITS_PER_CLUMP);
663 assert(clump->adjacent_clump_list_index + clump->num_adjacent <= STBCC__CLUSTER_ADJACENCY_COUNT);
664 adj[clump->num_adjacent++] = rc;
665 }
666 }
667
stbcc__remove_clump_connection(stbcc_grid * g,int x1,int y1,int x2,int y2)668 static void stbcc__remove_clump_connection(stbcc_grid *g, int x1, int y1, int x2, int y2)
669 {
670 stbcc__cluster *cluster;
671 stbcc__clump *clump;
672 stbcc__relative_clumpid *adj;
673 int i;
674
675 int cx1 = STBCC__CLUSTER_X_FOR_COORD_X(x1);
676 int cy1 = STBCC__CLUSTER_Y_FOR_COORD_Y(y1);
677 int cx2 = STBCC__CLUSTER_X_FOR_COORD_X(x2);
678 int cy2 = STBCC__CLUSTER_Y_FOR_COORD_Y(y2);
679
680 stbcc__clumpid c1 = g->clump_for_node[y1][x1];
681 stbcc__clumpid c2 = g->clump_for_node[y2][x2];
682
683 stbcc__relative_clumpid rc;
684
685 assert(cx1 != cx2 || cy1 != cy2);
686 assert(abs(cx1-cx2) + abs(cy1-cy2) == 1);
687
688 // add connection to c2 in c1
689
690 rc.clump_index = c2;
691 rc.cluster_dx = x2-x1;
692 rc.cluster_dy = y2-y1;
693
694 cluster = &g->cluster[cy1][cx1];
695 clump = &cluster->clump[c1];
696 adj = &cluster->adjacency_storage[clump->adjacent_clump_list_index];
697
698 for (i=0; i < clump->num_adjacent; ++i)
699 if (rc.clump_index == adj[i].clump_index &&
700 rc.cluster_dx == adj[i].cluster_dx &&
701 rc.cluster_dy == adj[i].cluster_dy)
702 break;
703
704 if (i < clump->num_adjacent)
705 adj[i] = adj[--clump->num_adjacent];
706 else
707 assert(0);
708 }
709
stbcc__add_connections_to_adjacent_cluster(stbcc_grid * g,int cx,int cy,int dx,int dy)710 static void stbcc__add_connections_to_adjacent_cluster(stbcc_grid *g, int cx, int cy, int dx, int dy)
711 {
712 unsigned char connected[STBCC__MAX_EDGE_CLUMPS_PER_CLUSTER][STBCC__MAX_EDGE_CLUMPS_PER_CLUSTER/8] = { 0 };
713 int x = cx * STBCC__CLUSTER_SIZE_X;
714 int y = cy * STBCC__CLUSTER_SIZE_Y;
715 int step_x, step_y=0, i, j, k, n;
716
717 if (cx < 0 || cx >= g->cw || cy < 0 || cy >= g->ch)
718 return;
719
720 if (cx+dx < 0 || cx+dx >= g->cw || cy+dy < 0 || cy+dy >= g->ch)
721 return;
722
723 if (g->cluster[cy][cx].rebuild_adjacency)
724 return;
725
726 assert(abs(dx) + abs(dy) == 1);
727
728 if (dx == 1) {
729 i = STBCC__CLUSTER_SIZE_X-1;
730 j = 0;
731 step_x = 0;
732 step_y = 1;
733 n = STBCC__CLUSTER_SIZE_Y;
734 } else if (dx == -1) {
735 i = 0;
736 j = 0;
737 step_x = 0;
738 step_y = 1;
739 n = STBCC__CLUSTER_SIZE_Y;
740 } else if (dy == -1) {
741 i = 0;
742 j = 0;
743 step_x = 1;
744 step_y = 0;
745 n = STBCC__CLUSTER_SIZE_X;
746 } else if (dy == 1) {
747 i = 0;
748 j = STBCC__CLUSTER_SIZE_Y-1;
749 step_x = 1;
750 step_y = 0;
751 n = STBCC__CLUSTER_SIZE_X;
752 } else {
753 assert(0);
754 }
755
756 for (k=0; k < n; ++k) {
757 if (STBCC__MAP_OPEN(g, x+i, y+j) && STBCC__MAP_OPEN(g, x+i+dx, y+j+dy)) {
758 stbcc__clumpid src = g->clump_for_node[y+j][x+i];
759 stbcc__clumpid dest = g->clump_for_node[y+j+dy][x+i+dx];
760 if (0 == (connected[src][dest>>3] & (1 << (dest & 7)))) {
761 assert((dest>>3) < sizeof(connected));
762 connected[src][dest>>3] |= 1 << (dest & 7);
763 stbcc__add_clump_connection(g, x+i, y+j, x+i+dx, y+j+dy);
764 if (g->cluster[cy][cx].rebuild_adjacency)
765 break;
766 }
767 }
768 i += step_x;
769 j += step_y;
770 }
771 }
772
stbcc__remove_connections_to_adjacent_cluster(stbcc_grid * g,int cx,int cy,int dx,int dy)773 static void stbcc__remove_connections_to_adjacent_cluster(stbcc_grid *g, int cx, int cy, int dx, int dy)
774 {
775 unsigned char disconnected[STBCC__MAX_EDGE_CLUMPS_PER_CLUSTER][STBCC__MAX_EDGE_CLUMPS_PER_CLUSTER/8] = { 0 };
776 int x = cx * STBCC__CLUSTER_SIZE_X;
777 int y = cy * STBCC__CLUSTER_SIZE_Y;
778 int step_x, step_y=0, i, j, k, n;
779
780 if (cx < 0 || cx >= g->cw || cy < 0 || cy >= g->ch)
781 return;
782
783 if (cx+dx < 0 || cx+dx >= g->cw || cy+dy < 0 || cy+dy >= g->ch)
784 return;
785
786 assert(abs(dx) + abs(dy) == 1);
787
788 if (dx == 1) {
789 i = STBCC__CLUSTER_SIZE_X-1;
790 j = 0;
791 step_x = 0;
792 step_y = 1;
793 n = STBCC__CLUSTER_SIZE_Y;
794 } else if (dx == -1) {
795 i = 0;
796 j = 0;
797 step_x = 0;
798 step_y = 1;
799 n = STBCC__CLUSTER_SIZE_Y;
800 } else if (dy == -1) {
801 i = 0;
802 j = 0;
803 step_x = 1;
804 step_y = 0;
805 n = STBCC__CLUSTER_SIZE_X;
806 } else if (dy == 1) {
807 i = 0;
808 j = STBCC__CLUSTER_SIZE_Y-1;
809 step_x = 1;
810 step_y = 0;
811 n = STBCC__CLUSTER_SIZE_X;
812 } else {
813 assert(0);
814 }
815
816 for (k=0; k < n; ++k) {
817 if (STBCC__MAP_OPEN(g, x+i, y+j) && STBCC__MAP_OPEN(g, x+i+dx, y+j+dy)) {
818 stbcc__clumpid src = g->clump_for_node[y+j][x+i];
819 stbcc__clumpid dest = g->clump_for_node[y+j+dy][x+i+dx];
820 if (0 == (disconnected[src][dest>>3] & (1 << (dest & 7)))) {
821 disconnected[src][dest>>3] |= 1 << (dest & 7);
822 stbcc__remove_clump_connection(g, x+i, y+j, x+i+dx, y+j+dy);
823 }
824 }
825 i += step_x;
826 j += step_y;
827 }
828 }
829
stbcc__incluster_find(stbcc__cluster_build_info * cbi,int x,int y)830 static stbcc__tinypoint stbcc__incluster_find(stbcc__cluster_build_info *cbi, int x, int y)
831 {
832 stbcc__tinypoint p,q;
833 p = cbi->parent[y][x];
834 if (p.x == x && p.y == y)
835 return p;
836 q = stbcc__incluster_find(cbi, p.x, p.y);
837 cbi->parent[y][x] = q;
838 return q;
839 }
840
stbcc__incluster_union(stbcc__cluster_build_info * cbi,int x1,int y1,int x2,int y2)841 static void stbcc__incluster_union(stbcc__cluster_build_info *cbi, int x1, int y1, int x2, int y2)
842 {
843 stbcc__tinypoint p = stbcc__incluster_find(cbi, x1,y1);
844 stbcc__tinypoint q = stbcc__incluster_find(cbi, x2,y2);
845
846 if (p.x == q.x && p.y == q.y)
847 return;
848
849 cbi->parent[p.y][p.x] = q;
850 }
851
stbcc__switch_root(stbcc__cluster_build_info * cbi,int x,int y,stbcc__tinypoint p)852 static void stbcc__switch_root(stbcc__cluster_build_info *cbi, int x, int y, stbcc__tinypoint p)
853 {
854 cbi->parent[p.y][p.x].x = x;
855 cbi->parent[p.y][p.x].y = y;
856 cbi->parent[y][x].x = x;
857 cbi->parent[y][x].y = y;
858 }
859
stbcc__build_clumps_for_cluster(stbcc_grid * g,int cx,int cy)860 static void stbcc__build_clumps_for_cluster(stbcc_grid *g, int cx, int cy)
861 {
862 stbcc__cluster *c;
863 stbcc__cluster_build_info cbi;
864 int label=0;
865 int i,j;
866 int x = cx * STBCC__CLUSTER_SIZE_X;
867 int y = cy * STBCC__CLUSTER_SIZE_Y;
868
869 // set initial disjoint set forest state
870 for (j=0; j < STBCC__CLUSTER_SIZE_Y; ++j) {
871 for (i=0; i < STBCC__CLUSTER_SIZE_X; ++i) {
872 cbi.parent[j][i].x = i;
873 cbi.parent[j][i].y = j;
874 }
875 }
876
877 // join all sets that are connected
878 for (j=0; j < STBCC__CLUSTER_SIZE_Y; ++j) {
879 // check down only if not on bottom row
880 if (j < STBCC__CLUSTER_SIZE_Y-1)
881 for (i=0; i < STBCC__CLUSTER_SIZE_X; ++i)
882 if (STBCC__MAP_OPEN(g,x+i,y+j) && STBCC__MAP_OPEN(g,x+i ,y+j+1))
883 stbcc__incluster_union(&cbi, i,j, i,j+1);
884 // check right for everything but rightmost column
885 for (i=0; i < STBCC__CLUSTER_SIZE_X-1; ++i)
886 if (STBCC__MAP_OPEN(g,x+i,y+j) && STBCC__MAP_OPEN(g,x+i+1,y+j ))
887 stbcc__incluster_union(&cbi, i,j, i+1,j);
888 }
889
890 // label all non-empty clumps along edges so that all edge clumps are first
891 // in list; this means in degenerate case we can skip traversing non-edge clumps.
892 // because in the first pass we only label leaders, we swap the leader to the
893 // edge first
894
895 // first put solid labels on all the edges; these will get overwritten if they're open
896 for (j=0; j < STBCC__CLUSTER_SIZE_Y; ++j)
897 cbi.label[j][0] = cbi.label[j][STBCC__CLUSTER_SIZE_X-1] = STBCC__NULL_CLUMPID;
898 for (i=0; i < STBCC__CLUSTER_SIZE_X; ++i)
899 cbi.label[0][i] = cbi.label[STBCC__CLUSTER_SIZE_Y-1][i] = STBCC__NULL_CLUMPID;
900
901 for (j=0; j < STBCC__CLUSTER_SIZE_Y; ++j) {
902 i = 0;
903 if (STBCC__MAP_OPEN(g, x+i, y+j)) {
904 stbcc__tinypoint p = stbcc__incluster_find(&cbi, i,j);
905 if (p.x == i && p.y == j)
906 // if this is the leader, give it a label
907 cbi.label[j][i] = label++;
908 else if (!(p.x == 0 || p.x == STBCC__CLUSTER_SIZE_X-1 || p.y == 0 || p.y == STBCC__CLUSTER_SIZE_Y-1)) {
909 // if leader is in interior, promote this edge node to leader and label
910 stbcc__switch_root(&cbi, i, j, p);
911 cbi.label[j][i] = label++;
912 }
913 // else if leader is on edge, do nothing (it'll get labelled when we reach it)
914 }
915 i = STBCC__CLUSTER_SIZE_X-1;
916 if (STBCC__MAP_OPEN(g, x+i, y+j)) {
917 stbcc__tinypoint p = stbcc__incluster_find(&cbi, i,j);
918 if (p.x == i && p.y == j)
919 cbi.label[j][i] = label++;
920 else if (!(p.x == 0 || p.x == STBCC__CLUSTER_SIZE_X-1 || p.y == 0 || p.y == STBCC__CLUSTER_SIZE_Y-1)) {
921 stbcc__switch_root(&cbi, i, j, p);
922 cbi.label[j][i] = label++;
923 }
924 }
925 }
926
927 for (i=1; i < STBCC__CLUSTER_SIZE_Y-1; ++i) {
928 j = 0;
929 if (STBCC__MAP_OPEN(g, x+i, y+j)) {
930 stbcc__tinypoint p = stbcc__incluster_find(&cbi, i,j);
931 if (p.x == i && p.y == j)
932 cbi.label[j][i] = label++;
933 else if (!(p.x == 0 || p.x == STBCC__CLUSTER_SIZE_X-1 || p.y == 0 || p.y == STBCC__CLUSTER_SIZE_Y-1)) {
934 stbcc__switch_root(&cbi, i, j, p);
935 cbi.label[j][i] = label++;
936 }
937 }
938 j = STBCC__CLUSTER_SIZE_Y-1;
939 if (STBCC__MAP_OPEN(g, x+i, y+j)) {
940 stbcc__tinypoint p = stbcc__incluster_find(&cbi, i,j);
941 if (p.x == i && p.y == j)
942 cbi.label[j][i] = label++;
943 else if (!(p.x == 0 || p.x == STBCC__CLUSTER_SIZE_X-1 || p.y == 0 || p.y == STBCC__CLUSTER_SIZE_Y-1)) {
944 stbcc__switch_root(&cbi, i, j, p);
945 cbi.label[j][i] = label++;
946 }
947 }
948 }
949
950 c = &g->cluster[cy][cx];
951 c->num_edge_clumps = label;
952
953 // label any internal clusters
954 for (j=1; j < STBCC__CLUSTER_SIZE_Y-1; ++j) {
955 for (i=1; i < STBCC__CLUSTER_SIZE_X-1; ++i) {
956 stbcc__tinypoint p = cbi.parent[j][i];
957 if (p.x == i && p.y == j)
958 if (STBCC__MAP_OPEN(g,x+i,y+j))
959 cbi.label[j][i] = label++;
960 else
961 cbi.label[j][i] = STBCC__NULL_CLUMPID;
962 }
963 }
964
965 // label all other nodes
966 for (j=0; j < STBCC__CLUSTER_SIZE_Y; ++j) {
967 for (i=0; i < STBCC__CLUSTER_SIZE_X; ++i) {
968 stbcc__tinypoint p = stbcc__incluster_find(&cbi, i,j);
969 if (p.x != i || p.y != j) {
970 if (STBCC__MAP_OPEN(g,x+i,y+j))
971 cbi.label[j][i] = cbi.label[p.y][p.x];
972 }
973 if (STBCC__MAP_OPEN(g,x+i,y+j))
974 assert(cbi.label[j][i] != STBCC__NULL_CLUMPID);
975 }
976 }
977
978 c->num_clumps = label;
979
980 for (i=0; i < label; ++i) {
981 c->clump[i].num_adjacent = 0;
982 c->clump[i].max_adjacent = 0;
983 }
984
985 for (j=0; j < STBCC__CLUSTER_SIZE_Y; ++j)
986 for (i=0; i < STBCC__CLUSTER_SIZE_X; ++i) {
987 g->clump_for_node[y+j][x+i] = cbi.label[j][i]; // @OPTIMIZE: remove cbi.label entirely
988 assert(g->clump_for_node[y+j][x+i] <= STBCC__NULL_CLUMPID);
989 }
990
991 // set the global label for all interior clumps since they can't have connections,
992 // so we don't have to do this on the global pass (brings from O(N) to O(N^0.75))
993 for (i=(int) c->num_edge_clumps; i < (int) c->num_clumps; ++i) {
994 stbcc__global_clumpid gc;
995 gc.f.cluster_x = cx;
996 gc.f.cluster_y = cy;
997 gc.f.clump_index = i;
998 c->clump[i].global_label = gc;
999 }
1000
1001 c->rebuild_adjacency = 1; // flag that it has no valid adjacency data
1002 }
1003
1004 #endif // STB_CONNECTED_COMPONENTS_IMPLEMENTATION
1005 /*
1006 ------------------------------------------------------------------------------
1007 This software is available under 2 licenses -- choose whichever you prefer.
1008 ------------------------------------------------------------------------------
1009 ALTERNATIVE A - MIT License
1010 Copyright (c) 2017 Sean Barrett
1011 Permission is hereby granted, free of charge, to any person obtaining a copy of
1012 this software and associated documentation files (the "Software"), to deal in
1013 the Software without restriction, including without limitation the rights to
1014 use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
1015 of the Software, and to permit persons to whom the Software is furnished to do
1016 so, subject to the following conditions:
1017 The above copyright notice and this permission notice shall be included in all
1018 copies or substantial portions of the Software.
1019 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
1020 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
1021 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
1022 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
1023 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
1024 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
1025 SOFTWARE.
1026 ------------------------------------------------------------------------------
1027 ALTERNATIVE B - Public Domain (www.unlicense.org)
1028 This is free and unencumbered software released into the public domain.
1029 Anyone is free to copy, modify, publish, use, compile, sell, or distribute this
1030 software, either in source code form or as a compiled binary, for any purpose,
1031 commercial or non-commercial, and by any means.
1032 In jurisdictions that recognize copyright laws, the author or authors of this
1033 software dedicate any and all copyright interest in the software to the public
1034 domain. We make this dedication for the benefit of the public at large and to
1035 the detriment of our heirs and successors. We intend this dedication to be an
1036 overt act of relinquishment in perpetuity of all present and future rights to
1037 this software under copyright law.
1038 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
1039 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
1040 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
1041 AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
1042 ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
1043 WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
1044 ------------------------------------------------------------------------------
1045 */
1046