#!/usr/bin/env python

import sys
import os


class MySettings(object):

    def __init__(self):

        self.f_pd_knot_11_15 = os.path.join(os.getcwd(), "knots_11_to_15.txt")
        self.f_knot_up_to_10 = os.path.join(os.getcwd(), "knots_3_to_10.txt")


class Crossing(object):

    def __init__(self, c_idx, paired_ind, complex, previous):

        self.c_idx = c_idx
        self.paired_ind = paired_ind
        self.previous = previous

        self.G = complex.knot.fundamental_group()
        self.F = self.G.free_group()
        self.pd = complex.pd_code[c_idx]
        if paired_ind is not None:
            self.edge = self.pd[paired_ind]
        else:
            self.edge = None
        self.orientation = complex.orientation[c_idx]
        self.pd_sign = self.get_pd_sign()
        self.element = self.set_element(complex)

        self.done = False
        self.path_by_edges = []
        self.w_i = self.F([])

    def set_w_i(self, complex):
        w_i = self.F([])
        path = self.get_path_by_edges(None)
        for edge in path:
            arc = complex.get_arc(abs(edge))
            g = self.F([arc+1])
            if edge < 0:
                g = g.inverse()
            w_i *= g
        self.path_by_edges = path
        self.w_i = w_i

    def get_path_by_edges(self, edge):
        path_by_edges = []
        if self.previous is not None:
            path_by_edges.extend(self.previous.get_path_by_edges(self.edge))
        if edge is not None:
            idx = self.pd.index(edge)
        else:
            idx = None
        path_by_edges.extend(self.get_correction(idx))
        return path_by_edges

    def get_correction(self, ind_to_pair):
        path = []
        correction_in = self.calculate_correction_in(ind_to_pair)
        if self.previous is not None:
            ind_to_pair = self.previous.pd.index(self.edge)
            p_out = self.previous.calculate_correction_out(ind_to_pair)
            path.extend(p_out)
        path.extend(correction_in)
        return path

    def calculate_correction_in(self, ind_to_pair):
        path_out = self.calculate_correction_out(ind_to_pair)
        ind = self.paired_ind
        if ind is None or ind == 0:
            return []
        pd = self.pd_sign
        if ind == 3:
            return [pd[3]]
        if ind == 1 and len(path_out) > 2:
            return [pd[1], pd[2], pd[3]]
        if ind == 2 and len(path_out) > 1:
            return [pd[2], pd[3]]
        if ind == 1:
            return [-pd[0]]
        return [-pd[1], -pd[0]]  # ind == 2

    def calculate_correction_out(self, ind_to_pair):
        path = []
        if ind_to_pair is not None:
            if ind_to_pair < 3:
                path.append(-self.pd_sign[3])
            if ind_to_pair < 2:
                path.append(-self.pd_sign[2])
            if ind_to_pair < 1:
                path.append(-self.pd_sign[1])
        return path

    def set_element(self, complex):
        loop = self.set_loop(complex)
        relation = self.F([])
        for element in loop:
            relation *= element
        return relation

    def set_loop(self, complex):
        F = self.F
        loop = []
        for edge in self.pd_sign:
            arc = complex.get_arc(abs(edge))
            g = F([arc+1])
            if edge < 0:
                g = g.inverse()
            loop.append(g)
        return loop

    def get_pd_sign(self):
        pd = []
        pd.append(self.pd[0])
        if self.orientation == 1:
            pd.append(self.pd[1])
            pd.append(-self.pd[2])
            pd.append(-self.pd[3])
        else:
            pd.append(-self.pd[1])
            pd.append(-self.pd[2])
            pd.append(self.pd[3])
        return pd


class TwistedChainComplex(object):
    """
    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.crossings_list = []

        self.pd_code = self.knot.pd_code()
        self.visited = [False] * len(self.pd_code)

        self.orientation = self.knot.orientation()
        # 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.overcrossing_seq = []
        self.G = self.get_fundamental_group()
        assert self.G.abelian_invariants() == (0,)

    def get_fundamental_group(self):
        G = self.knot.fundamental_group()
        pd_code = self.pd_code
        orientation = self.knot.orientation()
        writhe = self.knot.writhe()
        arc = self.get_arc(1)
        overcrossing_seq = [0] * len(pd_code)
        longitude = G([arc + 1] * abs(writhe))
        if writhe > 0:
            longitude = longitude.inverse()
        for entry in range(1, 2 * len(pd_code) + 1):
            for idx, pd in enumerate(pd_code):
                if entry == pd[0]:
                    # print "undercrossing pd[0]"
                    overcrossing_seq[idx] = longitude
                    overcrossing = pd[1]
                    arc = self.get_arc(overcrossing)
                    g = G([arc + 1])
                    if orientation[idx] == -1:
                        g = g.inverse()
                        overcrossing = -overcrossing
                    longitude *= g
                    break
                elif entry == pd[1] and orientation[idx] == 1:
                    # print "overcrossing pd[1]"
                    break
                elif entry == pd[3] and orientation[idx] == -1:
                    # print "overcrossing pd[3]"
                    break
        relations = list(G.relations())
        relations.append(longitude)
        F = G.free_group().quotient(relations)
        self.overcrossing_seq = overcrossing_seq
        return F

    def get_crossings_list(self):
        pd_code = self.pd_code
        pd_ind = 0  # current crossing id
        paired_ind = None  # position for a paired edge
        crossing = None
        while not all(self.visited):
            self.visited[pd_ind] = True
            crossing = Crossing(pd_ind, paired_ind, self, crossing)
            self.crossings_list.append(crossing)
            pd = crossing.pd
            for i in reversed(range(4)):
                pd_ind, paired_ind = self.find_next(crossing.c_idx, pd[i])
                if not self.visited[pd_ind]:
                    break
                elif self.visited[pd_ind] and i == 0:
                    if all(self.visited):
                        break
                    crossing, pd_ind, paired_ind = self.find_previous()
        return self.crossings_list

    def compute_wi(self):

        F = self.G.free_group()
        self.crossings_list = self.get_crossings_list()
        crossings_list = self.crossings_list
        null_loop = F([])
        full_walk = []  # conjugated elements
        big_lst = []  # elements

        for c in crossings_list:
            c.set_w_i(self)

        for c in crossings_list[::-1]:
            lst = []
            walk = []
            p = c
            while p is not None:
                if not p.done:
                    g = p.w_i * p.element * p.w_i.inverse()
                    walk.append(g)
                    lst.append(p)
                    p.done = True
                p = p.previous
            full_walk.extend(walk[::-1])
            big_lst.extend(lst[::-1])

        for el in full_walk:
            null_loop *= el

        if null_loop != F([]):
            n_loop = F([])
            for c in crossings_list:
                n_loop *= c.w_i * c.element * c.w_i.inverse()
            if n_loop == F([]):
                return -1
            print "n_loop = " + str(n_loop)
            return 0
        return 1

    def find_previous(self):
        previous = None
        for c in self.crossings_list:
            for i in reversed(range(4)):
                new_ind, paired_ind = self.find_next(c.c_idx, c.pd[i])
                if not self.visited[new_ind]:
                    previous = c
                    break
            if previous is not None:
                break
        if previous is None:
            raise ValueError("This knot is to difficult or doesn't exist.")
        return previous, new_ind, paired_ind

    def find_next(self, pd_ind, edge):
        pd_code = self.pd_code
        for ind, pd in enumerate(pd_code):
            if ind == pd_ind:
                continue
            if edge in pd:
                return ind, pd.index(edge)
        raise ValueError("The knot.pd_code is incorrect.")

    def get_arc(self, edge):
        arcs = self.knot.arcs()
        for idx, arc in enumerate(arcs):
            if edge in arc:
                return idx


def parse_pd_code(pd_code_from_file):
    set = '0987654321[],'
    pd_code = ''.join([c for c in pd_code_from_file if c in set])
    return eval(pd_code)


def parse_knot_name(name):
    data = name[5: -2].split(',')
    name = data[0].strip() + data[1].strip().lower()[:1] + data[2].strip()
    return name


def check_11_to_15(f_out=None):
    with open(settings.f_pd_knot_11_15, 'r') as f:
        line = f.readline()
        while line:
            name = parse_knot_name(line)
            pd_code = parse_pd_code(f.readline())
            line = f.readline()
            knot = Link(pd_code)
            C = TwistedChainComplex(knot)
            result = C.compute_wi()
            if result == 1:
                # print C.knot.is_alternating()
                pass
                # print "ok"
            # elif result == -1:
            #     print name
            elif result == 0:
                print "ERROR while checking " + str(name)


def check_up_to_10(f_out=None):
    with open(settings.f_knot_up_to_10, 'r') as f:
        line = f.readline()
        while line:
            line = line.split(" = ")
            name = str(line[0])[5:]
            pd_code = parse_pd_code(str(line[1]))
            line = f.readline()
            knot = Link(pd_code)
            C = TwistedChainComplex(knot)
            if C.compute_wi() == 1:
                # print C.knot.is_alternating()
                print "ok"
            else:
                print "!!!!!!!!!!!!!!"
                print knot
                print "!!!!!!!!!!!!!!"

def perform_test():
    # check_up_to_10()
    check_11_to_15()

if __name__ == '__main__':
    settings = MySettings()
    perform_test()