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

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

unsigned
expandFill(const Board &board, pair<int, int> src, vector<DIR> &v, unsigned limit, unsigned long timeout)
{
	stack<Fill> q;
	pair<int, int> c, d, e;
	Fill fmax(board, v);

	Fill f(board, v);
	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);
	f.a = src;
	q.push(f);
restart:
	while (!q.empty()) {
		Fill g = q.top();
		q.pop();

		while (g.i < g.l) {
			if (g.s == -1) {
				g.b = g.a;
				switch (g.v[g.i]) {
				case NORTH:
					g.a.second--;
					break;
				case EAST:
					g.a.first++;
					break;
				case SOUTH:
					g.a.second++;
					break;
				case WEST:
					g.a.first--;
					break;
				}
			}
			while (g.s <= 1) {
				if (usec() >= timeout)
					goto done;
				switch (g.v[g.i]) {
				case NORTH:
					c = make_pair(g.a.first + g.s, g.a.second);
					d = make_pair(g.b.first + g.s, g.b.second);
					break;
				case SOUTH:
					c = make_pair(g.a.first - g.s, g.a.second);
					d = make_pair(g.b.first - g.s, g.b.second);
					break;
				case EAST:
					c = make_pair(g.a.first, g.a.second + g.s);
					d = make_pair(g.b.first, g.b.second + g.s);
					break;
				case WEST:
					c = make_pair(g.a.first, g.a.second - g.s);
					d = make_pair(g.b.first, g.b.second - g.s);
					break;
				}
				if (!g.board.read(c.first, c.second) &&
				    !g.board.read(d.first, d.second)) {
					Fill h(g.board, g.v);
					h.board.write(c.first, c.second);
					h.board.write(d.first, d.second);
					h.v.insert(h.v.begin() + g.i + 1, (DIR)((g.v[g.i] + 2 + g.s) % 4));
					h.v.insert(h.v.begin() + g.i, (DIR)((g.v[g.i] + 4 + g.s) % 4));
					h.l += 2;
					h.i = f.i;
					h.s = f.s;
					h.a = f.a;
					h.b = f.b;

					if (h.l > fmax.l) {
						fmax = h;
						if (fmax.l >= limit) {
							debug("expandFill: max %u >= limit %u, abort\n", fmax.l, limit);
							goto done;
						}
					}
					g.s += 2;
					if (g.s > 1) {
						g.i++;
						g.s = -1;
					}
					q.push(g);
					q.push(h);
					goto restart;
				}
				g.s += 2;
			}
			g.i++;
			g.s = -1;
		}
	}
	#ifdef DEBUG
	if (q.empty() && fmax.l < limit) {
		debug("expandFill: exhausted all improvements "
		    "(max %u < limit %u)\n", fmax.l, limit);
	}
	#endif
done:
	#ifdef DEBUG
	if (usec() >= timeout) {
		debug("expandFill: timed out (max %u < limit %u)\n",
		    fmax.l, limit);
	}
	#endif
	v = fmax.v;
	return fmax.l;
}