/*
 * 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"

const char *dname[] = { "NORTH", "EAST", "SOUTH", "WEST" };
const char *rname[] = { "LOSS", "UNDECIDED", "DRAW", "WIN" };

bool
Board::isolated() const
{
	Board b(*this);
	queue<pair<int, int> > q;
	pair<int, int> o(ox, oy), n;
	bool found = false;

	q.push(pair<int, int>(mx, my));
	do {
		n = q.front();
		q.pop();
		if (n == o) {
			found = true;
			break;
		}
		if (!b.read(n.first, n.second)) {
			b.write(n.first, n.second);
			q.push(pair<int, int>(n.first, n.second - 1));
			q.push(pair<int, int>(n.first, n.second + 1));
			q.push(pair<int, int>(n.first - 1, n.second));
			q.push(pair<int, int>(n.first + 1, n.second));
		}
	} while (!q.empty());
	return !found;
}

/* find shortest path to opponent
 * return number of steps needed to walk into opponent
 * or 0 if we are isolated from opponent
 */
unsigned
Board::pathToOpponent() const
{
	vector<set<pair<int, int> > > sc(2500);
	map<pair<int, int>, unsigned> cs;
	pair<int, int> m(getMyPos()), o(getOpPos());
	unsigned step = 0;
	sc[0].insert(m);
	cs[m] = step;
	while (true) {
		unsigned found = 0;
		for (set<pair<int, int> >::iterator c = sc[step].begin();
		    c != sc[step].end(); ++c) {
			for (int d = 0; d < 4; ++d) {
				pair<int, int> n = *c;
				switch (d) {
				case NORTH: n.second--; break;
				case EAST:  n.first++;  break;
				case SOUTH: n.second++; break;
				case WEST:  n.first--;  break;
				}
				if (n == o)
					return step + 1;
				if (!read(n.first, n.second) && n != m &&
				    cs.find(n) == cs.end()) {
					sc[step + 1].insert(n);
					cs[n] = step + 1;
					found++;
				}
			}
		}
		if (!found)
			return 0;
		step++;
	}
	return step;
}

#ifdef DEBUG
void
Board::print() const {
	for (int y = 0; y < h; ++y) {
		for (int x = 0; x < w; ++x) {
			if (read(x, y))
				debug("#");
			else if (y == my && x == mx)
				debug("1");
			else if (y == oy && x == ox)
				debug("2");
			else
				debug("%c", read(x, y) ? '#' : ' ');
		}
		debug("\n");
	}
}
#endif

#ifdef DEBUG
void
Board::checkPath(pair<int, int> s, const vector<DIR> &v) const
{
	Board b(*this);
/*
	if (b.read(s.first, s.second)) {
		debug("checkPath: src (%d,%d) occupied!\n", s.first, s.second);
		b.print();
		exit(0);
	}
*/
	for (unsigned i = 0; i < v.size(); ++i) {
		b.write(s.first, s.second);
		s = step(s, v[i]);
		if (b.read(s.first, s.second)) {
			debug("checkPath: (%d,%d) occupied in step %u!\n",
			    s.first, s.second, i);
			b.print();
			debug("checkPath: bad path:");
			for (unsigned j = 0; j < v.size(); ++j)
				debug(" %u=%s", j, dname[v[j]]);
			debug("\n");
			exit(0);
		}
	}
}
#endif

struct Path {
	pair<int, int> dst;
	unsigned step;
};

int
Board::voronoi() const
{
	Path *p, *n;
	queue<Path *> q;
	map<pair<int, int>, unsigned> m, o;

	Board b(*this);
	p = new Path;
	p->dst = b.getMyPos();
	b.write(p->dst.first, p->dst.second);
	p->dst = b.getOpPos();
	b.write(p->dst.first, p->dst.second);

	/* flood-fill from opponent */
	p->step = 0;
	q.push(p);
	do {
		p = q.front();
		q.pop();
		for (int d = 0; d < 4; ++d) {
			n = new Path;
			n->dst = step(p->dst, (DIR)d);
			if (!b.read(n->dst.first, n->dst.second) &&
			    o.find(n->dst) == o.end()) {
				n->step = p->step + 1;
				o.insert(make_pair(n->dst, n->step));
				q.push(n);
			} else
				delete n;
		}
		delete p;
	} while (!q.empty());

	/* flood-fill from me */
	p = new Path;
	p->dst = b.getMyPos();
	p->step = 0;
	q.push(p);
	do {
		p = q.front();
		q.pop();
		for (int d = 0; d < 4; ++d) {
			n = new Path;
			n->dst = step(p->dst, (DIR)d);
			if (!b.read(n->dst.first, n->dst.second) &&
			    m.find(n->dst) == m.end()) {
				n->step = p->step + 1;
				m.insert(make_pair(n->dst, n->step));
				q.push(n);
			} else
				delete n;
		}
	} while (!q.empty());

	int count = 0;
	for (map<pair<int, int>, unsigned>::iterator i = m.begin(); i != m.end(); ++i) {
		map<pair<int, int>, unsigned>::iterator j = o.find(i->first);
		if (j == o.end() || i->second < j->second)
			count++;
	}
	for (map<pair<int, int>, unsigned>::iterator i = o.begin(); i != o.end(); ++i) {
		map<pair<int, int>, unsigned>::iterator j = m.find(i->first);
		if (j == m.end() || i->second < j->second)
			count--;
	}

	return count;
}