#import "MazeView.h"
#import <stdlib.h>
#import <sys/time.h>
#import <dpsclient/psops.h>
#import <dpsclient/dpsNeXT.h>
#import <appkit/Control.h>
#import <appkit/nextstd.h>
#import <appkit/graphics.h>
#import <appkit/Cursor.h>

#define	FAT	10

extern long random();
extern srandom(int seed);
extern void NXBeep(void);
extern void PSflushgraphics(void);

struct mazecell
{ BOOL wall, floor, already; };

struct place
{ short x,y; };

int horiz, vert;
struct mazecell *theMaze;
int solutionLen, numAllocated, tickie, lowTouch;
struct place *theSolution;
int spacing, tickPeriod;

void drawSolution(int lowlimit)
{
	int k, numOps;
	BOOL dash;
	short *data, boundingBox[4];
	char *ops;

	lowlimit--;
	if (lowlimit < 0) lowlimit = 0;
	boundingBox[0] = 0;
	boundingBox[1] = 0;
	boundingBox[2] = horiz * spacing;
	boundingBox[3] = vert * spacing;
	data = malloc((solutionLen - lowlimit + 1) * 2 * sizeof(short));
	ops = malloc((solutionLen - lowlimit + 1) * sizeof(char));
	data[0] = theSolution[lowlimit].x * spacing;
	data[1] = (vert - 1 - theSolution[lowlimit].y) * spacing;
	ops[0] = dps_moveto;
	numOps = 1;
	for (k=lowlimit; k<solutionLen; k++)
	{
		data[numOps * 2] = theSolution[k].x * spacing;
		data[numOps * 2 + 1] = (vert - 1 - theSolution[k].y) * spacing;
		ops[numOps++] = dps_lineto;
	}
	DPSDoUserPath(data, numOps * 2, dps_short, ops, numOps, boundingBox, dps_ustroke);
	free(data);
	free(ops);
}

BOOL findSolution(struct place where)
{
	theMaze[where.x + where.y * horiz].already = YES;
	if (solutionLen < lowTouch) lowTouch = solutionLen;
	theSolution[solutionLen++] = where;
	if (++tickie == tickPeriod)
	{
		PSsetgray(NX_WHITE);
		drawSolution(lowTouch);
		PSflushgraphics();
		PSsetgray(NX_BLACK);
		drawSolution(lowTouch);
		NXPing();
		tickie = 0;  lowTouch = 1000000000;
	}
	if (solutionLen == numAllocated)
	{
		numAllocated += 1000;
		theSolution = realloc(theSolution, numAllocated * sizeof(struct place));
	}
	if (((where.x == (horiz - 1)) && (where.y == (vert - 1))) || ((theMaze[where.x + where.y * horiz].wall == NO) && (theMaze[(where.x + 1) + where.y * horiz].already == NO) && (findSolution((struct place){where.x + 1, where.y}))) || ((theMaze[where.x + where.y * horiz].floor == NO) && (theMaze[where.x + (where.y + 1) * horiz].already == NO) && (findSolution((struct place){where.x, where.y + 1}))) || ((where.x > 0) && (theMaze[(where.x - 1) + where.y * horiz].wall == NO) && (theMaze[(where.x - 1) + where.y * horiz].already == NO) && (findSolution((struct place){where.x - 1, where.y}))) || ((where.y > 0) && (theMaze[where.x + (where.y - 1) * horiz].floor == NO) && (theMaze[where.x + (where.y - 1) * horiz].already == NO) && (findSolution((struct place){where.x, where.y - 1}))))
		return YES;
	else { solutionLen--; return NO; }
}

void drawSelfGlue(DPSTimedEntry te, double now, void *me)
{ DPSRemoveTimedEntry(te); [(id)me lockFocus]; [(id)me drawSelf:NULL :0]; [(id)me unlockFocus]; [[(id)me window] flushWindow]; }

@implementation MazeView

- setRanFactor:anObject
{
	ranFactor = anObject;
	return self;
}

+ newFrame:(const NXRect *) frameRect
{
	self = [super newFrame:frameRect];
	horiz = vert = spacing = 8;
	theMaze = NULL;
	theSolution = NULL;
	tickPeriod = 100;
	[self newMaze:self];
	return self;
}

- changeSpacing:sender
{
	int oldSpacing;

	oldSpacing = spacing;
	spacing = [sender intValue];
	horiz = (horiz * oldSpacing) / spacing;
	vert = (vert * oldSpacing) / spacing;
	if (horiz < 2) horiz = 2;
	if (vert < 2) vert = 2;
	[[self window] sizeWindow:horiz * spacing + FAT :vert * spacing + FAT];
	[self newMaze:self];
	return self;
}

- changeTickPeriod:sender
{
	tickPeriod = [sender intValue];
}

- drawFloors
{
	int j, k, numInGroup, numOps;
	BOOL dash;
	short *data, boundingBox[4];
	char *ops;

	PSmoveto(0, vert * spacing + 1);
	PSrlineto(horiz * spacing, 0);
	PSstroke();
	boundingBox[0] = bounds.origin.x;
	boundingBox[2] = bounds.size.width;
	boundingBox[3] = 1;
	data = malloc((horiz + 1) * 2 * sizeof(short));
	ops = malloc((horiz + 1) * sizeof(char));
	for (k=0; k<vert; k++) /* floors */
	{
		data[0] = 0;
		data[1] = k * spacing + 1;
		boundingBox[1] = k * spacing + 1;
		ops[0] = dps_moveto;
		numOps = 1;
		j=0;
		dash = theMaze[(vert - 1 - k) * horiz + j].floor;
		do {
			dash = !dash;
			numInGroup = 0;
			while ((j<horiz) && (theMaze[(vert - 1 - k) * horiz + j].floor == dash)) {j++; numInGroup++;}
			data[numOps * 2] = spacing * numInGroup;
			data[numOps * 2 + 1] = 0;
			ops[numOps++] = dash ? dps_rlineto : dps_rmoveto;
		} while (j<horiz);
		DPSDoUserPath(data, numOps * 2, dps_short, ops, numOps, boundingBox, dps_ustroke);
		PSflushgraphics();
	}
	free(data);
	free(ops);
}

- drawWalls
{
	int j, k, numInGroup, numOps;
	BOOL dash;
	short *data, boundingBox[4];
	char *ops;

	PSmoveto(0, 1);
	PSlineto(0, vert * spacing);
	PSstroke();
	boundingBox[1] = bounds.origin.y;
	boundingBox[2] = 1;
	boundingBox[3] = bounds.size.height;
	data = malloc((vert + 1) * 2 * sizeof(short));
	ops = malloc((vert + 1) * sizeof(char));
	for (k=0; k<horiz; k++) /* walls */
	{
		boundingBox[0] = (k + 1) * spacing;
		data[0] = (k + 1) * spacing;
		data[1] = 1;
		ops[0] = dps_moveto;
		numOps = 1;
		j=vert-1;
		dash = theMaze[j * horiz + k].wall;
		do {
			dash = !dash;
			numInGroup = 0;
			while ((j>=0) && (theMaze[j * horiz + k].wall == dash)) {j--; numInGroup++;}
			data[numOps * 2] = 0;
			data[numOps * 2 + 1] = spacing * numInGroup;
			ops[numOps++] = dash ? dps_rlineto : dps_rmoveto;
		} while (j>=0);
		DPSDoUserPath(data, numOps * 2, dps_short, ops, numOps, boundingBox, dps_ustroke);
		PSflushgraphics();
	}
	free(data);
	free(ops);
}

- drawMaze
{
	[self drawFloors];
	[self drawWalls];
}

- drawSelf:(const NXRect *)rects :(int)rectCount
{

	if (theMaze == NULL) return;
	if (bounds.size.width != horiz * spacing + 2) return;
	if (bounds.size.height != vert * spacing + 2) return;
	if (rects != NULL)
		{ DPSAddTimedEntry(0.0, &drawSelfGlue, (void *)self, 1); return self; }
	PSgsave();
	PSsetgray(NX_LTGRAY);  PSsetlinewidth(0.15);
	PSrectfill(0, 0, bounds.size.width, bounds.size.height);
	PStranslate(0, 1);  PSsetgray(NX_DKGRAY); [self drawMaze];
	if (spacing > 4)
		{ PStranslate(1, -1);  PSsetgray(NX_WHITE);  [self drawMaze]; }
	PSgrestore();
	return self;
}

- generateNewMaze
{
	struct timeval theTime;
	int width, row, column, temp, *J, *T, factor;
	struct mazecell *currentCell;

	if (ranFactor) factor = [ranFactor intValue];
	else factor = 800000000;
	if (theMaze != NULL) free(theMaze);
	if (theSolution != NULL) free(theSolution);
	theSolution = NULL;
	theMaze = malloc(horiz * vert * sizeof(struct mazecell));
	currentCell = theMaze;
	width = horiz + 1;
	J = malloc(width * sizeof(int));
	T = malloc(width * sizeof(int));
	row = vert;
	gettimeofday(&theTime, NULL);
	srandom(theTime.tv_sec + theTime.tv_usec);
	J[0] = column = 1;
	for(temp=width; --temp; J[temp] = T[temp] = temp);
	while (1) /* until break */
	{
		column--;
		if (column == 0)
		{
			column = width - 1;
			if (row == 0) break;
			row--;
		}

		temp = J[column - 1];
		if ((column-temp) && ((factor < random()) || ((row == 0) && (column == T[column]))))
		{
			T[temp] = T[column];
			J[T[temp]] = temp;
			T[column] = column - 1;
			J[T[column]] = column;
			currentCell->wall = NO;
		}
		else currentCell->wall = YES;

		temp = J[column];
		if ((row == 0) || ((column-temp) && ((factor < random()) || ((row == 0) && (column == T[column])))))
		{
			T[temp] = T[column];
			J[T[temp]] = temp;
			T[column] = column;
			J[T[column]] = column;
			currentCell->floor = YES;
		}
		else currentCell->floor = NO;

		currentCell->already = NO;

		currentCell++;
	}
}

- newMaze:sender
{
	[NXWait push];
	[self generateNewMaze];
	[[self window] display];
	[NXWait pop];
	return self;
}

- solve:sender
{
	int j, k;

	[self lockFocus];
	if (theSolution != NULL)
	{
		free(theSolution);
		[self drawSelf:NULL :0];
	}
	if (spacing > 4)
	{
		PStranslate(spacing / 2 + 1, spacing / 2 + 1);
		PSsetlinewidth(spacing - 4);
	}
	else if (spacing == 3)
	{ PStranslate(2, 3); PSsetlinewidth(2.0); }
	else
	{
		PStranslate(spacing / 2, spacing / 2 + 2);
		PSsetlinewidth(0.15);
	}
	PSsetlinecap(2);  PSsetlinejoin(0);
	numAllocated = 1000;
	solutionLen = 0;
	theSolution = malloc(numAllocated * sizeof(struct place));
	tickie = 0;  lowTouch = 1000000000;
	findSolution((struct place){0,0});
	for (j=0; j<horiz; j++)  for (k=0; k<vert; k++)
		theMaze[j + k * horiz].already = NO;
	PSsetgray(NX_WHITE);
	drawSolution(0);
	PSflushgraphics();
	[self unlockFocus];
}

- windowWillResize:sender toSize:(NXSize *)frameSize;
{
  NXRect startRect, tempRect, resultRect;
  int tempHoriz, tempVert;

  startRect.size = *frameSize;
  [Window getContentRect:&tempRect forFrameRect:&startRect style:[sender style]];
  tempHoriz = (tempRect.size.width - FAT) / spacing;
  tempVert = (tempRect.size.height - FAT) / spacing;
  if (tempHoriz < 2) tempHoriz = 2;
  if (tempVert < 2) tempVert = 2;
  tempRect.size.width = tempHoriz * spacing + FAT;
  tempRect.size.height = tempVert * spacing + FAT;
  [Window getFrameRect:&resultRect forContentRect:&tempRect style:[sender style]];
  *frameSize = resultRect.size;
}

- windowDidResize:sender
{
	NXRect startRect, tempRect;
	int tempHoriz, tempVert;

	[[self window] getFrame:&startRect];
	[Window getContentRect:&tempRect forFrameRect:&startRect style:[[self window] style]];
	horiz = (tempRect.size.width - FAT) / spacing;
	vert = (tempRect.size.height - FAT) / spacing;
	[self generateNewMaze];
	return self;
}

@end

