1 // This file is part of Golly.
2 // See docs/License.html for the copyright notice.
3
4 #include "lifealgo.h"
5 #include "util.h" // for lifestatus
6 #include "string.h"
7 using namespace std ;
~lifealgo()8 lifealgo::~lifealgo() {
9 poller = 0 ;
10 maxCellStates = 2 ;
11 }
12 int lifealgo::verbose ;
13 /*
14 * Right now, the base/expo should match the current increment.
15 * We do not check this.
16 */
startrecording(int basearg,int expoarg)17 int lifealgo::startrecording(int basearg, int expoarg) {
18 if (timeline.framecount) {
19 // already have a timeline; skip to its end
20 gotoframe(timeline.framecount-1) ;
21 } else {
22 // use the current frame and increment to start a new timeline
23 void *now = getcurrentstate() ;
24 if (now == 0)
25 return 0 ;
26 timeline.base = basearg ;
27 timeline.expo = expoarg ;
28 timeline.frames.push_back(now) ;
29 timeline.framecount = 1 ;
30 timeline.end = timeline.start = generation ;
31 timeline.inc = increment ;
32 }
33 timeline.next = timeline.end ;
34 timeline.next += timeline.inc ;
35 timeline.recording = 1 ;
36 return timeline.framecount ;
37 }
stoprecording()38 pair<int, int> lifealgo::stoprecording() {
39 timeline.recording = 0 ;
40 timeline.next = 0 ;
41 return make_pair(timeline.base, timeline.expo) ;
42 }
extendtimeline()43 void lifealgo::extendtimeline() {
44 if (timeline.recording && generation == timeline.next) {
45 void *now = getcurrentstate() ;
46 if (now && timeline.framecount < MAX_FRAME_COUNT) {
47 timeline.frames.push_back(now) ;
48 timeline.framecount++ ;
49 timeline.end = timeline.next ;
50 timeline.next += timeline.inc ;
51 }
52 }
53 }
54 /*
55 * Note that this *also* changes inc, so don't call unless this is
56 * what you want to do. It does not update or change the base or
57 * expo if the base != 2, so they can get out of sync.
58 *
59 * Currently this is only used by bgolly, and it will only work
60 * properly if the increment argument is a power of two.
61 */
pruneframes()62 void lifealgo::pruneframes() {
63 if (timeline.framecount > 1) {
64 for (int i=2; i<timeline.framecount; i += 2)
65 timeline.frames[i >> 1] = timeline.frames[i] ;
66 timeline.framecount = (timeline.framecount + 1) >> 1 ;
67 timeline.frames.resize(timeline.framecount) ;
68 timeline.inc += timeline.inc ;
69 timeline.end = timeline.inc ;
70 timeline.end.mul_smallint(timeline.framecount-1) ;
71 timeline.end += timeline.start ;
72 timeline.next = timeline.end ;
73 timeline.next += timeline.inc ;
74 if (timeline.base == 2)
75 timeline.expo++ ;
76 }
77 }
gotoframe(int i)78 int lifealgo::gotoframe(int i) {
79 if (i < 0 || i >= timeline.framecount)
80 return 0 ;
81 setcurrentstate(timeline.frames[i]) ;
82 // AKT: avoid mul_smallint(i) crashing with divide-by-zero if i is 0
83 if (i > 0) {
84 generation = timeline.inc ;
85 generation.mul_smallint(i) ;
86 } else {
87 generation = 0;
88 }
89 generation += timeline.start ;
90 return timeline.framecount ;
91 }
destroytimeline()92 void lifealgo::destroytimeline() {
93 timeline.frames.clear() ;
94 timeline.recording = 0 ;
95 timeline.framecount = 0 ;
96 timeline.end = 0 ;
97 timeline.start = 0 ;
98 timeline.inc = 0 ;
99 timeline.next = 0 ;
100 }
101
102 // -----------------------------------------------------------------------------
103
104 // AKT: the following routines provide support for a bounded universe
105
setgridsize(const char * suffix)106 const char* lifealgo::setgridsize(const char* suffix) {
107 // parse a rule suffix like ":T100,200" and set the various grid parameters;
108 // note that we allow any legal partial suffix -- this lets people type a
109 // suffix into the Set Rule dialog without the algorithm changing to UNKNOWN
110 const char *p = suffix;
111 char topology = 0;
112 gridwd = gridht = 0;
113 hshift = vshift = 0;
114 htwist = vtwist = false;
115 boundedplane = false;
116 sphere = false;
117
118 p++;
119 if (*p == 0) return 0; // treat ":" like ":T0,0"
120 if (*p == 't' || *p == 'T') {
121 // torus or infinite tube
122 topology = 'T';
123 } else if (*p == 'p' || *p == 'P') {
124 boundedplane = true;
125 topology = 'P';
126 } else if (*p == 's' || *p == 'S') {
127 sphere = true;
128 topology = 'S';
129 } else if (*p == 'k' || *p == 'K') {
130 // Klein bottle (either htwist or vtwist should become true)
131 topology = 'K';
132 } else if (*p == 'c' || *p == 'C') {
133 // cross-surface
134 htwist = vtwist = true;
135 topology = 'C';
136 } else {
137 return "Unknown grid topology.";
138 }
139
140 p++;
141 if (*p == 0) return 0; // treat ":<char>" like ":T0,0"
142
143 while ('0' <= *p && *p <= '9') {
144 if (gridwd >= 200000000) {
145 gridwd = 2000000000; // keep width within editable limits
146 } else {
147 gridwd = 10 * gridwd + *p - '0';
148 }
149 p++;
150 }
151 if (*p == '*') {
152 if (topology != 'K') return "Only specify a twist for a Klein bottle.";
153 htwist = true;
154 p++;
155 }
156 if (*p == '+' || *p == '-') {
157 if (topology == 'P') return "Plane can't have a shift.";
158 if (topology == 'S') return "Sphere can't have a shift.";
159 if (topology == 'C') return "Cross-surface can't have a shift.";
160 if (topology == 'K' && !htwist) return "Shift must be on twisted edges.";
161 if (gridwd == 0) return "Can't shift infinite width.";
162 int sign = *p == '+' ? 1 : -1;
163 p++;
164 while ('0' <= *p && *p <= '9') {
165 hshift = 10 * hshift + *p - '0';
166 p++;
167 }
168 if (hshift >= (int)gridwd) hshift = hshift % (int)gridwd;
169 hshift *= sign;
170 }
171 if (*p == ',' && topology != 'S') {
172 p++;
173 } else if (*p) {
174 return "Unexpected stuff after grid width.";
175 }
176
177 // gridwd has been set
178 if ((topology == 'K' || topology == 'C' || topology == 'S') && gridwd == 0) {
179 return "Given topology can't have an infinite width.";
180 }
181
182 if (*p == 0) {
183 // grid height is not specified so set it to grid width;
184 // ie. treat ":T100" like ":T100,100";
185 // this also allows us to have ":S100" rather than ":S100,100"
186 gridht = gridwd;
187 } else {
188 while ('0' <= *p && *p <= '9') {
189 if (gridht >= 200000000) {
190 gridht = 2000000000; // keep height within editable limits
191 } else {
192 gridht = 10 * gridht + *p - '0';
193 }
194 p++;
195 }
196 if (*p == '*') {
197 if (topology != 'K') return "Only specify a twist for a Klein bottle.";
198 if (htwist) return "Klein bottle can't have both horizontal and vertical twists.";
199 vtwist = true;
200 p++;
201 }
202 if (*p == '+' || *p == '-') {
203 if (topology == 'P') return "Plane can't have a shift.";
204 if (topology == 'C') return "Cross-surface can't have a shift.";
205 if (topology == 'K' && !vtwist) return "Shift must be on twisted edges.";
206 if (hshift != 0) return "Can't have both horizontal and vertical shifts.";
207 if (gridht == 0) return "Can't shift infinite height.";
208 int sign = *p == '+' ? 1 : -1;
209 p++;
210 while ('0' <= *p && *p <= '9') {
211 vshift = 10 * vshift + *p - '0';
212 p++;
213 }
214 if (vshift >= (int)gridht) vshift = vshift % (int)gridht;
215 vshift *= sign;
216 }
217 if (*p) return "Unexpected stuff after grid height.";
218 }
219
220 // gridht has been set
221 if ((topology == 'K' || topology == 'C') && gridht == 0) {
222 return "Klein bottle or cross-surface can't have an infinite height.";
223 }
224
225 if (topology == 'K' && !(htwist || vtwist)) {
226 // treat ":K10,20" like ":K10,20*"
227 vtwist = true;
228 }
229
230 if ((hshift != 0 || vshift != 0) && (gridwd == 0 || gridht == 0)) {
231 return "Shifting is not allowed if either grid dimension is unbounded.";
232 }
233
234 // now ok to set grid edges
235 if (gridwd > 0) {
236 gridleft = -int(gridwd) / 2;
237 gridright = int(gridwd) - 1;
238 gridright += gridleft;
239 } else {
240 // play safe and set these to something
241 gridleft = bigint::zero;
242 gridright = bigint::zero;
243 }
244 if (gridht > 0) {
245 gridtop = -int(gridht) / 2;
246 gridbottom = int(gridht) - 1;
247 gridbottom += gridtop;
248 } else {
249 // play safe and set these to something
250 gridtop = bigint::zero;
251 gridbottom = bigint::zero;
252 }
253 return 0;
254 }
255
canonicalsuffix()256 const char* lifealgo::canonicalsuffix() {
257 if (gridwd > 0 || gridht > 0) {
258 static char bounds[64];
259 if (boundedplane) {
260 sprintf(bounds, ":P%u,%u", gridwd, gridht);
261 } else if (sphere) {
262 // sphere requires a square grid (gridwd == gridht)
263 sprintf(bounds, ":S%u", gridwd);
264 } else if (htwist && vtwist) {
265 // cross-surface if both horizontal and vertical edges are twisted
266 sprintf(bounds, ":C%u,%u", gridwd, gridht);
267 } else if (htwist) {
268 // Klein bottle if only horizontal edges are twisted
269 if (hshift != 0 && (gridwd & 1) == 0) {
270 // twist and shift is only possible if gridwd is even and hshift is 1
271 sprintf(bounds, ":K%u*+1,%u", gridwd, gridht);
272 } else {
273 sprintf(bounds, ":K%u*,%u", gridwd, gridht);
274 }
275 } else if (vtwist) {
276 // Klein bottle if only vertical edges are twisted
277 if (vshift != 0 && (gridht & 1) == 0) {
278 // twist and shift is only possible if gridht is even and vshift is 1
279 sprintf(bounds, ":K%u,%u*+1", gridwd, gridht);
280 } else {
281 sprintf(bounds, ":K%u,%u*", gridwd, gridht);
282 }
283 } else if (hshift < 0) {
284 // torus with -ve horizontal shift
285 sprintf(bounds, ":T%u%d,%u", gridwd, hshift, gridht);
286 } else if (hshift > 0) {
287 // torus with +ve horizontal shift
288 sprintf(bounds, ":T%u+%d,%u", gridwd, hshift, gridht);
289 } else if (vshift < 0) {
290 // torus with -ve vertical shift
291 sprintf(bounds, ":T%u,%u%d", gridwd, gridht, vshift);
292 } else if (vshift > 0) {
293 // torus with +ve vertical shift
294 sprintf(bounds, ":T%u,%u+%d", gridwd, gridht, vshift);
295 } else {
296 // unshifted torus, or an infinite tube
297 sprintf(bounds, ":T%u,%u", gridwd, gridht);
298 }
299 return bounds;
300 } else {
301 // unbounded universe
302 return 0;
303 }
304 }
305
JoinTwistedEdges()306 void lifealgo::JoinTwistedEdges()
307 {
308 // set grid edges
309 int gl = gridleft.toint();
310 int gt = gridtop.toint();
311 int gr = gridright.toint();
312 int gb = gridbottom.toint();
313
314 // border edges are 1 cell outside grid edges
315 int bl = gl - 1;
316 int bt = gt - 1;
317 int br = gr + 1;
318 int bb = gb + 1;
319
320 if (htwist && vtwist) {
321 // cross-surface
322 // eg. :C4,3
323 // a l k j i d
324 // l A B C D i
325 // h E F G H e
326 // d I J K L a
327 // i d c b a l
328
329 for (int x = gl; x <= gr; x++) {
330 int twistedx = gr - x + gl;
331 int state = getcell(twistedx, gt);
332 if (state > 0) setcell(x, bb, state);
333 state = getcell(twistedx, gb);
334 if (state > 0) setcell(x, bt, state);
335 }
336
337 for (int y = gt; y <= gb; y++) {
338 int twistedy = gb - y + gt;
339 int state = getcell(gl, twistedy);
340 if (state > 0) setcell(br, y, state);
341 state = getcell(gr, twistedy);
342 if (state > 0) setcell(bl, y, state);
343 }
344
345 // copy grid's corner cells to SAME corners in border
346 // (these cells are topologically different to non-corner cells)
347 setcell(bl, bt, getcell(gl, gt));
348 setcell(br, bt, getcell(gr, gt));
349 setcell(br, bb, getcell(gr, gb));
350 setcell(bl, bb, getcell(gl, gb));
351
352 } else if (htwist) {
353 // Klein bottle with top and bottom edges twisted 180 degrees
354 // eg. :K4*,3
355 // i l k j i l
356 // d A B C D a
357 // h E F G H e
358 // l I J K L i
359 // a d c b a d
360
361 for (int x = gl; x <= gr; x++) {
362 int twistedx = gr - x + gl;
363 int state = getcell(twistedx, gt);
364 if (state > 0) setcell(x, bb, state);
365 state = getcell(twistedx, gb);
366 if (state > 0) setcell(x, bt, state);
367 }
368
369 for (int y = gt; y <= gb; y++) {
370 // join left and right edges with no twist
371 int state = getcell(gl, y);
372 if (state > 0) setcell(br, y, state);
373 state = getcell(gr, y);
374 if (state > 0) setcell(bl, y, state);
375 }
376
377 // do corner cells
378 setcell(bl, bt, getcell(gl, gb));
379 setcell(br, bt, getcell(gr, gb));
380 setcell(bl, bb, getcell(gl, gt));
381 setcell(br, bb, getcell(gr, gt));
382
383 } else { // vtwist
384 // Klein bottle with left and right edges twisted 180 degrees
385 // eg. :K4,3*
386 // d i j k l a
387 // l A B C D i
388 // h E F G H e
389 // d I J K L a
390 // l a b c d i
391
392 for (int x = gl; x <= gr; x++) {
393 // join top and bottom edges with no twist
394 int state = getcell(x, gt);
395 if (state > 0) setcell(x, bb, state);
396 state = getcell(x, gb);
397 if (state > 0) setcell(x, bt, state);
398 }
399
400 for (int y = gt; y <= gb; y++) {
401 int twistedy = gb - y + gt;
402 int state = getcell(gl, twistedy);
403 if (state > 0) setcell(br, y, state);
404 state = getcell(gr, twistedy);
405 if (state > 0) setcell(bl, y, state);
406 }
407
408 // do corner cells
409 setcell(bl, bt, getcell(gr, gt));
410 setcell(br, bt, getcell(gl, gt));
411 setcell(bl, bb, getcell(gr, gb));
412 setcell(br, bb, getcell(gl, gb));
413 }
414 }
415
JoinTwistedAndShiftedEdges()416 void lifealgo::JoinTwistedAndShiftedEdges()
417 {
418 // set grid edges
419 int gl = gridleft.toint();
420 int gt = gridtop.toint();
421 int gr = gridright.toint();
422 int gb = gridbottom.toint();
423
424 // border edges are 1 cell outside grid edges
425 int bl = gl - 1;
426 int bt = gt - 1;
427 int br = gr + 1;
428 int bb = gb + 1;
429
430 if (hshift != 0) {
431 // Klein bottle with shift by 1 on twisted horizontal edge (with even number of cells)
432 // eg. :K4*+1,3
433 // j i l k j i
434 // d A B C D a
435 // h E F G H e
436 // l I J K L i
437 // b a d c b a
438
439 int state, twistedx, shiftedx;
440
441 for (int x = gl; x <= gr; x++) {
442 // join top and bottom edges with a twist and then shift by 1
443 twistedx = gr - x + gl;
444 shiftedx = twistedx - 1; if (shiftedx < gl) shiftedx = gr;
445 state = getcell(shiftedx, gb);
446 if (state > 0) setcell(x, bt, state);
447
448 state = getcell(shiftedx, gt);
449 if (state > 0) setcell(x, bb, state);
450 }
451
452 for (int y = gt; y <= gb; y++) {
453 // join left and right edges with no twist or shift
454 state = getcell(gl, y);
455 if (state > 0) setcell(br, y, state);
456 state = getcell(gr, y);
457 if (state > 0) setcell(bl, y, state);
458 }
459
460 // do corner cells
461 shiftedx = gl - 1; if (shiftedx < gl) shiftedx = gr;
462 setcell(bl, bt, getcell(shiftedx, gb));
463 setcell(bl, bb, getcell(shiftedx, gt));
464 shiftedx = gr - 1; if (shiftedx < gl) shiftedx = gr;
465 setcell(br, bt, getcell(shiftedx, gb));
466 setcell(br, bb, getcell(shiftedx, gt));
467
468 } else { // vshift != 0
469 // Klein bottle with shift by 1 on twisted vertical edge (with even number of cells)
470 // eg. :K3,4*+1
471 // f j k l d
472 // c A B C a
473 // l D E F j
474 // i G H I g
475 // f J K L d
476 // c a b c a
477
478 int state, twistedy, shiftedy;
479
480 for (int x = gl; x <= gr; x++) {
481 // join top and bottom edges with no twist or shift
482 state = getcell(x, gt);
483 if (state > 0) setcell(x, bb, state);
484 state = getcell(x, gb);
485 if (state > 0) setcell(x, bt, state);
486 }
487
488 for (int y = gt; y <= gb; y++) {
489 // join left and right edges with a twist and then shift by 1
490 twistedy = gb - y + gt;
491 shiftedy = twistedy - 1; if (shiftedy < gt) shiftedy = gb;
492 state = getcell(gr, shiftedy);
493 if (state > 0) setcell(bl, y, state);
494
495 state = getcell(gl, shiftedy);
496 if (state > 0) setcell(br, y, state);
497 }
498
499 // do corner cells
500 shiftedy = gt - 1; if (shiftedy < gt) shiftedy = gb;
501 setcell(bl, bt, getcell(gr, shiftedy));
502 setcell(br, bt, getcell(gl, shiftedy));
503 shiftedy = gb - 1; if (shiftedy < gt) shiftedy = gb;
504 setcell(bl, bb, getcell(gr, shiftedy));
505 setcell(br, bb, getcell(gl, shiftedy));
506 }
507 }
508
JoinShiftedEdges()509 void lifealgo::JoinShiftedEdges()
510 {
511 // set grid edges
512 int gl = gridleft.toint();
513 int gt = gridtop.toint();
514 int gr = gridright.toint();
515 int gb = gridbottom.toint();
516
517 // border edges are 1 cell outside grid edges
518 int bl = gl - 1;
519 int bt = gt - 1;
520 int br = gr + 1;
521 int bb = gb + 1;
522
523 if (hshift != 0) {
524 // torus with horizontal shift
525 // eg. :T4+1,3
526 // k l i j k l
527 // d A B C D a
528 // h E F G H e
529 // l I J K L i
530 // a b c d a b
531
532 int state, shiftedx;
533
534 for (int x = gl; x <= gr; x++) {
535 // join top and bottom edges with a horizontal shift
536 shiftedx = x - hshift;
537 if (shiftedx < gl) shiftedx += gridwd; else if (shiftedx > gr) shiftedx -= gridwd;
538 state = getcell(shiftedx, gb);
539 if (state > 0) setcell(x, bt, state);
540
541 shiftedx = x + hshift;
542 if (shiftedx < gl) shiftedx += gridwd; else if (shiftedx > gr) shiftedx -= gridwd;
543 state = getcell(shiftedx, gt);
544 if (state > 0) setcell(x, bb, state);
545 }
546
547 for (int y = gt; y <= gb; y++) {
548 // join left and right edges with no shift
549 state = getcell(gl, y);
550 if (state > 0) setcell(br, y, state);
551
552 state = getcell(gr, y);
553 if (state > 0) setcell(bl, y, state);
554 }
555
556 // do corner cells
557 shiftedx = gr - hshift;
558 if (shiftedx < gl) shiftedx += gridwd; else if (shiftedx > gr) shiftedx -= gridwd;
559 setcell(bl, bt, getcell(shiftedx, gb));
560 shiftedx = gl - hshift;
561 if (shiftedx < gl) shiftedx += gridwd; else if (shiftedx > gr) shiftedx -= gridwd;
562 setcell(br, bt, getcell(shiftedx, gb));
563 shiftedx = gr + hshift;
564 if (shiftedx < gl) shiftedx += gridwd; else if (shiftedx > gr) shiftedx -= gridwd;
565 setcell(bl, bb, getcell(shiftedx, gt));
566 shiftedx = gl + hshift;
567 if (shiftedx < gl) shiftedx += gridwd; else if (shiftedx > gr) shiftedx -= gridwd;
568 setcell(br, bb, getcell(shiftedx, gt));
569
570 } else { // vshift != 0
571 // torus with vertical shift
572 // eg. :T4,3+1
573 // h i j k l a
574 // l A B C D e
575 // d E F G H i
576 // h I J K L a
577 // l a b c d e
578
579 int state, shiftedy;
580
581 for (int x = gl; x <= gr; x++) {
582 // join top and bottom edges with no shift
583 state = getcell(x, gt);
584 if (state > 0) setcell(x, bb, state);
585
586 state = getcell(x, gb);
587 if (state > 0) setcell(x, bt, state);
588 }
589
590 for (int y = gt; y <= gb; y++) {
591 // join left and right edges with a vertical shift
592 shiftedy = y - vshift;
593 if (shiftedy < gt) shiftedy += gridht; else if (shiftedy > gb) shiftedy -= gridht;
594 state = getcell(gr, shiftedy);
595 if (state > 0) setcell(bl, y, state);
596
597 shiftedy = y + vshift;
598 if (shiftedy < gt) shiftedy += gridht; else if (shiftedy > gb) shiftedy -= gridht;
599 state = getcell(gl, shiftedy);
600 if (state > 0) setcell(br, y, state);
601 }
602
603 // do corner cells
604 shiftedy = gb - vshift;
605 if (shiftedy < gt) shiftedy += gridht; else if (shiftedy > gb) shiftedy -= gridht;
606 setcell(bl, bt, getcell(gr, shiftedy));
607 shiftedy = gb + vshift;
608 if (shiftedy < gt) shiftedy += gridht; else if (shiftedy > gb) shiftedy -= gridht;
609 setcell(br, bt, getcell(gl, shiftedy));
610 shiftedy = gt - vshift;
611 if (shiftedy < gt) shiftedy += gridht; else if (shiftedy > gb) shiftedy -= gridht;
612 setcell(bl, bb, getcell(gr, shiftedy));
613 shiftedy = gt + vshift;
614 if (shiftedy < gt) shiftedy += gridht; else if (shiftedy > gb) shiftedy -= gridht;
615 setcell(br, bb, getcell(gl, shiftedy));
616 }
617 }
618
JoinAdjacentEdges(int pt,int pl,int pb,int pr)619 void lifealgo::JoinAdjacentEdges(int pt, int pl, int pb, int pr) // pattern edges
620 {
621 // set grid edges
622 int gl = gridleft.toint();
623 int gt = gridtop.toint();
624 int gr = gridright.toint();
625 int gb = gridbottom.toint();
626
627 // border edges are 1 cell outside grid edges
628 int bl = gl - 1;
629 int bt = gt - 1;
630 int br = gr + 1;
631 int bb = gb + 1;
632
633 // sphere
634 // eg. :S3
635 // a a d g c
636 // a A B C g
637 // b D E F h
638 // c G H I i
639 // g c f i i
640
641 // copy live cells in top edge to left border
642 for (int x = pl; x <= pr; x++) {
643 int state;
644 int skip = nextcell(x, gt, state);
645 if (skip < 0) break;
646 x += skip;
647 if (state > 0) setcell(bl, gt + (x - gl), state);
648 }
649
650 // copy live cells in left edge to top border
651 for (int y = pt; y <= pb; y++) {
652 // no point using nextcell() here -- edge is only 1 cell wide
653 int state = getcell(gl, y);
654 if (state > 0) setcell(gl + (y - gt), bt, state);
655 }
656
657 // copy live cells in bottom edge to right border
658 for (int x = pl; x <= pr; x++) {
659 int state;
660 int skip = nextcell(x, gb, state);
661 if (skip < 0) break;
662 x += skip;
663 if (state > 0) setcell(br, gt + (x - gl), state);
664 }
665
666 // copy live cells in right edge to bottom border
667 for (int y = pt; y <= pb; y++) {
668 // no point using nextcell() here -- edge is only 1 cell wide
669 int state = getcell(gr, y);
670 if (state > 0) setcell(gl + (y - gt), bb, state);
671 }
672
673 // copy grid's corner cells to SAME corners in border
674 setcell(bl, bt, getcell(gl, gt));
675 setcell(br, bt, getcell(gr, gt));
676 setcell(br, bb, getcell(gr, gb));
677 setcell(bl, bb, getcell(gl, gb));
678 }
679
JoinEdges(int pt,int pl,int pb,int pr)680 void lifealgo::JoinEdges(int pt, int pl, int pb, int pr) // pattern edges
681 {
682 // set grid edges
683 int gl = gridleft.toint();
684 int gt = gridtop.toint();
685 int gr = gridright.toint();
686 int gb = gridbottom.toint();
687
688 // border edges are 1 cell outside grid edges
689 int bl = gl - 1;
690 int bt = gt - 1;
691 int br = gr + 1;
692 int bb = gb + 1;
693
694 if (gridht > 0) {
695 // copy live cells in top edge to bottom border
696 for (int x = pl; x <= pr; x++) {
697 int state;
698 int skip = nextcell(x, gt, state);
699 if (skip < 0) break;
700 x += skip;
701 if (state > 0) setcell(x, bb, state);
702 }
703 // copy live cells in bottom edge to top border
704 for (int x = pl; x <= pr; x++) {
705 int state;
706 int skip = nextcell(x, gb, state);
707 if (skip < 0) break;
708 x += skip;
709 if (state > 0) setcell(x, bt, state);
710 }
711 }
712
713 if (gridwd > 0) {
714 // copy live cells in left edge to right border
715 for (int y = pt; y <= pb; y++) {
716 // no point using nextcell() here -- edge is only 1 cell wide
717 int state = getcell(gl, y);
718 if (state > 0) setcell(br, y, state);
719 }
720 // copy live cells in right edge to left border
721 for (int y = pt; y <= pb; y++) {
722 // no point using nextcell() here -- edge is only 1 cell wide
723 int state = getcell(gr, y);
724 if (state > 0) setcell(bl, y, state);
725 }
726 }
727
728 if (gridwd > 0 && gridht > 0) {
729 // copy grid's corner cells to opposite corners in border
730 setcell(bl, bt, getcell(gr, gb));
731 setcell(br, bt, getcell(gl, gb));
732 setcell(br, bb, getcell(gl, gt));
733 setcell(bl, bb, getcell(gr, gt));
734 }
735 }
736
CreateBorderCells()737 bool lifealgo::CreateBorderCells()
738 {
739 // no need to do anything if there is no pattern or if the grid is a bounded plane
740 if (isEmpty() || boundedplane) return true;
741
742 bigint top, left, bottom, right;
743 findedges(&top, &left, &bottom, &right);
744
745 // no need to do anything if pattern is completely inside grid edges
746 if ( (gridwd == 0 || (gridleft < left && gridright > right)) &&
747 (gridht == 0 || (gridtop < top && gridbottom > bottom)) ) {
748 return true;
749 }
750
751 // if grid has infinite width or height then pattern might be too big to use setcell/getcell
752 if ( (gridwd == 0 || gridht == 0) &&
753 (top < bigint::min_coord || left < bigint::min_coord ||
754 bottom > bigint::max_coord || right > bigint::max_coord) ) {
755 lifestatus("Pattern is beyond editing limit!");
756 // return false so caller can exit step() loop
757 return false;
758 }
759
760 if (sphere) {
761 // to get a sphere we join top edge with left edge, and right edge with bottom edge;
762 // note that grid must be square (gridwd == gridht)
763 int pl = left.toint();
764 int pt = top.toint();
765 int pr = right.toint();
766 int pb = bottom.toint();
767 JoinAdjacentEdges(pt, pl, pb, pr);
768
769 } else if (htwist || vtwist) {
770 // Klein bottle or cross-surface
771 if ( (htwist && hshift != 0 && (gridwd & 1) == 0) ||
772 (vtwist && vshift != 0 && (gridht & 1) == 0) ) {
773 // Klein bottle with shift is only possible if the shift is on the
774 // twisted edge and that edge has an even number of cells
775 JoinTwistedAndShiftedEdges();
776 } else {
777 JoinTwistedEdges();
778 }
779
780 } else if (hshift != 0 || vshift != 0) {
781 // torus with horizontal or vertical shift
782 JoinShiftedEdges();
783
784 } else {
785 // unshifted torus or infinite tube
786 int pl = left.toint();
787 int pt = top.toint();
788 int pr = right.toint();
789 int pb = bottom.toint();
790 JoinEdges(pt, pl, pb, pr);
791 }
792
793 endofpattern();
794 return true;
795 }
796
ClearRect(int top,int left,int bottom,int right)797 void lifealgo::ClearRect(int top, int left, int bottom, int right)
798 {
799 int cx, cy, v;
800 for ( cy = top; cy <= bottom; cy++ ) {
801 for ( cx = left; cx <= right; cx++ ) {
802 int skip = nextcell(cx, cy, v);
803 if (skip + cx > right)
804 skip = -1; // pretend we found no more live cells
805 if (skip >= 0) {
806 // found next live cell so delete it
807 cx += skip;
808 setcell(cx, cy, 0);
809 } else {
810 cx = right + 1; // done this row
811 }
812 }
813 }
814 }
815
DeleteBorderCells()816 bool lifealgo::DeleteBorderCells()
817 {
818 // no need to do anything if there is no pattern
819 if (isEmpty()) return true;
820
821 // need to find pattern edges because pattern may have expanded beyond grid
822 // (typically by 2 cells, but could be more if rule allows births in empty space)
823 bigint top, left, bottom, right;
824 findedges(&top, &left, &bottom, &right);
825
826 // no need to do anything if grid encloses entire pattern
827 if ( (gridwd == 0 || (gridleft <= left && gridright >= right)) &&
828 (gridht == 0 || (gridtop <= top && gridbottom >= bottom)) ) {
829 return true;
830 }
831
832 // set pattern edges
833 int pl = left.toint();
834 int pt = top.toint();
835 int pr = right.toint();
836 int pb = bottom.toint();
837
838 // set grid edges
839 int gl = gridleft.toint();
840 int gt = gridtop.toint();
841 int gr = gridright.toint();
842 int gb = gridbottom.toint();
843
844 if (gridht > 0 && pt < gt) {
845 // delete live cells above grid
846 ClearRect(pt, pl, gt-1, pr);
847 pt = gt; // reduce size of rect below
848 }
849
850 if (gridht > 0 && pb > gb) {
851 // delete live cells below grid
852 ClearRect(gb+1, pl, pb, pr);
853 pb = gb; // reduce size of rect below
854 }
855
856 if (gridwd > 0 && pl < gl) {
857 // delete live cells left of grid
858 ClearRect(pt, pl, pb, gl-1);
859 }
860
861 if (gridwd > 0 && pr > gr) {
862 // delete live cells right of grid
863 ClearRect(pt, gr+1, pb, pr);
864 }
865
866 endofpattern();
867
868 // do this test AFTER clearing border
869 if ( top < bigint::min_coord || left < bigint::min_coord ||
870 bottom > bigint::max_coord || right > bigint::max_coord ) {
871 lifestatus("Pattern exceeded editing limit!");
872 // return false so caller can exit step() loop
873 return false;
874 }
875
876 return true;
877 }
878
getcells(unsigned char * buf,int x,int y,int w,int h)879 void lifealgo::getcells(unsigned char *buf, int x, int y, int w, int h) {
880 viewport vp(w, h) ;
881 vp.setpositionmag(x+(w>>1), y+(h>>1), 0) ;
882 staterender hsr(buf, w, h) ;
883 memset(buf, 0, w*h) ;
884 draw(vp, hsr) ;
885 }
886
887 // -----------------------------------------------------------------------------
888
889 int staticAlgoInfo::nextAlgoId = 0 ;
890 staticAlgoInfo *staticAlgoInfo::head = 0 ;
staticAlgoInfo()891 staticAlgoInfo::staticAlgoInfo() {
892 id = nextAlgoId++ ;
893 next = head ;
894 head = this ;
895 // init default icon data
896 defxpm7x7 = NULL;
897 defxpm15x15 = NULL;
898 defxpm31x31 = NULL;
899 }
byName(const char * s)900 staticAlgoInfo *staticAlgoInfo::byName(const char *s) {
901 for (staticAlgoInfo *i=head; i; i=i->next)
902 if (strcmp(i->algoName, s) == 0)
903 return i ;
904 return 0 ;
905 }
nameToIndex(const char * s)906 int staticAlgoInfo::nameToIndex(const char *s) {
907 staticAlgoInfo *r = byName(s) ;
908 if (r == 0)
909 return -1 ;
910 return r->id ;
911 }
tick()912 staticAlgoInfo &staticAlgoInfo::tick() {
913 return *(new staticAlgoInfo()) ;
914 }
915