#include <cstdlib>
#include <cassert>
#include "board.h"
#include "util.h"

using namespace std;


Bag Bag::uninitialised() {
	return Bag();
}

Bag Bag::makeFull() {
	Bag bag;
	for (int i = 0; i < NC; i++) bag.num[i] = N;
	bag.sum = N * NC;
	return bag;
}

int Bag::numLeft(uint8_t clr) const {
	return num[clr - 1];
}

int Bag::totalLeft() const {
	return sum;
}

uint8_t Bag::peekRandom() const {
	assert(sum != 0);

	int i = random() % sum;
	int accum = 0;
	for (int clr = 1; clr <= NC; clr++) {
		accum += num[clr - 1];
		if (i < accum) {
			return clr;
		}
	}

	assert(false);
}

uint8_t Bag::drawRandom() {
	uint8_t clr = peekRandom();
	num[clr - 1]--;
	sum--;
	return clr;
}

void Bag::drawColour(uint8_t clr) {
	assert(num[clr - 1] != 0);
	num[clr - 1]--;
	sum--;
}

void Bag::replace(uint8_t clr) {
	num[clr - 1]++;
	sum++;
}


Board Board::makeEmpty() {
	static_assert(NC + 1 <= 256, "Too many colours");

	Board bd;
	bd.bag = Bag::makeFull();
	bd.bd.fill(0);
	bd.edgeCells.reserve(BSZ * BSZ);
	bd.inEdgeCells.fill(-1);
	return bd;
}

// Do not call with clr == 0
int Board::countStones(uint8_t clr, int idx, int delta) const {
	// Since clr != 0 and the stones will never reach the edge of the board
	// (it's too large for that), this loop will always terminate before
	// accessing invalid memory.
	int num = 0;
	while (bd[idx] == clr) {
		num++;
		idx += delta;
	}
	return num;
}

void Board::newEdgeCand(int idx) {
	// cerr << "(newEdgeCand(" << Idx(idx) << "))" << endl;
	if (inEdgeCells[idx] == -1 && bd[idx] == 0 && checkEdge(idx)) {
		inEdgeCells[idx] = edgeCells.size();
		edgeCells.push_back(idx);
	}
}

void Board::removeEdgeCell(int idx) {
	// cerr << "(removeEdgeCell(" << Idx(idx) << "))" << endl;
	int pos = inEdgeCells[idx];
	if (pos != -1 && (bd[idx] != 0 || !checkEdge(idx))) {
		inEdgeCells[idx] = -1;
		if ((unsigned)pos < edgeCells.size() - 1) {
			int val = edgeCells[pos] = edgeCells.back();
			inEdgeCells[val] = pos;
		}
		edgeCells.pop_back();
	}
}

void Board::put(int idx, uint8_t clr) {
	bd[idx] = clr;

	removeEdgeCell(idx);
	newEdgeCand(idx - 1);
	newEdgeCand(idx + 1);
	newEdgeCand(idx - BSZ);
	newEdgeCand(idx + BSZ);
}

void Board::undo(int idx) {
	bd[idx] = 0;

	newEdgeCand(idx);
	removeEdgeCell(idx - 1);
	removeEdgeCell(idx + 1);
	removeEdgeCell(idx - BSZ);
	removeEdgeCell(idx + BSZ);
}

uint8_t Board::putCW(int idx, uint8_t clr) {
	put(idx, clr);

	int count[8];
#define DO_COUNT_STONES(_i, _dx, _dy) do { int _delta = BSZ * (_dy) + (_dx); count[_i] = countStones(clr, idx + _delta, _delta); } while (0)
	DO_COUNT_STONES(0,  0, -1);
	DO_COUNT_STONES(1,  1, -1);
	DO_COUNT_STONES(2,  1,  0);
	DO_COUNT_STONES(3,  1,  1);
	DO_COUNT_STONES(4,  0,  1);
	DO_COUNT_STONES(5, -1,  1);
	DO_COUNT_STONES(6, -1,  0);
	DO_COUNT_STONES(7, -1, -1);
#undef DO_COUNT_STONES

	for (int i = 0; i < 4; i++) {
		if (1 + count[i] + count[4 + i] >= RLEN) return clr;
	}

	return 0;
}

bool Board::checkEdge(int idx) const {
	// Because there are always two spaces free at the ends of the board, we
	// can safely inspect the neighbours of this cell. This is because we only
	// call this function on cells that have either had or neighboured a stone.
	return bd[idx - 1] || bd[idx + 1] || bd[idx - BSZ] || bd[idx + BSZ];
}

const vector<int>& Board::getEdgeCells() const {
	return edgeCells;
}

Bounds Board::computeBounds() const {
	Bounds bounds;

	for (int idx : edgeCells) {
		int x = idx % BSZ, y = idx / BSZ;
		if (bd[idx] != 0 || checkEdge(idx)) {
			bounds.left = min(bounds.left, x);
			bounds.right = max(bounds.right, x);
			bounds.top = min(bounds.top, y);
			bounds.bottom = max(bounds.bottom, y);
		}
	}

	return bounds;
}

void Board::write(ostream &os) const {
	Bounds bounds = computeBounds();

	for (int y = bounds.top; y <= bounds.bottom; y++) {
		for (int x = bounds.left; x <= bounds.right; x++) {
			if (x != bounds.left) os << ' ';

			int idx = BSZ * y + x;
			if (bd[idx] != 0) os << Stone(bd[idx]);
			else if (checkEdge(idx)) os << EDGE_STR;
			else os << OPEN_STR;
		}
		os << endl;
	}

	os << "Bag:";
	for (uint8_t clr = 1; clr <= NC; clr++) {
		os << ' ' << bag.numLeft(clr);
	}
	os << " / " << bag.totalLeft() << endl;
}

ostream& operator<<(ostream &os, Stone stone) {
	static const char *alphabet[] = {
		"\x1B[1;31mR\x1B[0m",
		"\x1B[1;34mB\x1B[0m",
		"\x1B[1;33mY\x1B[0m",
	};
	static_assert(
			NC <= sizeof(alphabet) / sizeof(alphabet[0]),
			"Increase alphabet in Board::write");

	uint8_t clr = stone.clr;
	assert(1 <= clr && clr <= NC);
	return os << alphabet[clr - 1];
}

ostream& operator<<(ostream &os, const Board &bd) {
	bd.write(os);
	return os;
}