import numpy as np
from collections import Counter

def find_best_split(feature_vector, target_vector):
    """
    Под критерием Джини здесь подразумевается следующая функция:
    $$Q(R) = -\frac {|R_l|}{|R|}H(R_l) -\frac {|R_r|}{|R|}H(R_r)$$,
    $R$ — множество объектов, $R_l$ и $R_r$ — объекты, попавшие в левое и правое поддерево,
     $H(R) = 1-p_1^2-p_0^2$, $p_1$, $p_0$ — доля объектов класса 1 и 0 соответственно.
    Указания:
    * Пороги, приводящие к попаданию в одно из поддеревьев пустого множества объектов, не рассматриваются.
    * В качестве порогов, нужно брать среднее двух соседних (при сортировке) значений признака
    * Поведение функции в случае константного признака может быть любым.
    * При одинаковых приростах Джини нужно выбирать минимальный сплит.
    * За наличие в функции циклов балл будет снижен. Векторизуйте! :)
    :param feature_vector: вещественнозначный вектор значений признака
    :param target_vector: вектор классов объектов,  len(feature_vector) == len(target_vector)
    :return thresholds: отсортированный по возрастанию вектор со всеми возможными порогами, по которым объекты можно
     разделить на две различные подвыборки, или поддерева
    :return ginis: вектор со значениями критерия Джини для каждого из порогов в thresholds len(ginis) == len(thresholds)
    :return threshold_best: оптимальный порог (число)
    :return gini_best: оптимальное значение критерия Джини (число)
    """
    # ╰( ͡° ͜ʖ ͡° )つ──☆*:・ﾟ

#    df = pd.DataFrame({
#        "feature": pd.Series(feature_vector),
#        "target": pd.Series(target_vector)
#    })
#    df = df.sort_values('feature')

    feature = np.sort(feature_vector)
    target = target_vector[feature_vector.argsort()]

#    print(feature)
#    print(target)

    feature_values, indices = np.unique(feature, return_index=True)
#    feature = np.array(df['feature'])
#    target = np.array(df['target'])

    indices = indices[1:]
#    print(indices)

    if len(indices) == 0:
        return 'All feature values are equal'

    threshold = (feature_values[:-1] + feature_values[1:]) / 2

    R = len(feature)
    Rl = indices
    n1l = np.array(np.cumsum(target)[indices - 1])
    p1l = n1l / Rl
    p0l = 1 - p1l
    Hl = 1 - p1l ** 2 - p0l ** 2

    Rr = R - Rl
    n1r = np.array(np.sum(target) - n1l)
    p1r = n1r / Rr
    p0r = 1 - p1r
    Hr = 1 - p1r ** 2 - p0r ** 2

    gini = -(Rl * Hl + Rr * Hr) / R
    max_index = np.argmax(gini)
    edge = threshold[max_index]

    return threshold, gini, edge, np.max(gini)