// Graphikkram
import java.awt.*;

public class baum
{
    // leerer rs-Baum
    public baum()
    {
        // keine Wurzel -> Baum ist leer
        wurzel = null;
    }

    // Wurzel
    private knoten wurzel;

    // Baum leer machen indem die Wurzel dereferenziert wird
    public void loescheBaum()
    {
        gui.aktionen=" loescheBaum ";
        wurzel = null;
    }

    //              _   _  _         _     
    //   ____  _ __| |_(_)(_)_ _  __| |___ 
    //  |_ / || (_-<  _/ _` | ' \/ _` / -_)
    //  /__|\_,_/__/\__\__,_|_||_\__,_\___|

    // Variablen um einen Zustand im Baum zu repräsentieren und darauf
    // aufbauend die entsprechende Behandlung festzulegen


    // Knoten konnte nicht eingefügt werden 
    private static final int knotenEinfuegeFehler = 0;

    // wurzel nicht verändert
    // Rot-Schwarz Kriterium erfüllt
    private static final int wurzel_sr = 1;

    // Großvater ist rot
    // Modifikation eventuell nötig
    private static final int opaRot = 2;

    // Großvater *und* rechtes Kind sind rot
    // rotieren oder umfarben nötig
    private static final int rechtsRot = 3;


    // Wurzel und Onkel sind rot, farbtausch oder Rotation nötig
    private static final int onkelIstRot = 4;

    // Knoten kommt doppelt vor, keinen neuen Knoten rein sondern Wert
    // in Dublette ändern
    private static final int doppelterKnoten = 5;

    // Variable hält status 
    private int status;


    // Status festlegen
    public void setzeStatus(int status)
    {
        this.status = status;
    }//setzeStatus



    //      _       __ _  _               
    //  ___(_)_ _  / _(_)(_)__ _ ___ _ _  
    // / -_) | ' \|  _| || / _` / -_) ' \ 
    // \___|_|_||_|_|  \_,_\__, \___|_||_|
    //                     |___/          
    // 
    // neuen Knoten einfügen, bei leerem Baum als Wurzel allozieren
    public int knotenEinfuegen(int wert)
    {
    gui.aktionen+=" baum.knotenEinfuegen ";
        if ( wurzel == null)
        {
            try
            {
            // wurzel rein
                wurzel = new knoten(wert);
                // schwärzen
                wurzel.einfaerben(Color.black);
                return 1;
            }
                // Speicher alle
            catch (OutOfMemoryError e)
            {
                System.err.println("Speicher voll. Kauf mehr RAM!");
                return 0;
            }
        }

        // Wurzell rekursiv einfügen
        wurzel = rekursivEinfuegen(wurzel, wert);
        switch (status)
        {
        case knotenEinfuegeFehler:
            return 0;
        case opaRot:
            // wurzel ist per definitionem schwarz
            wurzel.einfaerben(Color.black);
            break;

        // Baum iO
        case doppelterKnoten:
            gui.aktionen+=" doppelter Knoten ";
        case wurzel_sr:
        default:
            break;
        }

        return 1;
    }


    // Knotenposition rekursiv finden 
    private knoten rekursivEinfuegen(knoten jetziger, int wert)
    {
        int wertVergleich;
        wertVergleich = jetziger.vergleiche(wert);

        if (wertVergleich == 0)
        {
            // Wert schon vorhanden, kein Einfügen oder ändern
            setzeStatus(doppelterKnoten);
            return jetziger;
        }

        // neuer Wert ist kleiner
        // daher als linkes Kind einfügen
        if (wertVergleich < 0)
        {
            // kein linkes Kind, neues anhängen
            if ( jetziger.linkesKind == null )
            {
                jetziger.linkesKind = new knoten(wert);
                setzeStatus(opaRot);
                return linkerTeilbaum(jetziger);
            }
            // in Rekursion absteigen
            else
            {
                jetziger.linkesKind = rekursivEinfuegen(jetziger.linkesKind, wert);
                return linkerTeilbaum(jetziger);
            }
        }
        // Wert ist größer, rechts anhängen
        else
        {
            // kein rechtes Kind, neues anhängen
            if ( jetziger.rechtesKind == null )
            {
                jetziger.rechtesKind = new knoten(wert);
                setzeStatus(opaRot);
                return rechterTeilbaum(jetziger);
            }
            // rechtes Kind da -> in rekursion absteigen
            else
            {
                jetziger.rechtesKind = rekursivEinfuegen(jetziger.rechtesKind, wert);
                return rechterTeilbaum(jetziger);
            }
        }// else rechtes kind
    }//if (wertvergleich )




    // es wurde links eingefügt, linken TB beachten
    private knoten linkerTeilbaum(knoten jetziger)
    {
        // Zustand des linken Teilbaumes
        switch (status)
        {
        case opaRot:
            if (jetziger.holeFarbe() == Color.red)
            {
                // jetziger Knoten und dessen linkes Kind sind rot 
                setzeStatus(onkelIstRot);
                return jetziger;
            }
            else
            {  // jetziger Knoten ist schwarz und linkes Kind rot, gut
                setzeStatus(wurzel_sr);
                return jetziger;
            }

        case onkelIstRot:
            if (jetziger.rechtesKind == null ||
                    jetziger.rechtesKind.holeFarbe() == Color.black)
            {
                // rechtes kind schwarz, linkes rot -> rechts rotieren
                return rechtsRotieren(jetziger);
            }
            else
            {
                // beide Kinder rot -> umfärben
                return umfaerben(jetziger);
            }

        case rechtsRot:
            if (jetziger.rechtesKind == null ||
                    jetziger.rechtesKind.holeFarbe() == Color.black)
            {

                // rechtes kind schwarz, linkes rot -> doppelt rechts rotieren             
                return doppelRechtsRotation(jetziger);
            }
            else
            {
                // beide Kinder rot -> umfärben
                return umfaerben(jetziger);
            }

        // Baum iO
        case wurzel_sr:
        // Baum iO
        case doppelterKnoten:

        default:
            break;
        }

        return jetziger;

    }

    // im rechten Teilbaum eingefügt
    private knoten rechterTeilbaum(knoten jetziger)
    {
        // Zustand des rechten TB
        switch (status)
        {
        case opaRot:
            if (jetziger.holeFarbe() == Color.red)
            {
                // jetziger Knoten und  rechtes Kind rot
                setzeStatus(rechtsRot);
                return jetziger;
            }
            else
            {
                // jetziger Knoten ist schwarz
                setzeStatus(wurzel_sr);
                return jetziger;
            }

        case onkelIstRot:
            if (jetziger.linkesKind == null ||
                    jetziger.linkesKind.holeFarbe() == Color.black)
            {
                // linkes Kind schwarz, rechtes rot
                return doppelLinksRotation(jetziger);
            }
            else
            {
                // beide Kinder rot
                return umfaerben(jetziger);
            }

        case rechtsRot:
            if (jetziger.linkesKind == null ||
                    jetziger.linkesKind.holeFarbe() == Color.black)
            {
                // linkes Kind schwarz, rechts rot
                return linksRotiere(jetziger);
            }
            else
            {
                // beide rot
                return umfaerben(jetziger);
            }

        //Baum iO
        case wurzel_sr:
        // Baum iO
        case doppelterKnoten:
        default:
            break;
        }

        return jetziger;

    }



    //              __              _              
    //  _  _ _ __  / _|__ _ ___ _ _| |__  ___ _ _  
    // | || | '  \|  _/ _` / -_) '_| '_ \/ -_) ' \ 
    //  \_,_|_|_|_|_| \__,_\___|_| |_.__/\___|_||_|

    private knoten umfaerben(knoten jetziger)
    {
        // Kinder schwarz
        jetziger.linkesKind.einfaerben(Color.black);
        jetziger.rechtesKind.einfaerben(Color.black);
        // wurzel rot
        jetziger.einfaerben(Color.red);

        setzeStatus(opaRot);

        gui.aktionen+=" umfaerben ";

        return jetziger;
    }


    //  ___     _   _                  
    // | _ \___| |_(_)___ _ _ ___ _ _  
    // |   / _ \  _| / -_) '_/ -_) ' \ 
    // |_|_\___/\__|_\___|_| \___|_||_|

    // links rum rotieren
    //
    // 1                    2        
    //  \                  / \          
    //    2       ==>     1   3           
    //     \                             
    //      3                             

    private knoten linksRotiere(knoten jetziger)
    {
        knoten temp;
        knoten rechtesKind;

        temp = jetziger;
        rechtesKind = temp.rechtesKind;
        temp.rechtesKind = rechtesKind.linkesKind;
        temp.einfaerben(Color.red);

        rechtesKind.linkesKind = temp;
        rechtesKind.einfaerben(Color.black);
        jetziger = rechtesKind;

        gui.aktionen+=(" linksRotiere");
        // SR Kriterium iO
        setzeStatus(wurzel_sr);
        return jetziger;
    }


    // rechts rum rotieren
    //
    //      3               2        
    //     /               / \          
    //    2       ==>     1   3           
    //   /                               
    //  1      


    private knoten rechtsRotieren(knoten jetziger)
    {
        knoten temp;
        knoten linkesKind;

        temp = jetziger;
        linkesKind = temp.linkesKind;
        temp.linkesKind = linkesKind.rechtesKind;
        temp.einfaerben(Color.red);
        linkesKind.rechtesKind = temp;
        linkesKind.einfaerben(Color.black);
        jetziger = linkesKind;

        gui.aktionen+=(" rechtsRotiere");

        // SR Kriterium erfüllt
        setzeStatus(wurzel_sr);

        return jetziger;
    }


    // doppelt links rum rotieren 
    // Eingefuegt im rechten TB des linken Kindes
    //   2           1
    //  /           / \
    // 1    ==>    2   3  
    //  \
    //   3  
    // 

    public knoten doppelLinksRotation(knoten jetziger)
    {
        knoten temp;
        knoten rechtesKind;
        knoten linkesKindVonrechtesKind;


        temp = jetziger;
        rechtesKind = temp.rechtesKind;
        linkesKindVonrechtesKind = rechtesKind.linkesKind;
        rechtesKind.linkesKind = linkesKindVonrechtesKind.rechtesKind;
        temp.rechtesKind = linkesKindVonrechtesKind.linkesKind;
        temp.einfaerben(Color.red);
        linkesKindVonrechtesKind.rechtesKind = rechtesKind;
        linkesKindVonrechtesKind.linkesKind = temp;
        linkesKindVonrechtesKind.einfaerben(Color.black);
        jetziger = linkesKindVonrechtesKind;

        setzeStatus(wurzel_sr);

        gui.aktionen+=" doppelLinksRotation ";
        return jetziger;

    }

    //  doppelt rechts rum
    //    Eingeefuegt im rechten TB des rechten Kindes
    //   3           1
    //  /           / \
    // 1    ==>    2   3  
    //  \
    //   2  
    // 

    private knoten doppelRechtsRotation(knoten jetziger)
    {
        knoten temp;
        knoten linkesKind;
        knoten rechtesKindvomLinkenKind;

        temp = jetziger;
        linkesKind = temp.linkesKind;
        rechtesKindvomLinkenKind = linkesKind.rechtesKind;

        // rotieren
        linkesKind.rechtesKind = rechtesKindvomLinkenKind.linkesKind;
        temp.linkesKind = rechtesKindvomLinkenKind.rechtesKind;
        temp.einfaerben(Color.red);

        rechtesKindvomLinkenKind.linkesKind = linkesKind;
        rechtesKindvomLinkenKind.rechtesKind = temp;
        rechtesKindvomLinkenKind.einfaerben(Color.black);

        // Knoten über dem Rotiert wurde
        jetziger = rechtesKindvomLinkenKind;

        // RS Kriterium erfüllt
        setzeStatus(wurzel_sr);

        gui.aktionen+=" doppelRechtsRotation ";

        return jetziger;
    }


    // baum leer?
    public boolean isEmpty()
    {

        if (wurzel == null)
        {
            return true;
        }
        else
        {
            return false;
        }
    }


    //             _          
    //  _ __  __ _| |___ _ _  
    // | '  \/ _` | / -_) ' \ 
    // |_|_|_\__,_|_\___|_||_|


    // Baum malen 
    public void maleBaum(Graphics g, int breite, int hoehe)
    {
        //saubermachen
        g.clearRect(0,0,breite,hoehe);

        // Baum nicht leer, alle Knoten malen
        if (isEmpty() == false)
        {
            maleKnoten(wurzel, g, breite, (breite / 2), 50, (breite / 2), 50);
        }
    }// maleBaum


    // rekursiv malen
    // knoten, graphics, breite des Fensters, x-Koordinate, y-Koordinate, alten Koordinaten 
    private void maleKnoten(knoten jetzigerKnoten, Graphics g,
                          int breite, int x, int y,
                          int altesX, int altesY)
    {


        // rekursive traversierung
        // weiter links absteigen 
        if (jetzigerKnoten.linkesKind != null)
        {
            // male linkes kind
            maleKnoten(jetzigerKnoten.linkesKind, g,
                     (breite / 2), x - (breite / 4),
                     y + 60, x, y);
        }
        //weiter rechts runter
        if (jetzigerKnoten.rechtesKind != null)
        {
            //male rechtes kind
            maleKnoten(jetzigerKnoten.rechtesKind, g,
                     (breite / 2), x + (breite / 4),
                     y + 60, x, y);
        }

        // Farbe malen die der Knoten hat
        g.setColor(jetzigerKnoten.holeFarbe());

        // Knoten zwischen Linien malen
        if (altesX != x)
        {
            g.drawLine(altesX, altesY+20, x, y-20);
        }



       // male Wert
        g.drawString( new String().valueOf(jetzigerKnoten.gibWertZurueck()),
                      x -10 ,  y );
    }//zeichnen
}//class