import time
import sys
import numpy as np
from functools import reduce
from math import gcd


FILE_PATH = './test.txt'
RANDOM = False
RESULTS_PATH = './result-random.txt'
sys.stdout = open(RESULTS_PATH, 'w')

_p = list()
_q = list()


def generate_matrix_for_input(d=3):
    return np.eye(d)


def timeit(method):
    def timed(*args, **kw):
        ts = time.time()
        result = method(*args, **kw)
        te = time.time()
        if 'log_time' in kw:
            name = kw.get('log_name', method.__name__.upper())
            kw['log_time'][name] = int((te - ts) * 1000)
        else:
            print('execution time for %r: %2.2f ms' % (
                method.__name__, (te - ts) * 1000))
        return result
    return timed


@timeit
def normalize(vector):
    # since vector is a matrix row - convert it to 1-d array
    # (т.к. вектор - строка матрицы: превращаем его в одномерный массив)
    vector = np.array(vector).flatten()  # [[1. 2. 0. 1.]] -> [1. 2. 0. 1.]
    vector = list(map(int, vector))
    if not any(vector):  # we don't need to normalize zero vector (нам не нужно нормализовать нулевой вектор)
        return vector
    _gcd = reduce(lambda x, y: gcd(x, y), vector)  # compute gcd (считаем НОД)
    return np.array(list(map(lambda x: x / _gcd, vector)))  # divide all elements by gcd (делим все элементы на НОД)

@timeit
def _bool(vector, xor=False):
    # since vector is a matrix row - convert it to 1-d array
    # (т.к. вектор - строка матрицы: превращаем его в одномерный массив)
    vector = np.array(vector).flatten()  # [[1. 2. 0. 1.]] -> [1. 2. 0. 1.]
    # возвращаем 1 если больше 0, иначе - 0
    if not xor:
        return np.matrix([[int(bool(element))
                           for element in vector]]).transpose()
    else:
        return np.matrix([[1 if element == 1 else 0
                           for element in vector]]).transpose()

@timeit
def adjacent(q, j_1, j_2, j_pos_neg):
    for k in range(q.shape[0]):
        if k != j_1 and k != j_2:
            if not any([q[k, m] for m in j_pos_neg]):
                return False
    return True

@timeit
def DDM_DYN(matrix):

    m = matrix.shape[0]  # number of rows (количество строк)
    d = matrix.shape[1]  # number of columns (количество столбцов)

    U = np.matrix(np.eye(m))  # to understand why m, not d - look at U(0) at tests
    # (чтобы понять, почему тут m - смотри тест U(0)

    # V and Q should be width m but without rows
    # (V и Q должны содержать m столбцов но не содержать строк)
    V = np.empty((0, m))  # to understand, why m, not d - look at V(1) at tests
    # (чтобы понять, почему m - смотри V(1) в тестах
    Q = np.empty((0, 0))

    print("ITER 0: \nU:\n{U} \nV:\n{V} \nQ:\n{Q}".format(
        U=U, V=V, Q=Q))

    for i in range(d):  # m, not d, check tests (we have d iterations)
        # (d итераций - смотри тесты, там d итераций, а не m)

        p = U * matrix[:, i]

        # if V was just initialized - shape == (0, m)
        # Если V только что инициализировано (нет строк, shape == (0, m)) пишем просто столбец
        q = V * matrix[:, i] if V.shape[0] != 0 else matrix[:, i]
        print("p: ", p)
        print("q: ", q)

        if np.count_nonzero(p) == 0:  # if zero vector
            # (если p - нулевой вектор)
            Q = np.hstack((Q, _bool(q)))

            j_pos = {idx for idx, value in enumerate(q) if value > 0}
            j_neg = {idx for idx, value in enumerate(q) if value < 0}

            V_new = np.empty((0, m))  # same that for V
            # (то же самое, что и для V)
            Q_new = np.empty((0, Q.shape[1]))  # we need to add Q_new rows to Q
            # (нам нужно добавить Q_new к Q - количество столбцов должно быть равно)

            r = d - Q.shape[0]  # should be U, but works with Q

            for j_1 in j_pos:
                for j_2 in j_neg:

                    j_pos_neg = {k for k in range(Q.shape[1])
                                 if Q[j_1, k] == Q[j_2, k] == 0}

                    if len(j_pos_neg) >= r - 2:
                        if adjacent(Q, j_1, j_2, j_pos_neg):
                            V_new = np.vstack(
                                (V_new, normalize(q[j_1] * V[j_2] - q[j_2] * V[j_1])))

                            # disjunction of Q[j_1] and Q[j_2]
                            # (xor - исключающий или Q[j_1] и Q[j_2]
                            xor = _bool(
                                _bool(Q[j_1]).transpose() + _bool(Q[j_2]).transpose(),
                                xor=True).transpose()
                            Q_new = np.vstack(
                                (Q_new, normalize(xor)))

            # if Q_new.shape[0]:  # add column if Q_new has rows
            #     Q_new = np.hstack((Q_new, np.zeros((Q_new.shape[0], 1))))

            V = np.delete(V, list(j_neg), axis=0)
            Q = np.delete(Q, list(j_neg), axis=0)

            if V_new.shape[0]:  # if V_new has rows (numpy won't let add 0xVALUE row or column)
                # (если V_new имеет строки (numpy не даст нам добавить матрицу без строк)
                V = np.vstack((V, V_new))
            if Q_new.shape[0]:  # same as for V_new
                # (то же самое, что для V_new)
                Q = np.vstack((Q, Q_new))

        else:
            j_0 = None
            for idx, value in enumerate(p):
                if value:
                    j_0 = idx
                    break

            if p[j_0] < 0:
                U[j_0] = -U[j_0]
                p[j_0] = -p[j_0]

            t = U.shape[0]  # t because U shape is (t, d)
            # (потому что размерность U - t на d)
            for j in range(t):  # range(t) because p length equals to number of rows in U
                # range(t) потому что длина p равна количеству строк в U
                if j != j_0 and p[j] != 0:
                    U[j] = normalize(
                        p[j_0] * U[j] - p[j] * U[j_0])

            s = V.shape[0]  # because V is shape (s, d), check algorithm description
            # (потому что размерность V - s на d, смотри описание алгоритма)
            for j in range(s):
                if q[j]:
                    V[j] = normalize(
                        p[j_0] * V[j] - q[j] * U[j_0])

            V = np.vstack((V, U[j_0]))
            U = np.delete(U, [j_0], axis=0)

            if Q.shape == (0, 0):
                Q = np.matrix([[1]])
            else:
                Q = np.hstack((Q, np.zeros((Q.shape[0], 1))))
                Q = np.vstack((Q, [0 for _ in range(Q.shape[1] - 1)] + [1]))

        print("ITER {i}: \nU:\n{U} \nV:\n{V} \nQ:\n{Q}".format(
            i=i + 1, U=U, V=V, Q=Q))

    return Q, U, V, p, q


def main():
    if RANDOM:
        matrix = generate_matrix_for_input(d=4)
        print(matrix)
    else:
        with open(FILE_PATH, 'rt') as f:
            matrix = np.matrix([
                list(map(float, line.split()))
                for line in f.readlines()
            ])
    print("INPUT MATRIX: {}\n".format(matrix))
    Q, U, V, p, q = DDM_DYN(matrix)
    print("ANSWER: \nQ:\n {Q} \nU:\n {U} \nV:\n {V} \np:\n {p} \nq:\n {q}".format(
        Q=Q, U=U, V=V, p=p, q=q))


if __name__ == "__main__":
    main()