import logging as log

class ImageAnalyzer:

	def __init__(self,tresB=30,tresW=60):

		self.grid=None

		self.tresB=tresB

		self.tresW=tresW

	# let's not concern ourselves with sizecoef and shift here anymore. we want corners to come already properly recomputed

	def analyze(self,image):

		if self.grid==None:

			log.info("ImageAnalyzer.analyze() aborted: no grid available.")

			return False

		for r in range(19):

			for c in range(19):

				intersection=self.grid.intersections[r][c]

				self.board[r][c]=self.analyzePoint(image,r,c,intersection,*(self.grid.stoneSizeAt(r,c)))

		log.info("board analyzed:\n%s", exportBoard(self.board))

		return True

	def analyzePoint(self,image,row,col,imageCoords,stoneWidth,stoneHeight):

		b=w=e=0

		((x1,y1),(x2,y2))=relevantRect(imageCoords,stoneWidth,stoneHeight)

		for y in range(y1,y2+1):

			for x in range(x1,x2+1):

				try:

					red,green,blue=image.getpixel((x,y))

				except IndexError: continue

				I=(red+green+blue)/255/3

				m=min(red,green,blue)

				S=1-m/I if I!=0 else 0

				if 100*I<self.tresB: b+=1

				elif 100*I>self.tresW: w+=1

				else: e+=1

		log.debug("(%d,%d) ... (b=%d,w=%d,e=%d)", row, col, b, w, e)

	def setGridCorners(self,corners):

		self.grid=Grid(corners)

def relevantRect(imageCoords,stoneWidth,stoneHeight):

	x=int(imageCoords.x)

	y=int(imageCoords.y)

	xmax=max(int(stoneWidth*2//7), 2) # !! optimal parameters subject to further research

	ymax=max(int(stoneHeight*2//7), 2)

	return ((x-xmax,y-ymax), (x+xmax,y+ymax))

class Corners:

	def __init__(self):

		self.corners=[]

	## Adds a new corner if there are less than four, replaces the closest otherwise.

	def add(self,x,y):

		a=EPoint(x,y)

		# for i,c in enumerate(self.corners): # move an improperly placed point

			# if a.dist(c)<20:

				# self.corners[i]=a

				# return

		if len(self.corners)<4: # add a new corner

			self.corners.append(a)

		if len(self.corners)<4:

			return

		index,minDist=0,float('inf') # replace the corner closest to the clicked point

		for i,c in enumerate(self.corners):

			if a.dist(c)<minDist:

				index,minDist=i,a.dist(c)

		self.corners[index]=a

	## Order the corners (0,1,2,3) so they make a quadrangle with vertices KLMN in counter-clockwise order, K being in the upper left.

	#

	#  For four points ABCD, there are 24 possible permutations corresponding to the desired KLMN.

	#  When we relax the condition of K being the upper left one, we get six groups of four equivalent permutations. KLMN ~ LMNK ~ MNKL ~ NKLM.

	#

	#  We determine which of the points' triplets are oriented clockwise and which counter-clockwise (minus/plus in the table below)

	#  and swap them so that all triangles turn counter-clockwise.

	#

	#  xxxx -> KLMN | ABC | ABD | ACD | BCD | index | swap

	#  ------------ | :-: | :-: | :-: | :-: | ----: | ----

	#  A BCD        |  +  |  +  |  +  |  +  |    15 | 0

	#  A BDC        |  +  |  +  |  -  |  -  |    12 | CD

	#  A CBD        |  -  |  +  |  +  |  -  |     6 | BC

	#  A CDB        |  -  |  -  |  +  |  +  |     3 | AB

	#  A DBC        |  +  |  -  |  -  |  +  |     9 | AD

	#  A DCB        |  -  |  -  |  -  |  -  |     0 | BD

	#

	#  For every non-degenerate quadrangle, there must be 1-3 edges going right-left (from a higher to a lower x coordinate).

	#  From these pick the one with the lowest slope (dy/dx) and declare its ending point the upper left corner. For the same slope pick the one further left.

	#

	#  @return True for a convex quadrangle, False for concave and degenerate cases.

import numpy

## Projective transformation of a point with a matrix A.

#  

#  Takes a point as a horizontal vector, transposes it and multiplies with A from left.

#  

#  @return transformed point as a numpy.array

def transformPoint(point,A):

	return (A*numpy.matrix(point).transpose()).getA1()

class Grid:

	## Creates a Grid from the provided Corners object.

	#

	#  Finds the vanishing points of the board lines (corner points define perspectively transformed parallel lines). The vanishing points define the image horizon.

	#

	#  The horizon can be used to construct a matrix for affine rectification of the image (restoring parallel lines parallelism). We transform the corner points by this matrix,

	#  interpolate them to get proper intersections' coordinates and then transform these back to get their placement at the original image.

	#

	#  The result is stored in grid.intersections, a boardSize*boardSize list with [row][column] coordinates.

	#

	#  @param corners list of EPoints in ABCD order per corners.Corners.canonizeOrder().

	# !! Needs a check for proper initialization.

	def __init__(self,corners):

		# ad

		# bc

		a,b,c,d=[c.toProjective() for c in corners]

		p1=numpy.cross(a,b)

		p2=numpy.cross(c,d)

		vanish1=numpy.cross(p1,p2)

		# !! 32 bit int can overflow. keeping it reasonably small. might want to use a cleaner solution

		vanish1=EPoint.fromProjective(vanish1).toProjective() # !! EPoint fails with point in infinity

		p3=numpy.cross(a,d)

		p4=numpy.cross(b,c)

		vanish2=numpy.cross(p3,p4)

		vanish2=EPoint.fromProjective(vanish2).toProjective()

		horizon=numpy.cross(vanish1,vanish2)

		horizon=EPoint.fromProjective(horizon).toProjective()

		rectiMatrix=numpy.matrix([horizon,[0,1,0],[0,0,1]])

		rectiMatrixInv=numpy.linalg.inv(rectiMatrix)

		affineCorners=[EPoint.fromProjective(transformPoint(x,rectiMatrix)) for x in (a,b,c,d)]

import os

import multiprocessing

import threading

import logging as log

import PIL

from util import MsgQueue

from gui import gui

from statebag import StateBag

import config as cfg

class Core:

	def __init__(self):

		self.grid=None

		self.go=Go()

		self.detector=ImageAnalyzer()

		self.states=StateBag()

		self._ownMessages=MsgQueue(self._handleEvent)

		self._guiMessages=MsgQueue()

		self._imgs=sorted(os.listdir(cfg.misc.imgDir))

		self._imgIndex=cfg.misc.defaultImage

		imgPath=os.path.join(cfg.misc.imgDir,self._imgs[self._imgIndex])

		self._frame=PIL.Image.open(imgPath)

		self._guiProc=multiprocessing.Process(name="gui", target=gui, args=(self._guiMessages,self._ownMessages))

		self._guiProc.start()

		self.relativeFrame(0)

	def setCorners(self,corners):

		self.detector.setGridCorners(corners)

		self.analyze()

	def setTresholds(self,tresB=None,tresW=None):

		if tresB is not None: self.detector.tresB=tresB

		if tresW is not None: self.detector.tresW=tresW

		self.analyze()

	def relativeFrame(self,step):

		self._imgIndex=(self._imgIndex+step)%len(self._imgs)

		imgPath=os.path.join(cfg.misc.imgDir,self._imgs[self._imgIndex])

		self._frame=PIL.Image.open(imgPath)

		self._guiMessages.send("setCurrentFrame",(self._frame.copy(),))

		self.analyze()

	def analyze(self):

		if self.detector.analyze(self._frame):

			if isLegalPosition(self.detector.board):

				self.states.pushState(self.detector.board)

				self._guiMessages.send("setGameState",(self.detector.board,))

				self.go.transitionMove(self.detector.board)

				log.debug("game record: %s",self.go._record)

			else:

import logging as log

from util import EMPTY,BLACK,WHITE,colorNames

class Go:

	## Initializes self.board to a list[r][c]=EMPTY.

	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._record=GameRecord()

	## Executes a move.

	#

	#  Doesn't check for kos. Suicide not allowed.

	#

	#  @param color BLACK or WHITE

	#  @return True on success, False on failure (illegal move)

	def move(self,color,row,col):

		if color!=self.toMove: log.warning("move by %s out of order",colorNames[color])

		if self.board[row][col]!=EMPTY: return False

		self.board[row][col]=color

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

		# check for suicide

		self._clearTemp()

		if not self._floodFill(color,row,col):

			self.board[row][col]=EMPTY

			return False

		self._record.move(color,row,col)

		self.toMove=-1*color

		return True

	def transitionMove(self,board):

		res=transitionMove(self.board,board)

		if not res: return res

		(r,c,color)=res

		return self.move(color,r,c)

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

	#

from .resizablecanvas import ResizableCanvas

## Handles and presents the game state as detected by the program.

class BoardView(ResizableCanvas):

	def __init__(self, master=None):

		super().__init__(master)

		self.configure(width=360,height=360,background="#ffcc00")

		self._padding=18

		self._cellWidth=(self._width-2*self._padding)/18

		self._cellHeight=(self._height-2*self._padding)/18

		self._drawGrid()

	def redrawState(self,gameState):

		self.delete("black","white")

		for r,row in enumerate(gameState):

			for c,point in enumerate(row):

				self._drawStone(r, c, point)

	def _drawGrid(self):

		padding=self._padding

		for i in range(19):

			self.create_line(padding,18*i+padding,self._width-padding,18*i+padding,tags="row",fill="#000000") # rows

			self.create_line(18*i+padding,padding,18*i+padding,self._height-padding,tags="col",fill="#000000") # cols

		self._drawStars()

	def _drawStars(self):

		radius=2

		for r in range(3,19,6):

			for c in range(3,19,6):

				x=c*self._cellHeight+self._padding

				y=r*self._cellWidth+self._padding

				self.create_oval(x-radius,y-radius,x+radius,y+radius,tags="star",fill='#000000')

	## Draws a stone at provided coordinates.

	#

	#  For an unknown color draws nothing and returns False.

	#

	#  @param r row coordinate, [0-18], counted from top

	#  @param c column coordinate, [0-18], counted from left

	#  @param color color indicator, go.BLACK or go.WHITE

	def _drawStone(self, r, c, color):

		if color==BLACK:

			hexCode='#000000'

import logging as log

from PIL import ImageTk

import config

from .resizablecanvas import ResizableCanvas

class ImgView(ResizableCanvas):

	def __init__(self,master=None,parent=None):

		super().__init__(master)

		self._parent=parent

		self._corners=Corners()

		self._boardGrid=None

		self._img=None

		self._tkImg=None

		self.configure(width=480,height=360)

		self.bind('<1>',lambda e: self.addCorner(e.x,e.y))

	## Redraws the current image and its overlay.

	def redraw(self):

		self.delete("all")

		if self._img:

			img=self._img.copy()

			img.thumbnail((int(self._width),int(self._height)))

			self._tkImg=ImageTk.PhotoImage(img) # just to save the image from garbage collector

			self.create_image(self._width//2, self._height//2, anchor="center", image=self._tkImg)

		for corner in self._corners.corners:

			self.markPoint(corner.x,corner.y)

		if self._boardGrid!=None and config.gui.showGrid:

			for r in range(19):

				a=self._boardGrid.intersections[r][0]

				b=self._boardGrid.intersections[r][-1]

				self.create_line(a.x,a.y,b.x,b.y,fill='#00ff00')

			for c in range(19):

				a=self._boardGrid.intersections[0][c]

				b=self._boardGrid.intersections[-1][c]

				self.create_line(a.x,a.y,b.x,b.y,fill='#00ff00')

		if self._boardGrid!=None and config.gui.showBigPoints:

			for r in range(19):

				for c in range(19):

					self.create_rectangle(r1,c1,r2,c2,outline="#00ffff")

	def setImg(self,img):

		self._img=img

	## Stores a grid corner located at x,y coordinates.

	def addCorner(self,x,y):

		self._corners.add(x,y)

		log.debug("click on %d,%d",x,y)

		if self._corners.canonizeOrder():

			# transform corners from show coordinates to real coordinates

			log.debug(self._corners.corners)

			self._boardGrid=Grid(self._corners.corners)

			corners=[self._transformPoint(c) for c in self._corners.corners]

			self._parent.sendMsg("setCorners",(corners,))

		self.redraw()

	## Marks a point at the image with a green cross. Used for corners.

	def markPoint(self,x,y):

		self.create_line(x-3,y-3,x+4,y+4,fill="#00ff00")

		self.create_line(x-3,y+3,x+4,y-4,fill="#00ff00")

	def _onResize(self,event):

		w=self._width

		super()._onResize(event)

		self._corners.scale(self._width/w)

		if len(self._corners.corners)==4:

			self._boardGrid=Grid(self._corners.corners)

		self.redraw()

	def _transformPoint(self,point):

		w=int(self._width)

		h=int(self._height)

		wo,ho=self._img.size # o for original

		widthRatio=wo/w

		heightRatio=ho/h

		self._imgSizeCoef=max(widthRatio,heightRatio)

		# shift compensates possible horizontal or vertical empty margins from unmatching aspect ratios

		self._imgShift=EPoint(wo-w*self._imgSizeCoef,ho-h*self._imgSizeCoef)/2

		return EPoint(self.canvasx(point.x),self.canvasy(point.y)) * self._imgSizeCoef + self._imgShift

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

"""

## Crude lower bound on edit distance between states.

def estimateDistance(diff):

	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 # ???

class BoardState:

	def __init__(self,board):

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

		self.prev=None

		self._next=None

		self.moves=[]

		self.weight=0

		self.diff2Prev=None

	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,item2,item1)) # from->to

		return res

class StateBag:

	def __init__(self):

		self._states=[]

	def pushState(self,board):

		sn=BoardState(board)

		for s in reversed(self._states):

			diff=sn-s

			distEst=estimateDistance(diff)

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

			weightEst=s.weight-distEst

from unittest import TestCase

class TestLegal(TestCase):

	def testLegal(self):

		board=[

			[0,0,0,0,0],

			[1,1,1,1,1],

			[-1,-1,0,1,0],

			[0,0,0,-1,-1],

			[0,-1,0,-1,0]

		]

		self.assertTrue(isLegalPosition(board))

	def testIllegal(self):

		board=[

			[0,1,0,0,0],

			[1,-1,1,0,0],

			[0,1,0,0,0],

			[0,0,0,0,0],

			[0,0,0,0,0]

		]

		self.assertFalse(isLegalPosition(board))