/*
 * 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 "node.h"
#include "graph.h"
#include "maxsteps.h"

Node		*root = NULL;
list<Node *>	 nodes;
unsigned long	 treesize = 0;

Node::Node(const Board &b) : board(b), parent(NULL) {
	treesize++;
	worst[0] = worst[1] = worst[2] = worst[3] = UNDECIDED;
	for (int m = 0; m < 4; ++m)
		for (int o = 0; o < 4; ++o)
			children[m][o] = NULL;
	best = board.rate();
	movesToWin = (best == WIN) ? 0 : 999;
	movesToDraw = (best != LOSS) ? 0 : -999;
	movesToLoss = 0;
	area = -999;
	leaf = best != UNDECIDED;
	if (!leaf)
		isolated = board.isolated();
	else
		isolated = false;
	i = leaf ? nodes.end() : nodes.insert(nodes.end(), this);
}

Node::Node(Node *p, DIR m, DIR o, unsigned long timeout) : board(p->board), parent(p) {
	treesize++;
	board.move(false, m);
	board.move(true, o);
	worst[0] = worst[1] = worst[2] = worst[3] = UNDECIDED;
	for (int m = 0; m < 4; ++m)
		for (int o = 0; o < 4; ++o)
			children[m][o] = NULL;
	best = board.rate();
	leaf = best != UNDECIDED;
	if (!parent->isolated && !leaf) {
		isolated = board.isolated();
	} else {
		/* parent->isolated || leaf */
		isolated = parent->isolated;
		if (leaf) {
			movesToWin = (best == WIN) ? 0 : 9999;
			movesToDraw = (best != LOSS) ? 0 : -9999;
			movesToLoss = 0;
			area = -7777;
		} else {
			/* parent->isolated */
			if (best == UNDECIDED)
				best = parent->best;
			movesToWin = (best == WIN) ? parent->movesToWin - 1 : 9999;
			movesToDraw = (best != LOSS) ? parent->movesToDraw - 1 : -9999;
			movesToLoss = parent->movesToLoss - 1;
			area = parent->area - 1;
		}
	}
	if (!leaf) {
		if (isolated)
			isolation(timeout);
		else
			area = board.voronoi();
	}
	i = leaf ? nodes.end() : nodes.insert(nodes.end(), this);
}

Node::~Node() {
	treesize--;
	if (leaf)
		return;
	if (i != nodes.end()) {
		nodes.erase(i);
		i = nodes.end();
	}
	for (int m = 0; m < 4; ++m)
		for (int o = 0; o < 4; ++o)
			if (children[m][o])
				delete children[m][o];
}

void
Node::spawn(unsigned long timeout)
{
	const unsigned minRateTime = 8000 +
	    (72000 * board.getWidth() * board.getHeight() / 2500);

	if (!isolated) {
		RESULT best = LOSS;
		RESULT worst[4] = { WIN, WIN, WIN, WIN };
		unsigned undecided_count = 0;
		DIR undecided_dir = NORTH; // shut up warning
		for (int m = 0; m < 4; ++m) {
			for (int o = 0; o < 4; ++o) {
				if (usec() + minRateTime > timeout) {
					if (root == this) {
						debug("Node::spawn() timeout on root, must continue\n");
					} else
						return;
				}
				if (!children[m][o])
					children[m][o] = new Node(this, (DIR)m, (DIR)o, timeout);
				if (children[m][o]->best < worst[m])
					worst[m] = children[m][o]->best;
			}
			if (worst[m] > best)
				best = worst[m];
			if (worst[m] == UNDECIDED) {
				undecided_count++;
				undecided_dir = (DIR)m;
			}
		}
		push();
/* XXX actually seems to make things worse, interesting
		if (this != root && best == UNDECIDED && undecided_count == 1) {
			// no worst[m] is WIN, exactly one worst[m] is UNDECIDED
			// re-schedule children[m] to our place in the queue
			for (int o = 0; o < 4; ++o) {
				if (children[undecided_dir][o]->i != nodes.end()) {
					debug("Node::spawn: RE-SCHEDULING ONLY CHOICE TO FRONT OF QUEUE!\n");
					nodes.erase(children[undecided_dir][o]->i);
					children[undecided_dir][o]->i = nodes.insert(i, children[undecided_dir][o]);
				}
			}
		}
*/
	}
	/* !leaf && i != nodes.end() */
	nodes.erase(i);
	i = nodes.end();
}

/* children[m][o] has changed its best/worst[], update mine if needed,
 * and push to parent, if changed */
void
Node::push()
{
	bool changed = false;

	/* update best/worst[] */
	RESULT old_best = best;
	best = LOSS;
	for (int m = 0; m < 4; ++m) {
		worst[m] = WIN;
		for (int o = 0; o < 4; ++o) {
			if (!children[m][o]) {
				#ifdef DEBUG
				debug("Node::push: child NULL\n");
				exit(0);
				#endif
				return;
			}
			if (children[m][o]->best < worst[m])
				worst[m] = children[m][o]->best;
		}
		if (worst[m] > best)
			best = worst[m];
	}
	if (best != old_best)
		changed = true;

	if (best == WIN) {
		int old_movesToWin = movesToWin;
		movesToWin = 999999;
		for (int m = 0; m < 4; ++m) {
			if (worst[m] != WIN)
				continue;
			int max = -999999;
			for (int o = 0; o < 4; ++o) {
				/* if worst[m] is WIN, all children must be WIN */
				if (children[m][o]->movesToWin > max)
					max = children[m][o]->movesToWin;
			}
			if (max < movesToWin)
				movesToWin = max;
		}
		movesToWin++;
		if (movesToWin != old_movesToWin)
			changed = true;
	}

	if (best == DRAW) {
		int old_movesToDraw = movesToDraw;
		movesToDraw = -999999;
		for (int m = 0; m < 4; ++m) {
			if (worst[m] != DRAW)
				continue;
			int min = 999999;
			for (int o = 0; o < 4; ++o) {
				if (children[m][o]->best > DRAW)
					continue;
				if (children[m][o]->movesToDraw < min)
					min = children[m][o]->movesToDraw;
			}
			if (min > movesToDraw)
				movesToDraw = min;
		}
		movesToDraw++;
		if (movesToDraw != old_movesToDraw)
			changed = true;
	}

	if (best == LOSS) {
		int old_movesToLoss = movesToLoss;
		movesToLoss = -999999;
		for (int m = 0; m < 4; ++m) {
			int min = 999999;
			/* if best is LOSS, all worst[m] must be LOSS */
			for (int o = 0; o < 4; ++o) {
				if (children[m][o]->best > LOSS)
					continue;
				if (children[m][o]->movesToLoss < min)
					min = children[m][o]->movesToLoss;
			}
			if (min > movesToLoss)
				movesToLoss = min;
		}
		movesToLoss++;
		if (movesToLoss != old_movesToLoss)
			changed = true;
	}

	if (best == UNDECIDED) {
		int old_area = area;
		area = -999999;
		for (int m = 0; m < 4; ++m) {
			if (worst[m] != UNDECIDED)
				continue;
			int min = 999999;
			for (int o = 0; o < 4; ++o) {
				if (children[m][o]->best > UNDECIDED)
					continue;
				if (children[m][o]->area < min)
					min = children[m][o]->area;
			}
			if (min > area)
				area = min;
		}
		if (area != old_area)
			changed = true;
	}

	if (changed && parent && parent->i == nodes.end())
		parent->push();
}

void
Node::rateIsolation(unsigned max, unsigned min, vector<DIR> &v,
    unsigned long timeout)
{
	if (!min && !max) {
		best = DRAW;
		movesToDraw = 1;
		return;
	}
	if (!max) {
		best = LOSS;
		movesToLoss = 1;
		return;
	}
	if (!min) {
		best = WIN;
		movesToWin = 1;
		return;
	}
	/* max > 0 && min > 0 */
	debug("Node::rateIsolation: max %u, min %u: calling maxSteps(limit %u) on board:\n", max, min, ((max <= min) ? max : (min + 1)));
	#ifdef DEBUG
	board.print();
	#endif
	Graph g(board);
	pair<int, int> me = board.getMyPos();
	set<pair<int, int> > a = g.findAllArticulations(me);
	Board b(board);
	for (set<pair<int, int> >::const_iterator i = a.begin();
	    i != a.end(); ++i)
		b.write(i->first, i->second);
	unsigned opt = maxSteps(a, b, me, v,
	    ((max <= min) ? max : (min + 1)), timeout);
	if (opt > min) {
		debug("Node::rateIsolation: max %u, min %u, opt %u -> WIN\n", max, min, opt);
		best = WIN;
		movesToWin = min + 1;
		return;
	}
	if (opt == min) {
		debug("Node::rateIsolation: max %u, min %u, opt %u -> DRAW\n", max, min, opt);
		best = DRAW;
		movesToDraw = opt + 1;
		return;
	}
	debug("Node::rateIsolation: max %u, min %u, opt %u -> LOSS\n", max, min, opt);
	best = LOSS;
	movesToLoss = opt + 1;
}

void
Node::isolation(unsigned long timeout)
{
	unsigned max = floodFill(false);
	unsigned min = floodFill(true);
	rateIsolation(max, min, path, timeout);
}

/* called only when isolated
 * return the number of empty spaces reachable from my/op position
 * i.e. the maximum number of steps the player can still make
 * this is cheap, but doesn't guarantee a walkable path of such length
 * used as upper limit in the precise (but slow) search with maxSteps()
 */
unsigned
Node::floodFill(bool op) const
{
	Board b(board);
	queue<pair<int, int> > q;
	pair<int, int> m = op ? b.getOpPos() : b.getMyPos();
	unsigned count = 0, sameColor = 0, diffColor = 0;
	int myColor = (m.first + m.second) % 2;
	list<pair<int, int> > s;

//	debug("floodFill: %s\n", op ? "op" : "me");
	q.push(m);
	do {
		pair<int, int> n = q.front();
		if (!b.read(n.first, n.second)) {
			b.write(n.first, n.second);
			s.insert(s.end(), n);
			if (n != m) {
				count++;
				if (((n.first + n.second) % 2) == myColor)
					sameColor++;
				else
					diffColor++;
			}
			q.push(step(n, NORTH));
			q.push(step(n, EAST));
			q.push(step(n, SOUTH));
			q.push(step(n, WEST));
		}
		q.pop();
	} while (!q.empty());

	if (count <= 1)
		return count;

//	debug("floodFill: %s upper limit flood: %u (%u same, %u diff color)\n", op ? "op" : "me", count, sameColor, diffColor);

	unsigned reductionColor = 0;
	// dmj's "mostly useless" idea ;)
	if (sameColor > diffColor)
		reductionColor = sameColor - diffColor;
	else if (diffColor > sameColor + 1)
		reductionColor = diffColor - (sameColor + 1);

	unsigned reductionLeafs = 0;
	b = board;
	unsigned leafs;
	do {
		Board c(b);
		leafs = 0;
		list<pair<int, int> >::iterator p = s.begin();
		while (p != s.end()) {
			bool leafisme = *p == m;
			/* count number of empty neighbours */
			unsigned n = 0;
			DIR d = NORTH;
			if (!b.read(p->first, p->second - 1)) { n++; d = NORTH; }
			if (!b.read(p->first + 1, p->second)) { n++; d = EAST;  }
			if (!b.read(p->first, p->second + 1)) { n++; d = SOUTH; }
			if (!b.read(p->first - 1, p->second)) { n++; d = WEST;  }
			if (n < 2) {
				if (leafisme) {
					c.move(op, d);
					m = op ? c.getOpPos() : c.getMyPos();
				} else {
					c.write(p->first, p->second);
					leafs++;
				}
				p = s.erase(p);
			} else
				p++;
		}
		b = c;
		if (leafs > 1)
			reductionLeafs += leafs - 1;
	} while (leafs);

	return count - ((reductionColor > reductionLeafs) ?  reductionColor :
	    reductionLeafs);
}

int
Node::farthestLoss(DIR &dir) const
{
	vector<DIR> v;
	int max = -999999;
	for (int m = 0; m < 4; ++m) {
		int min = 999999;
		/* root->best == LOSS implies worst[any m] == LOSS */
		for (int o = 0; o < 4; ++o) {
			if (children[m][o]->best > LOSS)
				continue;
			if (children[m][o]->movesToLoss < min)
				min = children[m][o]->movesToLoss;
		}
		if (min == max)
			v.insert(v.end(), (DIR)m);
		else if (min > max) {
			max = min;
			v.clear();
			v.insert(v.end(), (DIR)m);
		}
	}
	if (v.empty()) {
		debug("ERROR: farthestLoss() v.empty()\n");
	} else
		dir = (DIR)v[(rand() >> 8) % v.size()];
	return max;
}

int
Node::farthestDraw(DIR &dir) const
{
	/* XXX this should consider picking a worst[m] UNDECIDED, under some circumstances */
	vector<DIR> v;
	int max = -999999;
	for (int m = 0; m < 4; ++m) {
		int min = 999999;
		if (worst[m] < DRAW)
			continue;
		for (int o = 0; o < 4; ++o) {
			if (children[m][o]->best > DRAW)
				continue;
			if (children[m][o]->movesToDraw < min)
				min = children[m][o]->movesToDraw;
		}
		if (min == max)
			v.insert(v.end(), (DIR)m);
		else if (min > max) {
			max = min;
			v.clear();
			v.insert(v.end(), (DIR)m);
		}
	}
	if (v.empty()) {
		debug("ERROR: farthestDraw() v.empty()\n");
	} else
		dir = (DIR)v[(rand() >> 8) % v.size()];
	return max;
}

int
Node::nearestWin(DIR &dir) const
{
	vector<DIR> v;
	int min = 999999;
	for (int m = 0; m < 4; ++m) {
		if (worst[m] < WIN)
			continue;
		int max = -999999;
		for (int o = 0; o < 4; ++o) {
			if (children[m][o]->movesToWin > max)
				max = children[m][o]->movesToWin;
		}
		if (max == min)
			v.insert(v.end(), (DIR)m);
		else if (max < min) {
			min = max;
			v.clear();
			v.insert(v.end(), (DIR)m);
		}
	}
	if (v.empty()) {
		debug("ERROR: nearestWin() v.empty()\n");
	} else
		dir = (DIR)v[(rand() >> 8) % v.size()];
	return min;
}

int
Node::bestUndecided(DIR &dir) const
{
	/* best == UNDECIDED -> at least one worst[m] == UNDECIDED, all other worst[m] == LOST */
	map<DIR, unsigned> v;
	int max = -999999;
	pair<int, int> m = board.getMyPos(), o = board.getOpPos();

	for (int m = 0; m < 4; ++m) {
		int min = 999999;
		unsigned pto = 0;
		if (worst[m] < UNDECIDED)
			continue;
		for (int o = 0; o < 4; ++o) {
			if (children[m][o]->best > UNDECIDED)
				continue;
			if (children[m][o]->area < min) {
				min = children[m][o]->area;
				pto = children[m][o]->board.pathToOpponent();
			}
		}
		if (min == max)
			v.insert(make_pair((DIR)m, pto));
		else if (min > max) {
			max = min;
			v.clear();
			v.insert(make_pair((DIR)m, pto));
		}
	}
	if (v.empty()) {
		#ifdef DEBUG
		debug("largestArea: ERROR: v.empty()\n");
		exit(0);
		#endif
		return 0;
	}
	#ifdef DEBUG
	debug("largestArea: picking shortest pto out of");
	for (map<DIR, unsigned>::iterator i = v.begin(); i != v.end(); ++i)
		debug(" %s (pto %u)", dname[i->first], i->second);
	debug(" (%d) with area %d\n", (int)v.size(), max);
	#endif
	vector<DIR> w;
	unsigned min = 999999;
	for (map<DIR, unsigned>::iterator i = v.begin(); i != v.end(); ++i) {
		if (i->second == min)
			w.insert(w.end(), i->first);
		else if (i->second < min) {
			min = i->second;
			w.clear();
			w.insert(w.end(), i->first);
		}
	}
	#ifdef DEBUG
	debug("largestArea: picking random out of");
	for (unsigned i = 0; i < w.size(); ++i)
		debug(" %s (pto %u)", dname[w[i]], min);
	debug(" (%d) with area %d\n", (int)w.size(), max);
	#endif
	dir = w[rand() % w.size()];
	return w.size();
}