package BinTrees;
import Queues.*;
public class BinaryTree implements BT {
    private BTNode root;        // la radice dell'albero
    private BTNode cursor;      // puntatore al nodo corrente
    private int count;          // numero nodi dell'albero


    // post: crea un albero binario vuoto
    public BinaryTree() {
        clear();
    }


    // post: ritorna il numero di nodi nell'albero
    public int size() {
        return count;
    }


    // post: ritorna true sse l'albero e' vuoto
    public boolean isEmpty() {
        return count == 0;
    }

    // post: rimuove tutti i nodi dall'albero
    public void clear() {
        root = null;
        cursor = null;
        count = 0;
    }


    // post: sposta il cursore sulla root
    public void reset() {
        cursor = root;
    }


    // pre: albero non vuoto
    // post: se possibile, cursor si sposta sul figlio sinistro e ritorna true.
    //       Ritorna false altrimenti.
    public boolean moveLeft() {
        if (cursor.left != null) {
           cursor = cursor.left;
           return true;
	}
	else
	   return false;
    }



    // pre: albero non vuoto
    // post: se possibile, cursor si sposta sul figlio sinistro e ritorna true.
    //       Ritorna false altrimenti.
    public boolean moveRight() {
        if (cursor.right != null) {
           cursor = cursor.right;
           return true;
	}
	else
	   return false;
    }




    // pre:  albero non vuoto
    // post: se possibile, cursor si sposta al nodo padre e ritorna true.
    //       Ritorna false altrimenti.
    public boolean moveUp() {
        if (cursor != root) {
            cursor = cursor.parent;
            return true;
        }
	else
	    return false;

    }


    // pre:  albero non vuoto
    // post: ritorna il valore del nodo puntato da cursor
    public Object getValue() {
        return cursor.key;
    }


    // pre:  ob non nullo 
    // post: se l'albero e' vuoto, inserisce ob come root.
    //       se cursor non ha figlio sinistro, inserisce ob come figlio 
    //       sinistro di cursor e ritorna true. Altrimenti, non 
    //       inserisce ob e ritorna false.
    public boolean insertLeft(Object ob) {


	// inserimento non valido
        if (cursor !=null && cursor.left != null)
	    return false;


        // primo caso: albero vuoto
        if (cursor == null)
            cursor = root = new BTNode(ob);
        else 
            // secondo caso: cursor non ha figlio sinistro
            cursor.setLeft(new BTNode(ob));

        count++;
        return true;
    }


    // pre:  ob non nullo 
    // post: se l'albero e' vuoto, inserisce ob come root.
    //       se cursor non ha figlo destro, inserisce ob come figlio destro di 
    //       cursor e ritorna true. Altrimenti, non inserisce ob e ritorna false.
    public boolean insertRight(Object ob) {


	// inserimento non valido
        if (cursor !=null && cursor.right != null)
	    return false;


        // primo caso: albero vuoto
        if (cursor == null)
            cursor = root = new BTNode(ob);
        else 
            // secondo caso: cursor non ha figlio destro
            cursor.setRight(new BTNode(ob));

        count++;
        return true;
    }


    // pre:  albero non vuoto
    // post: se cursor e' posizionato su una foglia, rimuove il nodo puntato 
    //       da cursor, sposta cursor sul nodo padre (se esiste) e ritorna il
    //       valore dell'elemento rimosso. Altrimenti ritorna null.
    public Object remove() {

        // se cursor non e' posizionato su una foglia ritorno null
        if (cursor.left != null || cursor.right != null)
	    return null;

        Object value = cursor.key;
        if (cursor.isLeftChild()) {
            moveUp();
            cursor.setLeft(null);
        } else if (cursor.isRightChild()) {
            moveUp();
            cursor.setRight(null);
        } else {
            root = cursor = null;
        }
        count--;
        return value;
    }


    // post: ritorna una stringa che contiene gli elementi dell'albero, visitati in
    //       pre-ordine
    public String preorderVisit() {
	StringBuffer pre = new StringBuffer("Visita pre-order: ");
        if (root != null)
	    formatPreorder(root, pre);
        return pre.toString();
    }

    // pre:  parametri diversi da null
    // post: appende a sb una stringa che rappresenta il sottoalbero con 
    //       radice n visitato in pre-order
    private void formatPreorder(BTNode n, StringBuffer sb) {

        if (n.left == null && n.right == null) 
            sb.append(" ("+n.key+")");
        else {
            sb.append(" ("+n.key);
            if (n.left != null) 
               formatPreorder(n.left,sb);
            else 
               sb.append(" ()");
            if (n.right != null) 
               formatPreorder(n.right,sb);
            else
		sb.append(" ()");
            sb.append(")");
        }
    }



    // post: ritorna una stringa che contiene gli elementi dell'albero, visitati in
    //       post-ordine
    public String postorderVisit() {
	StringBuffer post = new StringBuffer("Visita post-order: ");
        if (root != null)
	    formatPostorder(root, post);
        return post.toString();
    }


    // pre:  parametri diversi da null
    // post: appende a sb una stringa che rappresenta il sottoalbero con 
    //       radice n visitato in post-order
    private void formatPostorder(BTNode n, StringBuffer sb) {

        if (n.left == null && n.right == null) 
            sb.append(" ("+n.key+")");
        else {
	    sb.append("( ");
            if (n.left != null) 
               formatPostorder(n.left,sb);
            else 
               sb.append(" ()");
            if (n.right != null) 
               formatPostorder(n.right,sb);
            else
		sb.append(" ()");
            sb.append(n.key + ")");
        }
    }



    // post: ritorna una stringa che contiene gli elementi dell'albero, 
    //       visitati in ordine simmetrico
    public String inorderVisit() {
	StringBuffer in = new StringBuffer("Visita in-order: ");
        if (root != null)
	    formatInorder(root, in);
        return in.toString();
    }

    // pre:  parametri diversi da null
    // post: appende a sb una stringa che rappresenta il sottoalbero con 
    //       radice n visitato in-order
    private void formatInorder(BTNode n, StringBuffer sb) {

        if (n.left == null && n.right == null) 
            sb.append(" ("+n.key+")");
        else {
            sb.append("( ");
            if (n.left != null) 
               formatInorder(n.left,sb);
            else 
               sb.append(" ()");
            sb.append(n.key);
            if (n.right != null) 
               formatInorder(n.right,sb);
            else
		sb.append(" ()");
            sb.append(")");
        }
    }


    /* esercitazione 4 */


    // post: ritorna il numero di S-nodi , ovvero il numero di nodi 
    //       dell'albero che sono radici di un sottoalbero con piu' 
    //       nodi sinistri (cioe' nodi che sono figli sinistri) che destri
    public int Snumber() {
        int[] res = new int[] {0,0};
        Snumber(root, res);
        return res[0];
    }

    // post: ritorna il numero di S-nodi dell'albero radicato in n
    private void Snumber(BTNode n, int[] res) {

	if (n == null)
	    return ;
	Snumber(n.left,res);
	int temp = res[1];
        res[1]=0;
	Snumber(n.right,res);

	res[1] += temp + (n.left != null ? (n.right != null ? 0 : 1) : 
   		                           (n.right!= null ? -1 : 0));
        res[0] += (res[1] > 0 ? 1 : 0);
    }



    // post: ritorna il numero di S-nodi , ovvero il numero di nodi 
    //       dell'albero che sono radici di un sottoalbero con piu' 
    //       nodi sinistri (cioe' nodi che sono figli sinistri) che destri
    public int Snodi() {
        return Snodi(root);
    }

    // post: ritorna il numero di S-nodi dell'albero radicato in n
    private int Snodi(BTNode n) {
        int k = 0;
	if (n == null)
	    return 0;

	if (subSxDx(n) > 0)
	    k++;

        return k + Snodi(n.left) + Snodi(n.right);
    }


    // post: ritorna la differenza "nodi sinistri - nodi destri" dell'albero
    //       radicato in n
    private int subSxDx(BTNode n) {

	if (n == null)
	    return 0;
	int k = (n.left != null ? (n.right != null ? 0 : 1) : 
   		                   (n.right!= null ? -1 : 0));
        
        return k + subSxDx(n.left) + subSxDx(n.right);
    }



    // post: ritorna true se l'albero e' bilanciato; ritorna false altrimenti
    // NOTA: un albero binario e' bilanciato se, per ogni suo nodo n, le
    //       altezze dei sottoalberi sinistro e destro di n differiscono al 
    //       piu' di uno.
    public boolean isBalanced() {
	return isBalanced(root) != -2;
    }


    // post: ritorna l'altezza dell'albero radicato in n se tale albero
    //       e' bilanciato; ritorna -2 altrimenti
    private int isBalanced(BTNode n) {

	if (n == null)
	    return -1;

	int nl = isBalanced(n.left);
	int nr = isBalanced(n.right);
	if (nl != -2 && nr != -2 && Math.abs(nl-nr) <= 1)
	    return 1 + Math.max(nl,nr);
	else
	    return -2;
    }


    // post: ritorna una stringa contenente tutte le chiavi dei nodi
    //       interni dell'albero, elencati procedendo per livelli, da
    //       destra a sinistra e separati da uno spazio
    public String interniDxSx() {
	if (root == null)
		return "";
	BTNode n;
	QueueArray Q = new QueueArray();
        Q.enqueue(root);
	String s = "";
	while (!Q.isEmpty()) {
	    n = (BTNode)Q.dequeue();
	    if (n.left!= null || n.right != null)
	       s = s + n.key.toString() + " ";
            if (n.right != null)
		Q.enqueue(n.right);
	    if (n.left != null)
		Q.enqueue(n.left);
	}
        return s;
    }


}