// BinPuuEsim09.java SJ

import fi.joensuu.cs.tra.*;
import java.util.Random;

public class BinPuuEsim09 {

	public static void main(String[] args) {

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

		int N = 10;
		if (args.length > 0)
			N = Integer.valueOf(args[0]);

		System.out.println("Puuhun:");
		Random r = new Random(42);
		Integer x;
		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("Sisajarjestyksessa:");
		inorderPrint(puu);

		for (int i = 0; i < 16; i++) {
			System.out.println("Onko " + i + " : " +
							   inorderMember(puu, new Integer(i)));
		}

		puu = exampleBTree();
		
		System.out.println("Sisajarjestyksessa:");
		inorderPrint(puu);

		for (int i = 0; i < 20; i++) {
			System.out.println("Onko " + i + " : " +
							   inorderMember(puu, new Integer(i)));
		}


		System.out.println("Poistetaan:");
		for (int i = 0; i < N; i++) {
			x = r.nextInt(N*2);
			System.out.print(x + ":");
			BTreeNode n = inorderFindNode(puu, x);
			if (n != null) {
				inorderRemoveNode(puu, n);
				inorderPrint(puu);
			} else
				System.out.println();
		}
		System.out.println();

		
	} // main()

	/* Luo pienen sisajarjestyn esimerkkipuun
	                 
	       10        
	    __/  \__     
	   5        15   
	  / \      /  \  
	 3   8   12    18
	  \      /\      
	   4    11 13    
	                 
	*/

	public static BTree<Integer> exampleBTree() {

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

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

		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("       10        ");
		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()


    // lisäys sisäjärjestettyyn binääripuuhun

    // harjoitustehtävä
	public static void inorderInsert(BTree T, Comparable x) {

	} // inorderInsert()


	// etsii annettua elementtia puusta, palauttaa totuusarvon
	public static boolean inorderMember(BTree T, Comparable x) {
		BTreeNode 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()


	// etsii annetun elementin sisaltavan solmun
	public static BTreeNode inorderFindNode(BTree T, Comparable x) {
		BTreeNode n = T.getRoot();

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

	} // inorderFindNode()


	// etsii annetun elementin sisaltavan solmun
    // rekursiivinen versio esimerkin vuoksi

    // käynnistysaliohjelma
	public static BTreeNode inorderFindNode2(BTree T, Comparable x) {
        return inorderFindNode2_r(T.getRoot(), x);
	} // inorderFindNode2()

    // varsinainen rekursiivinen osa
	public static BTreeNode inorderFindNode2_r(BTreeNode n, Comparable x) {
        if (n == null)
            return null;

        // vertailu
        int cmp = x.compareTo(n.getElement());
        
        if (cmp == 0)   // löytyi tästä
            return n;

        if (cmp < 0)    // vasemmalle vai oikealle
            return inorderFindNode2_r(n.getLeftChild(), x);
        else
            return inorderFindNode2_r(n.getRightChild(), x);

	} // inorderFindNode2_r()



    // solmun seuraaja sisäjärjestyksessä:
    // harjoitustehtävä

	public static BTreeNode inorderNext(BTreeNode n) {

		// jos solmulla on oikea lapsi, haetaan sen
		// vasemmanpuoleinen jalkelainen

		// muutoin haetaan ensimmainen esivanhempi jonka
		// vasemmassa alipuussa solmu n on


		// jollei loytynyt
		return null;

	} // inorderNext()


	// poistaa annetun solmun siten, etta puu sailyy sisajarjestyksessa
	public static void inorderRemoveNode(BTree T, BTreeNode n) {

		// sukulaiset apumuuttujiin
		BTreeNode lc = n.getLeftChild();
		BTreeNode rc = n.getRightChild();

		BTreeNode par = n.getParent();

		// muistetaan onko n vanhempansa oikea vai vasen lapsi
		boolean vasen = false;
		if (par != null) {
			if (par.getLeftChild() == lc)
				vasen = true;
			else
				vasen = false;
		}

		// 0-1 -lapsiset tapaukset erikseen

		// jos juuri, ei vasenta lasta: oikea lapsi tilalle
		if (n == T.getRoot() && lc == null)
			T.setRoot(rc);

		// jos juuri, ei oikeaa lasta: vasen lapsi tilalle
		else if (n == T.getRoot() && rc == null)
			T.setRoot(lc);

		// jos ei juuri, ei vasenta lasta: oikea lapsi tilalle
		if (lc == null) {
			if (vasen)
				par.setLeftChild(rc);
			else
				par.setRightChild(rc);
		}

		// jos ei juuri, ei oikeaa lasta: vasen lapsi tilalle
		if (rc == null) {
			if (vasen)
				par.setLeftChild(lc);
			else
				par.setRightChild(lc);
		}


		// molemmat lapset olemassa
		else {

			BTreeNode korv = inorderNext(n);
			Object korvAlkio = korv.getElement();

			// poistetaan korvaava rekursiivisesti
			inorderRemoveNode(T, korv);

			// oikea lapsi saattoi muuttua
			rc = n.getRightChild();

			// uusi solmu
			korv = new BTreeNode(korvAlkio);
			if (n == T.getRoot())
				T.setRoot(korv);
			else if (vasen)
				par.setLeftChild(korv);
			else
				par.setRightChild(korv);

			// palautetaan lapset
			korv.setLeftChild(lc);
			korv.setRightChild(rc);

			// uusi alkio vanhan tilalle
			// n.setElement(korvAlkio);

		}


	} // inorderRemoveNode


	// Tulostus sisajarjestyksessa rekursiivisesti
	public static void inorderPrint(BTree T) {
		inorderPrintBranch(T.getRoot());
		System.out.println();
	} // inorderPrint()


	public static void inorderPrintBranch(BTreeNode n) {
		if (n == null)
			return;

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

	} // inorderPrintBranch()

	
} // class BinPuuEsim09