import cProfile

from tests.testEngine import TestTransitions

from .core import PASS

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

def getTransitionSequence(state1,state2,colorIn,colorOut,diff):

	eng.load(state1,diff)

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."""

		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))

				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:

	def __init__(self,g=None):

		self._g=g or SpecGo()

		self._moveList=(set(),set())

	def load(self,state1,diff):

		self._g.load(state1)

		self._moveList=self._g.listRelevantMoves(diff)

	def iterativelyDeepen(self,state2,colorIn,colorOut):

		startDepth=1 if colorIn==colorOut else 2

		self._g.toMove=colorIn

		for i in range(startDepth,10,2):

			seq=self.dfs(state2,i)

			if seq:

				seq.reverse()

				return seq

	def dfs(self,state2,limit):

		g=self._g

		moveSet=self._moveList[(1-g.toMove)>>1]

		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))

					return seq

			self._undoMove(m,captured)

	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()

"""Theory:

We have a sequence S of valid board states s_1, ..., s_n.

We search for a picked subsequence S_p of length k and m additional moves M such that:

- S_p augmented by M forms a valid sequence of moves

- k-m is maximal for S_p picked from S

It is relatively cheap to add new items to S.

User can change detector parameters, presumably in case the previous don't fit the (current) situation.

In such a case we assume the new parameters are correct from the current position onwards.

But the change might have been appropriate even earlier (before the user detected and fixed an error).

So we try to find the correct crossover point like this:

- construct a sequence S' = s'_i, ..., s'_n by reanalyzing the positions with a new set of parameters, where s_i is the point of previous user intervention or s_0

- for each s'_j:

	- try to append it to S[:j]

	- try to append it to S'[:j]

	- remember the better variant

- linearize the fork back by discarding s'_j-s preceding the crossover and s_j-s following the crossover

"""

from util import EMPTY,BLACK,WHITE, hashBoard,exportBoard

from go.engine import getTransitionSequence

## Crude lower bound on edit distance between states.

def estimateDistance(diff):

	# lot of room for improvements

	additions=sum(1 for d in diff if d[2]=="+")

	deletions=sum(1 for d in diff if d[2]=="-")

	replacements=len(diff)-additions-deletions

	if additions>0: return additions+replacements

	elif replacements==0 and deletions>0: return 2 # take n, return 1

	return replacements+1 # ???

class GameTreeNode:

	def __init__(self,parent,color):

		self.parent=parent

		self.color=color # color closing the move sequence

		self.prev=None

		self.moves=[] # move sequence from prev to self

		self.weight=0

	## Connect itself after v if it gains itself more weight.

	def tryConnect(self,v,diff):

		moves=getTransitionSequence(v.parent,self.parent,-1*v.color,self.color,diff)

		w=v.weight+2-len(moves) # proper one move transition increases the weight by 1

		if w>self.weight:

			self.moves=moves

			self.prev=v

			self.weight=w

class BoardState:

	def __init__(self,board):

		self._board=tuple(tuple(x for x in row) for row in board)

		self.nodes=(GameTreeNode(self,BLACK),GameTreeNode(self,WHITE))

		self.diff2Prev=None

		self._hash=None

	def tryConnect(self,s):

		distEst=estimateDistance(diff)

		if distEst>3: return # we couldn't find every such move sequence anyway without a clever algorithm

		if weightEst<=self.getWeight(): return

		for v1 in s.nodes:

			for v2 in self.nodes:

				v2.tryConnect(v1,diff)

	def hash(self):

		if self._hash is None: self._hash=hashBoard(self._board)

		return self._hash

	def export(self):

		return exportBoard(self._board)

	def exportDiff(self,s2):

		return "vvv\n{0}\n=== {1} ===\n{2}\n^^^".format(self.export(), s2-self, s2.export())

	def __iter__(self): return iter(self._board)

	def __getitem__(self,key): return self._board[key]

	def __sub__(self,x):

		res=[]

		for (r,(row1,row2)) in enumerate(zip(self._board,x)):

			for (c,(item1,item2)) in enumerate(zip(row1,row2)):

				if item1==item2: continue

				elif item2==EMPTY: res.append((r,c,"+",item1))

				elif item1==EMPTY: res.append((r,c,"-",item2))

				else: res.append((r,c,"*",item1)) # ->to

		return res

	def __eq__(self,x):

		return self.hash()==x.hash()

	def getWeight(self):

		return max(v.weight for v in self.nodes)

class StateBag:

	def __init__(self):

		self._states=[]

	def pushState(self,board):

		sn=BoardState(board)

		for s in reversed(self._states):

			sn.tryConnect(s)

		self._states.append(sn)

	def merge(self,branch):

		pass

import os.path

import logging as log

from unittest import TestCase

import config as cfg

from util import BLACK as B,WHITE as W,EMPTY as _

from go.engine import SpecGo,Engine

from statebag import BoardState

_log=log.getLogger(__name__)

_log.setLevel(log.INFO)

_log.propagate=False

formatter=log.Formatter("%(asctime)s %(levelname)s: %(message)s",datefmt="%Y-%m-%d %H:%M:%S")

handler=log.FileHandler("/tmp/oneeye.log",mode="w")

handler.setFormatter(formatter)

_log.addHandler(handler)

class TestTransitions(TestCase):

	def testBasic(self):

		s1=BoardState([

			[_,_,_],

			[_,_,_],

			[_,_,_]

		])

		s2=BoardState([

			[_,_,_],

			[_,B,_],

			[_,_,_]

		])

		g=SpecGo(3)

		eng=Engine(g)

		eng.load(s1,s2-s1)

		self.assertEqual(eng.dfs(s2,1),[(1,1,1)])

	def testCapture(self):

		s1=BoardState([

			[_,W,_],

			[W,B,_],

			[_,W,_]

		])

		s2=BoardState([

			[_,W,_],

			[W,_,W],

			[_,W,_]

		])

		g=SpecGo(3)

		g.toMove=W

		eng=Engine(g)

		eng.load(s1,s2-s1)

		self.assertEqual(eng.dfs(s2,1),[(W,1,2)])

	def testMulti(self):

		s1=BoardState([

			[_,_,_],

			[_,_,_],

			[_,_,_]

		])

		s2=BoardState([

			[_,_,_],

			[_,B,W],

			[_,_,_]

		])

		g=SpecGo(3)

		eng=Engine(g)

		eng.load(s1,s2-s1)

		self.assertEqual(eng.dfs(s2,2),[(W,1,2),(B,1,1)])

	def testSnapback(self):

		s1=BoardState([

			[B,B,B],

			[B,_,B],

			[B,W,B]

		])

		s2=BoardState([

			[_,_,_],

			[_,_,_],

			[_,W,_]

		])

		g=SpecGo(3)

		eng=Engine(g)

		eng.load(s1,s2-s1)

		self.assertEqual(eng.dfs(s2,2),[(W,2,1),(B,1,1)])

		s1=BoardState([

			[_,_,_],

			[W,B,B],

			[_,W,W]

		])

		s2=BoardState([

			[_,_,_],

			[W,B,B],

			[_,W,_]

		])

		eng.load(s1,s2-s1)

		self.assertEqual(eng.dfs(s2,2),[(W,2,1),(B,2,0)])

	def testReal(self):

		files=["O-Takao-20110106.sgf","Sakai-Iyama-20110110.sgf"]

		for f in files:

			moves=simpleLoadSgf(os.path.join(cfg.srcDir,"tests/data",f))

			states=listStates(moves)

			for k in range(1,4):

				toMove=B

				for (i,(s1,s2)) in enumerate(zip(states,states[k:])):

					diff=s2-s1

					eng.load(s1,diff)

					colorIn=W if i&1 else B

					colorOut=colorIn if k&1 else 1-colorIn

					seq=eng.iterativelyDeepen(s2,colorIn,colorOut)

					msg="\n"+s1.exportDiff(s2)

					self.assertIsNotNone(seq,msg)

					self.assertLessEqual(len(seq),k,msg)

					if len(seq)!=k: _log.warning("shorter than expected transition sequence:" + msg + "\n" + str(seq))

					toMove*=-1