From 1a996c6e016b28e09895aa17201720b63d70bd71 Mon Sep 17 00:00:00 2001
From: tomsmeding <tom.smeding@gmail.com>
Date: Sat, 16 Feb 2019 20:30:21 +0100
Subject: Optimise board edge handling

This new organisation assumes that you'll do very few modifications
before calling forEachMoves again.
---
 board.cpp | 53 ++++++++++++++++++++++++++---------------------------
 1 file changed, 26 insertions(+), 27 deletions(-)

(limited to 'board.cpp')

diff --git a/board.cpp b/board.cpp
index 822fddd..b3820a0 100644
--- a/board.cpp
+++ b/board.cpp
@@ -1,5 +1,4 @@
 #include <cstdlib>
-#include <cstring>
 #include <cassert>
 #include "board.h"
 #include "util.h"
@@ -65,7 +64,9 @@ Board Board::makeEmpty() {
 
 	Board bd;
 	bd.bag = Bag::makeFull();
-	memset(bd.bd, 0, BSZ * BSZ);
+	bd.bd.fill(0);
+	bd.edgeCells.reserve(BSZ * BSZ);
+	bd.inEdgeCells.fill(-1);
 	return bd;
 }
 
@@ -84,15 +85,29 @@ int Board::countStones(uint8_t clr, int idx, int delta) const {
 
 void Board::newEdgeCand(int idx) {
 	// cerr << "(newEdgeCand(" << Idx(idx) << "))" << endl;
-	if (!inEdgeCands.test(idx)) {
-		edgeCands.push_back(idx);
-		inEdgeCands.set(idx);
+	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) {
+		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);
@@ -103,6 +118,10 @@ 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) {
@@ -134,28 +153,8 @@ bool Board::checkEdge(int idx) const {
 	return bd[idx - 1] || bd[idx + 1] || bd[idx - BSZ] || bd[idx + BSZ];
 }
 
-void Board::forEachMove(const function<void(int idx)> &f) {
-	vector<int> eC = edgeCands;
-	bitset<BSZ * BSZ> iEC = inEdgeCands;
-
-	size_t j = 0;
-	for (size_t i = 0; i < eC.size(); i++) {
-		int idx = eC[i];
-		// cerr << "(fEM: candidate " << Idx(idx) << "; ";
-		if (bd[idx] == 0 && checkEdge(idx)) {
-			// cerr << "edge)" << endl;
-			f(idx);
-			eC[j++] = idx;
-		} else {
-			// cerr << "-)" << endl;
-			iEC.reset(idx);
-		}
-	}
-
-	eC.resize(j);
-
-	swap(edgeCands, eC);
-	swap(inEdgeCands, iEC);
+const vector<int>& Board::getEdgeCells() const {
+	return edgeCells;
 }
 
 Bounds Board::computeBounds() const {
-- 
cgit v1.2.3-54-g00ecf