/*
 * mkmap - Compute complete ASCII map by stitching pieces
 * together with a semi-heuristic+fallback bruteforce algorithm
 *
 * Programmed by Matti 'ccr' Hämäläinen (Ggr Pupunen)
 * (C) Copyright 2006 Tecnic Software productions (TNSP)
 */
#include "maputils.h"
#include <string.h>
#include <strings.h>
#include "th_args.h"
#include "th_string.h"


#define	MAX_FILES	(256)


/* Variables
 */
char	*progName = NULL;
int	nsrcFiles = 0;
char	*srcFiles[MAX_FILES],
	*destFile = NULL;

int	optBlockW = 21,
	optBlockH = 21,
	optMapFactor = 2,
	optRounds = 100;
BOOL	optInverse = FALSE,
	optHardDrop = FALSE;
float	optMatch = 90.0f, optFudge = 50.0f;
char	*optPattern = "You quack 'pfs.'";
char	*optInitialMap = NULL;


/* Arguments
 */
optarg_t optList[] = {
	{ 0, '?', "help",	"Show this help", OPT_NONE },
	{ 1, 'o', "output",	"Specify output file", OPT_ARGREQ },
	{ 2, 'v', "verbose",	"Be more verbose", OPT_NONE },
	{ 3, 'q', "quiet",	"Be quiet", OPT_NONE },
	{ 4, 'm', "match",	"Match percentage", OPT_ARGREQ },
	{ 12, 'f', "fudge",	"Matcher prevblock fudge %", OPT_ARGREQ },
	{ 5, 'r', "rounds",	"Processing timeout # rounds", OPT_ARGREQ },
	{ 6, 's', "start",	"Map block start marker string", OPT_ARGREQ },
	{ 7, 'i', "inverse",	"Use inverse search of blocks", OPT_NONE },
	{ 11,'d', "drop",	"Use hard dropping (bailout on first mismatch)", OPT_NONE },
	{ 8, 'w', "width",	"Block width", OPT_ARGREQ },
	{ 9, 'h', "height",	"Block height", OPT_ARGREQ },
	{ 10,'I', "initial",	"Initial map file", OPT_ARGREQ },
};

const int optListN = (sizeof(optList) / sizeof(optarg_t));


void argShowHelp()
{
	th_args_help(stdout, optList, optListN, progName,
		"[options] <inputfile> [inputfile#2..]");
}


BOOL argHandleOpt(const int optN, char *optArg, char *currArg)
{
	switch (optN) {
	case 0:
		argShowHelp();
		exit(0);
		break;

	case 1:
		destFile = optArg;
		THMSG(1, "Output file '%s'\n", destFile);
		break;

	case 2:
		th_verbosityLevel++;
		break;
	
	case 3:
		th_verbosityLevel = -1;
		break;
	
	case 4:
		optMatch = atof(optArg);
		if (optMatch < 10.0 || optMatch > 100.0) {
			THERR("Invalid match value %1.3f (x > 100% || x < 10%)\n",
				optMatch);
			return FALSE;
		}
		THMSG(1, "Match at %1.4f%%\n", optMatch);
		break;

	case 12:
		optFudge = atof(optArg);
		if (optFudge < 1.0 || optFudge > 100.0) {
			THERR("Invalid fudge value %1.3f (x > 100% || x < 1%)\n",
				optMatch);
			return FALSE;
		}
		THMSG(1, "Matching fudge factor = %1.4f%%\n", optFudge);
		break;

	case 5:
		optRounds = atoi(optArg);
		if (optRounds < 1) {
			THERR("Invalid rounds timeout %d! Must be > 1!\n",
				optRounds);
			return FALSE;
		}

		THMSG(1, "Processing rounds timeout = %d\n", optRounds);
		break;

	case 6:
		optPattern = optArg;
		THMSG(1, "Map block start marker = '%s'\n", optPattern);
		break;

	case 7:
		optInverse = TRUE;
		THMSG(1, "Using inverse processing of blocks.\n");
		break;

	case 8:
		optBlockW = atoi(optArg);
		if (optBlockW < 1) {
			THERR("Invalid block width %d, must be >= 1\n", optBlockW);
			return FALSE;
		}
		THMSG(1, "Map block width = %d\n", optBlockW);
		break;

	case 9:
		optBlockH = atoi(optArg);
		if (optBlockH < 1) {
			THERR("Invalid block height %d, must be >= 1\n", optBlockH);
			return FALSE;
		}
		THMSG(1, "Map block height = %d\n", optBlockH);
		break;

	case 10:
		optInitialMap = optArg;
		THMSG(1, "Using initial map file = '%s'\n", optArg);
		break;

	case 11:
		optHardDrop = TRUE;
		THMSG(1, "Using hard dropping (instant bailout on mismatch).\n");
		break;

	default:
		THERR("Unknown argument '%s'.\n", currArg);
		return FALSE;
	}

	return TRUE;
}


BOOL argHandleFile(char *currArg)
{
	if (nsrcFiles < MAX_FILES) {
		srcFiles[nsrcFiles] = currArg;
		nsrcFiles++;
	} else {
		THERR("Too many input files specified (%d max)!\n", MAX_FILES);
		return FALSE;
	}

	return TRUE;
}


/* Calculate matching percentage of given block against a map,
 * with using specified x/y offsets.
 */
float matchBlock(mapblock_t *map, mapblock_t *match, int ox, int oy, BOOL matchEmpty, BOOL hardDrop)
{
	int x, y, c1, c2, dy, dx, n, k;

	n = k = 0;
	
	for (y = 0; y < match->h; y++)
	for (x = 0; x < match->w; x++) {
		dx = (ox + x);
		dy = (oy + y);
		
		if (dx >= 0 && dx < map->w && dy >= 0 && dy < map->h)
			c2 = map->d[(dy * map->w) + dx];
		else
			c2 = 0;
		
		c1 = match->d[(y * match->w) + x];

		if ((c1 != 0 && c2 == 0) || (c1 == 0 && c2 != 0)) {
			/* Other is empty */
			if (matchEmpty) n++;
			k++;
		} else 
		if (c1 == 0 && c2 == 0) {
			/* Both empty ... */
		} else
		if (c1 == c2) {
			/* Exact match, increase % */
			n++;
			k++;
		} else
		if (hardDrop) {
			/* Mismatch, return failure */
			return -1;
		}
	}
	
	if (k > 0)
		return ((float) n * 100.0f) / (float) k;
	else
		return 0.0f;
}


/* Parse next block (marked by string optPattern) from
 * input stream into a mapblock, return NULL if not found or error.
 */
mapblock_t * parseBlock(FILE *inFile, int inW, int inH, char *inPattern)
{
	mapblock_t *tmp;
	int y, o;
	BOOL isFound;
	char s[4096];
	
	isFound = FALSE;
	while (!feof(inFile) && !isFound && fgets(s, sizeof(s), inFile)) {
		if (!strncmp(s, inPattern, strlen(inPattern)))
			isFound = TRUE;
	}
	
	if (!isFound) {
		THERR("No block start marker found.\n");
		return NULL;
	}
	
	if ((tmp = allocBlock(inW, inH)) == NULL) {
		THERR("Could not allocate mapblock (%d, %d)\n", inW, inH);
		return NULL;
	}
	
	o = y = 0;
	while (!feof(inFile) && (y < tmp->h)) {
		int x = 0, c = 0;
		
		while (x < tmp->w) {
			c = fgetc(inFile);
			if (c == '\n' || c == EOF)
				break;
			else
				tmp->d[o++] = c;
			x++;
		}
		
		while ((c = fgetc(inFile)) != EOF && c != '\n') x++;

		if (x != tmp->w) {
			THERR("Broken block, line width %d != %d on block y=%d\n",
				x, tmp->w, y);
			freeBlock(tmp);
			return NULL;
		}
		
		y++;
	}
	
	if (y != tmp->h) {
		THERR("Broken block, height %d != %d\n",
			y, tmp->h);
		freeBlock(tmp);
		return NULL;
	}
	
	return tmp;
}


/* Bruteforce search / block matching ..
 */
BOOL blockSearchBruteDo2(mapblock_t *map, mapblock_t *b,
	int *x, int *y, float m,
	int dx, int dy, float *vm)
{
	int ox, oy;
	float v;

THPRINT(3, "\nDo2: x=%d, y=%d, m=%1.2f, dx=%d, dy=%d, vm=%1.2f\n",
	*x, *y, m, dx, dy, *vm);
	
	for (oy = (*y - dy); oy < (*y + dy); oy++)
	for (ox = (*x - dx); ox < (*x + dx); ox++) {
		v = matchBlock(map, b, ox, oy, FALSE, optHardDrop);
		if (v >= m) {
			*vm = v;
			*x = ox;
			*y = oy;
			return TRUE;
		}
	}

	return FALSE;
}

BOOL blockSearchBruteDo(mapblock_t *map, mapblock_t *b,
	int *x, int *y, float m,
	int dx, int dy, float *vm, int skipx, int skipy, int *chkx, int *chky)
{
	int ox, oy;
	float v;


	
THPRINT(3, "\nDo: m=%1.2f, dx=%d, dy=%d, vm=%1.2f, skipx=%d, skipy=%d\n",
	m, dx, dy, *vm, skipx, skipy);


	for (oy = -(dy); oy < (map->h + dy); oy += skipy)
	for (ox = -(dx); ox < (map->w + dx); ox += skipx) {
		v = matchBlock(map, b, ox+skipx-1, oy+skipy-1, FALSE, optHardDrop);
		if (v >= *vm) {
			*vm = v;
			*chkx = ox;
			*chky = oy;
		}
		
		if (v >= m) {
			*x = ox;
			*y = oy;
			return TRUE;
		}
	}
	
	return FALSE;
}


BOOL blockSearchBrute(mapblock_t *map, mapblock_t *b, int *x, int *y, float m, float q)
{
	int dx, dy, skip, chkx, chky;
	float pvm = m * 0.5f, vm = -1;
	
	
	for (skip = 64; skip >= 1; skip /= 2) {
		dx = ((float) b->w) * q;
		dy = ((float) b->h) * q;
		
		if (blockSearchBruteDo(map, b, x, y, m,
			dx, dy, &vm, skip, skip, &chkx, &chky))
			return TRUE;
		
		THPRINT(3, "[%d, %d: vm=%1.2f, pvm=%1.2f]\n", chkx, chky, vm, pvm);
		if (vm > pvm) {
			pvm = vm;
			if (blockSearchBruteDo2(map, b, &chkx, &chky, m,
				skip/2, skip/2, &vm))
				return TRUE;
			THPRINT(3, "[Q: %d, %d: vm=%1.2f, pvm=%1.2f]\n", chkx, chky, vm, pvm);
		}
	}
	
	return FALSE;
}


BOOL blockSearch(mapblock_t *map, mapblock_t *b, int *x, int *y, float m, float q)
{
	int ox, oy, dx, dy;
	float v;
	
	dx = ((float) b->w) * q;
	dy = ((float) b->h) * q;

	for (oy = (*y - dy); oy < (*y + dy); oy++)
	for (ox = (*x - dx); ox < (*x + dx); ox++) {
		v = matchBlock(map, b, ox, oy, FALSE, optHardDrop);
		if (v >= m) {
			*x = ox;
			*y = oy;
			return TRUE;
		}
	}

	THPRINT(2, "?");
	
	return blockSearchBrute(map, b, x, y, m, q);
}


int main(int argc, char *argv[])
{
	FILE *tmpFile;
	BOOL isOK, isFirst;
	int i, n, ox, oy, nmapBlocks = 0;
	mapblock_t *worldMap = NULL, *tmp = NULL, *initialMap = NULL;
	mapblock_t **mapBlocks = NULL;

	progName = argv[0];
	th_init("mkmap", "ASCII Map Auto-Stitcher", "0.3", NULL, NULL);
	th_verbosityLevel = 1;
	
	/* Parse arguments */
	if (!th_args_process(argc, argv, optList, optListN,
		argHandleOpt, argHandleFile, TRUE))
		exit(1);
	
	if (nsrcFiles < 1) {
		THERR("Nothing to do. (try --help)\n");
		exit(0);
	}
	
	/* Read initial map */
	if (optInitialMap) {
		THMSG(1, "Reading initial map '%s'\n", optInitialMap);
		initialMap = parseFile(optInitialMap);
		if (initialMap) {
			THMSG(2, "Initial dimensions %d x %d\n",
				initialMap->w, initialMap->h);
		} else {
			THERR("Initial map could not be loaded!\n");
			exit(1);
		}
	}
	
	/* Read in continuous mapdata and parse it into map blocks
	 */
	for (i = 0; i < nsrcFiles; i++) {
		if ((tmpFile = fopen(srcFiles[i], "rb")) == NULL) {
			THERR("Error opening input file '%s'!\n",
				srcFiles[i]);
			exit(1);
		}
		
		while (!feof(tmpFile)) {
			if ((tmp = parseBlock(tmpFile, optBlockW, optBlockH, optPattern)) != NULL) {
				nmapBlocks++;
				mapBlocks = (mapblock_t **) th_realloc(mapBlocks, sizeof(mapblock_t *) * nmapBlocks);
				if (!mapBlocks) {
					THERR("Could not allocate/extend mapblock pointer structure (#%d)\n", nmapBlocks);
					exit(3);
				}
				cleanBlock(tmp, " *X");
				mapBlocks[nmapBlocks - 1] = tmp;
			}
		}
		
		fclose(tmpFile);
	}
	
	THMSG(1, "Total of %d mapblocks read.\n", nmapBlocks);
	

	/* Start matching the blocks with bruteforce
	 */
	if (initialMap) {
		worldMap = initialMap;
	} else if (nmapBlocks > 0) {
		if (optInverse)
			tmp = mapBlocks[nmapBlocks - 1];
		else
			tmp = mapBlocks[0];
		
		if ((worldMap = allocBlock(tmp->w * optMapFactor, tmp->h * optMapFactor)) == NULL) {
			THERR("Could not allocate world map.\n");
			exit(3);
		}
		
		putBlockDo(worldMap, tmp,
			(worldMap->w / 2) - (tmp->w / 2),
			(worldMap->h / 2) - (tmp->h / 2));
	} else {
		if ((worldMap = allocBlock(optBlockW * optMapFactor, optBlockH * optMapFactor)) == NULL) {
			THERR("Could not allocate world map.\n");
			exit(3);
		}
	}

	
	THMSG(1, "Initialized world map of (%d x %d)\n",
		worldMap->w, worldMap->h);

	n = 0;
	isFirst = TRUE;
	isOK = FALSE;
	while ((n < optRounds) && !isOK) {
		n++;
		THPRINT(2, "Round #%d: ", n);

		isOK = TRUE;
		for (i = 0; i < nmapBlocks; i++)
		if (!mapBlocks[i]->mark) {
			if ((isFirst &&
			blockSearchBrute(worldMap, mapBlocks[i], &ox, &oy, optMatch, optFudge/100.0f)) ||
			blockSearch(worldMap, mapBlocks[i], &ox, &oy, optMatch, optFudge/100.0f)) {
				THPRINT(2, "X");
				if (putBlock(&worldMap, mapBlocks[i], ox, oy, 15) < 0) {
					THERR("putBlock(%d, %d, %d) failed!\n",
						ox, oy, i);
				}
				isFirst = isOK = FALSE;
			} else {
				THPRINT(2, ".");
			}
		}
		
		THPRINT(2, "\n");
	}
	

	/* Output generated map
	 */
	if (worldMap) {
		THMSG(1, "Outputting generated map of (%d x %d) ...\n",
			worldMap->w, worldMap->h);

		if (destFile == NULL)
			tmpFile = stdout;
		else if ((tmpFile = fopen(destFile, "wb")) == NULL) {
			THERR("Error opening output file '%s'!\n",
				destFile);
			exit(1);
		}
	
		printBlock(tmpFile, worldMap);
	
		fclose(tmpFile);

		for (n = i = 0; i < nmapBlocks; i++)
		if (!mapBlocks[i]->mark) n++;
		
		THMSG(1, "%d mapblocks unused/discarded\n", n);
	} else {
		THERR("No map generated?\n");
	}
	
	exit(0);
	return 0;
}