/*
 * Copyright (c) 2010 Daniel Hartmeier <daniel@benzedrine.ch>
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 *    - Redistributions of source code must retain the above copyright
 *      notice, this list of conditions and the following disclaimer.
 *    - Redistributions in binary form must reproduce the above
 *      copyright notice, this list of conditions and the following
 *      disclaimer in the documentation and/or other materials provided
 *      with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 *
 */

#include <errno.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>
#include <list>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <string>

#include "Map.h"
#include "board.h"
#include "node.h"
#include "graph.h"
#include "expand.h"
#include "maxsteps.h"

#ifdef DEBUG
FILE *logfile = 0;
#endif

/* called whenever idle, spend at most t us spawning new nodes
 * return depth of tree, or 0 if tree is complete
 */
static unsigned
Spawn(unsigned long timeout)
{
	if (!root)
		return 0;
	while (!nodes.empty() && usec() < timeout)
		nodes.front()->spawn(timeout);
	if (nodes.empty())
		return 0;
	unsigned depth = 0;
	for (Node *n = nodes.front(); n; n = n->parent)
		depth++;
	return depth;
}

#ifdef DEBUG
static void
printChildren(const Node *p, unsigned ident, unsigned max)
{
	if (ident >= max)
		return;
	for (int m = 0; m < 4; ++m) {
		for (int o = 0; o < 4; ++o) {
			for (unsigned i = 0; i < ident; ++i)
				debug("  ");
			if (!p->children[m][o]) {
				debug("child m %s o %s NULL\n", dname[m], dname[o]);
				continue;
			}
			debug("child m %s o %s %s", dname[m],
			    dname[o], rname[p->children[m][o]->best]);
			if (p->children[m][o]->best == LOSS)
				debug(" movesToLoss %d", p->children[m][o]->movesToLoss);
			if (p->children[m][o]->best == DRAW)
				debug(" movesToDraw %d", p->children[m][o]->movesToDraw);
			if (p->children[m][o]->best == WIN)
				debug(" movesToWin %d", p->children[m][o]->movesToWin);
			if (p->children[m][o]->best == UNDECIDED)
				debug(" area %d", p->children[m][o]->area);
			if (p->children[m][o]->isolated)
				debug(" isolated");
			else {
				if (p->children[m][o]->leaf)
					debug(" leaf");
			}
			debug("\n");
			if (!p->children[m][o]->leaf && !p->children[m][o]->isolated)
				printChildren(p->children[m][o], ident + 1, max);
		}
	}
}
#endif

/* called when a move must be made within one second */
static string
MakeMove(const Map &map) {
	unsigned long t0 = usec();
	Board b(map);
	static DIR dir = NORTH;
	static bool first = true;
	static vector<DIR> path;

	debug("========================================\n\n");
	if (!root) {
		debug("got initial map, creating root node\n");
		root = new Node(b);
	} else {
		Node *newroot = NULL;
		/* dir contains my previous move */
		/* find opponent's previous move */
		for (int o = 0; o < 4; ++o) {
			if (step(root->board.getOpPos(), (DIR)o) == b.getOpPos()) {
				newroot = root->children[dir][o];
				root->children[dir][o] = NULL;
				break;
			}
		}
		if (newroot) {
			debug("new root found in children\n");
		} else {
			debug("newroot not found, creating new root\n");
			newroot = new Node(b);
			if (!newroot->isolated) {
				debug("ERROR: newroot NOT isolated\n");
				#ifdef DEBUG
				exit(0);
				#endif
			}
		}
		delete root;
		root = newroot;
		root->parent = NULL;
	}
	#if DEBUG
	debug("%lu nodes, %u unspawned\n", treesize, (unsigned)nodes.size());
	#endif
	if (!root->isolated && !nodes.empty()) {
		debug("start spawning after %lu us\n", usec() - t0);
		unsigned depth = Spawn(usec() + (first ? 2900000 : 940000));
		debug("%s: treesize %lu, %u nodes, depth %u\n", !depth ? "COMPLETE" :
		    "INCOMPLETE", treesize, (unsigned)nodes.size(), depth);
	}

	#ifdef DEBUG
	root->board.print();
	debug("root: %s%s", rname[root->best], root->isolated ?
	    " ISOLATED" : "");
	if (root->best == WIN)
		debug(" movesToWin %d", root->movesToWin);
	if (root->best == DRAW)
		debug(" movesToDraw %d", root->movesToDraw);
	if (root->best == LOSS)
		debug(" movesToLoss %d", root->movesToLoss);
	if (root->best == UNDECIDED)
		debug(" area %d", root->area);
	debug("\n");
	if (!root->isolated)
		printChildren(root, 0, 1);
	#endif

	debug("starting decision after %lu us\n", usec() - t0);
	if (root->isolated) {
		if (root->path.size() > path.size())
			path = root->path;
		unsigned max = root->floodFill(false);
		unsigned min = root->floodFill(true);
		if (path.size() > min) {
			debug("MakeMove: old path size %u > min %u, winning!\n",
			    (unsigned)path.size(), min);
		} else {
			vector<DIR> v;
			root->rateIsolation(max, min, v,
			    usec() + (first ? 2900000 : 900000));
			debug("MakeMove: rateIsolation() v.size %u\n",
			    (unsigned)v.size());
			if (!v.size())
				goto usepath;
			#ifdef DEBUG
			root->board.checkPath(root->board.getMyPos(), v);
			#endif
			if (v.size() > path.size()) {
				debug("MakeMove: v.size %u > path.size %u, "
				    "taking new path\n", (unsigned)v.size(),
				    (unsigned)path.size());
				path = v;
			} else {
				debug("MakeMove: v.size %u <= path.size %u, "
				    "keeping old path\n", (unsigned)v.size(),
				    (unsigned)path.size());
			}
		}
usepath:
		if (!path.size()) {
			debug("MakeMove: this is my dying move\n");
			/* this is not possible, unless there are bugs ;) */
			for (int d = 0; d < 4; ++d) {
				pair<int, int> m = step(root->board.getMyPos(),
				    (DIR)d);
				if (!root->board.read(m.first, m.second)) {
					dir = (DIR)d;
					break;
				}
			}
		} else {
			dir = (DIR)path[0];
			path.erase(path.begin());
		}
	} else {
		int r;
		switch (root->best) {
		case WIN:
			r = root->nearestWin(dir);
			debug("%s WIN in at most %d moves\n", dname[dir], r);
			break;
		case DRAW:
			r = root->farthestDraw(dir);
			debug("%s DRAW for at least %d moves\n", dname[dir], r);
			break;
		case LOSS:
			r = root->farthestLoss(dir);
			debug("%s LOSS for at least %d moves\n", dname[dir], r);
			break;
		case UNDECIDED:
			r = root->bestUndecided(dir);
			debug("%s best UNDECIDED (out of %d)\n",
			    dname[dir], r);
			break;
		}
	}

	if (first)
		first = false;
	debug("returning %s after %lu us\n", dname[dir], usec() - t0);
	return dname[dir];
}

int
main(int argc, char *argv[]) {
	int r;
	fd_set readfds;
	struct timeval tv;
	#ifdef DEBUG
	unsigned count = 0;
	#endif

	#ifdef DEBUG
	if (!(logfile = fopen("bot.log", "w"))) {
		debug("fopen: %s\n", strerror(errno));
		return 1;
	}
	#endif
	srand(time(NULL));
	if (!((r = fcntl(STDIN_FILENO, F_GETFL)) & O_NONBLOCK))
		fcntl(STDIN_FILENO, r | O_NONBLOCK);

	while (true) {
		FD_ZERO(&readfds);
		FD_SET(STDIN_FILENO, &readfds);
        	tv.tv_sec = tv.tv_usec = 0;
		r = select(STDIN_FILENO + 1, &readfds, 0, 0, &tv);
		if (r < 0) {
			if (errno != EINTR) {
				debug("main: select: %s\n", strerror(errno));
				break;
			}
			continue;
		}
		if (r > 0) {
			#ifdef DEBUG
			unsigned long t = usec();
			#endif
			Map map;
			Map::MakeMove(MakeMove(map));
			#ifdef DEBUG
			t = usec() - t;
			if (t < (count++ ? 1000000 : 3000000)) {
				debug("main: reply %u sent in %lu us\n",
				    count, t);
			} else {
				debug("==========================================\n");
				debug("!!! ERROR: TIME LIMIT EXCEEDED: %lu us !!!\n", t);
				debug("==========================================\n");
//				return 0;
			}
			#endif
			continue;
		}
		/* spend at most 1/10th of a second spawning */
//		if (!nodes.empty())
//			Spawn(100000);
	}
	return 0;
}