/*
 *	polyaboloes - make a list of polyaboloes of a given order.
 *	$Id: polyaboloes.c,v 1.6 2020/10/23 19:56:45 gls Exp $
 *
 *	polyaboloes [-x] <n>
 *
 *	-x	Generate polyfetts, vertex-connected polyaboloes.
 *
 *	Writes to polyaboloes.<n> or polyfetts.<n>.
 *
 *	The input and output files have one polyabolo on each line.
 *	A polyabolo is represented as a series of integers, of which
 *	the first three represent the first cell, the second three
 *	the second cell, and so on.  The three values are x, y
 *	(measured downward), and one of {3, 5, 10, 12, 15}.
 *	1 is the bottom sector, 2 the right, 4 the left, and 8 the top.
 */

#include <sys/stat.h>
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

typedef struct cell {
	int x, y, s;
} CELL;

static void usage();
static void add(int sector);
static void canonize();
static int vacant(int x, int y);
static int lexbefore();
static int cellcompare(const void *a, const void *b);
static void show();

int ncells, xnew, ynew, xflag;
int nwcells, nbcells;
CELL *cells, *wcells, *bcells;
static FILE *In, *Out;

static void
usage()
{
	fprintf(stderr, "usage: polyaboloes [-x] <n>\n"
		"-x\tGenerate polyfetts instead of polyaboloes.\n");
	exit(1);
}

static int reflbits[16] = {
	0, 1, 4, 5, 2, 3, 6, 7, 8, 9, 12, 13, 10, 11, 14, 15
};
static int rotbits[16] = {
	0, 2, 8, 10, 1, 3, 9, 11, 4, 6, 12, 14, 5, 7, 13, 15
};

int
main(int argc, char **argv)
{
	int n, k, c, x, y, v, opt;
	char outbuf[128], inbuf[128], *cur;
	struct stat outstat, instat;

	while (-1 != (opt = getopt(argc, argv, "x?")))
	switch(opt) {
	case 'x':
		xflag = 1;
		break;
	default:
		usage();
	}
	argc -= optind;
	argv += optind;
	if (argc != 1) usage();
	if (!isdigit(**argv)) usage();
	n = atoi(*argv);
	if (n==0) {
		fprintf(stderr, "polyaboloes: n must be positive.\n");
		exit(1);
	}
	if (n>99) {
		fprintf(stderr, "polyaboloes: n must be less than 100.\n");
		exit(1);
	}

	sprintf(outbuf, xflag? "polyfetts.%d": "polyaboloes.%d", n);
	if (0 == stat(outbuf, &outstat) && outstat.st_size > 0) {
		fprintf(stderr, "polyaboloes: %s is not empty.\n", outbuf);
		exit(1);
	}
	if (n == 1) {
		Out = fopen(outbuf, "w");
		if (!Out) {
			fprintf(stderr, "polyaboloes: cannot write to %s.\n",
				outbuf);
			exit(1);
		}
		fprintf(Out, "0 0 3\n");
		exit(0);
	}
	sprintf(inbuf, xflag? "polyfetts.%d": "polyaboloes.%d", n - 1);
	if (0 != stat(inbuf, &instat) || instat.st_size == 0) {
		fprintf(stderr, "polyaboloes: %s is missing or empty.\n",
			inbuf);
		exit(1);
	}
	In = fopen(inbuf, "r");
	if (!In) {
		fprintf(stderr, "polyaboloes: cannot write to %s.\n",
			outbuf);
		exit(1);
	}
	sprintf(outbuf, "sort -u --compress-program=gzip >%s.%d",
		xflag? "polyfetts": "polyaboloes", n);
	Out = popen(outbuf, "w");
	if (!Out) {
		fprintf(stderr, "polyaboloes: cannot sort to %s.\n",
			outbuf+33);
		exit(1);
	}
/*
 *	Allocate arrays of cells.
 */
	cells = calloc(n, sizeof(CELL));
	wcells = calloc(n, sizeof(CELL));	/* working */
	bcells = calloc(n, sizeof(CELL));	/* canonized */

	while (fgets(inbuf, 128, In)) {
/*
 *	Process an (n-1)-abolo.
 */
		char *nl = strchr(inbuf, '\n');
		if (!nl) {
			fprintf(stderr,
				"polyaboloes: incomplete input line.\n");
			exit(1);
		}
		*nl = '\0';
/*
fprintf(stderr, "read %s\n", inbuf);
 */
		ncells = 0;
		cur = inbuf;
		for (k=0; k<n-1; k++) {
	/*
	 * Read x.
	 */
			while (*cur && isspace(*cur)) cur++;
		/*
		 * The number of square grid cells may be less than n-1.
		 */
			if (!*cur) break;
			cells[ncells].x = atoi(cur);
			while (*cur && !isspace(*cur)) cur++;
			if (!*cur) {
				fprintf(stderr,
				"polyaboloes: incomplete input line.\n");
				exit(1);
			}
	/*
	 * Read y.
	 */
			while (*cur && isspace(*cur)) cur++;
			if (!*cur) {
				fprintf(stderr,
				"polyaboloes: incomplete input line.\n");
				exit(1);
			}
			cells[ncells].y = atoi(cur);
			while (*cur && !isspace(*cur)) cur++;
			if (!*cur) {
				fprintf(stderr,
				"polyaboloes: incomplete input line.\n");
				exit(1);
			}
	/*
	 * Read s.
	 */
			while (*cur && isspace(*cur)) cur++;
			if (!*cur) {
				fprintf(stderr,
				"polyaboloes: incomplete input line.\n");
				exit(1);
			}
			cells[ncells].s = atoi(cur);
			while (*cur && !isspace(*cur)) cur++;

			ncells++;
		}

	/* Adjoin a monabolo. */

		for (c=0; c<ncells; c++) {
			x = cells[c].x;
			y = cells[c].y;
			v = cells[c].s;
			if (v != 0x0 && v != 0xf) {	/* fill out the cell */
				cells[c].s = 0xf;
				add(0);		/* 0 means change nothing */
				cells[c].s = v;	/* restore the value */
			}

	/* Neighbor cell adjacencies.  Use a whole separate clause for -x. */

			if (xflag) {
	/*
	 *	Orthogonal moves.
	 */
			    if (v & 0x7) {	/* go down */
				xnew = x;
				ynew = y + 1;
				if (vacant(xnew, ynew)) {
					add(0xc);
					add(0xa);
					if (v & 0x2) add(0x3);
					if (v & 0x4) add(0x5);
				}
			    }
			    if (v & 0xb) {	/* go right */
				xnew = x + 1;
				ynew = y;
				if (vacant(xnew, ynew)) {
					add(0xc);
					add(0x5);
					if (v & 1) add(0x3);
					if (v & 8) add(0xa);
				}
			    }
			    if (v & 0xd) {	/* go left */
				xnew = x - 1;
				ynew = y;
				if (vacant(xnew, ynew)) {
					add(0xa);
					add(0x3);
					if (v & 1) add(0x5);
					if (v & 8) add(0xc);
				}
			    }
			    if (v & 0xe) {	/* go up */
				xnew = x;
				ynew = y - 1;
				if (vacant(xnew, ynew)) {
					add(0x5);
					add(0x3);
					if (v & 2) add(0xa);
					if (v & 4) add(0xc);
				}
			    }
	/*
	 *	Diagonal moves.
	 */
			    if (v & 0x3) {	/* down right. */
				xnew = x + 1;
				ynew = y + 1;
				if (vacant(xnew, ynew)) {
					add(0x5);
					add(0xa);
					add(0xc);
				}
			    }
			    if (v & 0x5) {	/* down left. */
				xnew = x - 1;
				ynew = y + 1;
				if (vacant(xnew, ynew)) {
					add(0x3);
					add(0xa);
					add(0xc);
				}
			    }
			    if (v & 0xa) {	/* up right. */
				xnew = x + 1;
				ynew = y - 1;
				if (vacant(xnew, ynew)) {
					add(0x3);
					add(0x5);
					add(0xc);
				}
			    }
			    if (v & 0xc) {	/* up left. */
				xnew = x - 1;
				ynew = y - 1;
				if (vacant(xnew, ynew)) {
					add(0x3);
					add(0x5);
					add(0xa);
				}
			    }
			}
			else {
			    if (v & 0x1) {	/* go down */
				xnew = x;
				ynew = y + 1;
				if (vacant(xnew, ynew)) {
					add(0xc);
					add(0xa);
				}
			    }
			    if (v & 0x2) {	/* go right */
				xnew = x + 1;
				ynew = y;
				if (vacant(xnew, ynew)) {
					add(0xc);
					add(0x5);
				}
			    }
			    if (v & 0x4) {	/* go left */
				xnew = x - 1;
				ynew = y;
				if (vacant(xnew, ynew)) {
					add(0xa);
					add(0x3);
				}
			    }
			    if (v & 0x8) {	/* go up */
				xnew = x;
				ynew = y - 1;
				if (vacant(xnew, ynew)) {
					add(0x5);
					add(0x3);
				}
			    }
			}
		}
	}
	fclose(In);
	fclose(Out);
	exit(0);
}

static void
add(int sector)
{
/*
fprintf(stderr, "add(%d)\n", sector);
 */
	if (sector) {
		cells[ncells].x = xnew;
		cells[ncells].y = ynew;
		cells[ncells].s = sector;
		ncells++;
	}
	canonize();			/* Writes into bcells[] */
	show();				/* Prints the contents */

	if (sector) ncells--;		/* Restore the cell count. */
}

/* Turn a polyabolo all different ways and choose the lexically first. */

static void
canonize()
{
	int c, refl, rot, ymin, xmin, t;

	nwcells = ncells;
	for (c=0; c<ncells; c++)
		wcells[c] = cells[c];

	nbcells = 0;
	for (refl=0; refl<2; refl++) {
		for (rot=0; rot<4; rot++) {
			ymin = xmin = 999;
			for (c=0; c<nwcells; c++) {
				if (wcells[c].x < xmin) xmin = wcells[c].x;
				if (wcells[c].y < ymin) ymin = wcells[c].y;
			}
			for (c=0; c<nwcells; c++) {
				wcells[c].x -= xmin;
				wcells[c].y -= ymin;
			}
			qsort(wcells, nwcells, sizeof(CELL), cellcompare);
			
			if (!nbcells || lexbefore()) {
				nbcells = nwcells;
				for (c=0; c<nwcells; c++)
					bcells[c] = wcells[c];
			}
		/*
		 *	Rotate the polyabolo.
		 */
			for (c=0; c<nwcells; c++) {
				t = wcells[c].y;
				wcells[c].y = - wcells[c].x;
				wcells[c].x = t;
				wcells[c].s = rotbits[wcells[c].s];
			}
		}
	/*
	 *	Reflect the polyabolo.
	 */
		for (c=0; c<nwcells; c++) {
			wcells[c].x = - wcells[c].x;
			wcells[c].s = reflbits[wcells[c].s];
		}
	}
}

/* Compare the current working polyabolo lexically to the "best" one. */

static int
lexbefore()
{
	int c, d;

	for (c=0; c<nwcells; c++) {
		d = cellcompare(wcells+c, bcells+c);
		if (d > 0) return 0;
		if (d < 0) return 1;
	}
	return 0;	/* identical */
}

static int
cellcompare(const void *a, const void *b)
{
	int d;

	const CELL *ca, *cb;
	ca = (const CELL *)a;
	cb = (const CELL *)b;
	d = ca->y - cb->y;
	if (d) return d;
	d = ca->x - cb->x;
	if (d) return d;
	d = ca->s - cb->s;
	return d;
}

static int
vacant(int x, int y)
{
	int c;
	for (c=0; c<ncells; c++) {
		if (cells[c].x == x && cells[c].y == y) return 0;
	}
	return 1;
}

static void
show()
{
	int c;

	for (c=0; c<nbcells; c++) {
		fprintf(Out, "%d %d %d%c", bcells[c].x, bcells[c].y,
			bcells[c].s, (c==nbcells-1? '\n': ' '));
	}
}