#include <stdio.h>
#include <stdlib.h>
#include <time.h>

struct coordinate
{
	unsigned int x;
	unsigned int y;
};
typedef struct coordinate coordinate;

struct zone
{
	unsigned int xmin;
	unsigned int xmax;
	unsigned int ymin;
	unsigned int ymax;
};
typedef struct zone zone;

char * createBytemap(unsigned int width, unsigned int height)
{
	int i, j;

	char * bytemap = (unsigned char *) malloc(width * height * sizeof(char *));

	//for(i = 0; i < height; i++)
	//	bytemap[i] = (unsigned char *) malloc(width * sizeof(char));

	return (unsigned char *) bytemap;
}

int findEntryPoint(coordinate * entryPoint, unsigned char * bytemap, unsigned int width, unsigned int height)
{
	unsigned int x, y;

	for(y = 0; y < height; y++)
	{
		for(x = 0; x < width; x++)
		{
			if(bytemap[y*width+x] == (unsigned char) 255)
			{
				entryPoint[0].x = x;
				entryPoint[0].y = y;

				printf("Entry point found @ (%u,%u)\n", x, y);

				return 1;
			}
		}
	}

	printf("No entry point found\n");
	entryPoint = NULL;
	return 0;
}

void findCenterPoint(unsigned char * bytemap, int width, int height)
{
	int i, j;

	coordinate entryPoint;
	coordinate point;

	unsigned int direction = 0;

	zone rectangle;

	while(findEntryPoint(&entryPoint, bytemap, width, height))
	{
		point = entryPoint;

		rectangle.xmin = point.x;
		rectangle.xmax = point.x;
		rectangle.ymin = point.y;
		rectangle.ymax = point.y;

		while(1)
		{
			switch(direction)
			{
				case 0: // Normal mode
					if(bytemap[((point.y + 0) * width) +  (point.x + 1)] == 255)
					{
						point.x += 1;
						point.y += 0;
						direction = 3;
					}
					else if(bytemap[((point.y + 1) * width) +  (point.x + 1)] == 255)
					{
						point.x += 1;
						point.y += 1;
						direction = 3;
					}
					else if(bytemap[((point.y + 1) * width) +  (point.x + 0)] == 255)
					{
						point.x += 0;
						point.y += 1;
						direction = 0;
					}
					else if(bytemap[((point.y + 1) * width) +  (point.x - 1)] == 255)
					{
						point.x += -1;
						point.y += 1;
						direction = 0;
					}
					else if(bytemap[((point.y + 0) * width) +  (point.x - 1)] == 255)
					{
						point.x += -1;
						point.y += 0;
						direction = 1;
					}
					else if(bytemap[((point.y - 1) * width) +  (point.x - 1)] == 255)
					{
						point.x += -1;
						point.y += -1;
						direction = 1;
					}
					else if(bytemap[((point.y - 1) * width) +  (point.x + 0)] == 255)
					{
						point.x += 0;
						point.y += -1;
						direction = 2;
					}
					else if(bytemap[((point.y - 1) * width) +  (point.x + 1)] == 255)
					{
						point.x += 1;
						point.y += -1;
						direction = 2;
					}
					/*else
					{
						point = previousPoint; // Return to previous point
					}*/
					break;
				case 1:
					if(bytemap[((point.y + 1) * width) +  (point.x + 0)] == 255)
					{
						point.x += 0;
						point.y += 1;
						direction = 0;
					}
					else if(bytemap[((point.y + 1) * width) +  (point.x - 1)] == 255)
					{
						point.x += -1;
						point.y += 1;
						direction = 0;
					}
					else if(bytemap[((point.y + 0) * width) +  (point.x - 1)] == 255)
					{
						point.x += -1;
						point.y += 0;
						direction = 1;
					}
					else if(bytemap[((point.y - 1) * width) +  (point.x - 1)] == 255)
					{
						point.x += -1;
						point.y += -1;
						direction = 1;
					}
					else if(bytemap[((point.y - 1) * width) +  (point.x + 0)] == 255)
					{
						point.x += 0;
						point.y += -1;
						direction = 2;
					}
					else if(bytemap[((point.y - 1) * width) +  (point.x + 1)] == 255)
					{
						point.x += 1;
						point.y += -1;
						direction = 2;
					}
					else if(bytemap[((point.y + 0) * width) +  (point.x + 1)] == 255)
					{
						point.x += 1;
						point.y = point.y;
						direction = 3;
					}
					else if(bytemap[((point.y + 1) * width) +  (point.x + 1)] == 255)
					{
						point.x += 1;
						point.y += 1;
						direction = 3;
					}
					break;
				case 2:
					if(bytemap[((point.y + 0) * width) +  (point.x - 1)] == 255)
					{
						point.x += -1;
						point.y += 0;
						direction = 1;
					}
					else if(bytemap[((point.y - 1) * width) +  (point.x - 1)] == 255)
					{
						point.x += -1;
						point.y += -1;
						direction = 1;
					}
					else if(bytemap[((point.y - 1) * width) +  (point.x + 0)] == 255)
					{
						point.x += 0;
						point.y += -1;
						direction = 2;
					}
					else if(bytemap[((point.y - 1) * width) +  (point.x + 1)] == 255)
					{
						point.x += 1;
						point.y += -1;
						direction = 2;
					}
					else if(bytemap[((point.y + 0) * width) +  (point.x + 1)] == 255)
					{
						point.x += 1;
						point.y += 0;
						direction = 3;
					}
					else if(bytemap[((point.y + 1) * width) +  (point.x + 1)] == 255)
					{
						point.x += 1;
						point.y += 1;
						direction = 3;
					}
					else if(bytemap[((point.y + 1) * width) +  (point.x + 0)] == 255)
					{
						point.x += 0;
						point.y += 1;
						direction = 0;
					}
					else if(bytemap[((point.y + 1) * width) +  (point.x - 1)] == 255)
					{
						point.x += -1;
						point.y += 1;
						direction = 0;
					}
					break;
				case 3:
					if(bytemap[((point.y - 1) * width) +  (point.x + 0)] == 255)
					{
						point.x += 0;
						point.y += -1;
						direction = 2;
					}
					else if(bytemap[((point.y - 1) * width) +  (point.x + 1)] == 255)
					{
						point.x += 1;
						point.y += -1;
						direction = 2;
					}
					else if(bytemap[((point.y + 0) * width) +  (point.x + 1)] == 255)
					{
						point.x += 1;
						point.y += 0;
						direction = 3;
					}
					else if(bytemap[((point.y + 1) * width) +  (point.x + 1)] == 255)
					{
						point.x += 1;
						point.y += 1;
						direction = 3;
					}
					else if(bytemap[((point.y + 1) * width) +  (point.x + 0)] == 255)
					{
						point.x += 0;
						point.y += 1;
						direction = 0;
					}
					else if(bytemap[((point.y + 1) * width) +  (point.x - 1)] == 255)
					{
						point.x += -1;
						point.y += 1;
						direction = 0;
					}
					else if(bytemap[((point.y + 0) * width) +  (point.x - 1)] == 255)
					{
						point.x += -1;
						point.y += 0;
						direction = 1;
					}
					else if(bytemap[((point.y - 1) * width) +  (point.x - 1)] == 255)
					{
						point.x += -1;
						point.y += -1;
						direction = 1;
					}
					break;
			}

			if(point.x < rectangle.xmin)
				rectangle.xmin = point.x;
			if(point.x > rectangle.xmax)
				rectangle.xmax = point.x;
			if(point.y < rectangle.ymin)
				rectangle.ymin = point.y;
			if(point.y > rectangle.ymax)
				rectangle.ymax = point.y;

			if(point.x == entryPoint.x && point.y == entryPoint.y)
				break;
		}

		// Calculate center point
		point.x = (((rectangle.xmax-rectangle.xmin)/2) + rectangle.xmin);
		point.y = (((rectangle.ymax-rectangle.ymin)/2) + rectangle.ymin);

		printf("Center: (%u, %u)\n", point.x, point.y);

		// Draw rectangle black (exclude this zone from further analysis)
		for(i = (rectangle.ymin - 1); i < (rectangle.ymax + 1); i++)
			for(j = (rectangle.xmin - 1); j < (rectangle.xmax + 1); j++)
				bytemap[i * width + j] = (unsigned char) 0;

		// Draw crosshair
		bytemap[(point.y - 1) * width + point.x] = 128;
		bytemap[point.y * width + point.x - 1] = 128;
		bytemap[point.y * width + point.x] = 128;
		bytemap[point.y * width + point.x + 1] = 128;
		bytemap[(point.y + 1) * width + point.x] = 128;
	}
}

int main()
{
	// Timing
	clock_t start;
	clock_t stop;

	unsigned char * bytemap;
	unsigned int width, height;
	int x, y;

	FILE * image = fopen("blobs.pgm", "rb");
	FILE * result = fopen("result.pgm", "wb");

	if(fscanf(image, "P5 %u %u 255 ", &width, &height) != 2) // Fetch height and width or die
		exit(1);

	bytemap = createBytemap(width, height);

	// Read bytes from original image
	for(y = 0; y < height; y++)
	{
		for(x = 0; x < width; x++)
		{
			bytemap[y * width + x] = (unsigned char) fgetc(image);
		}
	}

	start = clock();
	// Find center point
	findCenterPoint(bytemap, width, height);
	stop = clock();

	printf("Total time: %.3f s\n", ((double) stop - (double) start) / (double) CLOCKS_PER_SEC);

	// Write results to result image
	fprintf(result, "P5 %u %u 255 ", width, height);
	for(y = 0; y < height; y++)
	{
		for(x = 0; x < width; x++)
		{
			fputc((int) bytemap[y * width + x], result);
		}
	}

	fclose(image);
	fclose(result);
	return 0;
}