# Sprawdzamy wszystkie przykłady:
# for c in xrange(3,11):
#     for x in xrange(1, number_of_knots[c-3]+1):
#         k = 'knot_' + str(c) + '_' + str(x)
#         knot = eval(k)
#         print knot
#         C = TwistedChainComplex(knot)
#         print C.G



# Attach knot tables
attach("./knot-table.sage")

class TwistedChainComplex(object):
    r"""
    This class implements twisted Blanchfield pairing of a zero-surgery of a knot.
    """
    def __init__(self,knot,field=RationalField(),images=None):
	self.knot = knot
	self.field = field
	self.ring = LaurentPolynomialRing(self.field,'T')
	self.pol_ring = self.ring.polynomial_ring()
	self.T = self.ring.gen()
	self.TT = self.pol_ring.gen()
	self.G, self.ui = self._fundamental_group()
        assert self.G.abelian_invariants() == (0,)


    def _find_arc(self, edge):
	arcs = self.knot.arcs()
	for arc in arcs:
	    if edge in arc:
		return arcs.index(arc)


    def _fundamental_group(self):
	G = self.knot.fundamental_group()
	# print G
	pd_code = self.knot.pd_code()
	# print 'pd_code: ' + str(pd_code)
	arcs = self.knot.arcs()
	# print 'arcs: ' + str(arcs)
	orient = self.knot.orientation()
	# print 'orientation: ' + str(orient)
	w = self.knot.writhe()
	arc = self._find_arc(1)
	longitude = G([arc+1 for x in xrange(abs(w))])
	overcrossing_seq = [0] * len(arcs)
	if w>0:
	    longitude = longitude.inverse()
	# print 'longitude: ' + str(longitude)
	current_pos = -1
	for step in xrange(1,2 * len(pd_code)+1):
	    for c in xrange(len(pd_code)):
		if c != current_pos and step in pd_code[c]:
		    current_pos = c
		    break
	    # print 'step = ' + str(step)
	    # print 'current_pos = ' + str(current_pos)
	    ind = pd_code[current_pos].index(step)
	    # print 'ind = ' + str(ind)
	    if ind % 2 == 0:
		# print 'undercrossing'
		overcrossing = pd_code[current_pos][(ind+1) % 4]
		# print 'over = ' + str(overcrossing)
		for a in xrange(len(arcs)):
		    if overcrossing in arcs[a]:
			arc_num = a
			# print 'arc_num = ' + str(arc_num)
			break
		# print 'current_pos = ' + str(current_pos)
		overcrossing_seq[current_pos] = longitude
		g = G([arc_num+1]).inverse() if orient[current_pos] == -1 else G([arc_num+1])
		# print 'g = ' + str(g)
		longitude = longitude * g
	    # else:
		# print 'overcrossing'
	F = G.free_group()
	return F.quotient(list(G.relations()) + [longitude]), overcrossing_seq # [G([arc+1]) * x for x in overcrossing_seq]

    def _find_path(self,dest,regions):
	visited = [1] + [0] * (len(regions)-1)
	# visited = [0] * len(regions)
	current_region = regions[0]
	if -dest in current_region:
	    return []
	found = False
	path = []
	# print 'Find region: ' + str(dest)
	# print 'regions = ' + str(regions)
	# print 'current_region = ' + str(current_region)
	# print 'visited = ' + str(visited)
	# print 'path = ' + str(path)
	found = False
	while prod(visited) == 0 or found == True:
	    all_nbs_visited = True
	    for x in current_region:
		# print 'x = ' + str(x)
		r = self._find_region(x,regions)
		i = regions.index(r)
		# print 'r = ' + str(r)
		if visited[i] == 1:
		    # print 'visited'
		    continue
		else:
		    current_region = r
		    visited[i] = 1
		    path = path + [x]
		    # print 'current_region = ' + str(current_region)
		    # print 'visited = ' + str(visited)
		    # print 'path = ' + str(path)
		    if (-dest) in r:
			return path
		    else:
			all_nbs_visited = False
			break
	    if all_nbs_visited:
		# take tha last element from the path
		# print 'Stepping back'
		x = path[-1:][0]
		# print 'Currently last element in path list: ' + str(x)
		r = self._find_region(-x,regions)
		current_region = r
		path = path[:-1]
		# print 'current_region = ' + str(current_region)
		# print 'visited = ' + str(visited)
		# print 'path = ' + str(path)
	raise ValueError("We are screwed...")


    def _find_region(self,edge,regions):
	for reg in regions:
	    if -edge in reg:
		return reg


    def _compute_wi(self):
	# this function should work, but I am not completely sure that it does
	n = len(self.G.gens())
	rels = self.G.relations()
	M = [self.G([])] * n
	result = []
	pd_code = self.knot.pd_code()
	regions = self.knot.regions()
	# print 'regions = ' + str(regions)
	for pd in pd_code:
	    # print '##############################################################'
	    start = pd[0]
	    # print 'pd = ' + str(pd)
	    # print 'Destination region: ' + str(self._find_region(start,regions))
	    path = self._find_path(pd[0],regions)
	    # print 'Path: ' + str(path)
	    element = self.G([])
	    for x in path:
		if x >= 0:
		    element = element * self.G([self._find_arc(x)+1]).inverse()
		else:
		    element = element * self.G([self._find_arc(-x)+1])
	    # print 'element = ' + str(element)
	    result.append(element)
	return result


    def _compute_image_of_an_element(self, g):
	# assert g in self._G
	image = self.ring(1)
	for t in g.Tietze():
	    if t>0:
		image = image * self.images[t-1]
	    else:
		image = image * self.images[-t-1]^-1
	return image