/* -*- Mode: C; tab-width: 4 -*- */
/* life --- Conway's game of Life */

#if !defined( lint ) && !defined( SABER )
static const char sccsid[] = "@(#)life.c	4.07 98/01/18 xlockmore";

#endif

/*-
 * Copyright (c) 1991 by Patrick J. Naughton.
 * Copyright (c) 1997 by David Bagley.
 *
 * Permission to use, copy, modify, and distribute this software and its
 * documentation for any purpose and without fee is hereby granted,
 * provided that the above copyright notice appear in all copies and that
 * both that copyright notice and this permission notice appear in
 * supporting documentation.
 *
 * This file is provided AS IS with no warranties of any kind.  The author
 * shall have no liability with respect to the infringement of copyrights,
 * trade secrets or any patents by this file or any part thereof.  In no
 * event will the author be liable for any lost revenue or profits or
 * other special, indirect and consequential damages.
 *
 * Revision History:
 * 08-Dec-97: Paul Callahan's B2a/S2b34 rule added.  Described on the news
 *            site for cellular-automata.  <ppc997@aber.ac.uk>
 *            http://www.cs.jhu.edu/~callahan/lifepage.html
 *            http://www.cs.jhu.edu/~callahan/hexrule.txt
 *            B2a/S2b34: Birth of x if 2a,
 *                       Survival of x if 2b, 3, or 4 neighbors
 *                       Assume symmetry.
 *                       (2a, 2b, 2c: 2o, 2m, 2p original notation)
 *                  O O            O .            O .
 *            2a:  . x .     2b:  . x O     2c:  . x .
 *                  . .            . .            . O
 *            Also Bob Andreen's rule (my own notation for consistency)
 *            B2a3a4b/S2a2b4a (original notation: 234'B/22'4S)
 *            <andreen@msmc.edu>
 *                  O O            O O            O . 
 *            3a:  . x O     3b:  . x .     3c:  . x O
 *                  . .            . O            O .
 * 
 *                  O O            O O            O O 
 *            4a:  . x O     4b:  . x O     4c:  . x .
 *                  . O            O .            O O
 *            Some other rules
 *            B2a3b3c5/S12b2c3a4b4c6
 *            B23a3c4b4c6/S12b2c3c4a56
 *            B2a2c6/S13b
 * 27-Oct-97: xpm and ras capability added.
 * 04-Jun-97: Removed old algorithm, now use wator's.  I could not
 *            understand it and had trouble adding more features.
 *            New algorithm is more efficient iff there lots of blank areas
 * 10-May-97: Compatible with xscreensaver
 * 07-May-97: life neighbor option.  Still have to fix -neighbor 3
 * 07-Jan-95: life now has a random soup pattern.
 * 07-Dec-94: life now has new organisms.  They are now better centered.
 *            Some of the nonperiodic forms were removed. New life forms
 *            were taken from xlife (an AMAZING collection of life forms).
 *            life's gliders now come from the edge of the screen except
 *            when generated by a life form.
 * 23-Nov-94: Bug fix for different iconified window sizes
 * 21-Jul-94: Took out bzero & bcopy since memset & memcpy is more portable
 * 10-Jun-94: Changed name of function 'kill', which is a libc function on
 *            many systems from Victor Langeveld <vic@mbfys.kun.nl>
 * Changes in original xlock
 * 24-May-91: Added wraparound code from johnson@bugs.comm.mot.com.
 *        Made old cells stay blue.
 *        Made batchcount control the number of generations until restart.
 * 29-Jul-90: support for multiple screens.
 * 07-Feb-90: remove bogus semi-colon after #include line.
 * 15-Dec-89: Fix for proper skipping of {White,Black}Pixel() in colors.
 * 08-Oct-89: Moved seconds() to an extern.
 * 20-Sep-89: Written, life algorithm courtesy of Jim Graham <flar@sun.com>
 */

/*-
  Grid     Number of Neigbors
  ----     ------------------
  Square   4 or 8
  Hexagon  6
  Triangle 3, 9, or 12

  Conway's Life: -neighbors 8 -rule S23/B3
  Other things to try:
    -neighbors 4 -rule S234/B2
    -neighbors 6 -rule S23/B3
    -neighbors 3 -rule S12/B23
    -neighbors 6 -rule S2b34/B2a     <CALLAHAN>
    -neighbors 6 -rule S2a2b4a/B2b3a4b  <ANDREEN>
*/

#ifdef STANDALONE
#define PROGCLASS "Life"
#define HACK_INIT init_life
#define HACK_DRAW draw_life
#define life_opts xlockmore_opts
#define DEFAULTS "*delay: 750000 \n" \
 "*count: 40 \n" \
 "*cycles: 140 \n" \
 "*size: 0 \n" \
 "*ncolors: 200 \n" \
 "*bitmap: \n" \
 "*neighbors: 0 \n" \
 "*verbose: False \n"
#define UNIFORM_COLORS
#include "xlockmore.h"		/* in xscreensaver distribution */
#else /* STANDALONE */
#include "xlock.h"		/* in xlockmore distribution */
#include "color.h"
#endif /* STANDALONE */
#include "iostuff.h"
#include "automata.h"

/*-
 * neighbors of 0 does not randomize.  All inappropriate
 * modes will be set at 8.  3, 6, 9, & 12 also available.
 */
extern int  neighbors;

#if 1
#define DEF_RULE  "G"		/* All rules with known gliders */
#else
#define DEF_RULE  "P"		/* All rules with known patterns */
#define DEF_RULE  "S23/B3"	/* "B3/S23" */
#define DEF_RULE  "S2b34/B2a"	/* CALLAHAN */
#define DEF_RULE  "S2a2b4a/B2b3a4b"	/* ANDREEN */
#endif

#define DEF_CALLAHAN  "FALSE"
#define DEF_ANDREEN  "FALSE"

static char *rule;
static char *lifefile;

static Bool callahan;
static Bool andreen;
static XrmOptionDescRec opts[] =
{
	{"-rule", ".life.rule", XrmoptionSepArg, (caddr_t) NULL},
	{"-lifefile", ".life.lifefile", XrmoptionSepArg, (caddr_t) NULL},
	{"-callahan", ".life.callahan", XrmoptionNoArg, (caddr_t) "on"},
	{"+callahan", ".life.callahan", XrmoptionNoArg, (caddr_t) "off"},
	{"-andreen", ".life.andreen", XrmoptionNoArg, (caddr_t) "on"},
	{"+andreen", ".life.andreen", XrmoptionNoArg, (caddr_t) "off"}
};
static argtype vars[] =
{
	{(caddr_t *) & rule, "rule", "Rule", DEF_RULE, t_String},
	{(caddr_t *) & lifefile, "lifefile", "LifeFile", "", t_String},
      {(caddr_t *) & callahan, "callahan", "Callahan", DEF_CALLAHAN, t_Bool},
	{(caddr_t *) & andreen, "andreen", "Andreen", DEF_ANDREEN, t_Bool}
};
static OptionStruct desc[] =
{
	{"-rule string", "S<survival_neighborhood>/B<birth_neighborhood> parameters                                                                                "},
	{"-lifefile file", "life file"},
	{"-/+callahan", "turn on/off Callahan's hex rule B2a/S2b34"},
	{"-/+andreen", "turn on/off Andreen's hex rule B2a3a4b/S2a2m4a"}
};

ModeSpecOpt life_opts =
{sizeof opts / sizeof opts[0], opts, sizeof vars / sizeof vars[0], vars, desc};

#ifdef USE_MODULES
ModStruct   life_description =
{"life", "init_life", "draw_life", "release_life",
 "refresh_life", "change_life", NULL, &life_opts,
 750000, 40, 140, 0, 64, 1.0, "",
 "Shows Conway's game of Life", 0, NULL};

#endif

/* aliases for vars defined in the bitmap file */
#define CELL_WIDTH   image_width
#define CELL_HEIGHT    image_height
#define CELL_BITS    image_bits

#include "life.xbm"

#if defined( USE_XPM ) || defined( USE_XPMINC )
static char *image_name[] =
{""};

#define CELL_NAME image_name
#define DEFAULT_XPM 0
#endif

static int  local_neighbors = 0;
static int  neighbor_kind = 0;

#define REDRAWSTEP 2000		/* How many cells to draw per cycle */
#define MINGRIDSIZE 20
#define MINSIZE 4
#define MAXNEIGHBORS 12
#define MAXGROUPS 3		/* Eventually this may be MAXNEIGHBORS - 3 */
#define FIRSTGROUP 2		/* Need at least 2 to make a group */
#define MAXCOUNTNEIGHBORS 9	/* This restriction is because of base 10 */
#define NEIGHBORKINDS 6
#define DEAD 0
#define LIVE 1
#define STATES 2

typedef struct {
	long        position;
	unsigned short age;
	unsigned char state;
	unsigned char toggle;
} cellstruct;

/* Singly linked list */
typedef struct _CellList {
	cellstruct  info;
	struct _CellList *previous, *next;
} CellList;

typedef struct {
	int         survival, birth;
	int         survival_group[MAXGROUPS];
	int         birth_group[MAXGROUPS];
} paramstruct;

typedef struct {
	Bool        painted;
	paramstruct param;
	int         pattern, patterned_rule;
	int         pixelmode;
	int         generation;
	int         xs, ys, xb, yb;	/* cell size, grid border */
	int         nrows, ncols, npositions;
	int         width, height;
	int         state;
	int         redrawing, redrawpos;
	int         ncells[STATES];
	CellList   *last[STATES], *first[STATES];
	CellList  **arr;
	union {
		XPoint      hexagon[6];
		XPoint      triangle[2][3];
	} shape;
	XImage     *logo;
	Colormap    cmap;
	unsigned long black;
	int         graphics_format;
	GC          backGC;
} lifestruct;

static lifestruct *lifes = NULL;

static paramstruct input_param;
static Bool allPatterns = False, allGliders = False;
static char *filePattern = NULL;

static char plots[NEIGHBORKINDS] =
{
	3, 4, 6, 8, 9, 12	/* Neighborhoods */
};

static char maxgroups[NEIGHBORKINDS] =
{0, 0, 3, 0, 0, 0};
static char groupnumber[NEIGHBORKINDS][MAXGROUPS] =
{
	{0, 0, 0},		/* Triangular */
	{0, 0, 0},		/* Future improvement */
	{3, 3, 3},		/* Hexagonal */
	{0, 0, 0},		/* Maxgroup will expand... */
	{0, 0, 0},		/* Future improvement */
	{0, 0, 0}		/* Future improvement */
};

static char style6[64] =
{0, 0, 0, 0, 0, 1, 0, 0, 0, 2, 1, 1, 0, 1, 0, 0,
 0, 1, 2, 1, 1, 2, 1, 1, 0, 1, 1, 2, 0, 1, 0, 0,
 0, 0, 1, 0, 2, 1, 1, 0, 1, 1, 2, 1, 1, 2, 1, 0,
 0, 0, 1, 0, 1, 1, 2, 0, 0, 0, 1, 0, 0, 0, 0, 0};


#define NUMPTS  64
#define NUMFILEPTS  (2*NUMPTS)

/*-
 * Patterns have < NUMPTS pts (and should have a size of <= 32x32,
 * the Glider Gun is an exception)
 */
static char patterns_8S23B3[][2 * NUMPTS + 1] =
{
	{			/* GLIDER GUN */
		6, -4,
		5, -3, 6, -3,
		-6, -2, -5, -2, 8, -2, 9, -2, 16, -2,
		-7, -1, 8, -1, 9, -1, 10, -1, 16, -1, 17, -1,
		-18, 0, -17, 0, -8, 0, 8, 0, 9, 1,
		-17, 1, -8, 1, 5, 1, 6, 1,
		-8, 2, 6, 2,
		-7, 3,
		-6, 4, -5, 4,
		127
	},
	{			/* SHOWER TUB (PART OF OSCILATORS) */
		-3, -6, -2, -6, 2, -6, 3, -6,
		-4, -5, -2, -5, 2, -5, 4, -5,
		-4, -4, 4, -4,
		-7, -3, -6, -3, -4, -3, -3, -3, 3, -3, 4, -3, 6, -3, 7, -3,
		-7, -2, -6, -2, -4, -2, 0, -2, 4, -2, 6, -2, 7, -2,
		-4, -1, -2, -1, 2, -1, 4, -1,
		-4, 0, -2, 0, 2, 0, 4, 0,
		-5, 1, -4, 1, -2, 1, 2, 1, 4, 1, 5, 1,
		-4, 2, -1, 2, 0, 2, 1, 2, 4, 2,
		-4, 3, 4, 3, 6, 3,
		-3, 4, -2, 4, -1, 4, 5, 4, 6, 4,
		-1, 5,
		127
	},
	{			/* P4 LARGE TOASTER */
		-5, -3, -4, -3, -2, -3, 2, -3, 4, -3, 5, -3,
		-5, -2, 5, -2,
		-4, -1, -3, -1, 3, -1, 4, -1,
       -7, 0, -6, 0, -5, 0, -2, 0, -1, 0, 0, 0, 1, 0, 2, 0, 5, 0, 6, 0, 7, 0,
		-7, 1, -4, 1, 4, 1, 7, 1,
		-6, 2, -5, 2, 5, 2, 6, 2,
		127
	},
	{			/* STARGATE REPEATER P3 */
		0, -6,
		-1, -5, 1, -5,
		-2, -4, 0, -4, 2, -4,
		-2, -3, 2, -3,
		-4, -2, -3, -2, 0, -2, 3, -2, 4, -2,
		-5, -1, 0, -1, 5, -1,
		-6, 0, -4, 0, -2, 0, -1, 0, 1, 0, 2, 0, 4, 0, 6, 0,
		-5, 1, 0, 1, 5, 1,
		-4, 2, -3, 2, 0, 2, 3, 2, 4, 2,
		-2, 3, 2, 3,
		-2, 4, 0, 4, 2, 4,
		-1, 5, 1, 5,
		0, 6,
		127
	},
	{			/* OSCILLATOR 7 (P8) */
		-4, -2, -3, -2, -2, -2, -1, -2, 4, -2, 5, -2, 6, -2, 7, -2,
		-9, -1, -8, -1, 0, -1, 8, -1,
		-9, 0, -8, 0, -5, 0, -4, 0, 0, 0, 3, 0, 4, 0, 8, 0,
		-5, 1, -4, 1, -1, 1, 3, 1, 4, 1, 7, 1,
		127
	},
	{			/* P144 */
		-14, -9, -13, -9, 12, -9, 13, -9,
		-14, -8, -13, -8, 12, -8, 13, -8,
		4, -7, 5, -7,
		3, -6, 6, -6,
		4, -5, 5, -5,
		-1, -3, 0, -3, 1, -3,
		-1, -2, 1, -2,
		-1, -1, 0, -1, 1, -1,
		-1, 0, 0, 0,
		-2, 1, -1, 1, 0, 1,
		-2, 2, 0, 2,
		-2, 3, -1, 3, 0, 3,
		-6, 5, -5, 5,
		-7, 6, -4, 6,
		-6, 7, -5, 7,
		-14, 8, -13, 8, 12, 8, 13, 8,
		-14, 9, -13, 9, 12, 9, 13, 9,
		127
	},
	{			/* FIGURE EIGHT */
		-3, -3, -2, -3, -1, -3,
		-3, -2, -2, -2, -1, -2,
		-3, -1, -2, -1, -1, -1,
		0, 0, 1, 0, 2, 0,
		0, 1, 1, 1, 2, 1,
		0, 2, 1, 2, 2, 2,
		127
	},
	{			/* PULSAR 18-22-20 */
		0, -4, 1, -4, 2, -4,
		-1, -2, 4, -2,
		-2, -1, 0, -1, 4, -1,
		-4, 0, -3, 0, -2, 0, 1, 0, 4, 0,
		2, 1,
		0, 2, 1, 2,
		0, 3,
		0, 4,
		127
	},
	{			/* PULSAR 48-56-72 */
		-2, -1, -1, -1, 0, -1, 1, -1, 2, -1,
		-2, 0, 2, 0,
		127
	},
	{			/* BARBER POLE P2 */
		-6, -6, -5, -6,
		-6, -5, -4, -5,
		-4, -3, -2, -3,
		-2, -1, 0, -1,
		0, 1, 2, 1,
		2, 3, 4, 3,
		5, 4,
		4, 5, 5, 5,
		127
	},
	{			/* ACHIM P5 */
		-6, -6, -5, -6,
		-6, -5,
		-4, -4,
		-4, -3, -2, -3,
		-2, -1, 0, -1,
		0, 1, 2, 1,
		2, 3, 3, 3,
		5, 4,
		4, 5, 5, 5,
		127
	},
	{			/* HERTZ P4 */
		-2, -5, -1, -5,
		-2, -4, -1, -4,
		-7, -2, -6, -2, -2, -2, -1, -2, 0, -2, 1, -2, 5, -2, 6, -2,
		-7, -1, -5, -1, -3, -1, 2, -1, 4, -1, 6, -1,
		-5, 0, -3, 0, -2, 0, 2, 0, 4, 0,
		-6, 1, -5, 1, -3, 1, 2, 1, 4, 1, 5, 1,
		-2, 2, -1, 2, 0, 2, 1, 2,
		-2, 4, -1, 4,
		-2, 5, -1, 5,
		127
	},
	{			/* PUMP (TUMBLER, P14) */
		-2, -3, -1, -3, 1, -3, 2, -3,
		-2, -2, -1, -2, 1, -2, 2, -2,
		-1, -1, 1, -1,
		-3, 0, -1, 0, 1, 0, 3, 0,
		-3, 1, -1, 1, 1, 1, 3, 1,
		-3, 2, -2, 2, 2, 2, 3, 2,
		127
	},
	{			/* SMILEY (P8) */
		-3, -3, -2, -3, -1, -3, 1, -3, 2, -3, 3, -3,
		-2, -2, 0, -2, 2, -2,
		-2, 0, 2, 0,
		-3, 2, -1, 2, 1, 2, 3, 2,
		-1, 3, 1, 3,
		127
	},
	{			/* PULSE1 P4 */
		0, -3, 1, -3,
		-2, -2, 0, -2,
		-3, -1, 3, -1,
		-2, 0, 2, 0, 3, 0,
		0, 2, 2, 2,
		1, 3,
		127
	},
	{			/* SHINING FLOWER P5 */
		-1, -4, 0, -4,
		-2, -3, 1, -3,
		-3, -2, 2, -2,
		-4, -1, 3, -1,
		-4, 0, 3, 0,
		-3, 1, 2, 1,
		-2, 2, 1, 2,
		-1, 3, 0, 3,
		127
	},
	{			/* PULSE2 P6 */
		0, -4, 1, -4,
		-4, -3, -3, -3, -1, -3,
		-4, -2, -3, -2, 0, -2, 3, -2,
		1, -1, 3, -1,
		2, 0,
		1, 2, 2, 2,
		1, 3, 2, 3,
		127
	},
	{			/* PINWHEEL P4 */
		-2, -6, -1, -6,
		-2, -5, -1, -5,
		-2, -3, -1, -3, 0, -3, 1, -3,
		-3, -2, -1, -2, 2, -2, 4, -2, 5, -2,
		-3, -1, 1, -1, 2, -1, 4, -1, 5, -1,
		-6, 0, -5, 0, -3, 0, 0, 0, 2, 0,
		-6, 1, -5, 1, -3, 1, 2, 1,
		-2, 2, -1, 2, 0, 2, 1, 2,
		0, 4, 1, 4,
		0, 5, 1, 5,
		127
	},
	{			/* CLOCK P4 */
		-2, -6, -1, -6,
		-2, -5, -1, -5,
		-2, -3, -1, -3, 0, -3, 1, -3,
		-6, -2, -5, -2, -3, -2, 0, -2, 2, -2,
		-6, -1, -5, -1, -3, -1, -1, -1, 2, -1,
		-3, 0, -1, 0, 2, 0, 4, 0, 5, 0,
		-3, 1, 2, 1, 4, 1, 5, 1,
		-2, 2, -1, 2, 0, 2, 1, 2,
		0, 4, 1, 4,
		0, 5, 1, 5,
		127
	},
	{			/* CROSS P3 */
		-2, -4, -1, -4, 0, -4, 1, -4,
		-2, -3, 1, -3,
		-4, -2, -3, -2, -2, -2, 1, -2, 2, -2, 3, -2,
		-4, -1, 3, -1,
		-4, 0, 3, 0,
		-4, 1, -3, 1, -2, 1, 1, 1, 2, 1, 3, 1,
		-2, 2, 1, 2,
		-2, 3, -1, 3, 0, 3, 1, 3,
		127
	},
	{			/* BIG CROSS P3 */
		0, -5,
		-1, -4, 0, -4, 1, -4,
		-3, -3, -2, -3, -1, -3, 1, -3, 2, -3, 3, -3,
		-3, -2, 3, -2,
		-4, -1, -3, -1, 3, -1, 4, -1,
		-5, 0, -4, 0, 4, 0, 5, 0,
		-4, 1, -3, 1, 3, 1, 4, 1,
		-3, 2, 3, 2,
		-3, 3, -2, 3, -1, 3, 1, 3, 2, 3, 3, 3,
		-1, 4, 0, 4, 1, 4,
		0, 5,
		127
	},
	{			/* P4 DIAG SYM */
		-2, -4, 0, -4,
		-2, -3, 0, -3, 2, -3, 3, -3,
		-4, -2, -3, -2, 2, -2,
		0, -1, 1, -1, 2, -1,
		-4, 0, -3, 0, -1, 0, 2, 0,
		-1, 1, 2, 1,
		-3, 2, -2, 2, -1, 2, 0, 2, 1, 2,
		-3, 3,
		127
	},
	{			/* P4 ASYM */
		-4, -4, -2, -4,
		-4, -3, -1, -3,
		-1, -2,
		-2, -1, -1, -1, 0, -1, 3, -1, 4, -1, 5, -1,
		-5, 0, -4, 0, -3, 0, 0, 0, 1, 0, 2, 0,
		1, 1,
		1, 2, 4, 2,
		2, 3, 4, 3,
		127
	},
	{			/* P4 ASYM 2 */
		-3, -3, -1, -3, 2, -3, 4, -3, 5, -3, 6, -3,
		-4, -2, -1, -2, 1, -2, 3, -2, 5, -2,
		-4, -1,
		3, 0,
		-6, 1, -4, 1, -2, 1, 0, 1, 3, 1,
		-7, 2, -6, 2, -5, 2, -3, 2, 0, 2, 2, 2,
		127
	},
	{			/* P8 ASYM */
		-3, -4, -2, -4,
		-4, -3,
		-3, -2, 1, -2,
		-3, -1, 1, -1, 2, -1,
		-1, 0, 1, 0,
		-2, 1, -1, 1, 3, 1,
		-1, 2, 3, 2,
		4, 3,
		2, 4, 3, 4,
		127
	},
	{			/* P4 SYM */
		-6, -2, -5, -2, 4, -2, 5, -2,
		-6, -1, -5, -1, -3, -1, -2, -1, 1, -1, 2, -1, 4, -1, 5, -1,
		-5, 0, -2, 0, 1, 0, 4, 0,
		-5, 1, -4, 1, -2, 1, -1, 1, 0, 1, 1, 1, 3, 1, 4, 1,
		127
	},
	{			/* QUESTION P3 NOSYM */
		-2, -4, -1, -4, 0, -4,
		2, -3,
		-3, -2, 2, -2,
		1, -1,
		-2, 0, -1, 0,
		-2, 1,
		-2, 2,
		-2, 3,
		127
	},
	{			/* WHIRLY THING P12 */
		-5, -6,
		-5, -5, -4, -5, -3, -5, 5, -5, 6, -5,
		-2, -4, 5, -4,
		-3, -3, -2, -3, 3, -3, 5, -3,
		3, -2, 4, -2,
		0, -1, 1, -1,
		0, 0, 1, 0,
		0, 1, 1, 1,
		-4, 2, -3, 2,
		-5, 3, -3, 3, 2, 3, 3, 3,
		-5, 4, 2, 4,
		-6, 5, -5, 5, 3, 5, 4, 5, 5, 5,
		5, 6,
		127
	},
	{			/* PENTADECATHOLON P15 */
	     -5, 0, -4, 0, -3, 0, -2, 0, -1, 0, 0, 0, 1, 0, 2, 0, 3, 0, 4, 0,
		127
	},
	{			/* BALLOON P5 */
		-1, -3, 0, -3,
		-3, -2, 2, -2,
		-3, -1, 2, -1,
		-3, 0, 2, 0,
		-2, 1, 1, 1,
		-4, 2, -2, 2, 1, 2, 3, 2,
		-4, 3, -3, 3, 2, 3, 3, 3,
		127
	},
	{			/* FENCEPOST P12 */
		-11, -3, -9, -3, -7, -3,
	 -11, -2, -9, -2, -7, -2, 5, -2, 6, -2, 7, -2, 9, -2, 10, -2, 11, -2,
		-11, -1, -7, -1, -3, -1, 1, -1, 8, -1,
	  -10, 0, -8, 0, -3, 0, -2, 0, -1, 0, 1, 0, 5, 0, 6, 0, 10, 0, 11, 0,
		-11, 1, -7, 1, -3, 1, 1, 1, 8, 1,
		-11, 2, -9, 2, -7, 2, 5, 2, 6, 2, 7, 2, 9, 2, 10, 2, 11, 2,
		-11, 3, -9, 3, -7, 3,
		127
	},
	{			/* PISTON (SHUTTLE) P30 */
		1, -3, 2, -3,
		0, -2,
		-10, -1, -1, -1,
		-11, 0, -10, 0, -1, 0, 9, 0, 10, 0,
		-1, 1, 9, 1,
		0, 2,
		1, 3, 2, 3,
		127
	},
	{			/* P30 */
		-8, -5, 7, -5,
		-9, -4, -7, -4, 1, -4, 2, -4, 6, -4, 8, -4,
		-8, -3, 0, -3, 1, -3, 2, -3, 7, -3,
		1, -2, 2, -2,
		1, 2, 2, 2,
		-8, 3, 0, 3, 1, 3, 2, 3, 7, 3,
		-9, 4, -7, 4, 1, 4, 2, 4, 6, 4, 8, 4,
		-8, 5, 7, 5,
		127
	},
	{			/* PISTON2 P46 */
		-3, -5,
		-14, -4, -13, -4, -4, -4, -3, -4, 13, -4, 14, -4,
		-14, -3, -13, -3, -5, -3, -4, -3, 13, -3, 14, -3,
		-4, -2, -3, -2, 0, -2, 1, -2,
		-4, 2, -3, 2, 0, 2, 1, 2,
		-14, 3, -13, 3, -5, 3, -4, 3, 13, 3, 14, 3,
		-14, 4, -13, 4, -4, 4, -3, 4, 13, 4, 14, 4,
		-3, 5,
		127
	},
	{			/* GEARS (gear, flywheel, blinker) P2 */
		-1, -4,
		-1, -3, 1, -3,
		-3, -2,
		2, -1, 3, -1,
		-4, 0, -3, 0,
		2, 1,
		-2, 2, 0, 2,
		0, 3,

		5, 3,
		3, 4, 4, 4,
		5, 5, 6, 5,
		4, 6,

		8, 0,
		8, 1,
		8, 2,
		127
	},
	{			/* TURBINE8, KOK'S GALAXY */
		-4, -4, -3, -4, -2, -4, -1, -4, 0, -4, 1, -4, 3, -4, 4, -4,
		-4, -3, -3, -3, -2, -3, -1, -3, 0, -3, 1, -3, 3, -3, 4, -3,
		3, -2, 4, -2,
		-4, -1, -3, -1, 3, -1, 4, -1,
		-4, 0, -3, 0, 3, 0, 4, 0,
		-4, 1, -3, 1, 3, 1, 4, 1,
		-4, 2, -3, 2,
		-4, 3, -3, 3, -1, 3, 0, 3, 1, 3, 2, 3, 3, 3, 4, 3,
		-4, 4, -3, 4, -1, 4, 0, 4, 1, 4, 2, 4, 3, 4, 4, 4,
		127
	},
	{			/* P16 */
		-3, -6, 1, -6, 2, -6,
		-3, -5, 0, -5, 3, -5,
		3, -4,
		-5, -3, -4, -3, 1, -3, 2, -3, 5, -3, 6, -3,
		-6, -2, -3, -2,
		-6, -1, -3, -1,
		-5, 0, 5, 0,
		3, 1, 6, 1,
		3, 2, 6, 2,
		-6, 3, -5, 3, -2, 3, -1, 3, 4, 3, 5, 3,
		-3, 4,
		-3, 5, 0, 5, 3, 5,
		-2, 6, -1, 6, 3, 6,
		127
	},
	{			/* P28 (FLUTTER) */
		-9, -7, -7, -7, 7, -7, 9, -7,
		-6, -6, 6, -6,
		-10, -5, -7, -5, 7, -5, 10, -5,
		-11, -4, -9, -4, -7, -4, 7, -4, 9, -4, 11, -4,
		-11, -3, -8, -3, 8, -3, 11, -3,
		-10, -2, -9, -2, -4, -2, -3, -2, -2, -2,
		2, -2, 3, -2, 4, -2, 9, -2, 10, -2,
		-3, -1, 3, -1,
		-10, 1, -9, 1, 9, 1, 10, 1,
		-11, 2, -8, 2, 8, 2, 11, 2,
		-11, 3, -9, 3, -6, 3, 6, 3, 9, 3, 11, 3,
		-10, 4, 10, 4,
		-9, 5, -8, 5, -6, 5, 6, 5, 8, 5, 9, 5,
		-7, 6, 7, 6,
		127
	},
	{			/* P54 (PISTON3) */
		-14, -8, -13, -8, 13, -8, 14, -8,
		-13, -7, 13, -7,
		-13, -6, -11, -6, 11, -6, 13, -6,
		-12, -5, -11, -5, -1, -5, 11, -5, 12, -5,
		0, -4,
		-6, -3, -5, -3, 1, -3,
		-6, -2, -5, -2, -2, -2, 0, -2,
		-1, -1,
		-1, 1,
		-6, 2, -5, 2, -2, 2, 0, 2,
		-6, 3, -5, 3, 1, 3,
		0, 4,
		-12, 5, -11, 5, -1, 5, 11, 5, 12, 5,
		-13, 6, -11, 6, 11, 6, 13, 6,
		-13, 7, 13, 7,
		-14, 8, -13, 8, 13, 8, 14, 8,
		127
	},
	{			/* SWITCH ENGINE */
		-12, -3, -10, -3,
		-13, -2,
		-12, -1, -9, -1,
		-10, 0, -9, 0, -8, 0,
		13, 2, 14, 2,
		13, 3,
		127
	},
	{			/* PUFFER TRAIN */
		1, -9,
		2, -8,
		-2, -7, 2, -7,
		-1, -6, 0, -6, 1, -6, 2, -6,
		-2, -2,
		-1, -1, 0, -1,
		0, 0,
		0, 1,
		-1, 2,
		1, 5,
		2, 6,
		-2, 7, 2, 7,
		-1, 8, 0, 8, 1, 8, 2, 8,
		127
	},
	{			/* SCHOOL OF FISH (ESCORT) */
		3, -8,
		4, -7,
		-2, -6, 4, -6,
		-1, -5, 0, -5, 1, -5, 2, -5, 3, -5, 4, -5,
		-5, -1, -4, -1, -3, -1, -2, -1, -1, -1, 0, -1,
		1, -1, 2, -1, 3, -1, 4, -1, 5, -1, 6, -1,
		-6, 0, 6, 0,
		6, 1,
		5, 2,
		3, 4,
		4, 5,
		-2, 6, 4, 6,
		-1, 7, 0, 7, 1, 7, 2, 7, 3, 7, 4, 7,

		127
	},
	{			/* DART SPEED 1/3 */
		3, -7,
		2, -6, 4, -6,
		1, -5, 2, -5,
		4, -4,
		0, -3, 4, -3,
		-3, -2, 0, -2,
		-4, -1, -2, -1, 1, -1, 2, -1, 3, -1, 4, -1,
		-5, 0, -2, 0,
		-4, 1, -2, 1, 1, 1, 2, 1, 3, 1, 4, 1,
		-3, 2, 0, 2,
		0, 3, 4, 3,
		4, 4,
		1, 5, 2, 5,
		2, 6, 4, 6,
		3, 7,
		127
	},
	{			/* PERIOD 4 SPEED 1/2 */
		-3, -5,
		-4, -4, -3, -4, -2, -4, -1, -4, 0, -4,
		-5, -3, -4, -3, 0, -3, 1, -3, 3, -3,
		-4, -2, 4, -2,
		-3, -1, -2, -1, 1, -1, 3, -1,
		-3, 1, -2, 1, 1, 1, 3, 1,
		-4, 2, 4, 2,
		-5, 3, -4, 3, 0, 3, 1, 3, 3, 3,
		-4, 4, -3, 4, -2, 4, -1, 4, 0, 4,
		-3, 5,
		127
	},
	{			/* ANOTHER PERIOD 4 SPEED 1/2 */
		-4, -7, -3, -7, -1, -7, 0, -7, 1, -7, 2, -7, 3, -7, 4, -7,
		-5, -6, -4, -6, -3, -6, -2, -6, 5, -6,
		-6, -5, -5, -5,
		-5, -4, 5, -4,
		-4, -3, -3, -3, -2, -3, 0, -3,
		-2, -2,
		-2, -1,
		-1, 0,
		-2, 1,
		-2, 2,
		-4, 3, -3, 3, -2, 3, 0, 3,
		-5, 4, 5, 4,
		-6, 5, -5, 5,
		-5, 6, -4, 6, -3, 6, -2, 6, 5, 6,
		-4, 7, -3, 7, -1, 7, 0, 7, 1, 7, 2, 7, 3, 7, 4, 7,
		127
	},
	{			/* SMALLEST KNOWN PERIOD 3 SPACESHIP SPEED 1/3 */
		0, -8,
		-1, -7, 1, -7,
		-1, -6, 1, -6,
		-1, -5,
		-2, -3, -1, -3,
		-1, -2, 1, -2,
		-2, -1, 0, -1,
		-2, 0, -1, 0, 0, 0,
		-1, 2, 1, 2,
		-1, 3, 0, 3,
		0, 4,
		0, 5, 2, 5,
		0, 6, 2, 6,
		1, 7,
		127
	},
	{			/* TURTLE SPEED 1/3 */
		-4, -5, -3, -5, -2, -5, 6, -5,
		-4, -4, -3, -4, 0, -4, 2, -4, 3, -4, 5, -4, 6, -4,
		-2, -3, -1, -3, 0, -3, 5, -3,
		-4, -2, -1, -2, 1, -2, 5, -2,
		-5, -1, 0, -1, 5, -1,
		-5, 0, 0, 0, 5, 0,
		-4, 1, -1, 1, 1, 1, 5, 1,
		-2, 2, -1, 2, 0, 2, 5, 2,
		-4, 3, -3, 3, 0, 3, 2, 3, 3, 3, 5, 3, 6, 3,
		-4, 4, -3, 4, -2, 4, 6, 4,
		127
	},
	{			/* SMALLEST KNOWN PERIOD 5 SPEED 2/5 */
		1, -7, 3, -7,
		-2, -6, 3, -6,
		-3, -5, -2, -5, -1, -5, 4, -5,
		-4, -4, -2, -4,
		-5, -3, -4, -3, -1, -3, 0, -3, 5, -3,
		-4, -2, -3, -2, 0, -2, 1, -2, 2, -2, 3, -2, 4, -2,
		-4, 2, -3, 2, 0, 2, 1, 2, 2, 2, 3, 2, 4, 2,
		-5, 3, -4, 3, -1, 3, 0, 3, 5, 3,
		-4, 4, -2, 4,
		-3, 5, -2, 5, -1, 5, 4, 5,
		-2, 6, 3, 6,
		1, 7, 3, 7,
		127
	},
	{			/* SYM PUFFER */
		1, -4, 2, -4, 3, -4, 4, -4,
		0, -3, 4, -3,
		4, -2,
		-4, -1, -3, -1, 0, -1, 3, -1,
		-4, 0, -3, 0, -2, 0,
		-4, 1, -3, 1, 0, 1, 3, 1,
		4, 2,
		0, 3, 4, 3,
		1, 4, 2, 4, 3, 4, 4, 4,
		127
	},
	{			/* RAKE P20 BACKWARDS */
		0, -10, 1, -10, 10, -10,
		-1, -9, 0, -9, 1, -9, 2, -9, 11, -9,
		-1, -8, 0, -8, 2, -8, 3, -8, 7, -8, 11, -8,
		1, -7, 2, -7, 8, -7, 9, -7, 10, -7, 11, -7,
		6, -3, 7, -3,
		5, -2, 6, -2, 8, -2, 9, -2,
		6, -1, 9, -1,
		6, 0, 9, 0,
		7, 1, 8, 1,
		10, 4,
		11, 5,
		-8, 6, 7, 6, 11, 6,
		-7, 7, 8, 7, 9, 7, 10, 7, 11, 7,
		-11, 8, -7, 8,
		-10, 9, -9, 9, -8, 9, -7, 9,
		127
	},
	{			/* RAKE P20 FORWARDS */
		0, -10, 1, -10, 10, -10,
		-1, -9, 0, -9, 1, -9, 2, -9, 11, -9,
		-1, -8, 0, -8, 2, -8, 3, -8, 7, -8, 11, -8,
		1, -7, 2, -7, 8, -7, 9, -7, 10, -7, 11, -7,
		6, -3, 7, -3,
		5, -2, 6, -2, 8, -2, 9, -2,
		6, -1, 9, -1,
		6, 0, 9, 0,
		7, 1, 8, 1,
		10, 4,
		11, 5,
		7, 6, 11, 6,
		-9, 7, -8, 7, -7, 7, -6, 7, 8, 7, 9, 7, 10, 7, 11, 7,
		-10, 8, -6, 8,
		-6, 9,
		-7, 10,
		127
	},
	{			/* RAKE P24 BACKWARDS */
		-5, -10,
		-4, -9,
		-10, -8, -4, -8,
		-9, -7, -8, -7, -7, -7, -6, -7, -5, -7, -4, -7,
		6, -6, 7, -6,
		5, -5, 6, -5, 7, -5, 8, -5,
		5, -4, 6, -4, 8, -4, 9, -4,
		7, -3, 8, -3,
		0, -2, 2, -2,
		-1, -1, 2, -1, 3, -1,
		0, 0, 2, 0,
		7, 1, 8, 1,
		5, 2, 6, 2, 8, 2, 9, 2,
		5, 3, 6, 3, 7, 3, 8, 3,
		6, 4, 7, 4,
		-5, 6, -4, 6,
		-9, 7, -8, 7, -7, 7, -6, 7, -4, 7, -3, 7,
		-9, 8, -8, 8, -7, 8, -6, 8, -5, 8, -4, 8,
		-8, 9, -7, 9, -6, 9, -5, 9,
		127
	},
	{			/* BIG GLIDER 1 */
		-4, -7, -3, -7,
		-4, -6, -2, -6,
		-4, -5,
		-7, -4, -6, -4, -4, -4,
		-7, -3, -2, -3,
		-7, -2, -5, -2, -4, -2, 3, -2, 4, -2, 5, -2,
		-2, -1, -1, -1, 0, -1, 5, -1, 6, -1,
		-1, 0, 0, 0, 1, 0, 3, 0, 5, 0,
		6, 1,
		-1, 2, 1, 2,
		-2, 3, -1, 3, 1, 3,
		-1, 4,
		-3, 5, -2, 5, 0, 5,
		0, 6,
		-2, 7, -1, 7,
		127
	},
	{			/* BIG GLIDER 2 */
		0, -9, 1, -9,
		0, -8, 2, -8,
		0, -7,
		1, -6, 2, -6, 3, -6,
		1, -5, 3, -5, 4, -5, 5, -5,
		1, -4, 4, -4, 5, -4,
		3, -3, 5, -3, 7, -3, 8, -3,
		2, -2, 3, -2, 5, -2, 7, -2,
		1, -1, 2, -1, 7, -1,
		-9, 0, -8, 0, -7, 0,
		-9, 1, -6, 1, -5, 1, -4, 1, -1, 1, 3, 1, 4, 1,
		-8, 2, -6, 2, -2, 2, -1, 2,
		-6, 3, -5, 3, -3, 3, -2, 3, 1, 3,
		-5, 4, -4, 4, 1, 4,
		-5, 5, -4, 5, -3, 5, -2, 5,
		-3, 7, -2, 7, -1, 7,
		-3, 8,
		127
	},
	{			/* BIG GLIDER 3 */
		-1, -8,
		-2, -7, -1, -7,
		-2, -6, 0, -6,
		0, -4, 2, -4,
		-2, -3, 0, -3, 2, -3,
		-7, -2, -3, -2, -2, -2, 0, -2, 2, -2, 3, -2,
		-8, -1, -7, -1, -6, -1, -5, -1, -2, -1, 4, -1,
		-8, 0, -5, 0, -4, 0, -2, 0, -1, 0, 3, 0, 4, 0,
		-6, 1, -5, 1, 0, 1,
		-4, 2, -3, 2, 1, 2,
		-3, 3, -2, 3, -1, 3, 2, 3, 4, 3, 5, 3, 6, 3, 7, 3,
		-3, 4, 0, 4, 3, 4, 4, 4, 5, 4,
		-1, 5, 0, 5, 1, 5,
		1, 6, 2, 6, 3, 6,
		2, 7, 3, 7,
		127
	},
	{			/* PI HEPTOMINO (], NEAR SHIP) */
		-2, -1, -1, -1, 0, -1,
		1, 0,
		-2, 1, -1, 1, 0, 1,
		127
	},
	{			/* R PENTOMINO */
		0, -1, 1, -1,
		-1, 0, 0, 0,
		0, 1,
		127
	},
	{			/* BUNNIES */
		-4, -2, 2, -2,
		-2, -1, 2, -1,
		-2, 0, 1, 0, 3, 0,
		-3, 1, -1, 1,
		127
	}
};


/*-
 * This uses Callahan's "/" notation
 *    ABC                   A B C
 *    DEF          ->      D E F
 *    GHI                 G H I
 */
static char patterns_6S2b34B2a[][2 * NUMPTS + 1] =
{
#if 0
	{			/* GLIDER (P4) */
		0, -2,
		1, -1,
		-2, 0, 1, 0,
		1, 1,
		1, 2,
		127
	},
#endif
	{			/* 3 OSCILLATOR GLIDER GUN (P42) */
		5, -6, 6, -6,
		6, -5, 7, -5, 9, -5,
		6, -4, 8, -4, 9, -4,
		7, -3, 8, -3, 10, -3, 11, -3,
		8, -2, 10, -2,
		8, -1, 10, -1, 11, -1,
		8, 0, 9, 0, 10, 0, 12, 0,
		10, 1,

		-10, -5,
		-11, -4, -10, -4, -8, -4,
		-12, -3, -11, -3, -9, -3, -8, -3, -7, -3,
		-10, -2, -8, -2, -6, -2,
		-10, -1, -9, -1, -7, -1, -6, -1, -5, -1, -4, -1,
		-10, 0, -8, 0, -7, 0, -5, 0,

		0, -1, 1, -1,
		1, 0, 2, 0, 3, 0,
		1, 1, 3, 1,
		0, 2, 1, 2, 2, 2, 3, 2,
		0, 3, 4, 3,
		1, 4, 2, 4, 3, 4, 4, 4, 5, 4,
		3, 5,
		3, 6,
		127
	},
	{			/* ANOTHER GUN (P20) */
		-2, -7, -1, -7,
		-2, -6,

		-8, -2,
		-9, -1, -8, -1, -7, -1, -6, -1, -5, -1,
		-8, 0, -6, 0, -5, 0,
		-7, 1, -6, 1,
		-8, 2, -7, 2,
		-10, 3, -9, 3, -8, 3,
		-8, 4,
		-9, 5, -8, 5, -7, 5,
		-6, 6,

		4, 0,
		3, 1, 4, 1, 5, 1, 10, 1,
		3, 2, 4, 2, 6, 2, 7, 2, 10, 2,
		5, 3, 6, 3, 8, 3, 9, 3, 10, 3, 11, 3,
		7, 4, 10, 4, 12, 4,
		11, 5,
		127
	},
	{			/* SHIP (P48) */
		-3, -2, -1, -2,
		-2, -1, -1, -1,
		-2, 0, -1, 0, 0, 0, 2, 0,
		-1, 1, 0, 1, 3, 1,
		0, 2,
		127
	},
	{			/* SHIP (P15) */
		-3, -5, -1, -5,
		-2, -4, -1, -4, 0, -4,
		-4, -3, -3, -3, -2, -3, 0, -3,
		-2, -2, 0, -2,
		-1, -1, 0, -1,
		0, 1, 1, 1,
		0, 2, 2, 2,
		-1, 3, 0, 3, 1, 3, 3, 3,
		2, 4, 3, 4, 4, 4,
		2, 5, 4, 5,
		127
	},
	{			/* SHIP BY A COLLISION OF 3 GLIDERS (P15) */
		7, -4,
		8, -3,
		8, -2, 10, -2,
		-11, -1, -10, -1, 1, -1, 2, -1, 3, -1, 4, -1, 9, -1, 11, -1,
		-9, 0, 1, 0, 10, 0,
		-8, 1,
		-7, 2, 5, 2,
		-9, 3,
		127
	},
	{			/* STALK (P8) */
		-2, -4,
		-3, -3, -2, -3,
		-3, -2, -1, -2, 0, -2,
		-3, -1, -2, -1, -1, -1, 1, -1,
		0, 0, 1, 0,
		0, 1, 2, 1,
		0, 2, 1, 2, 2, 2,
		2, 3, 3, 3, 4, 3,
		127
	},
	{			/* STALK BY A COLLISION OF 3 GLIDERS */
		-8, -9,
		-5, -8,
		-5, -7,
		-5, -6,
		-6, -5, -5, -5,
		-3, 1,
		-4, 2, -2, 2,
		-3, 3, -1, 3,
		-1, 4,
		0, 5, 5, 5,
		5, 6,
		5, 7, 8, 7,
		5, 8,
		6, 9,
		127
	},
	{			/* STALK BY A COLLISION OF 2 GLIDERS AND EATER */
		3, -6,
		3, -5,
		-5, -4, 4, -4, 7, -4,
		-4, -3, -3, -3, 5, -3,
		6, -2,
		-7, 1, -6, 1,
		-5, 2,
		-4, 3,
		-3, 4,
		-5, 5,
		127
	},
	{			/* OSCILLATOR (P42) */
		-2, -3, -1, -3,
		-2, -2, 0, -2,
		-3, -1, -2, -1, -1, -1, 0, -1,
		-3, 0, 1, 0,
		-2, 1, -1, 1, 0, 1, 1, 1, 2, 1,
		0, 2,
		0, 3,
		127
	},
	{			/* TENTACLE (P66) */
		-3, -3, -2, -3,
		-5, -2, -4, -2, -3, -2, -1, -2,
		-5, -1, -3, -1, -1, -1,
		-4, 0, -3, 0, -1, 0, 0, 0,
		-4, 1, -2, 1, -1, 1, 1, 1, 3, 1,
		0, 2, 1, 2, 3, 2, 4, 2, 5, 2,
		2, 3, 3, 3,
		127
	},
	{			/* ROTATING OSCILLATOR (P42) */
		0, -2, 1, -2,
		-1, -1, 0, -1, 1, -1,
		1, 0,
		-2, 1, -1, 1, 0, 1, 1, 1,
		-2, 2, -1, 2,
		127
	},
	{			/* INTERNAL OSCILLATOR (P7) */
		-3, -6,
		-4, -5, -3, -5,
		-5, -4, -4, -4, -2, -4, -1, -4, 1, -4,
		-3, -3, -1, -3, 0, -3, 1, -3,
		-6, -2, -4, -2, -3, -2, -1, -2, 2, -2, 3, -2,
		-5, -1, -4, -1, -2, -1, 2, -1,
		-6, 0, -5, 0, -3, 0, -2, 0, -1, 0, 0, 0, 3, 0,
		-4, 1, -3, 1, 1, 1, 3, 1,
		-4, 2, -2, 2, 0, 2, 1, 2, 4, 2,
		-4, 3, -3, 3, -2, 3, 0, 3, 1, 3, 3, 3, 4, 3, 5, 3,
		-1, 4, 0, 4, 2, 4, 3, 4,
		1, 5, 2, 5,
		127
	},
	{			/* OSCILLATOR (P7) */
		-6, -7,
		-6, -6,
		-5, -5, -4, -5,
		-4, -4, -3, -4, -2, -4,
		-5, -3, -4, -3, -1, -3, 0, -3, 2, -3,
		-5, -2, 0, -2, 1, -2, 2, -2,
		-4, -1, 2, -1,
		3, 0,
		2, 1, 3, 1,
		2, 2,
		3, 3, 5, 3,
		2, 4, 3, 4, 4, 4, 5, 4,
		5, 5,
		6, 6,
		127
	},
	{			/* OSCILLATOR (P9) */
		-2, -6, -1, -6,
		-4, -5, -3, -5, -2, -5, 0, -5,
		-3, -4, -1, -4, 0, -4,
		-3, -3, -2, -3, -1, -3, 1, -3,
		0, -2, 1, -2,
		0, -1,
		-1, 0, 0, 0, 1, 0,
		-1, 1, 2, 1,
		-2, 2, -1, 2, 0, 2, 2, 2,
		-2, 3, 0, 3, 3, 3,
		-1, 4, 0, 4, 2, 4, 3, 4,
		1, 5, 2, 5,
		2, 6,
		127
	},
	{			/* OSCILLATOR1 (P11) */
		-4, -5,
		-5, -4, -4, -4,
		-4, -3, -3, -3, -1, -3,
		-6, -2, -5, -2, -4, -2, -2, -2, 0, -2,
		-4, -1, -2, -1, 1, -1, 2, -1,
		-4, 0, -3, 0, -2, 0, -1, 0, 0, 0, 1, 0, 3, 0, 4, 0, 5, 0,
		-4, 1, 0, 1, 1, 1, 4, 1,
		2, 2, 3, 2, 4, 2,
		4, 3,
		5, 4,
		127
	},
	{			/* OSCILLATOR2 (P11) */
		-3, -3, -2, -3, 0, -3,
		-3, -2, 0, -2, 1, -2,
		-1, -1, 0, -1, 2, -1,
		-3, 0, -2, 0, -1, 0, 1, 0, 2, 0,
		-2, 1, 0, 1, 1, 1, 3, 1,
		-1, 2, 0, 2, 2, 2, 3, 2,
		1, 3, 2, 3,
		127
	},
	{			/* OSCILLATOR (P14) */
		-2, -3, -1, -3, 0, -3,
		-3, -2, -2, -2, 0, -2,
		-3, -1, 1, -1, 2, -1,
		-3, 0, -2, 0, 0, 0, 1, 0,
		-1, 1, 0, 1, 2, 1, 3, 1,
		-1, 2, 1, 2, 2, 2,
		1, 3,
		127
	},
	{			/* OSCILLATOR (P17) */
		-3, -6,
		-3, -5,
		-5, -4, -4, -4, -3, -4, -2, -4, -1, -4, 0, -4,
		-3, -3, -1, -3, 0, -3,
		-2, -2, -1, -2,
		-2, 0, -1, 0, 2, 0,
		-3, 1, -2, 1, 0, 1, 1, 1,
		-3, 2, 0, 2, 2, 2,
		-2, 3, -1, 3, 1, 3, 2, 3,
		0, 4, 1, 4, 3, 4, 4, 4,
		2, 5, 3, 5,
		2, 6,
		127
	},
	{			/* OSCILLATOR (P18) */
		-5, -4, -3, -4,
		-4, -3, -3, -3, -2, -3,
		-5, -2, -4, -2, -2, -2,
		-6, -1, -5, -1, -3, -1, -2, -1, 0, -1, 1, -1, 2, -1, 4, -1,
		-6, 0, -4, 0, -3, 0, -1, 0, 1, 0, 3, 0, 4, 0, 5, 0, 6, 0,
		-5, 1, -4, 1, -2, 1, -1, 1, 0, 1, 1, 1, 2, 1, 4, 1, 5, 1,
		-3, 2, -2, 2, 0, 2, 2, 2, 3, 2, 4, 2, 6, 2,
		-3, 3, -1, 3, 4, 3,
		127
	},
	{			/* OSCILLATOR (P19) */
		-6, -4, -2, -4,
		-7, -3, -6, -3, -3, -3, -2, -3, -1, -3, 1, -3,
		-7, -2, -5, -2, -4, -2, -2, -2, 0, -2, 1, -2, 2, -2,
		-6, -1, -5, -1, -3, -1, -2, -1, -1, -1, 0, -1, 1, -1, 3, -1,
		-6, 0, -4, 0, -3, 0, 0, 0, 2, 0, 3, 0,
		-4, 1, -2, 1, 0, 1, 1, 1, 2, 1, 4, 1, 5, 1,
		0, 2, 1, 2, 3, 2, 4, 2, 5, 2,
		1, 3, 2, 3, 3, 3, 6, 3,
		3, 4,
		127
	},
	{			/* OSCILLATOR (P22) */
		-5, -5,
		-4, -4,
		-6, -3, -5, -3, -4, -3, -3, -3, -2, -3,
		-4, -2, -2, -2,
		-4, -1, -3, -1, -2, -1, -1, -1, 0, -1,
		-3, 0, -1, 0, 1, 0, 2, 0,
		0, 1, 1, 1, 2, 1, 3, 1,
		0, 2, 1, 2,
		4, 4,
		5, 5, 6, 5,
		127
	},
	{			/* OSCILLATOR (P26) */
		-5, -7,
		-5, -6, -3, -6,
		-6, -5, -5, -5, -4, -5, -3, -5, -2, -5,
		-5, -4, -3, -4, -1, -4, 0, -4,
		-5, -3, -2, -3, -1, -3, 1, -3,
		-3, -2, -2, -2, 1, -2,
		-1, -1, 0, -1, 1, -1, 2, -1, 3, -1,
		1, 0, 3, 0,
		-1, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, 1,
		-4, 2, -3, 2, -1, 2, 1, 2, 3, 2, 5, 2,
		-2, 3, 0, 3, 1, 3, 3, 3,
		2, 4, 3, 4, 4, 4,
		2, 5, 5, 5,
		5, 6,
		127
	},
	{			/* OSCILLATOR (P29) */
		-2, -6,
		-2, -5, -1, -5,
		-3, -4, -2, -4, 0, -4, 1, -4,
		-5, -3, -4, -3, -3, -3, 2, -3, 3, -3, 4, -3,
		-4, -2, -2, -2, 2, -2, 4, -2,
		-3, -1, -2, -1, -1, -1, 0, -1, 3, -1, 4, -1, 5, -1,
		-5, 0, -4, 0, -3, 0, -2, 0, 1, 0, 2, 0, 3, 0,
		-5, 1, -4, 1, -1, 1, 0, 1, 1, 1, 2, 1,
		-4, 2, -3, 2, -2, 2, 0, 2, 2, 2,
		-3, 3, 0, 3,
		1, 5,
		127
	},
	{			/* OSCILLATOR (P46) */
		-2, -4,
		-2, -3, -1, -3, 0, -3,
		-4, -2, -3, -2, -2, -2, 0, -2,
		-5, -1, -3, -1, -1, -1, 0, -1, 1, -1, 2, -1, 3, -1,
		-4, 0, -3, 0, -2, 0, -1, 0, 0, 0, 3, 0,
		-3, 1, -1, 1, 1, 1, 4, 1,
		-4, 2, -3, 2, -2, 2, -1, 2, 0, 2, 1, 2,
		-1, 3,
		-1, 4,
		127
	},
};

static char patterns_6S2a2b4aB2a3a4b[][2 * NUMPTS + 1] =
{
	{			/* GLIDERS */
		-5, -9,
		-5, -8,
		-4, -7, -3, -7,
		-4, -6,
		-3, -5,
		-1, -2,
		-1, -1, 1, -1,
		-1, 0, 1, 0,
		0, 1,
		0, 2,
		2, 5,
		2, 6,
		2, 7,
		3, 8, 5, 8,
		3, 9,
		127
	},
	{			/* SYMMETRIC 4 GLIDER GUN */
		-2, -3, -1, -3, 0, -3,
		-3, -2, -2, -2, 3, -2,
		-2, -1, 0, -1, 1, -1,
		-2, 0, 0, 0, 2, 0, 3, 0,
		-1, 1,
		-1, 2,
		127
	},
	{			/* PUFFER (P18) */
		-2, -4,
		-3, -3, -2, -3, -1, -3, 0, -3,
		-2, -2, 0, -2,
		-2, -1, 1, -1,
		-2, 0, 2, 0,
		-2, 2, 4, 2,
		-1, 3, 0, 3, 1, 3, 2, 3, 3, 3, 4, 3,
		0, 4, 1, 4, 3, 4, 4, 4,
		1, 5, 4, 5,
		127
	},
	{			/* QUASAR (P10) */
		-2, -1, -1, -1, 0, -1,
		-1, 0, 0, 0,
		0, 1,
		127
	},
};

static int  patterns_6rules[] =
{
	(sizeof patterns_6S2b34B2a / sizeof patterns_6S2b34B2a[0]),
	(sizeof patterns_6S2a2b4aB2a3a4b / sizeof patterns_6S2a2b4aB2a3a4b[0])
};

static int  patterns_8rules[] =
{
	(sizeof patterns_8S23B3 / sizeof patterns_8S23B3[0])
};

static paramstruct param_6rules[] =
{
	{
		0x18, 0x0,
		{0x2, 0x0, 0x0},
		{0x1, 0x0, 0x0}
	},
	{
		0x0, 0x0,
		{0x3, 0x0, 0x1},
		{0x1, 0x1, 0x2}
	}
};

static paramstruct param_8rules[] =
{
	{
		0xC, 0x8,
		{0x0, 0x0, 0x0},
		{0x0, 0x0, 0x0}
	}
};

#define LIFE_6S2b34B2a 0
#define LIFE_6GLIDERS 1		/* GLIDER rules are first in param_6rules */
#define LIFE_6S2a2b4aB2a3a4b 1
#define LIFE_6RULES (sizeof param_6rules / sizeof param_6rules[0])
#define LIFE_8S23B3 0
#define LIFE_8GLIDERS 1		/* GLIDER rules are first in param_8rules */
#define LIFE_8RULES (sizeof param_8rules / sizeof param_8rules[0])

static int
codeToPatternedRule(paramstruct param)
{
	unsigned int i;
	int         g;

	switch (local_neighbors) {
		case 6:
			for (i = 0; i < LIFE_6RULES; i++)
				if (param_6rules[i].survival == param.survival &&
				    param_6rules[i].birth == param.birth) {
					for (g = 0; g < maxgroups[neighbor_kind]; g++) {
						if (param_6rules[i].survival_group[g] !=
						    param.survival_group[g] ||
						    param_6rules[i].birth_group[g] !=
						    param.birth_group[g]) {
							break;
						}
					}
					if (g == maxgroups[neighbor_kind])
						return i;
				}
			return LIFE_6RULES;
		case 8:
			for (i = 0; i < LIFE_8RULES; i++)
				if (param_8rules[i].survival == param.survival &&
				    param_8rules[i].birth == param.birth) {
					for (g = 0; g < maxgroups[neighbor_kind]; g++) {
						if (param_8rules[i].survival_group[g] !=
						    param.survival_group[g] ||
						    param_8rules[i].birth_group[g] !=
						    param.birth_group[g]) {
							break;
						}
					}
					if (g == maxgroups[neighbor_kind])
						return i;
				}
			return LIFE_8RULES;
	}
	return 0;
}

static void
copyFromPatternedRule(paramstruct * param, int patterned_rule)
{
	int         i;

	switch (local_neighbors) {
		case 6:
			param->survival = param_6rules[patterned_rule].survival;
			param->birth = param_6rules[patterned_rule].birth;
			for (i = 0; i < maxgroups[neighbor_kind]; i++) {
				param->survival_group[i] =
					param_6rules[patterned_rule].survival_group[i];
				param->birth_group[i] =
					param_6rules[patterned_rule].birth_group[i];
			}
			break;
		case 8:
			param->survival = param_8rules[patterned_rule].survival;
			param->birth = param_8rules[patterned_rule].birth;
			for (i = 0; i < maxgroups[neighbor_kind]; i++) {
				param->survival_group[i] =
					param_8rules[patterned_rule].survival_group[i];
				param->birth_group[i] =
					param_8rules[patterned_rule].birth_group[i];
			}
			break;
	}
}

static void
printRule(paramstruct param)
{
	int         l, g;
	Bool        found;

	(void) fprintf(stdout, "rule (Survival/Birth neighborhood): S");
	for (l = 0; l <= local_neighbors; l++) {
		if (param.survival & (1 << l))
			(void) fprintf(stdout, "%d", l);
		else if (l >= FIRSTGROUP && l < FIRSTGROUP + maxgroups[neighbor_kind])
			for (g = 0; g < groupnumber[neighbor_kind][l - FIRSTGROUP]; g++) {
				if (param.survival_group[l - FIRSTGROUP] & (1 << g))
					(void) fprintf(stdout, "%d%c", l, 'a' + g);
			}
	} (void) fprintf(stdout, "/B");
	for (l = 0; l <= local_neighbors; l++) {
		if (param.birth & (1 << l))
			(void) fprintf(stdout, "%d", l);
		else if (l >= FIRSTGROUP && l < FIRSTGROUP + maxgroups[neighbor_kind])
			for (g = 0; g < groupnumber[neighbor_kind][l - FIRSTGROUP]; g++) {
				if (param.birth_group[l - FIRSTGROUP] & (1 << g))
					(void) fprintf(stdout, "%d%c", l, 'a' + g);
			}
	}
	(void) fprintf(stdout, "\nbinary rule: Survival 0x%X, Birth 0x%X\n",
		       param.survival, param.birth);
	found = False;
	for (l = 0; l <= maxgroups[neighbor_kind]; l++) {
		if (param.survival_group[l] || param.birth_group[l]) {
			found = True;
			break;
		}
	}
	if (found)
		for (l = 0; l < maxgroups[neighbor_kind]; l++) {
			(void) fprintf(stdout,
				       "groups in neighborhood %d: Survival 0x%X, Birth 0x%X\n",
				       l + FIRSTGROUP, param.survival_group[l], param.birth_group[l]);
		}
}

static int
position_of_neighbor(lifestruct * lp, int n, int col, int row)
{
	int         dir = n * 360 / local_neighbors;

	if (local_neighbors == 6) {
		switch (dir) {
			case 0:
				col = (col + 1 == lp->ncols) ? 0 : col + 1;
				break;
			case 60:
				if (!(row & 1))
					col = (col + 1 == lp->ncols) ? 0 : col + 1;
				row = (!row) ? lp->nrows - 1 : row - 1;
				break;
			case 120:
				if (row & 1)
					col = (!col) ? lp->ncols - 1 : col - 1;
				row = (!row) ? lp->nrows - 1 : row - 1;
				break;
			case 180:
				col = (!col) ? lp->ncols - 1 : col - 1;
				break;
			case 240:
				if (row & 1)
					col = (!col) ? lp->ncols - 1 : col - 1;
				row = (row + 1 == lp->nrows) ? 0 : row + 1;
				break;
			case 300:
				if (!(row & 1))
					col = (col + 1 == lp->ncols) ? 0 : col + 1;
				row = (row + 1 == lp->nrows) ? 0 : row + 1;
				break;
			default:
				(void) fprintf(stderr, "wrong direction %d\n", dir);
		}
	} else if (local_neighbors == 4 || local_neighbors == 8) {
		switch (dir) {
			case 0:
				col = (col + 1 == lp->ncols) ? 0 : col + 1;
				break;
			case 45:
				col = (col + 1 == lp->ncols) ? 0 : col + 1;
				row = (!row) ? lp->nrows - 1 : row - 1;
				break;
			case 90:
				row = (!row) ? lp->nrows - 1 : row - 1;
				break;
			case 135:
				col = (!col) ? lp->ncols - 1 : col - 1;
				row = (!row) ? lp->nrows - 1 : row - 1;
				break;
			case 180:
				col = (!col) ? lp->ncols - 1 : col - 1;
				break;
			case 225:
				col = (!col) ? lp->ncols - 1 : col - 1;
				row = (row + 1 == lp->nrows) ? 0 : row + 1;
				break;
			case 270:
				row = (row + 1 == lp->nrows) ? 0 : row + 1;
				break;
			case 315:
				col = (col + 1 == lp->ncols) ? 0 : col + 1;
				row = (row + 1 == lp->nrows) ? 0 : row + 1;
				break;
			default:
				(void) fprintf(stderr, "wrong direction %d\n", dir);
		}
	} else {		/* TRI */
		if ((col + row) % 2) {	/* right */
			switch (dir) {
				case 0:
					col = (!col) ? lp->ncols - 1 : col - 1;
					break;
				case 30:
				case 40:
					col = (!col) ? lp->ncols - 1 : col - 1;
					row = (row + 1 == lp->nrows) ? 0 : row + 1;
					break;
				case 60:
					col = (!col) ? lp->ncols - 1 : col - 1;
					if (row + 1 == lp->nrows)
						row = 1;
					else if (row + 2 == lp->nrows)
						row = 0;
					else
						row = row + 2;
					break;
				case 80:
				case 90:
					if (row + 1 == lp->nrows)
						row = 1;
					else if (row + 2 == lp->nrows)
						row = 0;
					else
						row = row + 2;
					break;
				case 120:
					row = (row + 1 == lp->nrows) ? 0 : row + 1;
					break;
				case 150:
				case 160:
					col = (col + 1 == lp->ncols) ? 0 : col + 1;
					row = (row + 1 == lp->nrows) ? 0 : row + 1;
					break;
				case 180:
					col = (col + 1 == lp->ncols) ? 0 : col + 1;
					break;
				case 200:
				case 210:
					col = (col + 1 == lp->ncols) ? 0 : col + 1;
					row = (!row) ? lp->nrows - 1 : row - 1;
					break;
				case 240:
					row = (!row) ? lp->nrows - 1 : row - 1;
					break;
				case 270:
				case 280:
					if (!row)
						row = lp->nrows - 2;
					else if (!(row - 1))
						row = lp->nrows - 1;
					else
						row = row - 2;
					break;
				case 300:
					col = (!col) ? lp->ncols - 1 : col - 1;
					if (!row)
						row = lp->nrows - 2;
					else if (!(row - 1))
						row = lp->nrows - 1;
					else
						row = row - 2;
					break;
				case 320:
				case 330:
					col = (!col) ? lp->ncols - 1 : col - 1;
					row = (!row) ? lp->nrows - 1 : row - 1;
					break;
				default:
					(void) fprintf(stderr, "wrong direction %d\n", dir);
			}
		} else {	/* left */
			switch (dir) {
				case 0:
					col = (col + 1 == lp->ncols) ? 0 : col + 1;
					break;
				case 30:
				case 40:
					col = (col + 1 == lp->ncols) ? 0 : col + 1;
					row = (!row) ? lp->nrows - 1 : row - 1;
					break;
				case 60:
					col = (col + 1 == lp->ncols) ? 0 : col + 1;
					if (!row)
						row = lp->nrows - 2;
					else if (row == 1)
						row = lp->nrows - 1;
					else
						row = row - 2;
					break;
				case 80:
				case 90:
					if (!row)
						row = lp->nrows - 2;
					else if (row == 1)
						row = lp->nrows - 1;
					else
						row = row - 2;
					break;
				case 120:
					row = (!row) ? lp->nrows - 1 : row - 1;
					break;
				case 150:
				case 160:
					col = (!col) ? lp->ncols - 1 : col - 1;
					row = (!row) ? lp->nrows - 1 : row - 1;
					break;
				case 180:
					col = (!col) ? lp->ncols - 1 : col - 1;
					break;
				case 200:
				case 210:
					col = (!col) ? lp->ncols - 1 : col - 1;
					row = (row + 1 == lp->nrows) ? 0 : row + 1;
					break;
				case 240:
					row = (row + 1 == lp->nrows) ? 0 : row + 1;
					break;
				case 270:
				case 280:
					if (row + 1 == lp->nrows)
						row = 1;
					else if (row + 2 == lp->nrows)
						row = 0;
					else
						row = row + 2;
					break;
				case 300:
					col = (col + 1 == lp->ncols) ? 0 : col + 1;
					if (row + 1 == lp->nrows)
						row = 1;
					else if (row + 2 == lp->nrows)
						row = 0;
					else
						row = row + 2;
					break;
				case 320:
				case 330:
					col = (col + 1 == lp->ncols) ? 0 : col + 1;
					row = (row + 1 == lp->nrows) ? 0 : row + 1;
					break;
				default:
					(void) fprintf(stderr, "wrong direction %d\n", dir);
			}
		}
	}

	return (row * lp->ncols + col);
}

static void
parseRule(ModeInfo * mi)
{
	int         n, g, l;
	char        serving = 0;
	static Bool found = False;

	if (found)
		return;
	input_param.survival = input_param.birth = 0;
	for (n = 0; n < MAXGROUPS; n++) {
		input_param.survival_group[n] = input_param.birth_group[n] = 0;
	}
	if (callahan) {
		local_neighbors = 6;
		neighbor_kind = 2;
		found = True;
		input_param.survival = param_6rules[0].survival;
		input_param.birth = param_6rules[0].birth;
		for (n = 0; n < maxgroups[neighbor_kind]; n++) {
			input_param.survival_group[n] = param_6rules[0].survival_group[n];
			input_param.birth_group[n] = param_6rules[0].birth_group[n];
		}
		return;
	} else if (andreen) {
		local_neighbors = 6;
		neighbor_kind = 2;
		found = True;
		input_param.survival = param_6rules[1].survival;
		input_param.birth = param_6rules[1].birth;
		for (n = 0; n < maxgroups[neighbor_kind]; n++) {
			input_param.survival_group[n] = param_6rules[1].survival_group[n];
			input_param.birth_group[n] = param_6rules[1].birth_group[n];
		}
		return;
	}
	if (rule) {
		n = 0;
		while (rule[n]) {
			if (rule[n] == 'P') {
				allPatterns = True;
				found = True;
				if (MI_IS_VERBOSE(mi))
					(void) fprintf(stdout, "rule: All rules with known patterns\n");
				return;
			} else if (rule[n] == 'G') {
				allGliders = True;
				found = True;
				if (MI_IS_VERBOSE(mi))
					(void) fprintf(stdout, "rule: All rules with known gliders\n");
				return;
			} else if (rule[n] == 'S' || rule[n] == 'E' || rule[n] == 'L') {
				serving = 'S';
			} else if (rule[n] == 'B') {
				serving = 'B';
			} else {
				l = rule[n] - '0';
				if (l >= 0 && l <= 9 && l <= local_neighbors) {		/* no 10, 11, 12 */
					g = rule[n + 1] - 'a';
					if (l >= FIRSTGROUP && l < FIRSTGROUP + maxgroups[neighbor_kind] &&
					    g >= 0 && g < groupnumber[neighbor_kind][l]) {	/* Groupings */
						if (serving == 'S') {
							found = True;
							input_param.survival_group[l - FIRSTGROUP] |= (1 << g);
						} else if (serving == 'B') {
							found = True;
							input_param.birth_group[l - FIRSTGROUP] |= (1 << g);
						}
					} else {
						if (serving == 'S') {
							found = True;
							input_param.survival |= (1 << l);
						} else if (serving == 'B') {
							found = True;
							input_param.birth |= (1 << l);
						}
					}
				}
			}
			n++;
		}
	}
	if (!found) {		/* Default to Conway's rule if very stupid */
		allGliders = True;
		found = True;
		if (MI_IS_VERBOSE(mi))
			(void) fprintf(stdout,
			"rule: Defaulting to all rules with known gliders\n");
		return;
	}
	if (MI_IS_VERBOSE(mi))
		printRule(input_param);
}

static void
parseFile()
{
	FILE       *file;
	static Bool done = False;
	int         firstx = 0, x = 0, y = 0, i = 0;
	char        line[256], c;

	if (done)
		return;
	done = True;
	if (!lifefile || !*lifefile || ((file = my_fopen(lifefile, "r")) == NULL)) {
		/*(void) fprintf(stderr, "could not read file \"%s\"\n", lifefile); */
		return;
	}
	for (;;) {
		if (!fgets(line, 256, file)) {
			(void) fprintf(stderr, "could not read header of file \"%s\"\n",
				       lifefile);
			(void) fclose(file);
			return;
		}
		if (strncmp(line, "#P", (size_t) 2) == 0 &&
		    sscanf(line, "#P %d %d", &x, &y) == 2)
			break;
	}
	c = getc(file);
	while (c != EOF && !(c == '0' || c == 'O' || c == '*' || c == '.')) {
		c = getc(file);
	}
	if (c == EOF || x <= -127 || y <= -127 || x >= 127 || y >= 127) {
		(void) fprintf(stderr, "corrupt file \"%s\" or file to large\n",
			       lifefile);
		(void) fclose(file);
		return;
	}
	firstx = x;
	filePattern = (char *) malloc((2 * NUMFILEPTS + 1) * sizeof (char));

	while (c != EOF && x < 127 && y < 127 && i < 2 * NUMFILEPTS) {
		if (c == '0' || c == 'O' || c == '*') {
			filePattern[i++] = x++;
			filePattern[i++] = y;
		} else if (c == '.') {
			x++;
		} else if (c == '\n') {
			x = firstx;
			y++;
		}
		c = getc(file);
	}
	(void) fclose(file);
	filePattern[i] = 127;
}

static void
init_list(lifestruct * lp, int state)
{
	/* Waste some space at the beginning and end of list
	   so we do not have to complicated checks against falling off the ends. */
	lp->last[state] = (CellList *) malloc(sizeof (CellList));
	lp->first[state] = (CellList *) malloc(sizeof (CellList));
	lp->first[state]->previous = lp->last[state]->next = NULL;
	lp->first[state]->next = lp->last[state]->previous = NULL;
	lp->first[state]->next = lp->last[state];
	lp->last[state]->previous = lp->first[state];
}

static void
addto_list(lifestruct * lp, int state, cellstruct info)
{
	CellList   *curr;

	curr = (CellList *) malloc(sizeof (CellList));
	lp->last[state]->previous->next = curr;
	curr->previous = lp->last[state]->previous;
	curr->next = lp->last[state];
	lp->last[state]->previous = curr;
	curr->info = info;
	if (info.position >= 0) {
		lp->arr[info.position] = curr;
		lp->ncells[state]++;
	}
}
static void
removefrom_list(lifestruct * lp, int state, CellList * curr)
{
	curr->previous->next = curr->next;
	curr->next->previous = curr->previous;
	if (curr->info.position >= 0) {
		lp->arr[curr->info.position] = NULL;
		lp->ncells[state]--;
	}
	(void) free((void *) curr);
}

#ifdef DEBUG
static void
print_state(ModeInfo * mi, int state)
{
	lifestruct *lp = &lifes[MI_SCREEN(mi)];
	CellList   *curr;
	int         i = 0;

	curr = lp->first[state]->next;
	(void) printf("state %d\n", state);
	while (curr != lp->last[state]) {
		(void) printf("%d: position %ld,	age %d, state %d, toggle %d\n",
			      i, curr->info.position, curr->info.age,
			      curr->info.state, curr->info.toggle);
		curr = curr->next;
		i++;
	}
}

#endif

static void
flush_list(lifestruct * lp, int state)
{
	while (lp->last[state]->previous != lp->first[state]) {
		CellList   *curr = lp->last[state]->previous;

		curr->previous->next = lp->last[state];
		lp->last[state]->previous = curr->previous;
		(void) free((void *) curr);
	}
	lp->ncells[state] = 0;
}


static void
draw_cell(ModeInfo * mi, cellstruct info)
{
	Display    *display = MI_DISPLAY(mi);
	lifestruct *lp = &lifes[MI_SCREEN(mi)];
	GC          gc = lp->backGC;
	int         col, row;

	col = (int) (info.position % lp->ncols);
	row = (int) (info.position / lp->ncols);
	if (info.state == LIVE) {
		if (MI_NPIXELS(mi) > 2)
			XSetForeground(display, gc, MI_PIXEL(mi, info.age));
		else
			XSetForeground(display, gc, MI_WHITE_PIXEL(mi));
	} else
		XSetForeground(display, gc, lp->black);

	if (local_neighbors == 6) {
		int         ccol = 2 * col + !(row & 1), crow = 2 * row;

		lp->shape.hexagon[0].x = lp->xb + ccol * lp->xs;
		lp->shape.hexagon[0].y = lp->yb + crow * lp->ys;
		if (lp->xs == 1 && lp->ys == 1)
			XFillRectangle(MI_DISPLAY(mi), MI_WINDOW(mi),
				       lp->backGC, lp->shape.hexagon[0].x, lp->shape.hexagon[0].y, 1, 1);
		else
			XFillPolygon(MI_DISPLAY(mi), MI_WINDOW(mi), lp->backGC,
			    lp->shape.hexagon, 6, Convex, CoordModePrevious);
	} else if (local_neighbors == 4 || local_neighbors == 8) {
		if (lp->pixelmode || info.state == DEAD)
			XFillRectangle(display, MI_WINDOW(mi), gc,
				       lp->xb + lp->xs * col, lp->yb + lp->ys * row,
				 lp->xs - (lp->xs > 3 && lp->pixelmode),
				 lp->ys - (lp->ys > 3 && lp->pixelmode));
		else
/*-
 * PURIFY 4.0.1 on SunOS4 and on Solaris 2 reports a 132 byte memory leak on
 * the next line */
			(void) XPutImage(display, MI_WINDOW(mi), gc, lp->logo,
			  0, 0, lp->xb + lp->xs * col, lp->yb + lp->ys * row,
					 lp->logo->width, lp->logo->height);
	} else {		/* TRI */
		int         orient = (col + row) % 2;	/* O left 1 right */

		lp->shape.triangle[orient][0].x = lp->xb + col * lp->xs;
		lp->shape.triangle[orient][0].y = lp->yb + row * lp->ys;
		if (lp->xs <= 3 || lp->ys <= 3)
			XFillRectangle(MI_DISPLAY(mi), MI_WINDOW(mi), lp->backGC,
			((orient) ? -1 : 1) + lp->shape.triangle[orient][0].x,
				       lp->shape.triangle[orient][0].y, 1, 1);
		else {
			if (orient)
				lp->shape.triangle[orient][0].x += (lp->xs / 2 - 1);
			else
				lp->shape.triangle[orient][0].x -= (lp->xs / 2 - 1);
			XFillPolygon(MI_DISPLAY(mi), MI_WINDOW(mi), lp->backGC,
				     lp->shape.triangle[orient], 3, Convex, CoordModePrevious);

		}
	}
}

static void
setcelltoggles(ModeInfo * mi, int col, int row)
{
	lifestruct *lp = &lifes[MI_SCREEN(mi)];
	int         position;
	CellList   *curr;

	position = row * lp->ncols + col;
	curr = lp->arr[position];
	if (!curr) {
		(void) fprintf(stderr, "state toggling but not on list\n");
		return;
	}
	curr->info.toggle = True;
}

static void
setcellfromtoggle(ModeInfo * mi, int col, int row)
{
	lifestruct *lp = &lifes[MI_SCREEN(mi)];
	int         neighbor, n, position;
	cellstruct  info;
	CellList   *curr, *currn;

	position = row * lp->ncols + col;
	curr = lp->arr[position];
	if ((curr && curr->info.state == DEAD && curr->info.toggle) ||
	    (curr && curr->info.state == LIVE && !curr->info.toggle)) {
		for (n = 0; n < local_neighbors; n++) {
			neighbor = position_of_neighbor(lp, n, col, row);
			currn = lp->arr[neighbor];
			if (!currn) {
				info.position = neighbor;
				info.age = 0;
				info.state = DEAD;
				info.toggle = False;
				addto_list(lp, DEAD, info);
			}
		}
	}
	if (curr && curr->info.state == DEAD && curr->info.toggle) {
		removefrom_list(lp, DEAD, curr);
		info.age = 0;
		info.position = position;
		info.toggle = False;
		info.state = LIVE;
		addto_list(lp, LIVE, info);
		draw_cell(mi, info);
	} else if (curr && curr->info.state == LIVE && !curr->info.toggle) {
		info = curr->info;
		/* if we aren't up to blue yet, then keep aging the cell. */
		if ((MI_NPIXELS(mi) > 2) &&
		    (info.age < (unsigned short) (MI_NPIXELS(mi) * 0.7))) {
			++(info.age);
			curr->info.age = info.age;
			draw_cell(mi, info);
		}
	}
}

static void
setcell(ModeInfo * mi, int col, int row, int state)
{
	lifestruct *lp = &lifes[MI_SCREEN(mi)];
	int         neighbor, n, position;
	cellstruct  info;
	CellList   *curr, *currn;

	position = row * lp->ncols + col;
	curr = lp->arr[position];
	if (state == LIVE) {
		if (curr && curr->info.state == DEAD) {
			removefrom_list(lp, DEAD, curr);
			curr = NULL;
		}
		if (!curr) {
			for (n = 0; n < local_neighbors; n++) {
				neighbor = position_of_neighbor(lp, n, col, row);
				currn = lp->arr[neighbor];
				if (!currn) {
					info.age = 0;
					info.position = neighbor;
					info.state = DEAD;
					info.toggle = False;
					addto_list(lp, DEAD, info);
				}
			}
			info.age = 0;
			info.position = position;
			info.state = LIVE;
			info.toggle = False;
			addto_list(lp, LIVE, info);
			draw_cell(mi, info);
		} else {
			info = curr->info;
			info.age = 0;
			draw_cell(mi, info);
		}
	} else if (curr && curr->info.state == LIVE) {
		info.age = 0;
		info.position = position;
		info.state = DEAD;
		info.toggle = False;
		removefrom_list(lp, LIVE, curr);
		addto_list(lp, DEAD, info);	/* Just in case... */
		draw_cell(mi, info);
	}
}

static void
alloc_cells(lifestruct * lp)
{
	lp->arr = (CellList **) calloc(lp->npositions, sizeof (CellList *));
}

static void
free_cells(lifestruct * lp)
{
	if (lp->arr != NULL)
		(void) free((void *) lp->arr);
	lp->arr = NULL;
}

#if 0
static int
n_neighbors(lifestruct * lp, CellList * curr)
{
	int         col, row, n, p, count = 0;

	col = curr->info.position % lp->ncols;
	row = curr->info.position / lp->ncols;
	for (n = 0; n < local_neighbors; n++) {
		p = position_of_neighbor(lp, n, col, row);
		if (lp->arr[p] && lp->arr[p]->info.state == LIVE) {
			count++;
		}
	}
	return count;
}
#endif

static int
ng_neighbors(lifestruct * lp, CellList * curr, int *group)
{
	int         col, row, n, p, count = 0, gcount = 0;

	col = (int) (curr->info.position % lp->ncols);
	row = (int) (curr->info.position / lp->ncols);
	for (n = 0; n < local_neighbors; n++) {
		p = position_of_neighbor(lp, n, col, row);
		gcount <<= 1;
		if (lp->arr[p] && lp->arr[p]->info.state == LIVE) {
			count++;
			gcount++;
		}
	}
	*group = gcount;
	return count;
}

static void
RandomSoup(ModeInfo * mi, int n, int v)
{
	lifestruct *lp = &lifes[MI_SCREEN(mi)];
	int         row, col;

	v /= 2;
	if (v < 1)
		v = 1;
	for (row = lp->nrows / 2 - v; row < lp->nrows / 2 + v; ++row)
		for (col = lp->ncols / 2 - v; col < lp->ncols / 2 + v; ++col)
			if (NRAND(100) < n && col > 1 && row > 1 &&
			    col < lp->ncols && row < lp->nrows)
				setcell(mi, col, row, LIVE);
	if (MI_IS_VERBOSE(mi))
		(void) fprintf(stdout, "random pattern\n");
}

static void
GetPattern(ModeInfo * mi, int pattern_rule, int pattern)
{
	lifestruct *lp = &lifes[MI_SCREEN(mi)];
	int         row, col;
	char       *patptr = NULL;

	if (filePattern) {
		patptr = &filePattern[0];
	} else {
		switch (local_neighbors) {
			case 6:
				switch (pattern_rule) {
					case LIFE_6S2b34B2a:
						patptr = &patterns_6S2b34B2a[pattern][0];
						break;
					case LIFE_6S2a2b4aB2a3a4b:
						patptr = &patterns_6S2a2b4aB2a3a4b[pattern][0];
						break;
				}
				break;
			case 8:
				switch (pattern_rule) {
					case LIFE_8S23B3:
						patptr = &patterns_8S23B3[pattern][0];
						break;
				}
				break;
		}
	}
	while ((col = *patptr++) != 127) {
		row = *patptr++;
		col += lp->ncols / 2;
		if (local_neighbors == 6) {
			if (row < 0)
				col += (lp->nrows / 2 % 2) ? -row / 2 : -(row - 1) / 2;
			else
				col += (lp->nrows / 2 % 2) ? -(row + 1) / 2 : -row / 2;
		}
		row += lp->nrows / 2;

		if (col >= 0 && row >= 0 && col < lp->ncols && row < lp->nrows)
			setcell(mi, col, row, LIVE);
	}
	if (MI_IS_VERBOSE(mi) && !filePattern)
		(void) fprintf(stdout, "table number %d\n", pattern);
}

static void
shooter(ModeInfo * mi)
{
	lifestruct *lp = &lifes[MI_SCREEN(mi)];
	int         hsp, vsp, hoff = 1, voff = 1, temp;

	/* Generate the glider at the edge of the screen */
	if (local_neighbors == 6 && lp->patterned_rule == LIFE_6S2b34B2a) {
		/*-
     * Generate gliders on left and right.... more could be done from top and
     * bottom... also phase with voff
     */
		hsp = (LRAND() & 1) ? 0 : lp->ncols - 1;
		hsp = lp->ncols - 1;
		temp = MIN(lp->nrows, 12);
		vsp = lp->nrows / 2 + NRAND(temp) - temp / 2;
		if (hsp > lp->ncols / 2) {
			hoff = -1;
			temp = (vsp % 2) ? 0 : hoff;
		} else
			temp = (vsp % 2) ? hoff : 0;

		setcell(mi, hsp + temp + 2 * hoff, vsp + 4 * voff, LIVE);
		setcell(mi, hsp + 3 * hoff, vsp + 3 * voff, LIVE);
		setcell(mi, hsp + temp + 3 * hoff, vsp + 2 * voff, LIVE);
		setcell(mi, hsp + temp + 0 * hoff, vsp + 2 * voff, LIVE);
		setcell(mi, hsp + 4 * hoff, vsp + 1 * voff, LIVE);
		setcell(mi, hsp + temp + 3 * hoff, vsp + 0 * voff, LIVE);
	} else if (local_neighbors == 8 && lp->patterned_rule == LIFE_8S23B3) {
		if (LRAND() & 1) {
			hsp = (LRAND() & 1) ? 0 : lp->ncols - 1;
			vsp = NRAND(lp->nrows);
		} else {
			vsp = (LRAND() & 1) ? 0 : lp->nrows - 1;
			hsp = NRAND(lp->ncols);
		}
		if (vsp > lp->nrows / 2)
			voff = -1;
		if (hsp > lp->ncols / 2)
			hoff = -1;
		setcell(mi, hsp + 2 * hoff, vsp + 0 * voff, LIVE);
		setcell(mi, hsp + 2 * hoff, vsp + 1 * voff, LIVE);
		setcell(mi, hsp + 2 * hoff, vsp + 2 * voff, LIVE);
		setcell(mi, hsp + 1 * hoff, vsp + 2 * voff, LIVE);
		setcell(mi, hsp + 0 * hoff, vsp + 1 * voff, LIVE);
	}
}

static void
init_stuff(ModeInfo * mi)
{
	Display    *display = MI_DISPLAY(mi);
	Window      window = MI_WINDOW(mi);
	lifestruct *lp = &lifes[MI_SCREEN(mi)];

	if (!lp->logo)
		getImage(mi, &lp->logo, CELL_WIDTH, CELL_HEIGHT, CELL_BITS,
#if defined( USE_XPM ) || defined( USE_XPMINC )
			 DEFAULT_XPM, CELL_NAME,
#endif
			 &lp->graphics_format, &lp->cmap, &lp->black);
#ifndef STANDALONE
	if (lp->cmap != None) {
		setColormap(display, window, lp->cmap, MI_IS_INWINDOW(mi));
		if (lp->backGC == None) {
			XGCValues   xgcv;

			xgcv.background = lp->black;
			lp->backGC = XCreateGC(display, window, GCBackground, &xgcv);
		}
	} else
#endif /* STANDALONE */
	{
		lp->black = MI_BLACK_PIXEL(mi);
		lp->backGC = MI_GC(mi);
	}
}

static void
free_stuff(Display * display, lifestruct * lp)
{
	if (lp->cmap != None) {
		XFreeColormap(display, lp->cmap);
		if (lp->backGC != None) {
			XFreeGC(display, lp->backGC);
			lp->backGC = None;
		}
		lp->cmap = None;
	} else
		lp->backGC = None;
	if (lp->logo)
		destroyImage(&lp->logo, &lp->graphics_format);
}

void
init_life(ModeInfo * mi)
{
	lifestruct *lp;
	int         size = MI_SIZE(mi), npats, i;

	if (lifes == NULL) {
		if ((lifes = (lifestruct *) calloc(MI_NUM_SCREENS(mi),
					       sizeof (lifestruct))) == NULL)
			return;
	}
	lp = &lifes[MI_SCREEN(mi)];

	lp->generation = 0;
	lp->redrawing = 0;

	if (!local_neighbors) {
		for (i = 0; i < NEIGHBORKINDS; i++) {
			if (neighbors == plots[i]) {
				local_neighbors = neighbors;
				neighbor_kind = i;
				break;
			}
			if (i == NEIGHBORKINDS - 1) {
#if 0
				local_neighbors = plots[NRAND(NEIGHBORKINDS)];
				local_neighbors = (LRAND() & 1) ? 4 : 8;
				neighbor_kind = (local_neighbors == 4) ? 1 : 3;
#else
				local_neighbors = 8;
				neighbor_kind = 3;
#endif
				break;
			}
		}
	}
	parseRule(mi);
	parseFile();
	if (allPatterns) {
		switch (local_neighbors) {
			case 6:
				lp->patterned_rule = NRAND(LIFE_6RULES);
				break;
			case 8:
				lp->patterned_rule = NRAND(LIFE_8RULES);
				break;
		}
		copyFromPatternedRule(&lp->param, lp->patterned_rule);
		if (MI_IS_VERBOSE(mi))
			printRule(lp->param);
	} else if (allGliders) {
		switch (local_neighbors) {
			case 6:
				lp->patterned_rule = NRAND(LIFE_6GLIDERS);
				break;
			case 8:
				lp->patterned_rule = NRAND(LIFE_8GLIDERS);
				break;
		}
		copyFromPatternedRule(&lp->param, lp->patterned_rule);
		if (MI_IS_VERBOSE(mi))
			printRule(lp->param);
	} else {
		lp->param.survival = input_param.survival;
		lp->param.birth = input_param.birth;
		for (i = 0; i < maxgroups[neighbor_kind]; i++) {
			lp->param.survival_group[i] = input_param.survival_group[i];
			lp->param.birth_group[i] = input_param.birth_group[i];
		}
		lp->patterned_rule = codeToPatternedRule(lp->param);
	}
	lp->width = MI_WIDTH(mi);
	lp->height = MI_HEIGHT(mi);

	if (lp->first[0])
		for (i = 0; i < STATES; i++)
			flush_list(lp, i);
	else
		for (i = 0; i < STATES; i++)
			init_list(lp, i);
	free_cells(lp);

	if (local_neighbors == 6) {
		int         nccols, ncrows, i;

		if (lp->width < 2)
			lp->width = 2;
		if (lp->height < 4)
			lp->height = 4;
		if (size < -MINSIZE)
			lp->ys = NRAND(MIN(-size, MAX(MINSIZE, MIN(lp->width, lp->height) /
				      MINGRIDSIZE)) - MINSIZE + 1) + MINSIZE;
		else if (size < MINSIZE) {
			if (!size)
				lp->ys = MAX(MINSIZE, MIN(lp->width, lp->height) / (4 * MINGRIDSIZE));
			else
				lp->ys = MINSIZE;
		} else
			lp->ys = MIN(size, MAX(MINSIZE, MIN(lp->width, lp->height) /
					       MINGRIDSIZE));
		lp->xs = lp->ys;
		nccols = MAX(lp->width / lp->xs - 2, 2);
		ncrows = MAX(lp->height / lp->ys - 1, 2);
		lp->ncols = nccols / 2;
		lp->nrows = 2 * (ncrows / 4);
		lp->xb = (lp->width - lp->xs * nccols) / 2 + lp->xs / 2;
		lp->yb = (lp->height - lp->ys * (ncrows / 2) * 2) / 2 + lp->ys;
		for (i = 0; i < 6; i++) {
			lp->shape.hexagon[i].x = (lp->xs - 1) * hexagonUnit[i].x;
			lp->shape.hexagon[i].y = ((lp->ys - 1) * hexagonUnit[i].y / 2) * 4 / 3;
		}
		lp->black = MI_BLACK_PIXEL(mi);
		lp->backGC = MI_GC(mi);
	} else if (local_neighbors == 4 || local_neighbors == 8) {
		init_stuff(mi);
		if (lp->width < 2)
			lp->width = 2;
		if (lp->height < 2)
			lp->height = 2;
#if 0
		if (size == 0 && !MI_IS_ICONIC(mi)) {
			lp->pixelmode = False;
			lp->xs = lp->logo->width;
			lp->ys = lp->logo->height;
		}
#else
		if (size == 0 ||
		    MINGRIDSIZE * size > lp->width || MINGRIDSIZE * size > lp->height) {
			if (lp->width > MINGRIDSIZE * lp->logo->width &&
			    lp->height > MINGRIDSIZE * lp->logo->height) {
				lp->pixelmode = False;
				lp->xs = lp->logo->width;
				lp->ys = lp->logo->height;
			} else {
				lp->pixelmode = True;
				lp->xs = lp->ys = MAX(MINSIZE, MIN(lp->width, lp->height) /
						      MINGRIDSIZE);
			}
		}
#endif
		else {
			lp->pixelmode = True;
			if (size < -MINSIZE)
				lp->ys = NRAND(MIN(-size, MAX(MINSIZE, MIN(lp->width, lp->height) /
				      MINGRIDSIZE)) - MINSIZE + 1) + MINSIZE;
			else if (size < MINSIZE)
				lp->ys = MINSIZE;
			else
				lp->ys = MIN(size, MAX(MINSIZE, MIN(lp->width, lp->height) /
						       MINGRIDSIZE));
			lp->xs = lp->ys;
		}
		lp->ncols = MAX(lp->width / lp->xs, 4);
		lp->nrows = MAX(lp->height / lp->ys, 4);
		lp->xb = (lp->width - lp->xs * lp->ncols) / 2;
		lp->yb = (lp->height - lp->ys * lp->nrows) / 2;
	} else {		/* TRI */
		int         orient, i;

		lp->black = MI_BLACK_PIXEL(mi);
		lp->backGC = MI_GC(mi);
		if (lp->width < 2)
			lp->width = 2;
		if (lp->height < 2)
			lp->height = 2;
		if (size < -MINSIZE)
			lp->ys = NRAND(MIN(-size, MAX(MINSIZE, MIN(lp->width, lp->height) /
				      MINGRIDSIZE)) - MINSIZE + 1) + MINSIZE;
		else if (size < MINSIZE) {
			if (!size)
				lp->ys = MAX(MINSIZE, MIN(lp->width, lp->height) / (4 * MINGRIDSIZE));
			else
				lp->ys = MINSIZE;
		} else
			lp->ys = MIN(size, MAX(MINSIZE, MIN(lp->width, lp->height) /
					       MINGRIDSIZE));
		lp->xs = (int) (1.52 * lp->ys);
		lp->ncols = (MAX(lp->width / lp->xs - 1, 2) / 2) * 2;
		lp->nrows = (MAX(lp->height / lp->ys - 1, 2) / 2) * 2;
		lp->xb = (lp->width - lp->xs * lp->ncols) / 2 + lp->xs / 2;
		lp->yb = (lp->height - lp->ys * lp->nrows) / 2 + lp->ys / 2;
		for (orient = 0; orient < 2; orient++) {
			for (i = 0; i < 3; i++) {
				lp->shape.triangle[orient][i].x =
					(lp->xs - 2) * triangleUnit[orient][i].x;
				lp->shape.triangle[orient][i].y =
					(lp->ys - 2) * triangleUnit[orient][i].y;
			}
		}
	}
	lp->npositions = lp->nrows * lp->ncols;

	MI_CLEARWINDOWCOLORMAP(mi, lp->backGC, lp->black);
	lp->painted = False;
	alloc_cells(lp);

	lp->patterned_rule = codeToPatternedRule(lp->param);
	npats = 0;
	switch (local_neighbors) {
		case 6:
			if ((unsigned) lp->patterned_rule < LIFE_6RULES)
				npats = patterns_6rules[lp->patterned_rule];
			break;
		case 8:
			if ((unsigned) lp->patterned_rule < LIFE_8RULES)
				npats = patterns_8rules[lp->patterned_rule];
			break;
	}
	lp->pattern = NRAND(npats + 2);
	if (lp->pattern >= npats && !filePattern)
		RandomSoup(mi, 30, MAX(2 * MIN(lp->nrows, lp->ncols) / 3, 15));
	else
		GetPattern(mi, lp->patterned_rule, lp->pattern);
}

void
draw_life(ModeInfo * mi)
{
	lifestruct *lp = &lifes[MI_SCREEN(mi)];
	CellList   *middle[STATES];	/* To distinguish between old and new stuff */
	CellList   *curr;
	cellstruct  info;
	int         i, count, gcount;

/*-
 * LIVE list are the on cells
 * DEAD list are the cells that may go on in the next iteration.
 * Init plan:
     Create live list and dead list which border all live cells
       (no good for rules like 0000 :) )
 * Big loop plan:
     Setup toggles, toggle state next iteration?
     Remove all from dead list except toggled and remove all from live list
       that are dead (but in this case draw background square)
     Toggle toggled states, age existing ones, create a new dead list, draw
 */

	/* Go through dead list to see if anything spawns (generate new lists),
	   then delete the used dead list */

	MI_IS_DRAWN(mi) = True;

	/* Setup toggles */
	curr = lp->first[DEAD]->next;
	while (curr != lp->last[DEAD]) {
		count = ng_neighbors(lp, curr, &gcount);
		if ((lp->param.birth & (1 << count)) || (count >= FIRSTGROUP &&
			     count < FIRSTGROUP + maxgroups[neighbor_kind] &&
				 (lp->param.birth_group[count - FIRSTGROUP] &
				  (1 << style6[gcount])))) {
			setcelltoggles(mi, (int) (curr->info.position % lp->ncols),
				    (int) (curr->info.position / lp->ncols));
		}
		curr = curr->next;
	}
	curr = lp->first[LIVE]->next;
	while (curr != lp->last[LIVE]) {
		count = ng_neighbors(lp, curr, &gcount);
		if (!((lp->param.survival & (1 << count)) || (count >= FIRSTGROUP &&
			     count < FIRSTGROUP + maxgroups[neighbor_kind] &&
			      (lp->param.survival_group[count - FIRSTGROUP] &
			       (1 << style6[gcount]))))) {
			setcelltoggles(mi, (int) (curr->info.position % lp->ncols),
				    (int) (curr->info.position / lp->ncols));
		}
		curr = curr->next;
	}

	/* Bring out your dead! */
	curr = lp->first[DEAD]->next;
	while (curr != lp->last[DEAD]) {
		curr = curr->next;
		if (!curr->previous->info.toggle)
			removefrom_list(lp, DEAD, curr->previous);
	}
	curr = lp->first[LIVE]->next;
	while (curr != lp->last[LIVE]) {
		if (curr->info.toggle) {
			curr->info.state = DEAD;
			draw_cell(mi, curr->info);
			curr = curr->next;
			removefrom_list(lp, LIVE, curr->previous);
		} else
			curr = curr->next;
	}

	/* Fence off the babies */
	info.position = -1;	/* dummy value */
	info.age = 0;		/* dummy value */
	addto_list(lp, DEAD, info);
	addto_list(lp, LIVE, info);
	middle[DEAD] = lp->last[DEAD]->previous;
	middle[LIVE] = lp->last[LIVE]->previous;

	/* Toggle toggled states, age existing ones, create a new dead list */
	while (lp->first[DEAD]->next != middle[DEAD]) {
		curr = lp->first[DEAD]->next;
		setcellfromtoggle(mi, (int) (curr->info.position % lp->ncols),
				  (int) (curr->info.position / lp->ncols));
	}
	curr = lp->first[LIVE]->next;
	while (curr != middle[LIVE]) {
		setcellfromtoggle(mi, (int) (curr->info.position % lp->ncols),
				  (int) (curr->info.position / lp->ncols));
		curr = curr->next;
	}
	removefrom_list(lp, DEAD, middle[DEAD]);
	removefrom_list(lp, LIVE, middle[LIVE]);

	if (lp->redrawing) {
		for (i = 0; i < REDRAWSTEP; i++) {
			CellList   *curr = lp->arr[lp->redrawpos];

			/* TODO: More efficient to use list rather than array. */
			if (curr && curr->info.state == LIVE) {
				draw_cell(mi, curr->info);
			}
			if (++(lp->redrawpos) >= lp->npositions) {
				lp->redrawing = 0;
				break;
			}
		}
	}
	if (++lp->generation > MI_CYCLES(mi))
		init_life(mi);
	else
		lp->painted = True;

	/*
	 * generate a randomized shooter aimed roughly toward the center of the
	 * screen after batchcount.
	 */

	if (lp->generation && lp->generation %
	    ((MI_COUNT(mi) < 0) ? 1 : MI_COUNT(mi)) == 0)
		shooter(mi);

}

void
release_life(ModeInfo * mi)
{
	if (lifes != NULL) {
		int         screen;

		for (screen = 0; screen < MI_NUM_SCREENS(mi); screen++) {
			lifestruct *lp = &lifes[screen];
			int         state;

			for (state = 0; state < STATES; state++) {
				if (lp->first[0])
					flush_list(lp, state);
				if (lp->last[state])
					(void) free((void *) lp->last[state]);
				if (lp->first[state])
					(void) free((void *) lp->first[state]);
			}
			free_cells(lp);
			free_stuff(MI_DISPLAY(mi), lp);
		}
		(void) free((void *) lifes);
		lifes = NULL;
	}
}

void
refresh_life(ModeInfo * mi)
{
	lifestruct *lp = &lifes[MI_SCREEN(mi)];

	if (lp->painted) {
		MI_CLEARWINDOWCOLORMAP(mi, lp->backGC, lp->black);
		lp->redrawing = 1;
		lp->redrawpos = 0;
		lp->painted = False;
	}
}

void
change_life(ModeInfo * mi)
{
	lifestruct *lp = &lifes[MI_SCREEN(mi)];
	int         npats, i;

	lp->generation = 0;
	if (lp->first[0])
		for (i = 0; i < STATES; i++)
			flush_list(lp, i);
	else
		for (i = 0; i < STATES; i++)
			init_list(lp, i);
	free_cells(lp);
	alloc_cells(lp);

	MI_CLEARWINDOWCOLORMAP(mi, lp->backGC, lp->black);

	lp->pattern++;
	lp->patterned_rule = codeToPatternedRule(lp->param);
	npats = 0;
	switch (local_neighbors) {
		case 6:
			if ((unsigned) lp->patterned_rule < LIFE_6RULES)
				npats = patterns_6rules[lp->patterned_rule];
			break;
		case 8:
			if ((unsigned) lp->patterned_rule < LIFE_8RULES)
				npats = patterns_8rules[lp->patterned_rule];
			break;
	}
	if (lp->pattern >= npats + 2) {
		lp->pattern = 0;
		if (allPatterns) {
			lp->patterned_rule++;
			switch (local_neighbors) {
				case 6:
					if ((unsigned) lp->patterned_rule >= LIFE_6RULES)
						lp->patterned_rule = 0;
					break;
				case 8:
					if ((unsigned) lp->patterned_rule >= LIFE_8RULES)
						lp->patterned_rule = 0;
					break;
			}
			copyFromPatternedRule(&lp->param, lp->patterned_rule);
			if (MI_IS_VERBOSE(mi))
				printRule(lp->param);
		} else if (allGliders) {
			lp->patterned_rule++;
			switch (local_neighbors) {
				case 6:
					if ((unsigned) lp->patterned_rule >= LIFE_6GLIDERS)
						lp->patterned_rule = 0;
					break;
				case 8:
					if ((unsigned) lp->patterned_rule >= LIFE_8GLIDERS)
						lp->patterned_rule = 0;
					break;
			}
			copyFromPatternedRule(&lp->param, lp->patterned_rule);
			if (MI_IS_VERBOSE(mi))
				printRule(lp->param);
		}
	}
	if (lp->pattern >= npats)
		RandomSoup(mi, 30, MAX(2 * MIN(lp->nrows, lp->ncols) / 3, 15));
	else
		GetPattern(mi, lp->patterned_rule, lp->pattern);
}
