/* $Id$ */

/*
 * Copyright (c) 2010 Daniel Hartmeier <daniel@benzedrine.ch>
 * All rights reserved.
 *
 * COPYING, REDISTRIBUTION AND USE IN ANY FORM ARE PROHIBITED WITHOUT
 * EXPLICIT WRITTEN PERMISSION.
 *
 */

#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 "expand.h"

struct Fill {
	Fill(const Board &board, const vector<DIR> &v,
	    const pair<int, int> &src) : board(board), v(v), a(src), b(src),
	    l(v.size()), i(0), j(0), s(0), t(0) { }
	Board board;
	vector<DIR> v;
	pair<int, int> a, b;
	unsigned l;
	unsigned i, j;
	int s, t;
private:
	Fill(const Fill &f) : board(f.board), v(f.v), a(f.a), b(f.b), l(f.l),
	    i(f.i), j(f.j), s(f.s), t(f.t) { }
};

static vector<DIR>
shortestPath(const Board &board, const pair<int, int> &src,
    const pair<int, int> &dst)
{
	vector<DIR> v;
	vector<set<pair<int, int> > > sc(2);
	map<pair<int, int>, unsigned> cs;
	pair<int, int> n;
	unsigned s = 0;

	sc[0].insert(src);
	cs[src] = s;
	while (true) {
		bool found = false;
		for (set<pair<int, int> >::iterator c = sc[s].begin();
		    c != sc[s].end(); ++c) {
			for (int d = 0; d < 4; ++d) {
				n = step(*c, (DIR)d);
				if (n != src &&
				    !board.read(n.first, n.second) &&
				    cs.find(n) == cs.end()) {
					sc[s + 1].insert(n);
					cs[n] = s + 1;
					found = true;
					if (n == dst) {
						s++;
						goto walkback;
					}
				}
			}
		}
		if (!found)
			return v;
		s++;
		set<pair<int, int> > e;
		sc.insert(sc.end(), e);
	}
walkback:
	pair<int, int> o = dst;
	while (s > 0) {
		bool found = false;
		for (int d = 0; d < 4; ++d) {
			n = step(o, (DIR)((d + 2) % 4));
			if (cs.find(n) != cs.end() && cs[n] == s - 1) {
				v.insert(v.begin(), (DIR)d);
				o = n;
				found = true;
				break;
			}
		}
		if (!found) {
			#ifdef DEBUG
			debug("shortestPath: ERROR: !found\n");
			exit(0);
			#endif
			return v;
		}
		if (s == 1)
			break;
		s--;
	}
	return v;
}

/*
 * v may not be empty, i.e. v.size() >= 1
 * board must have entire path unwritten, including src and dst
 */
unsigned
expandFill(const Board &board, pair<int, int> src, vector<DIR> &v,
    unsigned limit, unsigned long timeout)
{
	vector<DIR> maxv = v, p;
	unsigned maxl = v.size();
	stack<Fill *> q;
	Fill *f, *h;
	pair<int, int> c, d, e;
	unsigned count = 0;

	#ifdef DEBUG
	if (v.empty()) {
		debug("expandFill: ERROR: input path empty\n");
		exit(0);
	}
	debug("expandFill: src (%d,%d) input path (%d)", src.first, src.second, (int)v.size());
	for (unsigned k = 0; k < v.size(); ++k)
		debug(" %s", dname[v[k]]);
	debug("\n");
	board.checkPath(src, v);
	#endif

	debug("expandFill: called with limit %u for src (%d,%d) on board:\n",
	    limit, src.first, src.second);
	f = new Fill(board, v, src);
	e = src;
	for (unsigned k = 0; k < v.size(); ++k) {
		f->board.write(e.first, e.second);
		e = step(e, (DIR)v[k]);
	}
	f->board.write(e.first, e.second);
	#ifdef DEBUG
	f->board.print();
	#endif
	f->a = step(src, (DIR)v[0]);
	f->i = 1;
	q.push(f);

restart:
	while (!q.empty() && usec() < timeout) {
		Fill *g = q.top();
		q.pop();
		while (usec() < timeout) {
			count++;
			if (g->s == 4) {
//debug("s == 4: i %u -> %u\n", g->i, g->i + 1);
				g->a = step(g->a, (DIR)g->v[g->i]);
				g->i++;
				g->s = 0;
			}
// XXX			if (g->i > g->l) {
			if (g->i > g->l || g->i > g->j + 1) {
//debug("i %u == l %u - 1: t %d -> %d\n", g->i, g->l, g->t, g->t + 1);
				g->t++;
				g->i = g->j + 1;
				g->a = step(g->b, (DIR)g->v[g->j]);
			}
			if (g->t == 4) {
//debug("t == 4: j %u -> %u\n", g->j, g->j + 1);
				g->b = step(g->b, (DIR)g->v[g->j]);
				g->a = step(g->a, (DIR)g->v[g->j + 1]);
				g->j++;
				g->i++;
				g->t = 0;
			}
			if (g->j > g->l - 1) {
//debug("j %u == l %u - 2: break\n", g->j, g->l);
				break;
			}
			c = step(g->a, (DIR)g->s);
			d = step(g->b, (DIR)g->t);
//			debug("expandFill: i %u, j %u, s %s, t %s, a (%d,%d), b(%d,%d), c(%d,%d), d(%d,%d)\n", g->i, g->j, dname[g->s], dname[g->t], g->a.first, g->a.second, g->b.first, g->b.second, c.first, c.second, d.first, d.second);
			#ifdef DEBUG
			if (c.first < 0 || c.second < 0 || d.first < 0 || d.second < 0) {
				debug("invalid coordinates!!!\n");
				exit(0);
			}
			#endif
			if (g->board.read(c.first, c.second) ||
			    g->board.read(d.first, d.second) ||
			    ((p = shortestPath(g->board, d, c))).empty() ||
			    p.size() + 2 <= g->i - g->j)
				goto skip;
/*
			debug("expandFill: replacement (%d)", (int)p.size());
			for (unsigned k = 0; k < p.size(); ++k)
				debug(" %s", dname[p[k]]);
			debug("\n");
			debug("expandFill: old");
			for (unsigned k = 0; k < g->v.size(); ++k)
				debug(" %s", dname[g->v[k]]);
			debug("\n");
*/
			h = new Fill(g->board, g->v, src);

			// remove old path
			e = g->b;
			for (unsigned k = g->j; k < g->i; ++k) {
				e = step(e, (DIR)g->v[k]);
				if (k + 1 < g->i)
					h->board.clear(e.first, e.second);
//debug("removing %s at %u\n", dname[h->v[k]], g->j);
				h->v.erase(h->v.begin() + g->j);
				h->l--;
			}
/*
debug("path after removal:");
for (unsigned k = 0; k < h->v.size(); ++k)
	debug(" %s", dname[h->v[k]]);
debug("\n");
*/
			// insert new path (inserts before)
//debug("inserting %s at %u\n", dname[g->t], g->j);
			h->v.insert(h->v.begin() + g->j, (DIR)g->t);
			h->board.write(d.first, d.second);
			h->l++;
/*
debug("path after first insert:");
for (unsigned k = 0; k < h->v.size(); ++k)
	debug(" %s", dname[h->v[k]]);
debug("\n");
*/
			e = d;
			for (unsigned k = 0; k < p.size(); ++k) {
				e = step(e, (DIR)p[k]);
				h->board.write(e.first, e.second);
//debug("inserting %s at %u\n", dname[p[k]], g->j + k + 1);
				h->v.insert(h->v.begin() + g->j + k + 1, (DIR)p[k]);
				h->l++;
			}
/*
debug("path after second insert:");
for (unsigned k = 0; k < h->v.size(); ++k)
	debug(" %s", dname[h->v[k]]);
debug("\n");
*/
//debug("inserting %s at %u\n", dname[(g->s + 2) % 4], g->j + (unsigned)p.size() + 1);
			h->v.insert(h->v.begin() + g->j + p.size() + 1,
			    (DIR)((g->s + 2) % 4));
			h->board.write(c.first, c.second);
			h->l++;
/*
			debug("expandFill: h board:\n");
			h->board.print();
			debug("expandFill: new");
			for (unsigned k = 0; k < h->v.size(); ++k)
				debug(" %s", dname[h->v[k]]);
			debug("\n");
*/
			#ifdef DEBUG
			board.checkPath(src, h->v);
			#endif

			if (h->l > maxl) {
//				debug("expandFill: max %u -> %u\n", maxl, h->l);
				maxv = h->v;
				maxl = h->l;
/*
debug("new max path (%d=%d):", (int)h->v.size(), h->l);
for (unsigned k = 0; k < h->v.size(); ++k)
debug(" %s", dname[h->v[k]]);
debug("\n");
*/
				if (maxl >= limit) {
//					debug("expandFill: max %u >= limit "
//					    "%u, abort\n", maxl, limit);
					goto done;
				}
			}

			// prepare h for first loop pass
			h->a = step(h->a, (DIR)h->v[0]);
			h->i = 1;

			g->s++;
			q.push(g);
			q.push(h);
			goto restart;
skip:
			g->s++;
		}
		delete g;
	}
done:
//	debug("expandFill: after loop, q.size %u\n", (unsigned)q.size());
	if (q.empty()) {
		debug("expandFill: exhausted all improvements\n");
	} else {
		while (!q.empty()) {
			delete q.top();
			q.pop();
		}
	}
	#ifdef DEBUG
	if (usec() >= timeout) {
		debug("expandFill: timed out after %u iterations\n", count);
	}
	#endif
	v = maxv;
	return maxl;
}