# HG changeset patch
# User Laman
# Date 2017-12-05 21:35:36
# Node ID 07f3fda1cbd7088953a4163e9e65a8f6c71307bf
# Parent  3798475f45c15713431ff72c5ca6d509d5c20b1d

optimized go floodFill

diff --git a/src/analyzer/__init__.py b/src/analyzer/__init__.py
--- a/src/analyzer/__init__.py
+++ b/src/analyzer/__init__.py
@@ -1,12 +1,13 @@
 import logging as log
+
 from .grid import Grid
-from go.core import exportBoard, EMPTY,BLACK,WHITE
+from util import BLACK,WHITE,EMPTY
+from go.core import exportBoard
 
 
 class ImageAnalyzer:
-
 	def __init__(self,tresB=30,tresW=60):
-		self.board=[[EMPTY] * 19 for r in range(19)]
+		self.board=[[EMPTY]*19 for r in range(19)]
 		self.grid=None
 
 		self.tresB=tresB
diff --git a/src/go/core.py b/src/go/core.py
--- a/src/go/core.py
+++ b/src/go/core.py
@@ -1,6 +1,7 @@
 import logging as log
 
 from util import EMPTY,BLACK,WHITE,colorNames
+from .helperboard import HelperBoard
 from .gamerecord import GameRecord
 
 
@@ -9,10 +10,13 @@ class Go:
 	def __init__(self,boardSize=19):
 		self.boardSize=boardSize
 		self.board=[[EMPTY]*boardSize for x in range(boardSize)]
-		self._temp=[[EMPTY]*boardSize for x in range(boardSize)]
 		self.toMove=BLACK
+		self._helper=HelperBoard(self.board)
 		self._record=GameRecord()
 
+	def listMoves(self,diff=[]):
+		return []
+
 	## Executes a move.
 	#
 	#  Doesn't check for kos. Suicide not allowed.
@@ -27,48 +31,39 @@ class Go:
 
 		# capture neighbors
 		for r,c in ((-1,0),(1,0),(0,-1),(0,1)):
-			self._clearTemp()
-			if not self._floodFill(-color,row+r,col+c): self._remove()
+			self._helper.clear()
+			if not self._helper.floodFill(-color,row+r,col+c,EMPTY): self._remove()
 
 		# check for suicide
-		self._clearTemp()
-		if not self._floodFill(color,row,col):
+		self._helper.clear()
+		if not self._helper.floodFill(color,row,col,EMPTY):
 			self.board[row][col]=EMPTY
 			return False
 		self._record.move(color,row,col)
 		self.toMove=-1*color
 		return True
 
+	def undoMove(self,color,r,c,captures):
+		self.board[r][c]=color
+		if len(captures)>0:
+			self._helper.clear()
+			for (r,c) in captures:
+				self._helper.floodFill(EMPTY,r,c)
+			self._fill(-color)
+
 	def transitionMove(self,board):
 		res=transitionMove(self.board,board)
 		if not res: return res
 		(r,c,color)=res
 		return self.move(color,r,c)
 
+	## Removes stones at coordinates marked with True in self.helper.
+	def _remove(self):
+		self._fill(EMPTY)
 
-	## Checks for liberties of a stone at given coordinates.
-	#
-	#  The stone's group is marked with True in self.temp, ready for capture if needed. Recursively called for stone's neighbors.
-	#
-	#  @return True if alive, False if captured
-	def _floodFill(self,color,row,col):
-		if col<0 or col>=self.boardSize or row<0 or row>=self.boardSize: return False # out of range
-		if self._temp[row][col]: return False # already visited
-		if self.board[row][col]==EMPTY: return True # found a liberty
-		if self.board[row][col]!=color: return False # opponent's stone
-		self._temp[row][col]=True # set visited
-		return self._floodFill(color,row,col-1) or self._floodFill(color,row,col+1) or self._floodFill(color,row-1,col) or self._floodFill(color,row+1,col) # check neighbors
-
-	## Removes stones at coordinates marked with True in self.temp.
-	def _remove(self):
-		for r in range(self.boardSize):
-			for c in range(self.boardSize):
-				if self._temp[r][c]: self.board[r][c]=EMPTY
-
-	def _clearTemp(self):
-		for i in range(self.boardSize):
-			for j in range(self.boardSize):
-				self._temp[i][j]=EMPTY
+	def _fill(self,filling):
+		for (r,c) in self._helper.continuousArea():
+			self.board[r][c]=filling
 
 
 def exportBoard(board):
@@ -106,7 +101,7 @@ def transitionMove(state1,state2):
 		return False
 
 
-def transitionSequence(state1,state2,diff):
+def transitionSequence(state1,state2,diff,limit=0):
 	return []
 
 
diff --git a/src/go/helperboard.py b/src/go/helperboard.py
new file mode 100644
--- /dev/null
+++ b/src/go/helperboard.py
@@ -0,0 +1,37 @@
+from util import EMPTY
+
+
+## Utility class for finding continuous regions on a Go.board.
+class HelperBoard:
+	def __init__(self,board):
+		self._refBoard=board # Go.board, readonly
+		self._boardSize=len(board)
+		self._board=[[EMPTY]*self._boardSize for i in range(self._boardSize)]
+		self._usedCoords=[0]*(self._boardSize**2)*2
+		self._usedCount=0
+
+	def floodFill(self,filling,r,c,needle=None):
+		if c<0 or c>=self._boardSize or r<0 or r>=self._boardSize: return False # out of range
+		if self._board[r][c]: return False # already visited
+		if self._refBoard[r][c]==needle: return True # found something
+		if self._refBoard[r][c]!=filling: return False # out of area boundary
+		self._board[r][c]=True # set visited
+		self._usedCoords[self._usedCount*2]=r
+		self._usedCoords[self._usedCount*2+1]=c
+		self._usedCount+=1
+
+		# check neighbors
+		return self.floodFill(filling,r,c-1) or \
+			self.floodFill(filling,r,c+1) or \
+			self.floodFill(filling,r-1,c) or \
+			self.floodFill(filling,r+1,c)
+
+	def continuousArea(self):
+		for i in range(self._usedCount):
+			yield (self._usedCoords[i*2],self._usedCoords[i*2+1])
+
+	def clear(self):
+		for i in range(self._usedCount):
+			(r,c)=(self._usedCoords[i*2],self._usedCoords[i*2+1])
+			self._board[r][c]=EMPTY
+		self._usedCount=0