import java.util.HashMap;
import java.util.Map;
import java.util.LinkedList;
import java.util.Set;
import java.util.List;
import java.util.HashSet;


/**
 * Diese Klasse implementiert einen Entscheidungsbaum für die Klassifikation basierend auf gegebenen Datenpunkten.
 * Sie nutzt Methoden zum Aufteilen von Daten, Berechnen von Fehlern, Informationsgewinn und zur Bestimmung des besten Attributs,
 * um den Baum aufzubauen und Vorhersagen zu treffen.
 * 
 * @author Benedikt Lindemann
 */
public class ENTSCHEIDUNGSBAUM {

    private String attribut;
    private Map<String, ENTSCHEIDUNGSBAUM> kinder;
    private Set<String> attributeNochNichtVerwendet;
    private String label;

    /**
     * Konstruktor zum Initialisieren eines neuen Entscheidungsbaumknotens. Handelt es sich um 
     * ein Blatt, so koennen auch beide Uebergabeparameter mit null uebergeben werden.
     * Allerdings sollte dann im Anschluss das Attribut label gesetzt werden.
     * 
     * @param attribut Das Attribut, nach dem in diesem Knoten aufgeteilt wird.
     * @param attributeNochNichtVerwendet Die Menge von Attributen, die noch nicht verwendet wurden.
     */
    private ENTSCHEIDUNGSBAUM(String attribut, Set<String> attributeNochNichtVerwendet) {
        this.attribut = attribut;
        this.attributeNochNichtVerwendet = attributeNochNichtVerwendet;
        this.kinder = new HashMap<String, ENTSCHEIDUNGSBAUM>();
    }

    /**
     * Setzt das Label für den Knoten, das verwendet wird, wenn dieser Knoten ein Blatt ist.
     * @param label Das zu setzende Label.
     */
    public void setzeLabel(String label) {
        this.label = label;
    }

    /**
     * Fügt ein Kind zum aktuellen Knoten hinzu.
     * @param merkmalsWert Der Wert des Merkmals, bei dem dieses Kind hinzugefügt wird.
     * @param kind Das Kind-Entscheidungsbaum-Objekt.
     */
    public void addKind(String merkmalsWert, ENTSCHEIDUNGSBAUM kind) {
        this.kinder.put(merkmalsWert, kind);
    }

    /**
     * Teilt die gegebenen Daten nach dem angegebenen Attribut auf.
     * @param daten Die Liste von Daten, die aufgeteilt werden sollen.
     * @param attribut Das Attribut, nach dem aufgeteilt wird.
     * @return Eine HashMap von Datenlisten, aufgeteilt nach dem Wert des Attributs.
     */
    private static Map<String, LinkedList<GELABELTEDATEN>> splitDataByAttribut(List<GELABELTEDATEN> daten, String attribut) {
        Map<String, LinkedList<GELABELTEDATEN>> splitData = new HashMap<String, LinkedList<GELABELTEDATEN>>();
        for (GELABELTEDATEN point : daten) {
            String attributWert = point.nenneAttribute().get(attribut);
            
            if(attributWert != null) {
                if (!splitData.containsKey(attributWert)) {
                    splitData.put(attributWert, new LinkedList<GELABELTEDATEN>());
                }
                splitData.get(attributWert).add(point);
            }
        }
        return splitData;
    }

    /**
     * Berechnet den Fehler für eine Liste von Daten, indem die am häufigsten vorkommende Label-Klasse ermittelt wird.
     * @param daten Die Datenliste, für die der Fehler berechnet werden soll.
     * @return Die Anzahl der falsch klassifizierten Elemente, basierend auf dem häufigsten Label.
     */
    private static int berechneFehler(List<GELABELTEDATEN> daten) {
        Map<String, Integer> labelCount = new HashMap<String, Integer>();
        for (GELABELTEDATEN point : daten) {
            if (!labelCount.containsKey(point.nenneLabel())) {
                labelCount.put(point.nenneLabel(), 1);
            } else {
                labelCount.put(point.nenneLabel(), labelCount.get(point.nenneLabel())+1);
            }
        }
        int max = Integer.MIN_VALUE;
        int sum = 0;
        for (Integer i : labelCount.values()) {
            max = Integer.max(max, i);
            sum = sum + i;
        }
        return sum - max;
    }

    /**
     * Bestimmt das Label für eine Liste von Daten basierend auf der Mehrheitsregel.
     * @param daten Die Daten, für die das Label bestimmt werden soll.
     * @return Das am häufigsten vorkommende Label in der Datenliste.
     */
    private static String berechneLabel(List<GELABELTEDATEN> daten) {
        Map<String, Integer> labelCount = new HashMap<String, Integer>();
        for (GELABELTEDATEN point : daten) {
            if (!labelCount.containsKey(point.nenneLabel())) {
                labelCount.put(point.nenneLabel(), 1);
            } else {
                labelCount.put(point.nenneLabel(), labelCount.get(point.nenneLabel())+1);
            }
        }
        int max = Integer.MIN_VALUE;
        String label = "";
        for (String s : labelCount.keySet()) {
            int actCount = labelCount.get(s);
            if (max < actCount) {
                max = actCount;
                label = s;
            }
        }
        return label;
    }

    /**
     * Wählt das Attribut mit dem höchsten Informationsgewinn aus.
     * @param informationsGewinn Eine HashMap von Attributen und deren assoziierten Informationsgewinnen.
     * @return Das Attribut mit dem höchsten Informationsgewinn.
     */
    private static String bestesAttribut(Map<String, Integer> informationsGewinn) {
        String bestesAttribut = "";
        int maxInformationsGewinn = Integer.MIN_VALUE;
        for (String att : informationsGewinn.keySet()) {
            if (informationsGewinn.get(att) > maxInformationsGewinn) {
                maxInformationsGewinn = informationsGewinn.get(att);
                bestesAttribut = att;
            }
        }
        return bestesAttribut;
    }

    /**
     * Ermittelt den maximalen Informationsgewinn aus einer Karte von Informationsgewinnen.
     * @param informationsGewinn Eine Karte von Attributen und deren assoziierten Informationsgewinnen.
     * @return Der höchste Informationsgewinn.
     */
    private static int maxInformationsGewinn(Map<String, Integer> informationsGewinn) {
        int maxInformationsGewinn = Integer.MIN_VALUE;
        for (String att : informationsGewinn.keySet()) {
            if (informationsGewinn.get(att) > maxInformationsGewinn) {
                maxInformationsGewinn = informationsGewinn.get(att);
            }
        }
        return maxInformationsGewinn;
    }

    /**
     * Erzeugt einen Entscheidungsbaum basierend auf einer Liste von Datenpunkten, gegebenen Attributen, 
     * einem Pfad der zu diesem Entscheidungsbaumknoten geführt hat, dem Wert der Aufteilung, einer 
     * maximalen Tiefe und der aktuellen Tiefe. Diese Methode wird rekursiv aufgerufen und erstellt 
     * den Baum durch Minimierung des Fehlers.
     *
     * @param daten Die Liste der Datenpunkte, die für die Baumgenerierung verwendet werden.
     * @param attribute Die Menge von Attributen, die noch bisher noch nicht zur Entscheidungsfindung verwendet wurden.
     * @param baumpfad Der aktuelle Pfad im Baum, repräsentiert durch die Namen der Attribute, die bereits verwendet wurden.
     * @param aufteilungsWert Der Wert des Attributs, bei dem die aktuelle Aufteilung erfolgt.
     * @param maxTiefe Die maximale Tiefe des Baumes.
     * @param aktTiefe Die aktuelle Tiefe im Baum.
     * @return Ein Objekt des Entscheidungsbaums, das an diesem Knoten erstellt wurde.
     */
    private static ENTSCHEIDUNGSBAUM erzeugeBaum(LinkedList<GELABELTEDATEN> daten, Set<String> attribute, String baumpfad, String aufteilungsWert, int maxTiefe, int aktTiefe) {
        int altFehler = berechneFehler(daten);
        if (baumpfad != null && baumpfad.length() > 0 && aufteilungsWert != null && aufteilungsWert.length() > 0) {
            System.out.println("Bisherige Aufteilung: "+baumpfad);
            System.out.println("Attributwert dieser Aufteilung: "+aufteilungsWert);
        }
        System.out.println("Fehler ohne Aufteilung: "+altFehler);
        System.out.println("Zu testende Attribute: "+attribute.toString());
        System.out.println("----------------------------------------------------------");
        Map<String, Integer> informationsGewinn = new HashMap<String, Integer>();
        Map<String, Integer> fehlerMap = new HashMap<String, Integer>();
        for (String att : attribute) {
            Map<String, LinkedList<GELABELTEDATEN>> aufgeteilteListen = splitDataByAttribut(daten, att);
            System.out.println("Teile die Liste auf nach dem Attribut: "+att);
            int fehler = 0;
            for (String attributWert : aufgeteilteListen.keySet()) {
                int teilFehler = berechneFehler(aufgeteilteListen.get(attributWert));
                fehler = fehler + teilFehler;
                System.out.println("Fehler beim Wert "+attributWert+" = "+teilFehler);    
            }
            System.out.println("Insgesamter Fehler für das Attribut: "+att+" = "+fehler);
            System.out.println("Informationsgewinn für das Attribut: "+att+" = "+(altFehler-fehler));
            System.out.println("----------------------------------------------------------");
            informationsGewinn.put(att, altFehler-fehler);
            fehlerMap.put(att, fehler);
        }
        String bestesAttribut = bestesAttribut(informationsGewinn); 
        int maxInfGew = maxInformationsGewinn(informationsGewinn);
        if (maxInfGew > 0) {
            System.out.println("=> bestes Attribut: "+bestesAttribut);   
        } else {
            System.out.println("=> keine Aufteilung verbessert die Genauigkeit...");
        }
        System.out.println("----------------------------------------------------------");
        attribute.remove(bestesAttribut);
        ENTSCHEIDUNGSBAUM neu = new ENTSCHEIDUNGSBAUM(bestesAttribut, attribute);
        Map<String, LinkedList<GELABELTEDATEN>> aufgeteilteListen = splitDataByAttribut(daten, bestesAttribut);
        for (String attributWert : aufgeteilteListen.keySet()) {
            if (fehlerMap.get(bestesAttribut) == 0 || aktTiefe+1 >= maxTiefe || attribute.isEmpty() || berechneFehler(aufgeteilteListen.get(attributWert)) == 0) {
                ENTSCHEIDUNGSBAUM blatt = new ENTSCHEIDUNGSBAUM(null, null);
                blatt.setzeLabel(berechneLabel(aufgeteilteListen.get(attributWert)));
                neu.addKind(attributWert, blatt);
            } else if (maxInfGew <= 0) {
                neu.setzeLabel(berechneLabel(daten));
                return neu;
            } else {
                Set<String> attributeClone = new HashSet<String>(attribute);
                neu.addKind(attributWert, erzeugeBaum(aufgeteilteListen.get(attributWert), attributeClone, baumpfad+" -> "+bestesAttribut, attributWert, maxTiefe, aktTiefe+1));
            }
        }
        return neu;
    }

    /**
     * Generiert einen Entscheidungsbaum aus einer gegebenen Liste von Datenpunkten.
     * Diese Methode ist ein Einstiegspunkt zur Erzeugung des Baumes, der die Attribute automatisch aus den Daten extrahiert.
     *
     * @param daten Die Liste von Datenpunkten, die zum Aufbau des Entscheidungsbaums verwendet werden.
     * @return Ein vollständig aufgebauter Entscheidungsbaum.
     */
    public static ENTSCHEIDUNGSBAUM erzeugeBaum(LinkedList<GELABELTEDATEN> daten) {
        GELABELTEDATEN buffer = daten.get(0);
        Set<String> attribute = buffer.nenneAttribute().keySet();
        return erzeugeBaum(daten, attribute, "", "", 3, 0);
    }

    // /**
     // * Erzeugt einen Entscheidungsbaum zu dem grossen Datensatz aus der Fisch-Datenbank
     // *
     // * @return Der passende Entscheidungsbaum
     // */
    // public static ENTSCHEIDUNGSBAUM erzeugeFischGrosserDatensatzBaum() {
        // return erzeugeBaum(Connect.getFischeGrosserDatensatz(1000,0));
    // }
    
    // /**
     // * Erzeugt einen Entscheidungsbaum zu dem kleinen Datensatz aus der Fisch-Datenbank
     // *
     // * @return Der passende Entscheidungsbaum
     // */
    // public static ENTSCHEIDUNGSBAUM erzeugeFischKleinerDatensatzBaum() {
        // return erzeugeBaum(Connect.getFischeKleinerDatensatz(9,0));
    // }

    /**
     * Erzeugt einen Entscheidungsbaum zu dem kleinen Datensatz aus der Fisch-Datenbank
     *
     * @return Der passende Entscheidungsbaum
     */
    public static ENTSCHEIDUNGSBAUM erzeugeIrisDatensatzBaum() {
        ENTSCHEIDUNGSBAUM e = erzeugeBaum(Connect.getIrisDatensatz(100,0));
        e.testeDatensatzBaum(Connect.getIrisDatensatz(50,100),"Blume");
        return e;
    }
    
    /**
     * Klassifiziert einen gegebenen Datenpunkt basierend auf dem Entscheidungsbaum.
     * Die Methode durchläuft den Baum basierend auf den Attributen des Datenpunkts und gibt das finale Label zurück.
     *
     * @param point Der Datenpunkt, der klassifiziert werden soll.
     * @return Das Label, das dem Datenpunkt basierend auf dem Entscheidungsbaum zugeordnet wird.
     */
    public String klassifiziere(GELABELTEDATEN point) {
        if (this.label != null && this.label.length() > 0) {
            return this.label;
        } else if (this.attribut != null && this.attribut.length() > 0) {
            if (this.kinder.get(point.nenneAttribute().get(this.attribut)) != null) {
                return this.kinder.get(point.nenneAttribute().get(this.attribut)).klassifiziere(point); 
            } else {
                return "Für diesen Datenpunkt wurde kein passender Pfad gefunden...";
            }
        } else {
          return "";  
        }
    }
    
    /**
     * Testet den Entscheidungsbaum mit einer gegebenen Liste von Datenpunkten und druckt die Ergebnisse aus.
     * Diese Methode ist hilfreich, um die Genauigkeit und Effektivität des Entscheidungsbaums zu evaluieren.
     *
     * @param daten Die Liste von Datenpunkten, die für den Test verwendet werden.
     */
    public void testeDatensatzBaum(LinkedList<GELABELTEDATEN> daten, String object) {
        System.out.println("####################");
        System.out.println("#  Test des Baums  #");
        System.out.println("####################");
        int fehlerCount = 0;
        for (GELABELTEDATEN fisch : daten) {
            System.out.print(object+": ");
            for (String key : fisch.nenneAttribute().keySet()) {
                System.out.print(fisch.nenneAttribute().get(key)+" ");
            }
            String fischLabel = fisch.nenneLabel();
            String baumLabel = this.klassifiziere(fisch);
            System.out.println("\ntatsaechliches Label      : " + fischLabel);
            String fehler = "";
            if (!fischLabel.equals(baumLabel)) {
                 fehler = "   ###Fehler###";
                 fehlerCount++;
            }
            System.out.println("vom Baum berechnetes Label: " + baumLabel+fehler);   
            System.out.println();
        }
        System.out.println("##############################################################################");
        System.out.println("Ergebnis: "+fehlerCount+" von "+daten.size()+" Datensaetze wurden fehlerhaft zugeordnet.");
        System.out.println("##############################################################################");
    }
    
    // /**
     // * Erzeugt und testet einen Entscheidungsbaum mit einem kleineren Datensatz von Fischen.
     // * Diese Methode ist speziell für die Demonstration und das Testen des Entscheidungsbaums mit einer kleineren Datenmenge gedacht.
     // */
    // public static void testeFischKleinerDatensatzBaum() {
        // ENTSCHEIDUNGSBAUM e = erzeugeBaum(Connect.getFischeKleinerDatensatz(9,0));
        // e.testeDatensatzBaum(Connect.getFischeKleinerDatensatz(5,9));
    // }
    
    // /**
     // * Erzeugt und testet einen Entscheidungsbaum mit einem größeren Datensatz von Fischen.
     // * Diese Methode ist für umfangreichere Tests und Demonstrationen mit einem großen Datensatz gedacht.
     // */
    // public static void testeFischGrosserDatensatzBaum() {
        // ENTSCHEIDUNGSBAUM e = erzeugeBaum(Connect.getFischeGrosserDatensatz(1000,0));
        // e.testeDatensatzBaum(Connect.getFischeGrosserDatensatz(1000,1000));
    // }
}
