// TRAI_23_t14_15.java.java SJ


/**
 * 14. Kirjoita algoritmi joka laskee annetun binääripuun korkeuden, ts. pisimmän polun juuresta
 * lehtisolmuun. Aikavaativuus? Vihje: rekursio.
 * <p>
 * 15. Kirjoita algoritmi joka lisää sisäjärjestyksessä olevaan binääripuuhun uuden solmun siten,
 * että puu säilyy sisäjärjestyksessä. Jos sama alkio (.equals()) oli jo puussa, niin alkiota ei
 * lisätä puuhun. Parametreina puu ja alkio. Algoritmi luo uuden solmun jos lisäys tehdään.
 * Algoritmi palauttaa totuusarvon lisättiinkö alkio vai ei. Algoritmin toiminta käydään
 * läpi luennolla. Aikavaativuus?
 */

// Tarvitset projektiin (tai komentoriville) TRA-kirjaston Moodlesta.

import fi.uef.cs.tra.BTree;
import fi.uef.cs.tra.BTreeNode;
import java.util.Random;

public class TRAI_23_t14_15_esim {

    public static void main(String[] args) {

        BTree<Integer> puu = new BTree<>();

        int N = 12;
        if (args.length > 0)
            N = Integer.parseInt(args[0]);

        // testataan ensin vakiopuulla

        puu = exampleBTree();
        System.out.println("Sisäjärjestyksessä:");
        inorderPrint(puu);

        System.out.println("Korkeus = " + korkeus(puu));

        System.out.println();


        // tehdään vielä uusi generoitu ja testataan samalla
        // tehtävää 15

        puu = new BTree<>();

        System.out.println("\nPuuhun:");
        Random r = new Random(42);
        Integer x = null;
        for (int i = 0; i < N; i++) {
            x = r.nextInt(N * 2);
            System.out.print(x + " ");
            inorderInsert(puu, x);
        }
        System.out.println();

        System.out.println("Sisäjärjestyksessä:");
        inorderPrint(puu);

        System.out.println("Korkeus = " + korkeus(puu));

        // testataan vielä hakemista
        for (int i = 0; i < N * 2; i++) {
            System.out.println("Onko " + i + " : " +
                    inorderMember(puu, i));
        }

    } // main()

    /**
     * 14. Puun korkeus. Käynnistysmetodi
     * @param t tarkasteltava binääripuu.
     * @return puun korkeus tai -1 jos puu on tyhjä
     **/
    public static <E> int korkeus(BTree<E> t) {
        return korkeus(t.getRoot());
    }

    /**
     * Solmun korkeus.
     * @param n tarkasteltava solmu
     * @return solmun korkeus, tai -1 jos n==null
     */
    public static <E> int korkeus(BTreeNode<E> n) {

        // null:n "korkeus" on -1 jotta lehtisolmun korkeus
        // on max(-1,-1)+1 = 0
        if (n == null)
            return -1;

        // solmun korkeus on maksimi lasten korkeuksista + 1
        return Math.max(korkeus(n.getLeftChild()),
                korkeus(n.getRightChild())) + 1;
    }

    /**
     * 15. Lisäys sisäjärjestettyyn binääripuuhun.
     * @param T binääripuu
     * @param x lisättävä alkio
     * @return tehtiinkö lisäys vai ei
     */
    public static <E extends Comparable<? super E>> boolean inorderInsert(BTree<E> T, E x) {
        BTreeNode<E> n = T.getRoot();
        if (n == null) {
            T.setRoot(new BTreeNode<>(x));
            return true;
        }

        while (true) {

            if (x.compareTo(n.getElement()) == 0)
                // x jo puussa, eli lisätä
                return false;

            else if (x.compareTo(n.getElement()) < 0) {
                // x edeltää n:n alkiota
                if (n.getLeftChild() == null) {
                    // lisäyskohta läydetty
                    n.setLeftChild(new BTreeNode<>(x));
                    return true;
                } else
                    n = n.getLeftChild();
            } else {
                // x suurempi kuin n
                if (n.getRightChild() == null) {
                    // lisäyskohta läydetty
                    n.setRightChild(new BTreeNode<>(x));
                    return true;
                } else
                    n = n.getRightChild();
            }
        } // while

    } // inorderInsert()


    // -------------------------------
    // esimerkkejä


    public static BTree<Integer> exampleBTree() {

        BTree<Integer> T = new BTree<Integer>();

        // juuri
        T.setRoot(new BTreeNode<Integer>(9));

        BTreeNode<Integer> n = T.getRoot();

        // juuren lapset
        n.setLeftChild(new BTreeNode<Integer>(5));
        n.setRightChild(new BTreeNode<Integer>(15));

        // vasen haara
        BTreeNode<Integer> l = n.getLeftChild();

        l.setLeftChild(new BTreeNode<Integer>(3));
        l.setRightChild(new BTreeNode<Integer>(8));

        l.getLeftChild().setRightChild(new BTreeNode<Integer>(4));

        // oikea haara
        l = n.getRightChild();

        l.setLeftChild(new BTreeNode<Integer>(12));
        l.setRightChild(new BTreeNode<Integer>(18));

        l.getLeftChild().setLeftChild(new BTreeNode<Integer>(11));
        l.getLeftChild().setRightChild(new BTreeNode<Integer>(13));


        System.out.println("                 ");
        System.out.println("       9        ");
        System.out.println("    __/  \\__     ");
        System.out.println("   5        15   ");
        System.out.println("  / \\      /  \\  ");
        System.out.println(" 3   8   12    18");
        System.out.println("  \\      /\\      ");
        System.out.println("   4    11 13    ");
        System.out.println("                 ");

        return T;

    } // exampleBTree()



    /**
     * Onko alkio sisäjärjestetyssä binääripuussa vai ei
     * @param T sisäjärjestetty binääripuu
     * @param x etsittävä alkio
     * @param <E> alkiotyyppi
     * @return true jos alkio x on puussa, muuten false
     */
    public static <E extends Comparable<? super E>>
    boolean inorderMember(BTree<E> T, E x) {
        BTreeNode<E> n = T.getRoot();

        while (n != null) {
            if (x.compareTo(n.getElement()) == 0)
                return true;
            else if (x.compareTo(n.getElement()) < 0)
                n = n.getLeftChild();
            else
                n = n.getRightChild();
        } // while
        return false;

    } // inorderMember()


    /**
     * Tulostus sisäjärjestyksessä rekursiivisesti.
     * @param T tulostettava puu
     */
    public static void inorderPrint(BTree T) {
        inorderPrintBranch(T.getRoot());
        System.out.println();
    } // inorderPrint()


    /**
     * Tulostus sisäjärjestyksessä rekursiivisesti.
     * @param n tulostettavan alipuun juuri
     */
    public static void inorderPrintBranch(BTreeNode n) {
        if (n == null)
            return;

        inorderPrintBranch(n.getLeftChild());
        System.out.print(n.getElement() + " ");
        inorderPrintBranch(n.getRightChild());

    } // inorderPrintBranch()


} // class TRAI_23_t14_15.java