def p_y_x_knn(y, k):
    """
    Funkcja wyznacza rozklad prawdopodobienstwa p(y|x) dla
    kazdej z klas dla obiektow ze zbioru testowego wykorzystujac
    klasfikator KNN wyuczony na danych trenningowych
    :param y: macierz posortowanych etykiet dla danych treningowych N1xN2
    :param k: liczba najblizszuch sasiadow dla KNN
    :return: macierz prawdopodobienstw dla obiektow z X
    """
    points_number = 4
    result_matrix = []
    for i in range(np.shape(y)[0]):
        helper = []
        for j in range(k):
            helper.append(y[i][j])
        line = np.bincount(helper, None, points_number)
        result_matrix.append([line[0] / k, line[1] / k, line[2] / k, line[3] / k])
    return result_matrix


def classification_error(p_y_x, y_true):
    """
    Wyznacz blad klasyfikacji.
    :param p_y_x: macierz przewidywanych prawdopodobienstw
    :param y_true: zbior rzeczywistych etykiet klas 1xN.
    Kazdy wiersz macierzy reprezentuje rozklad p(y|x)
    :return: blad klasyfikacji
    """

    points_number = 4
    errors_number = 0
    n_val = np.shape(y_true)[0]
    for i in range(0, n_val):
        reverse = (p_y_x[i])[::-1]
        index = points_number - np.argmax(reverse) - 1
        if index != y_true[i]:
            errors_number += 1
    return errors_number / n_val


def model_selection_knn(Xval, Xtrain, yval, ytrain, k_values):
    """
    :param Xval: zbior danych walidacyjnych N1xD
    :param Xtrain: zbior danych treningowych N2xD
    :param yval: etykiety klas dla danych walidacyjnych 1xN1
    :param ytrain: etykiety klas dla danych treningowych 1xN2
    :param k_values: wartosci parametru k, ktore maja zostac sprawdzone
    :return: funkcja wykonuje selekcje modelu knn i zwraca krotke (best_error,best_k,errors), gdzie best_error to najnizszy
    osiagniety blad, best_k - k dla ktorego blad byl najnizszy, errors - lista wartosci bledow dla kolejnych k z k_values
    """

    errors = np.zeros(len(k_values))
    distancesSorted = sort_train_labels_knn(hamming_distance(Xval, Xtrain), ytrain)
    for i in range(len(errors)):
        errors[i] = classification_error(p_y_x_knn(distancesSorted, k_values[i]), yval)
    best_index = 0
    for i in range(len(k_values)):
        if errors[i] < errors[best_index]:
            best_index = i
    return min(errors), k_values[best_index], errors


def estimate_a_priori_nb(ytrain):
    """
    :param ytrain: etykiety dla dla danych treningowych 1xN
    :return: funkcja wyznacza rozklad a priori p(y) i zwraca p_y - wektor prawdopodobienstw a priori 1xM
    """
    vector = np.bincount(ytrain)
    vector = vector / (np.shape(ytrain)[0])
    return vector


def estimate_p_x_y_nb(Xtrain, ytrain, a, b):
    """
    n = 50, d = 20 k = 4
    :param Xtrain: dane treningowe NxD
    :param ytrain: etykiety klas dla danych treningowych 1xN
    :param a: parametr a rozkladu Beta
    :param b: parametr b rozkladu Beta
    :return: funkcja wyznacza rozklad prawdopodobienstwa p(x|y) zakladajac, ze x przyjmuje wartosci binarne i ze elementy
    x sa niezalezne od siebie. Funkcja zwraca macierz p_x_y o wymiarach MxD.
    """
    points_number = 4
    result_matrix = []
    vector = np.bincount(ytrain)
    denominator = (vector + a + b - 2)

    def numerator(Xtrain, ytrain, d):
        Xtrain = Xtrain.toarray()
        occurences = [0, 0, 0, 0]
        for i in range(np.shape(ytrain)[0]):
            if Xtrain[i][d] == 1:
                occurences[ytrain[i]] += 1
        occurences_add = [(x + (a - 1)) for x in occurences]
        return np.squeeze(occurences_add)

    for k in range(points_number):
        line = []
        for d in range(np.shape(Xtrain)[1]):
            line.append((numerator(Xtrain, ytrain, d)[k]) / denominator[k])
        result_matrix.append(line)

    return np.array(result_matrix)


def p_y_x_nb(p_y, p_x_1_y, X):
    """
    N = 40, M = 4, D = 20
    return 40 x 4
    :param p_y: wektor prawdopodobienstw a priori o wymiarach 1xM
    :param p_x_1_y: rozklad prawdopodobienstw p(x=1|y) - macierz MxD
    :param X: dane dla ktorych beda wyznaczone prawdopodobienstwa, macierz NxD
    :return: funkcja wyznacza rozklad prawdopodobienstwa p(y|x) dla kazdej z klas z wykorzystaniem klasyfikatora Naiwnego
    Bayesa. Funkcja zwraca macierz p_y_x o wymiarach NxM.
    """

    X = X.toarray()

    def helper(line):
        result = X * line
        result += np.logical_not(X) - np.logical_not(X) * line
        result = np.apply_along_axis(np.prod, arr=result, axis=1)
        return result

    def helper2(line, x):
        result = np.multiply(line, x)
        return result

    def helper3(line):
        result = 1 / np.sum(line)
        return np.multiply(line, result)

    result_matrix = np.apply_along_axis(helper, axis=0, arr=np.transpose(p_x_1_y))
    result_matrix = np.apply_along_axis(helper2, axis=1, arr=result_matrix, x=p_y)
    result_matrix = np.apply_along_axis(helper3, axis=1, arr=result_matrix)

    return result_matrix


def model_selection_nb(Xtrain, Xval, ytrain, yval, a_values, b_values):
    """
    :param Xtrain: zbior danych treningowych N2xD
    :param Xval: zbior danych walidacyjnych N1xD
    :param ytrain: etykiety klas dla danych treningowych 1xN2
    :param yval: etykiety klas dla danych walidacyjnych 1xN1
    :param a_values: lista parametrow a do sprawdzenia
    :param b_values: lista parametrow b do sprawdzenia
    :return: funkcja wykonuje selekcje modelu Naive Bayes - wybiera najlepsze wartosci parametrow a i b. Funkcja zwraca
    krotke (error_best, best_a, best_b, errors) gdzie best_error to najnizszy
    osiagniety blad, best_a - a dla ktorego blad byl najnizszy, best_b - b dla ktorego blad byl najnizszy,
    errors - macierz wartosci bledow dla wszystkich par (a,b)
    """
    errors = np.zeros((len(a_values), len(b_values)))
    p_y = estimate_a_priori_nb(ytrain)
    for i in range(len(a_values)):
        for j in range(len(b_values)):
            p_x_y = estimate_p_x_y_nb(Xtrain, ytrain, a_values[i], b_values[j])
            errors[i, j] = classification_error(p_y_x_nb(p_y, p_x_y, Xval), yval)

    error_best = errors[0, 0]
    best_a = a_values[0]
    best_b = b_values[0]
    for i in range(len(errors)):
        for j in range(len(errors[i])):
            if errors[i, j] < error_best:
                error_best = errors[i, j]
                best_a = a_values[i]
                best_b = b_values[j]

    return error_best, best_a, best_b, errors