load "Homology.sage"

class FukayaAlg():

	"""
	This code computes the Hochschild homology of an undirected Fukaya algebra.

	Inputs:
		See examples at the bottom.

		given_number is the number of curves
		intersection_dict is a dictionary; the keys are the curves (tuples of integers), and the values are the intersection points (strings.)
		given_polygons is a list of polygons, and each polygon is stored as a list of tuples.

	Methods:
		seq(int,int)
		get_generators(int)
		getGenerators()
		product_list(list of lists)
		cycle(int)
		cycle2(list)
		multiplication(list of tuples)
		get_structure (tuple of tuples)
		mult_product(int,int,list of tuples)
		add(list,list)
		differential(list of tuples)
		GetDigraph()

	"""
	def __init__(self,given_number, intersection_dict, given_polygons):
		self.n=given_number        	
		self.intersection_dict=intersection_dict
		self.P=given_polygons
 		
		#creates a list of intersections
		lst=[]
		length=len(self.intersection_dict)
		for  i in range(length):
			for k in self.intersection_dict[self.intersection_dict.keys()[i]]:
				lst.append((self.intersection_dict.keys()[i][0],self.intersection_dict.keys()[i][1],k))  #(1,2,'a')
				lst.append((self.intersection_dict.keys()[i][1],self.intersection_dict.keys()[i][0],k))  #(2,1,'a')
		for i in range(self.n):
			lst.append((i+1,i+1,'t'))
			lst.append((i+1,i+1,'s'))
		self.intersection=lst
		
		#creates a dictionary of structure constants			
		Ttemp={}
		for i in range(self.n-1):
			for x in self.P[i]: #length(x)=i+2 
				C=[]
				for k in range(i+2):
					C.append(x[k][0])
				
				ccount=[]
				for y in C:
					ccount.append(C.count(y))
					
				if max(ccount)!=1:
					s=[]
					for j in range(i+1):
						s.append(x[j])
					S=tuple(s)
					if S in Ttemp.keys():
						Ttemp[S].append((x[i+1][1],x[i+1][0],x[i+1][2]))
					else:
				 		Ttemp[S]=[(x[i+1][1],x[i+1][0],x[i+1][2])]
								
		
				else:
					for y in self.cycle(i+2): 
						s=[]
						for j in range(i+1):
							s.append(x[y[j]])
							S=tuple(s)
						if S in Ttemp.keys():
							Ttemp[S].append((x[y[i+1]][1],x[y[i+1]][0],x[y[i+1]][2]))
						else:
							Ttemp[S]=[(x[y[i+1]][1],x[y[i+1]][0],x[y[i+1]][2])]
		self.T=Ttemp
									
	def seq(self,m,k):
		lst=[]
		if k>m:
			raise Exception('Halt!')
		if k==1:
			for i in range(1,m+1):
				lst.append([i])
			return lst
		for i in range(k,m+1):
			tmp=self.seq(i-1,k-1)
			for v in tmp:
				v.insert(0,i)
			lst.extend(tmp)
		return lst


	def get_generators(self,r):
		gens=[]
		if r==1:
			for v in self.intersection:
				if v[0]==v[1]:
					gens.append([v])
			return gens
		for l in self.seq(self.n,r):
			lst=[]
			for i in range(r-1):
				temp=[]
				for v in self.intersection:
					if v[0]==l[i] and v[1]==l[i+1]:
						temp.append(v)
				lst.insert(0,temp)
			temp=[]
			for v in self.intersection:	
				if v[0]==l[r-1] and v[1]==l[0]:
					temp.append(v)
			lst.insert(0,temp)
			gens.extend(self.product_list(lst))
		return list(gens)

	def getGenerators(self):
		gens=[]
		for r in range(1,self.n+1):
			gens.extend(self.get_generators(r))
		return gens

	def product_list(self,listoflists):
		"""
		Examples:
		sage: product_list([[1,2],[3,4]])
		[(1, 3), (1, 4), (2, 3), (2, 4)]
		sage: product_list([[1,2],[3,4],[1,2]])
		[(1, 3, 1), (1, 3, 2), (1, 4, 1), (1, 4, 2), (2, 3, 1), (2, 3, 2), (2, 4, 1), (2, 4, 2)]
		"""
		the_product=[]
		for a in listoflists[0]:
			the_product.append((a,))
		for i in range(1,len(listoflists)):
			next_product = []
			for b in the_product:
				for c in listoflists[i]:
					next_product.append(b+(c,))
			the_product = next_product
		The_product=[]
		for x in the_product:
			The_product.append(list(x))
		return The_product

	def cycle(self, r):
		lst=[]
		for i in range(r):
			temp=[]
			for j in range(r):
				temp.append((i+j)%r)
			lst.append(temp)
		return lst

	def cycle2(self, L):
		lst=[]
		l=len(L)
		for y in self.cycle(l):
			s=[]
			for j in range(l):
				s.append(L[y[j]])
			lst.append(s)
		return lst

	def multiplication(self, A):
		# A is a list of tuples.
		l=len(A)
		temp=[]
		for x in self.P[l-1]:
			for y in self.cycle(l+1):
				a=y[0:l]
				lst=[]
				for i in range(len(a)):
					lst.append(x[a[i]])
				if lst==A:
					b=x[y[l]]
					temp.append((b[1],b[0],b[2]))
		return temp
		return []


	def get_structure(self, A):
		if A in self.T.keys():
			return copy(self.T[A])
		else:
			return []

	
	def mult_product(self,k,j,vec):
		d=len(vec)
		temp1=[]
		temp2=[]
		temp3=[]
		i=0
		while i<k:
			temp1.append(vec[i])
			i=i+1	
		i=k
		while i<k+j:
			temp2.append(vec[i])
			i=i+1
		temp2.reverse()
                temp2=tuple(temp2)
		temp2=self.get_structure(temp2)
		i=k+j
		while i<d:
			temp3.append(vec[i])
			i=i+1
		if temp2==[]:
			return []
		if temp1==[] and temp3==[]:
			return temp2
		
		kkk=[]
		for x in temp2:
			t=copy(temp1)
			t.extend([x])
		       	t.extend(temp3)
			kkk=self.add(kkk,t)
		return kkk	
		
	
	def add(self, A,B):
		"Returns A+B"
		A.extend(B)
		lst=[]
		for x in A:
			if A.count(x)%2 == 1:
				lst.append(x)
		return lst

	def differential(self,L):
		l=len(L)
		if l>1:	
			lst1=[]

			for k in range(0,l):
				for j in range(1,l-k+1):
					if self.mult_product(k,j,L)!=[]:
						lst1=self.add(lst1,[self.mult_product(k,j,L)])
		
			for j in range(1,l):
				for k in range(l-j):
					lst2=L[j:(j+k)]
					lst3=[]
					lst3.extend(L[(j+k):l])
					lst3.extend(L[0:j])
					lst3.reverse()
					lst3=tuple(lst3)
					lst3=self.get_structure(lst3)
					if lst3!=[]:
						lst3.extend(lst2)
						lst1=self.add(lst1,[lst3])
			
			return lst1
		if l==1:
			return self.get_structure((L[0],))


	def GetDigraph(self):
		G=ChainCx({0:[]})	
		for x in self.getGenerators():
			G.add_vertices({tuple(x):[]})
		
		for y in self.getGenerators():
			for z in self.differential(y):
				G.add_edge(tuple(y),tuple(z))
		
		G.delete_vertex(0)
	
		return G



"""
Tim=FukayaAlg(3,{(1,3):['a','c'],(2,3):['d'],(1,2):['b']},[[],[[(2,1,'b'),(1,3,'c'),(3,2,'d')],[(3,2,'d'),(2,3,'d'),(3,3,'t')],[(2,3,'d'),(3,2,'d'),(2,2,'t')],[(2,1,'b'),(1,2,'b'),(2,2,'t')],[(1,2,'b'),(2,1,'b'),(1,1,'t')],[(3,1,'a'),(1,3,'a'),(3,3,'t')],[(1,3,'a'),(3,1,'a'),(1,1,'t')],[(3,1,'c'),(1,3,'c'),(3,3,'t')],[(1,3,'c'),(3,1,'c'),(1,1,'t')]]])
sage: Tim.differential([(1, 3, 'a'), (2, 1, 'b'), (3, 2, 'd')])
[[(1, 3, 'a'), (3, 1, 'c')]]
sage: Tim.differential([(1, 3, 'c'), (2, 1, 'b'), (3, 2, 'd')])
[[(2, 3, 'd'), (3, 2, 'd')],
 [(1, 3, 'c'), (3, 1, 'c')],
 [(1, 2, 'b'), (2, 1, 'b')]]
sage: Tim.differential([(1, 2, 'b'), (2, 1, 'b')])
[[(2, 2, 't')], [(1, 1, 't')]]
sage: Tim.differential([(1, 3, 'a'), (3, 1, 'a')])
[[(3, 3, 't')], [(1, 1, 't')]]
sage: G=Tim.GetDigraph()
sage: G
Digraph on 14 vertices
sage: G.edges()
[(((1, 2, 'b'), (2, 1, 'b')), ((1, 1, 't'),), None),
 (((1, 2, 'b'), (2, 1, 'b')), ((2, 2, 't'),), None),
 (((1, 3, 'a'), (2, 1, 'b'), (3, 2, 'd')), ((1, 3, 'a'), (3, 1, 'c')), None),
 (((1, 3, 'a'), (3, 1, 'a')), ((1, 1, 't'),), None),
 (((1, 3, 'a'), (3, 1, 'a')), ((3, 3, 't'),), None),
 (((1, 3, 'c'), (2, 1, 'b'), (3, 2, 'd')), ((1, 2, 'b'), (2, 1, 'b')), None),
 (((1, 3, 'c'), (2, 1, 'b'), (3, 2, 'd')), ((1, 3, 'c'), (3, 1, 'c')), None),
 (((1, 3, 'c'), (2, 1, 'b'), (3, 2, 'd')), ((2, 3, 'd'), (3, 2, 'd')), None),
 (((1, 3, 'c'), (3, 1, 'c')), ((1, 1, 't'),), None),
 (((1, 3, 'c'), (3, 1, 'c')), ((3, 3, 't'),), None),
 (((2, 3, 'd'), (3, 2, 'd')), ((2, 2, 't'),), None),
 (((2, 3, 'd'), (3, 2, 'd')), ((3, 3, 't'),), None)]
sage: G.Homology()
Homology is 6
"""


"""

sage: Tim.mult_product(0,2,L)
[(3, 1, 'c'), (1, 3, 'c')]

sage: Tim.mult_product(1,2,L)
[(2, 3, 'd'), (3, 2, 'd')]

sage: Tim.add([],Tim.mult_product(0,2,Tim.cycle2(L)[2])
....: )
[(2, 1, 'b'), (1, 2, 'b')]
sage: Tim.add([],Tim.mult_product(1,2,Tim.cycle2(L)[2])
)
[(1, 3, 'c'), (3, 1, 'c')]
sage: Tim.add([],Tim.mult_product(1,2,Tim.cycle2(L)[1])
)
[(2, 1, 'b'), (1, 2, 'b')]
sage: Tim.add([],Tim.mult_product(0,2,Tim.cycle2(L)[1])
)
[(2, 3, 'd'), (3, 2, 'd')] [(1, 3, 'a'), (2, 1, 'b'), (3, 2, 'd')]
"""

#### Example: F=FukayaAlg(3,{(1,2):['d'],(2,3):['c'],(1,3):['a','b']},[[],[[(2,1,'a'),(1,2,'a'),(1,1,'t')],[(3,1,'a'),(1,3,'a'),(1,1,'t')],[(1,2,'a'),(2,1,'a'),(2,2,'t')],[(3,2,'a'),(2,3,'a'),(2,2,'t')],[(1,3,'a'),(3,1,'a'),(3,3,'t')],[(2,3,'a'),(3,2,'a'),(3,3,'t')]]])

#F=FukayaAlg(3,{(1,2):['b'],(2,3):['a'],(1,3):['c']},[[],[]

####G=FukayaAlg(4,{(1,4):['a'],(3,4):['b'],(2,3):['c'],(1,2):['d']},[[],[],[[(1,4,'a'),(4,3,'b'),(3,2,'c'),(2,1,'d')],[(1,4,'a'),(4,3,'b'),(3,2,'c'),(2,1,'e')]]])

####H=FukayaAlg(4,{(1,4):['a'],(3,4):['b'],(2,3):['c'],(1,2):['d']},[[],[[(1,4,'a'),(4,2,'k'),(2,1,'p')],[(2,1,'p'),(1,2,'q'),(2,2,'s')]],[[(1,4,'a'),(4,3,'b'),(3,2,'c'),(2,1,'d')],[(1,4,'a'),(4,3,'b'),(3,2,'c'),(2,1,'e')]]])

####H=FukayaAlg(4,{(1,4):['a'],(3,4):['b'],(2,3):['c'],(1,2):['d']},[[[(1,2,'d'),(1,2,'e')]],[[(1,4,'a'),(4,2,'k'),(2,1,'p')],[(3,4,'e'),(1,2,'d'),(5,6,'x')],[(3,4,'e'),(1,2,'e'),(4,3,'t')],[(2,1,'p'),(1,2,'q'),(2,2,'s')]],[[(1,4,'a'),(4,3,'b'),(3,2,'c'),(2,1,'d')],[(1,4,'a'),(4,3,'b'),(3,2,'c'),(2,1,'e')]]])

####H=FukayaAlg(4,{(1,4):['a'],(3,4):['b'],(2,3):['c'],(1,2):['d']},[[[(1,2,'d'),(1,2,'e')]],[[(1,4,'a'),(4,2,'k'),(2,1,'p')],[(3,4,'e'),(1,2,'d'),(5,6,'x')],[(3,4,'e'),(2,1,'e'),(4,3,'t')],[(2,1,'p'),(1,2,'q'),(2,2,'s')]],[[(1,4,'a'),(4,3,'b'),(3,2,'c'),(2,1,'d')],[(1,4,'a'),(4,3,'b'),(3,2,'c'),(2,1,'e')]]])