from .core import PASS
from .transpositiontable import TranspositionTable
from . import core


## Compute move sequence from state1 to state2.
#
# @param colorIn {BLACK,WHITE}: color to start the sequence
# @param colorOut {BLACK,WHITE}: color to close the sequence
# @return [(c,row,col), ...] or None. c in {BLACK,WHITE} == {1,-1}
def getTransitionSequence(state1,state2,colorIn,colorOut,diff):
	eng.load(state1)
	return eng.iterativelyDeepen(state2,diff,colorIn,colorOut)


class SpecGo(core.Go):
	def __init__(self,boardSize=19):
		super().__init__(boardSize)

	def listRelevantMoves(self,diff):
		"""There can be 3 different changes in the diff: additions, deletions and replacements.
		Additions can be taken as relevant right away.
		Deletions and replacements had to be captured, so we add their liberties.
		Also any non-missing stones of partially deleted (or replaced) groups had to be replayed, so add them too.
		Needs to handle snapback, throw-in.
		There's no end to what could be theoretically relevant, but such sequences are long and we will pretend they won't happen.

		:return: (blackMoves,whiteMoves) == ({(row,col), ...}, {(row,col), ...})"""
		res=({PASS},{PASS})
		for d in diff:
			(r,c,action,color)=d
			colorKey=(1-color)>>1 # {-1,1}->{1,0}
			if action!="-" and (r,c) not in res[colorKey]:
				res[colorKey].add((r,c))
				if action=="*":
					for (ri,ci) in self.listNeighbours(r,c): # in case a stone was played and captured. !! might want to add even more
						res[1-colorKey].add((ri,ci))
			# this is rather sloppy but correct. the time will show if it is effective enough
			# just floodFill from the current intersection, add everything you find and also all the neighbours to be sure
			if action!="+" and (r,c) not in res[colorKey] and (r,c) not in res[1-colorKey]:
				self._helper.clear()
				self._helper.floodFill(color if action=="-" else 1-color, r, c)
				res[colorKey].union(self._helper.getContinuousArea())
				for (ri,ci) in self._helper.getContinuousArea():
					res[colorKey].add((ri,ci))
					res[1-colorKey].add((ri,ci))
					for (rj,cj) in self.listNeighbours(ri,ci):
						res[colorKey].add((rj,cj))
						res[1-colorKey].add((rj,cj))
		return res

	def listNeighbours(self,r,c):
		if r>0: yield (r-1,c)
		if r+1<self.boardSize: yield (r+1,c)
		if c>0: yield (r,c-1)
		if c+1<self.boardSize: yield (r,c+1)


class Engine:
	"""Class searching for move sequences changing one board state into another."""
	def __init__(self,g=None):
		self._g=g or SpecGo()
		self._moveList=(set(),set())
		self._transpositions=TranspositionTable()

	def load(self,state1):
		self._g.load(state1)

	def iterativelyDeepen(self,state2,diff,colorIn,colorOut):
		"""Search for a move sequence from the loaded state to state2. Tries progressively longer sequences.

		:return: [(c,row,col), ...] or None. c in {BLACK,WHITE} == {1,-1}"""
		self._moveList=self._g.listRelevantMoves(diff)
		startDepth=1 if colorIn==colorOut else 2
		self._g.toMove=colorIn

		for i in range(startDepth,5,2):
			seq=self._dfs(state2,i)
			if seq:
				seq.reverse()
				return seq
		return None

	def _dfs(self,state2,limit):
		"""Search for a "limit" move sequence from the loaded state to state2."""
		g=self._g
		moveSet=self._moveList[(1-g.toMove)>>1]
		transKey=(g.hash()*state2.hash()*limit)&0xffffffff

		transSeq=self._transpositions.get(transKey)
		if transSeq is not None:
			return transSeq[:] if transSeq else transSeq

		for m in moveSet.copy():
			if not g.doMove(g.toMove,*m): continue
			captured=g.captures[:g.captureCount]
			moveSet.remove(m)
			if m==PASS: # no reason for both players to pass
				self._moveList[(1-g.toMove)>>1].remove(m)

			if limit>1:
				seq=self._dfs(state2,limit-1)
				if seq:
					self._undoMove(m,captured)
					seq.append((g.toMove,*m))
					self._transpositions.put(transKey,seq[:])
					return seq
				else: self._transpositions.put(transKey,False)

			if limit==1 and g.hash()==state2.hash():
				self._undoMove(m,captured)
				return [(g.toMove,*m)]

			self._undoMove(m,captured)
		return None

	def _undoMove(self,move,captured):
		g=self._g
		g.undoMove(*move,captured)
		k=(1-g.toMove)>>1
		self._moveList[k].add(move)
		if move==PASS:
			self._moveList[1-k].add(move)

eng=Engine()