import csv
from math import log
from graphviz import Digraph

class Noeud:
    def __init__(self, valeur: str, enfants = None):
        self.valeur = valeur
        self.enfants = enfants # de type dictionnaire Python

class ArbreDecision:

    def __init__(self, data: list[dict[str]]):
        self.exemples = data
        self.titres = ... # titres des colonnes de données = clefs de chaque dictionnaire dans le tableau d'exemples
        self.etiquette = ... # la décision à prendre = le dernier titre
        self.attributs = ... # tableau des attributs = les titres, sauf l'étiquette

        #self.arbre = ... # affecté lors de la création de l'arbre

    def valeurs_possibles(self, exemples: list[dict[str]], titre: str)->list[str]:
        """
        Détermine les valeurs possibles dans une colonne de titre donné dans un ensemble d'exemples.
        """
        pass

    def sous_ensemble(self, exemples: list[dict[str]], attribut: str, valeur: str)->list[dict[str]]:
        """
        Renvoie un sous-ensemble d'exemples pour lesquels un attribut donné a une certaine valeur.
        """
        pass

    def classe_la_plus_frequente(self, exemples: list[dict[str]])->str:
        """
        Renvoi le nom de la classe la plus fréquente dans un ensemble d'exemples.
        """
        pass

    def entropie(self, ensemble: list[dict[str]])->float:
        """
        Calcul et renvoie l'entropie de Shannon d'un ensemble
        """
        ent = 0
        N = len(ensemble) # effectif de l'ensemble
        for classe in self.valeurs_possibles(ensemble, self.etiquette): # pour chaque classe de résultats
            N_i = 0 # effectif de la classe
            for dico in ensemble:
                if dico[self.etiquette] == classe:
                    N_i += 1
            p_i = N_i/N # probabilité de cette classe dans l'ensemble ( assimilée à sa proportion )
            ent += -p_i*log(p_i, 2) if p_i != 0 else 0 # on ajoute -p_i * log_2(p_i) à l'entropie
        return ent

    def gain_info(self, ensemble:list[dict[str]], attribut: str)->float:
        """
        retourne le gain d'information apporté par un attribut donné
        """
        somme = 0
        #pour chaque valeur de l'attribut en question
        for valeur in self.valeurs_possibles(ensemble, attribut):
            sous_ensemble = self.sous_ensemble(ensemble, attribut, valeur) # le sous-ensemble pour une valeur donnée de l'attribut
            # somme = somme sur v de p_v * H(v)
            somme += len(sous_ensemble) * self.entropie(sous_ensemble)
        #Gain(ensemble, attribut) = H(ensemble) - somme/N
        return self.entropie(ensemble) - somme/len(ensemble)

    def meilleur_attribut(self, ensemble: list[dict[str]], liste_attributs)->str:
        """
        Dans une liste d'attributs, recherche l'attribut apportant le meilleur gain d'information pour un ensemble d'exemples.
        """
        pass

    def creer_arbre(self, exemples: list[dict[str]], liste_attributs: list[str])->Noeud:
        # si tous les exemples appartiennent à la même classe
        # on a trouvé un ensemble homogène, on créé alors une feuille.
        if ... :
            # on détermine la classe (unique) à laquelle appartiennent alors les exemples,
            classe = ...

            # et on crée une feuille avec comme valeur la classe en question
            return ...

        # s'il ne reste plus d'attribut à tester,
        # on crée une feuille correspondant à la classe la plus fréquente
        # dans l'ensemble d'exemples restant.
        if len(liste_attributs) == 0:
            return ...

        # détermination du meilleur attribut, et création du nœud associé
        attribut_optimal = ...


        # si il n'y a pas d'attribut optimal ( ils se valent tous ! ),
        # alors on crée une feuille ayant comme valeur la classe la plus fréquente
        if attribut_optimal == '':
            return ...

        # sinon, on crée le noeud associé à cet attribut optimal,
        # et on supprime celui-ci de la liste des attributs à étudier par la suite
        noeud = ...
        liste_attributs.remove(attribut_optimal)

        # création des nouveaux nœuds correspondant au partage de l'ensemble d'exemples actuel :
        for valeur in ... : # pour chaque valeur possible de l'attribut optimal,
            s =  ... # on crée le sous-ensemble d'exemples correspondant à la valeur de cet attribut,
            noeud.enfants[valeur] = ... # et on crée récursivement les nœuds enfants

        return noeud

    def affiche(self, noeud, niveau = 0):
        pass

    def _dessine_arbre(self, dot, noeud, parent = None): # méthode PRIVÉE
        if noeud.enfants is not None: # le noeud n'est pas une feuille
            parent = noeud.valeur
            for valeur in noeud.enfants:
                enfant = noeud.enfants[valeur]
                if enfant.enfants is None: # le nœud est une feuille
                    e = dot.node(enfant.valeur, shape = 'box')
                    dot.edge(parent, enfant.valeur, label = valeur)
                else:
                    dot.edge(parent, enfant.valeur, label = valeur)
                self._dessine_arbre(dot, enfant, parent)
        return dot

    def dessine_arbre(self): # méthode PUBLIQUE
        d = Digraph()
        d = self._dessine_arbre(d, self.arbre) # 'self.arbre' est l'attribut de la classe stockant la structure de l'arbre : à adapter au besoin
        d.view()

    def etiqueter(self, exemple:dict[str])->str:
        """
        Renvoie la classe à laquelle appartient l'exemple.
        """
        pass



with open("nom_de_fichier.csv", 'r') as file:
    data = []
    reader = csv.DictReader(file)
    for row in reader:
        data.append(row) # tableau des dictionnaires de données