import re


def skipWhitespace(s,start):
	i=start
	while i<len(s) and s[i].isspace(): i+=1
	return i


class Collection:
	def __init__(self,s):
		self.gameTrees=[]
		i,x=GameTree.create(s,0)
		if x is None:
			print("error when parsing Collection")
			return
		while x is not None:
			self.gameTrees.append(x)
			i,x=GameTree.create(s,i)

	def listGames(self):
		for tree in self.gameTrees:
			for game in tree.listGames(): yield game


class GameTree:
	def __init__(self):
		self.nodes=[]
		self.branches=[]

	@staticmethod
	def create(s,start):
		res=GameTree()
		i=skipWhitespace(s,start)
		if i>=len(s) or s[i]!="(":
			# print("error when parsing GameTree")
			return (start,None)
		i,x=Node.create(s,start+1)
		if x is None:
			# print("error when parsing GameTree")
			return (i,None)
		y=None
		while x is not None:
			res.nodes.append(x)
			if y: y.addChild(x)
			x.setParent(y)
			y=x
			i=skipWhitespace(s,i)
			i,x=Node.create(s,i)
		i=skipWhitespace(s,i)
		i,x=GameTree.create(s,i)
		while x is not None:
			res.branches.append(x)
			subroot=x.getNode(0)
			if subroot:
				subroot.setParent(y)
			if y: y.addChild(subroot)
			i=skipWhitespace(s,i)
			i,x=GameTree.create(s,i)
		if s[i]!=")":
			# print("error when parsing GameTree")
			return (i,None)
		return (i+1,res)

	## Expand multiple games into distinct GameTrees and yield each.
	def listGames(self):
		for node in self._listGINodes():
			yield self._buildSubtree(node)

	def getNode(self,i):
		if 0<=i<len(self.nodes):
			return self.nodes[i]
		return None

	## Create and return a new GameTree containing the provided Node.
	#
	# The Node objects are shared between the trees, not copied.
	def _buildSubtree(self,node):
		res=GameTree()

		return res
		# chci celou cestu ke kořeni a všechny podstromy nodu

	## Find and yield Game Info nodes.
	def _listGINodes(self):
		for node in self.nodes:
			if node.isGINode():
				yield node
		for tree in self.branches:
			for node in tree._listGINodes():
				yield node


class Node:
	def __init__(self):
		self.properties=dict()
		self._parent=None
		self._children=[]

	@staticmethod
	def create(s,start):
		res=Node()
		if s[start]!=";":
			# print("error when parsing Node")
			return (start,None)
		i=skipWhitespace(s,start+1)
		i,x=Property.create(s,start+1)
		while x is not None:
			if x.name in res.properties:
				print(res.properties)
				raise ParserError(0,0,'duplicate "{0}" property in node at position {1}. second value ignored'.format(x.name,start))
			else:
				res.properties[x.name]=x
			i=skipWhitespace(s,i)
			i,x=Property.create(s,i)
		return (i,res)

	def isGINode(self):
		return any(prop.type==Property.GAME_INFO for prop in self.properties.values())

	def setProperty(self,name,value):
		self.properties[name]=value
		# zkontrolovat typ value

	def setParent(self,node):
		self._parent=node

	def addChild(self,node):
		if node in self._children: return node
		self._children.append(node)
		return node

	def removeChild(self,node):
		if node not in self._children:
			return None
		del self._children[self._children.index(node)]
		return node

	def removeChildAt(self,i):
		if -len(self._children)<i<len(self._children):
			res=self._children[i]
			del self._children[i]
			return res
		return None
		
	def getProperty(self,name):
		if name in self.properties: return self.properties[name]
		else: return None
	
class Property:
	GAME_INFO=1
	UNKNOWN=99

	def __init__(self):
		self.name=""
		self.value=""

	@staticmethod
	def create(s,start):
		res=Property()
		i,x=Property.ident(s,start)
		if x is None:
			return (start,None)
		res.name=x
		i,x=PropValue.create(s,i,res.name)
		if x is None:
			print('error when parsing property "{0}" at position {1}'.format(res.name,i))
			return (start,None)
		res.value=x
		return (i,res)

	@staticmethod
	def ident(s,start):
		r=re.compile(r"[A-Z]+")
		m=r.match(s,start)
		if m is None: return (start,None)
		return (m.end(),m.group())

	@property
	def type(self):
		gameInfo={"AN","BR","BT","CP","DT","EV","GN","GC","ON","OT","PB","PC","PW","RE","RO","RU","SO","TM","US","WR","WT"}
		if self.name in gameInfo: return Property.GAME_INFO
		else: return Property.UNKNOWN

class PropValue:
	def __init__(self):
		self.type=""
		self.value=None

	patterns=dict()

	@staticmethod
	def create(s,start,name):
		if name in PropValue.patterns:
			return PropValue.patterns[name](s,start)
		else:
			print('warning, unknown property "{0}" at position {1}'.format(name,start))
			return PropValue.singleton(PropValue.anything)(s,start)

	def choose(*vTypes):
		def f(s,start):
			for vType in vTypes:
				i,x=vType(s,start)
				if x is not None: return (i,x)
			return (start,None)
		return f

	def singleton(vType):
		def f(s,start):
			if s[start]!="[":
				return (start,None)
			i,x=vType(s,start+1)
			if x is None: return (start,None)
			if s[i]!="]":
				return (start,None)
			return (i+1,x)
		return f

	def listOf(vType,allowEmpty=False):
		def f(s,start):
			res=[]
			single=PropValue.singleton(vType)
			i,x=single(s,start)
			while x!=None:
				res.append(x)
				i,x=single(s,i)
			if len(res)==0 and not allowEmpty: return (start,None)
			return (i,res)
		return f

	def compose(vTypeA,vTypeB):
		def f(s,start):
			i,a=vTypeA(s,start)
			# print(">",i,a)
			if a==None or s[i]!=":": return (start,None)
			i,b=vTypeB(s,i+1)
			# print(">",i,b)
			if b==None: return start,None
			return (i,(a,b))
		return f

	def number(s,start):
		r=re.compile(r"(\+|-|)\d+")
		m=r.match(s,start)
		if m is None: return (start,None)
		res=int(m.group(0))
		return (m.end(),res)

	def real(s,start):
		r=re.compile(r"(\+|-|)\d+(\.\d+)?")
		m=r.match(s,start)
		if m is None: return (start,None)
		res=float(m.group(0))
		return (m.end(),res)

	def double(s,start):
		r=re.compile(r"1|2")
		m=r.match(s,start)
		if m is None: return (start,None)
		res=int(m.group(0))
		return (m.end(),res)

	def color(s,start):
		r=re.compile(r"B|W")
		m=r.match(s,start)
		if m is None: return (start,None)
		return (m.end(),m.group(0))

	def text(simple=True,composed=False):
		def f(s,start):
			res=""
			esc=False
			lastC=""
			for i,c in enumerate(s[start:],start):
				if esc:
					if c!="\n" and c!="\r": res+=c
					esc=False
				elif (c=="\n" and lastC=="\r") or (c=="\r" and lastC=="\n"): pass
				elif c=="\r" or c=="\n" and not simple:
					res+="\n"
				elif c.isspace():
					res+=" "
				elif c=="\\":
					esc=True
				elif c=="]" or (c==":" and composed):
					break
				else:
					res+=c
				lastC=c
			return (i,res)
		return f

	def empty(s,start): return (start,"")

	def anything(s,start):
		esc=False
		for i,c in enumerate(s[start:],start):
			if esc: esc=False
			elif c=="\\": esc=True
			elif c=="]": break
		return (i,s[start:i])
	
	# go specific
	def point(s,start):
		r=re.compile(r"[a-zA-Z]{2}|") # !! limit to board size
		m=r.match(s,start)
		if m is None: return (start,None)
		if m.group(0)=="": # pass, !! tt
			return (m.end(),tuple())
		col=m.group(0)[0]
		row=m.group(0)[1]
		col=ord(col) - (ord("a") if "a"<=col<="z" else ord("A")-26)
		row=ord(row) - (ord("a") if "a"<=row<="z" else ord("A")-26)
		return (m.end(),(col,row))

	move=point
	stone=point
	
	patterns={
		"B":singleton(move),
		"KO":singleton(empty),
		"MN":singleton(number),
		"W":singleton(move),
		"AB":listOf(stone), #
		"AE":listOf(point), #
		"AW":listOf(stone), #
		"PL":singleton(color),
		"C":singleton(text(simple=False)),
		"DM":singleton(double),
		"GB":singleton(double),
		"GW":singleton(double),
		"HO":singleton(double),
		"N":singleton(text()),
		"UC":singleton(double),
		"V":singleton(real),
		"BM":singleton(double),
		"DO":singleton(empty),
		"IT":singleton(empty),
		"TE":singleton(double),
		"AR":listOf(compose(point,point)), #
		"CR":listOf(point), #
		"DD":listOf(point,allowEmpty=True), #
		"LB":listOf(compose(point,text())), #
		"LN":listOf(compose(point,point)), #
		"MA":listOf(point), #
		"SL":listOf(point), #
		"SQ":listOf(point), #
		"TR":listOf(point), #
		"AP":singleton(compose(text(composed=True),text())), #
		"CA":singleton(text()),
		"FF":singleton(number),
		"GM":singleton(number),
		"ST":singleton(number),
		"SZ":choose(singleton(number),singleton(compose(number,number))), #
		"AN":singleton(text()),
		"BR":singleton(text()),
		"BT":singleton(text()),
		"CP":singleton(text()),
		"DT":singleton(text()),
		"EV":singleton(text()),
		"GN":singleton(text()),
		"GC":singleton(text(simple=False)),
		"ON":singleton(text()),
		"OT":singleton(text()),
		"PB":singleton(text()),
		"PC":singleton(text()),
		"PW":singleton(text()),
		"RE":singleton(text()),
		"RO":singleton(text()),
		"RU":singleton(text()),
		"SO":singleton(text()),
		"TM":singleton(real),
		"US":singleton(text()),
		"WR":singleton(text()),
		"WT":singleton(text()),
		"BL":singleton(real),
		"OB":singleton(number),
		"OW":singleton(number),
		"WL":singleton(real),
		"FG":choose(singleton(empty),singleton(compose(number,text()))), #
		"PM":singleton(number),
		"VW":listOf(point,allowEmpty=True), #
		
		# go specific
		"HA":singleton(number),
		"KM":singleton(real),
		"TB":listOf(point,allowEmpty=True),
		"TW":listOf(point,allowEmpty=True)
	}

class ParserError(Exception):
	def __init__(self,line,col,message):
		self.line=line
		self.col=col
		self.message=message

# TODO:
# date


"""
# move
B	move
KO	none
MN	number
W	move

# setup
AB	list of stone
AE	list of point
AW	list of stone
PL	color

# node annotation
C	text
DM	double
GB	double
GW	double
HO	double
N	simpleText
UC	double
V	real

# move annotation
BM	double
DO	none
IT	none
TE	double

# markup
AR	list of composed point:point
CR	list of point
DD	elist of point
LB	list of composed point:simpleText
LN	list of composed point:point
MA	list of point
SL	list of point
SQ	list of point
TR	list of point

# root
AP	composed simpleText:simpleText
CA	simpleText
FF	number
GM	number
ST	number
SZ	number | composed number:number

# game info
AN	simpleText
BR	simpleText
BT	simpleText
CP	simpleText
DT	simpleText
EV	simpleText
GN	simpleText
GC	text
ON	simpleText
OT	simpleText
PB	simpleText
PC	simpleText
PW	simpleText
RE	simpleText
RO	simpleText
RU	simpleText
SO	simpleText
TM	real
US	simpleText
WR	simpleText
WT	simpleText

# timing
BL	real
OB	number
OW	number
WL	real

# misc
FG	none | composition of number:simpleText
PM	number
VW	elist of point
"""