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

struct Path {
	bool operator<(const Path &o) const { return dst < o.dst; }
	pair<int, int> dst;
	vector<DIR> v;
};

unsigned
maxSteps(set<pair<int, int> > aps, const Board &board, pair<int, int> src,
    vector<DIR> &v, unsigned limit, unsigned long timeout, unsigned level)
{
	const unsigned maxExpandTime = 4000 + (36000 * limit / 2302);

	unsigned max = 0;
//	debug("maxSteps: level %u: called with limit %u for src (%d,%d)\n", level, limit, src.first, src.second);
//	board.print();

	Board b(board);
	queue<Path> q;
	Path p, n, m;
	vector<Path> r;
	unsigned count = 0;

	b.clear(src.first, src.second);
	p.dst = src;
	set<Path> caps;
	q.push(p);
	do {
		p = q.front();
		q.pop();
		if (aps.find(p.dst) != aps.end() && p.dst != src)
			caps.insert(p);
		if (!b.read(p.dst.first, p.dst.second)) {
			if (p.dst != src) {
				m = p;
				r.insert(r.end(), p);
			}
			b.write(p.dst.first, p.dst.second);
			count++;
			for (int d = 0; d < 4; ++d) {
				n = p;
				n.v.insert(n.v.end(), (DIR)d);
				n.dst = step(n.dst, (DIR)d);
				q.push(n);
			}
		}
	} while (!q.empty());
	count--;

	debug("maxSteps: level %u: count %u\n", level, count);

	debug("maxSteps: level %u: found %d caps:\n", level, (int)caps.size());
	for (set<Path>::iterator a = caps.begin(); a != caps.end(); ++a) {
		debug("(%d,%d) shortest path (%d)", a->dst.first, a->dst.second, (int)a->v.size());
		for (unsigned j = 0; j < a->v.size(); ++j)
			debug(" %s", dname[a->v[j]]);
		debug("\n");
	}

//	debug("maxSteps: board now:\n");
//	b.print();

	if (caps.empty()) {
		/* leaf room */
		if (count == 1) {
			/* trivial case */
			for (int d = 0; d < 4; ++d) {
				pair<int, int> n = step(src, (DIR)d);
				if (!board.read(n.first, n.second)) {
					debug("maxSteps: leaf room: trivial v=%s, max 1\n", dname[d]);
					v.insert(v.end(), (DIR)d);
					max++;
					return max;
				}
			}
		}
		unsigned submax = 0;
		vector<DIR> maxv;
		for (int d = -2; d < 4; ++d) {
			if (d == -1) {
				m = r[rand() % r.size()];
			} else if (d >= 0) {
				m.dst = step(src, (DIR)d);
				if (board.read(m.dst.first, m.dst.second))
					continue;
				m.v.clear();
				m.v.insert(m.v.end(), (DIR)d);
			}

			debug("maxSteps: level %u: leaf room: d %d corner (%d,%d) path (%d)", level, d, m.dst.first, m.dst.second, (int)m.v.size());
			for (unsigned j = 0; j < m.v.size(); ++j)
				debug(" %s", dname[m.v[j]]);
			debug("\n");
			debug("maxSteps: level %u: leaf room: calling expandFill() with src (%d,%d) and path (%d)", level, src.first, src.second, (int)m.v.size());
			for (unsigned j = 0; j < v.size(); ++j)
				debug(" %s", dname[v[j]]);
			debug(" on board:\n");
//			board.print();
			unsigned sub = expandFill(board, src, m.v, count - m.v.size(), usec() + maxExpandTime < timeout ? usec() + maxExpandTime : timeout);
			debug("maxSteps: level %u: leaf room: leaf room: expandFill() found max %u\n", level, sub);
			if (sub > submax) {
				submax = sub;
				maxv = m.v;
				if (submax >= count)
					break;
			}
		}
		v.insert(v.end(), maxv.begin(), maxv.end());
		max += submax;
		return max;
	}
	/* not a leaf room, one or more caps */
	debug("maxSteps: level %u: room is not a leaf, find maxcap\n", level);
	set<pair<int, int> > saps = aps;
	for (set<Path>::iterator a = caps.begin(); a != caps.end(); ++a)
		saps.erase(a->dst);
	saps.erase(src);
	Path maxcap;
	unsigned submax = 0;
	vector<DIR> maxv;
	for (set<Path>::iterator a = caps.begin(); a != caps.end(); ++a) {
		vector<DIR> subv;
		unsigned sub = maxSteps(saps, b, a->dst, subv, limit - a->v.size(), timeout, level + 1);
		aps.insert(a->dst);
		debug("maxSteps: level %u: cap v %d recursive call returned sub %u\n", level, (int)a->v.size(), sub);
		if (sub + a->v.size() > submax) {
			debug("maxSteps: level %u: submax %u -> %u\n", level, submax, sub + (unsigned)a->v.size());
			submax = sub + a->v.size();
			maxcap = *a;
			maxv = subv;
			if (max + submax >= limit)
				break;
		}
	}
	debug("maxSteps: level %u: maxcap dst (%d,%d) v %d + maxv %d\n", level, maxcap.dst.first, maxcap.dst.second, (int)maxcap.v.size(), (int)maxv.size());
	if (max + submax >= limit) {
		max += submax;
		v.insert(v.end(), maxcap.v.begin(), maxcap.v.end());
		v.insert(v.end(), maxv.begin(), maxv.end());
		return max;
	}
	unsigned sub = 0;
	if (count) {
		Board b(board);
		for (set<Path>::iterator a = caps.begin(); a != caps.end(); ++a) {
			debug("maxSteps: level %u: clearing caps dst (%d,%d)\n", level, a->dst.first, a->dst.second);
			b.clear(a->dst.first, a->dst.second);
		}
		debug("maxSteps: level %u: non-leaf room: calling expandFill() with src (%d,%d) and path (%d) on board:\n", level, src.first, src.second, (int)maxcap.v.size());
//		b.print();
		sub = expandFill(b, src, maxcap.v, count + 1, usec() + maxExpandTime < timeout ? usec() + maxExpandTime : timeout);
		debug("maxSteps: level %u: expandFill() found max %u for maxcap\n", level, sub);
	}
	v.insert(v.end(), maxcap.v.begin(), maxcap.v.end());
	max += sub;
	// append maxv to v
	v.insert(v.end(), maxv.begin(), maxv.end());
	debug("maxSteps: level %u: appending maxv to v, max %u + %u = %u\n", level, max, (unsigned)maxv.size(), max + (unsigned)maxv.size());
	max += maxv.size();
	debug("maxSteps: level %u: returning max %u\n", level, max);
//	b.print();
	return max;
}