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

#ifndef __BOARD_H__
#define __BOARD_H__

#include <sys/types.h>
#include <utility>

#include "Map.h"

using namespace std;

#ifdef DEBUG
extern FILE *logfile;
#define debug(format, ...)	do { fprintf(stderr, format, ## __VA_ARGS__); \
				fprintf(logfile, format, ##__VA_ARGS__);      \
				fflush(logfile); } while (0)
#else
#define debug(format, ...)	
#endif

enum DIR { NORTH=0, EAST=1, SOUTH=2, WEST=3 };
enum RESULT { LOSS=0, UNDECIDED=1, DRAW=2, WIN=3 };

extern const char *dname[];
extern const char *rname[];

static inline unsigned long
usec()
{
	static struct timeval tv;

	gettimeofday(&tv, NULL);
	return tv.tv_sec * 1000000 + tv.tv_usec;
}

static inline pair<int, int>
step(pair<int, int> s, DIR d)
{
	switch (d) {
	case NORTH: s.second--; break;
	case EAST:  s.first++;  break;
	case SOUTH: s.second++; break;
	case WEST:  s.first--;  break;
	}
	return s;
}

class Board {
public:
	Board(const Map &map) : w(map.Width()), h(map.Height()), mx(map.MyX()),
	    my(map.MyY()), ox(map.OpponentX()), oy(map.OpponentY()) {
		memset(b, 0, sizeof(b));
		for (int y = 0; y < h; ++y)
			for (int x = 0; x < w; ++x)
				if (map.IsWall(x, y))
					write(x, y);
		for (int x = 0; x < w; ++x) {
			if (!read(x, 0))
				write(x, 0);
			if (!read(x, h - 1))
				write(x, h - 1);
		}
		for (int y = 0; y < h; ++y) {
			if (!read(0, y))
				write(0, y);
			if (!read(w - 1, y))
				write(w - 1, y);
		}
	}
	/* default ctor and assignment operator are fine */
	bool operator==(const Board &o) const {
		return mx == o.mx && my == o.my && ox == o.ox && oy == o.oy &&
		    !memcmp(b, o.b, sizeof(b));
	}
	bool inline read(int x, int y) const {
		const int i = y * w + x;
		return b[i / 32] & (1 << (i % 32));
	}
	void inline write(int x, int y) {
		const int i = y * w + x;
		b[i / 32] |= (1 << (i % 32));
	}
	void inline clear(int x, int y) {
		const int i = y * w + x;
		b[i / 32] &= ~(1 << (i % 32));
	}
	void inline move(bool op, DIR dir) {
		int &x = op ? ox : mx, &y = op ? oy : my;
		write(x, y);
		switch (dir) {
		case NORTH: y--; break;
		case EAST:  x++; break;
		case SOUTH: y++; break;
		case WEST:  x--; break;
		}
	}
	RESULT rate() const {
		if (mx == ox && my == oy)
			return DRAW;
		const bool m = read(mx, my), o = read(ox, oy);
		if (m && o)
			return DRAW;
		if (m)
			return LOSS;
		if (o)
			return WIN;
		return UNDECIDED;
	}
	unsigned pathToOpponent() const;
	int voronoi() const;
	bool isolated() const;
	int getWidth() const { return w; }
	int getHeight() const { return h; }
	pair<int, int> getMyPos() const { return pair<int, int>(mx, my); }
	pair<int, int> getOpPos() const { return pair<int, int>(ox, oy); }
	#ifdef DEBUG
	void checkPath(pair<int, int> s, const vector<DIR> &v) const;
	void print() const;
	#endif
private:
	u_int32_t b[79]; /* 79*32=2528 bits, 50x50 board max */
	int w, h;
	int mx, my, ox, oy;
};

#endif