/*
^echo w; window -r 0 0 9999 9999 /shr/sdUad098/umbraticus/rc/rci '''cd /tmp && 6c wfc.c && 6l wfc.6 && 6.out'''
^echo w; window -r 0 0 9999 9999 rci '''cd src && mk 6.wfc && 6.wfc'''
*/
#include <u.h>
#include <libc.h>
#include <draw.h>
enum{
	DIM = 48,
	NTILE = 1 + 4,
	COLLAPSED = 1 << NTILE,
	SUPERPOSITION = COLLAPSED - 1
};
typedef struct Tile Tile;
struct Tile{Image *img; uchar socket[4 * 3];}tile[NTILE];
typedef struct Cell Cell;
struct Cell{int index, state;}*cell;
int x, y, xy;
void
drawtile(Cell *c){
	Rectangle r;
	int i;
	r.min = addpt(screen->r.min, mulpt(Pt(c->index % x, c->index / x), DIM));
	r.max = addpt(r.min, Pt(DIM, DIM));
	for(i = 0; i < NTILE && ~c->state & 1 << i; i++)
		;
	draw(screen, r, tile[i].img, nil, ZP);
}
void
rotate(Tile *dst, Tile *src){
	uchar o[DIM * DIM], r[DIM * DIM];
	int i, j;
	unloadimage(src->img, src->img->r, o, DIM * DIM);
	for(i = 0; i < DIM; i++)
		for(j = 0; j < DIM; j++)
			r[i * DIM + j] = o[DIM * (DIM - 1 - j) + i];
	loadimage(dst->img, dst->img->r, r, DIM * DIM);
	for(i = 0; i < 12; i++)
		dst->socket[i] = src->socket[(i + 9) % 12];
}
int
entropy(int n){
	int e;
	if(n & COLLAPSED)
		return COLLAPSED;
	for(e = 0; n; e++) /* hi, bwk */
		n &= n - 1;
	return e;
}
int
weigh(void *a, void *b){
	return entropy(((Cell*)a)->state) - entropy(((Cell*)b)->state);
}
int
index(void *a, void *b){
	return ((Cell*)a)->index - ((Cell*)b)->index;
}
void
collapse(Cell *c){
	int i;
	i = entropy(c->state);
	i = nrand(i);
	while(i--)
		c->state &= c->state - 1;
	c->state = COLLAPSED | c->state & -c->state;
}
int
reduced(Cell *a, Cell *b, int as){
	int at, bt, bs, mod;
	bs = (as + 6) % 12;
	if(b->state & COLLAPSED)
		return 0;
	for(mod = bt = 0; bt < NTILE; bt++)
		if(b->state & 1 << bt){
			for(at = 0; at < NTILE; at++)
				if((a->state & 1 << at)
				&& tile[at].socket[as] == tile[bt].socket[bs + 2]
				&& tile[at].socket[as + 1] == tile[bt].socket[bs + 1]
				&& tile[at].socket[as + 2] == tile[bt].socket[bs])
					break;
			if(at == NTILE){
				mod = 1;
				b->state ^= 1 << bt;
			}
		}
	return mod;
}
void
reduce(int i){
	int mod;
	mod = reduced(cell + i, cell + (i + xy - x) % xy, 0)
		| reduced(cell + i, cell + (i + 1) % xy, 3) << 1
		| reduced(cell + i, cell + (i + x) % xy, 6) << 2
		| reduced(cell + i, cell + (i + xy - 1) % xy, 9) << 3;
	if(mod & 1)
		reduce((i + xy - x) % xy);
	if(mod & 2)
		reduce((i + 1) % xy);
	if(mod & 4)
		reduce((i + x) % xy);
	if(mod & 8)
		reduce((i + xy - 1) % xy);
}
void
main(int, char*){
	Rectangle r;
	int i;
	if(initdraw(nil, nil, nil) < 0)
		sysfatal("initdraw: %r");
	srand(truerand());
	r = Rect(0, 0, DIM, DIM);
	for(i = 0; i < nelem(tile); i++){
		tile[i].img = allocimage(display, r, GREY8, 0, DBlack);
		if(tile[i].img == nil)
			sysfatal("allocimage: %r");
	}
	r.min.y += DIM / 3;
	r.max.y -= DIM / 3;
	draw(tile[1].img, r, display->white, nil, ZP);
	r = Rect(r.min.x + DIM / 3, r.max.y, r.max.x - DIM / 3, r.max.y + DIM / 3);
	draw(tile[1].img, r, display->white, nil, ZP);
	tile[1].socket[4] = tile[1].socket[7] = tile[1].socket[10] = 1;
	for(i = 2; i < 5; i++)
		rotate(tile + i, tile + i - 1);
	x = Dx(screen->r) / DIM + 1;
	y = Dy(screen->r) / DIM + 1;
	xy = x * y;
	cell = malloc(xy * sizeof(Cell));
	if(cell == nil)
		sysfatal("malloc: %r");
	while(9){
		draw(screen, screen->r, display->black, nil, ZP);
		for(i = 0; i < xy; i++){
			cell[i].index = i;
			cell[i].state = SUPERPOSITION;
		}
		while(cell[0].state && !(cell[0].state & COLLAPSED)){
			i = 1;
			while(i < xy && entropy(cell[i].state) == entropy(cell[i - 1].state))
				i++;
			i = cell[nrand(i)].index;
			qsort(cell, xy, sizeof(Cell), index);
			collapse(cell + i);
			drawtile(cell + i);
			reduce(i);
			qsort(cell, xy, sizeof(Cell), weigh);
			flushimage(display, 1);
			sleep(20);
		}
	}
	exits(nil);
}