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