import java.util.*;

public class Tipp<T extends Comparable> {

    private Integer info;
    private Tipp<T> vasakAlluv;
    private Tipp<T> paremAlluv;

    //Loob lehe
    public Tipp(Integer info) {
        this(info, null, null);
    }

    //Loob vahetipu kahe alamtipuga
    public Tipp(Integer info, Tipp vasakAlluv, Tipp paremAlluv) {
        this.info = info;
        this.vasakAlluv = vasakAlluv;
        this.paremAlluv = paremAlluv;
    }

    //tagastab tipu väärtuse
    public Integer getInfo() {
        return info;
    }

    //tagastab tipu kõrguse vaadates mõlemat alluvat
    public int kõrgus() {
        int vasakKõrgus = vasakAlluv == null ? 0 : vasakAlluv.kõrgus();
        int paremKõrgus = paremAlluv == null ? 0 : paremAlluv.kõrgus();
        return Math.max(paremKõrgus, vasakKõrgus)+1;
    }

    public int getKõrgus() {

        int vasakKorgus = 0;
        int paremKorgus = 0;


        if (vasakAlluv == null) {
            vasakKorgus = 0;
        }
        if (vasakAlluv != null) {
            vasakKorgus = vasakAlluv.kõrgus();
        }
        if (paremAlluv == null) {
            paremKorgus = 0;
        }
        if (paremAlluv != null) {
            paremKorgus = paremAlluv.kõrgus();
        }
        return 1 + Math.max(vasakKorgus, paremKorgus);
    }

    //tagastab kogu puu tippude arvu
    private int tippudeArv() {
        int vasakul = this.vasakAlluv == null ? 0 : this.vasakAlluv.tippudeArv();
        int paremal = this.paremAlluv == null ? 0 : this.paremAlluv.tippudeArv();
        return vasakul + paremal + 1;
    }

    //Genereerib juhusliku puu etteantud kõrguse põhjal
    public static Tipp<Integer> juhuslikPuu(int h) {
        if (h < 0) return null;
        if (h == 0) return new Tipp<>(0);
        Random r = new Random();
        Integer juhuslikArv = r.nextInt(3);
        switch (juhuslikArv) {
            case 0:
                return new Tipp<>(0, juhuslikPuu(h - 1), juhuslikPuu(h - 1));
            case 1:
                return new Tipp<>(0, juhuslikPuu(h - 1), juhuslikPuu(h - 2));
            default:
                return new Tipp<>(0, juhuslikPuu(h - 2), juhuslikPuu(h - 1));
        }
    }

    public Integer täidaArvudega(Tipp<Integer> puu, Integer n) {
        if (puu.vasakAlluv != null) {
            n = täidaArvudega(puu.vasakAlluv, n);
            puu.setInfo(n);
            n++;
            if (puu.paremAlluv != null) {
                n = täidaArvudega(puu.paremAlluv, n);
            }
        } else {
            puu.setInfo(n);
            n++;
            if (puu.paremAlluv == null) {
                return n;
            } else {
                n = täidaArvudega(puu.paremAlluv, n);
            }
        }
        return n;

    }

    //Meetod, mis tagastab booleani, kas puude struktuur ja tippude infod on samad
    public boolean equals(Tipp<T> teine) {
        return onVõrdsed(this, teine);
    }

    //Abimeetod equals käsklusele
    private boolean onVõrdsed(Tipp<T> esimene, Tipp<T> teine) {
        if (esimene == null) {
            return teine == null;
        }
        return teine != null &&
                esimene.getInfo().equals(teine.getInfo()) &&
                onVõrdsed(esimene.getVasakAlluv(), teine.getVasakAlluv()) &&
                onVõrdsed(esimene.getParemAlluv(), teine.getParemAlluv());
    }

    //otsib tipu info põhjal tippu. Tagastab selle, kui leiab või null
    private Tipp<T> otsiKirje(Tipp<T> tipp, Integer kirje) {
        if (tipp == null) {
            return null;
        }
        if (tipp.getInfo().equals(kirje)) {
            return tipp;
        }
        if (kirje < tipp.getInfo()) {
            return otsiKirje(tipp.vasakAlluv, kirje);
        } else {
            return otsiKirje(tipp.paremAlluv, kirje);
        }
    }

    private Tipp<T> otsiVanem(Tipp<T> tipp, Tipp<T> vanem, Integer kirje) {
        if (tipp == null) {
            return null;
        }
        if (tipp.getInfo().equals(kirje)) {
            return vanem;
        }
        if (kirje < tipp.getInfo()) {
            return otsiVanem(tipp.vasakAlluv, tipp, kirje);
        } else {
            return otsiVanem(tipp.paremAlluv, tipp, kirje);
        }
    }

    //tagastab vasaku alluva
    public Tipp<T> getVasakAlluv() {
        return vasakAlluv;
    }

    //tagastab parema alluva
    public Tipp<T> getParemAlluv() {
        return paremAlluv;
    }

    //paneb tipule täisarvulise väärtuse
    private void setInfo(Integer info) {
        this.info = info;
    }

    //muudab vasakut alluvat
    public void setVasakAlluv(Tipp<T> vasakAlluv) {
        this.vasakAlluv = vasakAlluv;
    }

    //muudab paremat alluvat
    public void setParemAlluv(Tipp<T> paremAlluv) {
        this.paremAlluv = paremAlluv;
    }

    //võtab sisendiks mingi tipu (juur) ja uue tipu info
    private Tipp<T> lisaKirje(Tipp<T> tipp, Integer tipuKirje) {
        Tipp<T> lisatudTipp;
        if (tipp == null) {
            return new Tipp<T>(tipuKirje);
        } else {
            if (tipuKirje >= tipp.getInfo()) {
                lisatudTipp = lisaKirje(tipp.paremAlluv, tipuKirje);
                if (tipp.paremAlluv == null) {
                    tipp.setParemAlluv(lisatudTipp);
                }
            } else {
                lisatudTipp = lisaKirje(tipp.vasakAlluv, tipuKirje);
                if (tipp.vasakAlluv == null) {
                    tipp.setVasakAlluv(lisatudTipp);
                }
            }
        }
        return tasakaalusta(tipp);
    }

    private Tipp<T> tasakaalusta(Tipp<T> tipp) {
        System.out.println("tasakaalustan");
        Tipp<T> parem = tipp.getParemAlluv();
        Tipp<T> vasak = tipp.getVasakAlluv();
        Integer vasakKõrgus = vasak == null ? 0 : vasak.kõrgus();
        Integer paremKõrgus = parem == null ? 0 : parem.kõrgus();
        System.out.println(vasakKõrgus);
        System.out.println(paremKõrgus);

        if(vasakKõrgus - paremKõrgus == -2){
            Integer paremParemKõrgus;
            Integer paremVasakKõrgus;
            if(parem != null) {
                paremParemKõrgus = parem.paremAlluv == null ? 0 : parem.paremAlluv.kõrgus();
                paremVasakKõrgus = parem.vasakAlluv == null ? 0 : parem.vasakAlluv.kõrgus();
            }
            else {
                paremParemKõrgus = -1;
                paremVasakKõrgus = -1;
            }

            if(paremVasakKõrgus - paremParemKõrgus == -1 || paremVasakKõrgus - paremParemKõrgus == 0){
                System.out.println("vasakpööre");
                return tipp.vasakPoore();
            }
            else if(paremVasakKõrgus - paremParemKõrgus == 1){
                System.out.println("paremvasak pööre");
                return tipp.paremVasakPoore();
            }
        }

        else if(vasakKõrgus - paremKõrgus == +2){
            Integer vasakVasakKõrgus;
            Integer vasakParemKõrgus;
            if(vasak != null) {
                vasakParemKõrgus = vasak.paremAlluv == null ? -1 : vasak.paremAlluv.kõrgus();
                vasakVasakKõrgus = vasak.vasakAlluv == null ? -1 : vasak.vasakAlluv.kõrgus();
            }
            else {
                vasakVasakKõrgus = -1;
                vasakParemKõrgus = -1;
            }

            if(vasakVasakKõrgus - vasakParemKõrgus == -1) {
                System.out.println("vasakparem pööre");
                return tipp.vasakParemPoore();
            }
            else if(vasakVasakKõrgus - vasakParemKõrgus == 0 || vasakVasakKõrgus - vasakParemKõrgus == 1) {
                System.out.println("parempööre");
                return tipp.paremPoore();
            }
        }
        return null;
    }

    public Tipp<T> eemaldaTipp(Tipp<T> tipp) {
        System.out.println("eemaldan tippu");
        // panen tühikud edaspidi erinevate funktsioonidega koodijuppide vahele
        // nagu tahaks eraldada koodijuppe, millele mingi kommentaar/selgitus rakendub :))))))))))))
        Tipp<T> eemaldatav = otsiKirje(this, tipp.getInfo());


        //kui eemaldataval tipul ei ole alluvaid
        if (eemaldatav.vasakAlluv == null && eemaldatav.paremAlluv == null) {
            Tipp<T> vanem = otsiVanem(this, null, tipp.getInfo());
            if(vanem == null){
                return null;
            }
            if (vanem.paremAlluv != null && vanem.paremAlluv.equals(tipp)) {
                vanem.setParemAlluv(null);
            } else {
                vanem.setVasakAlluv(null);
            }
            return tasakaalusta(vanem);
        }

        //Kui eemaldataval tipul on vaid vasakalluv
        else if (eemaldatav.paremAlluv == null) {
            System.out.println("on vasakalluv");
            Tipp<T> vanem = otsiVanem(this, null, tipp.getInfo());
            vanem.setVasakAlluv(eemaldatav.vasakAlluv);
            //return tasakaalusta(vanem.vasakAlluv);
            return tasakaalusta(vanem);
        }

        //Kui eemaldataval tipul on vaid paremalluv
        else if (eemaldatav.vasakAlluv == null) {
            System.out.println("on paremalluv");
            Tipp<T> vanem = otsiVanem(this, null, tipp.getInfo());
            vanem.setParemAlluv(eemaldatav.paremAlluv);
            return tasakaalusta(vanem);
        }

        //Kui eemaldataval tipul on kaks alluvat
        else {
            System.out.println("on mõlemad alluvad");
            //otsib keskjärjestuses järgmist tippu
            Tipp<T> puhver;
            if (eemaldatav.paremAlluv.vasakAlluv != null) {
                puhver = eemaldatav.paremAlluv.vasakAlluv;
                while (puhver.vasakAlluv != null) {
                    puhver = puhver.vasakAlluv;
                }
            }
            else {
                puhver = eemaldatav.paremAlluv;
            }
            Integer puhvriInfo = puhver.getInfo();
            eemaldaTipp(puhver);
            System.out.println(puhvriInfo);
            eemaldatav.setInfo(puhvriInfo);
        }
        System.out.println("pole alluvaid");
        return tasakaalusta(this);
    }

    private Tipp<T> vasakPoore() {
        Tipp<T> juur = paremAlluv;
        Tipp<T> paremaVasak = paremAlluv.getVasakAlluv();

        juur.setVasakAlluv(this);
        paremAlluv = paremaVasak;

        return juur;
    }

    private Tipp<T> paremPoore() {
        Tipp<T> juur = vasakAlluv;
        Tipp<T> vasakuParem = vasakAlluv.getParemAlluv();

        juur.setParemAlluv(this);
        vasakAlluv = vasakuParem;

        return juur;
    }

    private Tipp<T> vasakParemPoore() {
        this.vasakAlluv = vasakAlluv.vasakPoore();
        return this.paremPoore();
    }

    private Tipp<T> paremVasakPoore() {
        this.paremAlluv = paremAlluv.paremPoore();
        return this.vasakPoore();
    }

    public Tipp<T> eemaldaTipp(Integer kirje) {
        Tipp<T> leitudTipp = otsiKirje(this, kirje);
        if (leitudTipp != null) {
            return eemaldaTipp(leitudTipp);
        }
        return this;
    }



    public String toString() {
        return String.valueOf(info);
    }
   /* public String toString() {
        List<List<String>> kulili = abiToString(new ArrayList<List<String>>(), 0); //leiab puu kuju külili pööratuna
        int kõrgus = this.kõrgus();
        for (List<String> kasitletav : kulili) { //lisatakse igale elemendile tühikuid juurde, et külili pikkus oleks kõigil sama pikk, mis kõrgus
            while (kasitletav.size() < kõrgus) {
                kasitletav.add(" ");
            }
        }
        StringBuilder kokku = new StringBuilder();
        for (int i = 0; i < this.kõrgus() + 1; i++) { //Toimub külili kuju transponeerimine õigeks kujuks
            StringBuilder a = new StringBuilder();
            for (int j = 0; j < this.tippudeArv(); j++) {
                StringBuilder element = new StringBuilder(kulili.get(j).get(i));
                if (element.length() < String.valueOf(this.tippudeArv()).length()) //annab igale elemendile sama palju ruumi (tühikutena), et jaotuse välimus oleks ühtlane
                    while (element.length() < String.valueOf(this.tippudeArv()).length()) {
                        element.append(" ");
                    }
                a.append(element);
            }
            kokku.append(a).append(System.lineSeparator());
        }
        return kokku.toString();
    }

    private List<List<String>> abiToString(List<List<String>> jarjestus, int sugavus) {
        if (vasakAlluv != null)
            vasakAlluv.abiToString(jarjestus, sugavus + 1);
        List<String> a = new ArrayList<>();
        for (int i = 0; i < sugavus; i++) {
            a.add(" ");
        }
        a.add(this.info.toString());
        jarjestus.add(a);
        if (paremAlluv != null)
            paremAlluv.abiToString(jarjestus, sugavus + 1);
        return jarjestus;
    }
*/



    public String sulgEsitus() {
        return sulgEsitusI(this);
    }

    private static String sulgEsitusI(Tipp t) {
        if (t == null) {
            return "()";
        }
        return t.getInfo().toString()
                + "(" + sulgEsitusI(t.getVasakAlluv()) + sulgEsitusI(t.getParemAlluv()) + ")";
    }
}