package Trees;
public class GenTree implements Tree{
    private TreeNode root;      // radice dell'albero
    private int count;           // numero di nodi dell'albero
    private TreeNode cursor;    // riferimento al nodo corrente

    
    // post: costruisce un albero vuoto
    public GenTree() {
        clear();
    }

    // post: svuota l'albero
    public void clear() {
        root = cursor = null;
        count = 0;
    }

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

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

    // pre:  ob non nullo
    // post: l'oggetto e' inserito come figlio del nodo corrente, 
    //       o come radice se l'albero e' vuoto. Ritorna true.
    public boolean insert (Object ob) {
        if (isEmpty())
            cursor = root = new TreeNode(ob);
        else {
	    if (cursor.child == null)
	       cursor.child = new TreeNode(ob, cursor, null,null);
	    else {
  	       TreeNode index = cursor.child;
	       while (index.sibling != null) 
		  index = index.sibling;
	       index.sibling = new TreeNode(ob,cursor, null,null);
	    }
	}
        count++;
        return true;
    }



    // pre:  albero non vuoto 
    // post: se cursor e' una foglia, la rimuove e ne ritorna il valore;
    //       cursor viene assegnato al padre del nodo rimosso (se esiste)
    //       Altrimenti ritorna null
    public Object remove () {

        if (cursor.child != null)
	    return null;

        Object temp = cursor.key;
        if (cursor == root)
	    cursor = root = null;
        else {
            if (cursor.parent.child == cursor) // cursor e' il primo figlio
		cursor.parent.child = cursor.sibling;
	    else {
	        TreeNode index = cursor.parent.child;
		while (index.sibling != cursor)
		    index = index.sibling;
		index.sibling = cursor.sibling;
	    }
	    cursor = cursor.parent;
        }
	count --;
        return temp;
    }



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

    // pre: albero non vuoto e ob diverso da null
    // post: imposta il valore del nodo puntato da cursor 
    public void setValue(Object ob) { 
        cursor.key = ob; 
    }


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


    // post: se possibile cursor si sposta sul figlio in posizione 
    //       childIndex e ritorna true; altrimenti rimane dov'e' e 
    //       ritorna false 
    public boolean moveDown (int childIndex) {

        if (isEmpty() || cursor.child == null || childIndex < 1)
	    return false;
        
	TreeNode index = cursor.child;
	int i;
        for (i = 1; i<childIndex && index.sibling != null; i++) 
            index = index.sibling; 
	if (i == childIndex) {
	    cursor = index;
	    return true;
	}
	else
	    return false;
    }


    // post: se possibile sposta cursor sul nodo padre e ritorna true;
    //       altrimenti ritorna false; 
    public boolean moveUp () {

        if (isEmpty() || cursor.parent == null)
	    return false;
        else {
           cursor=cursor.parent;
           return true;
	}
    }


    // post: ritorna una stringa che rappresenta l'albero
    public String DFvisit() {
        StringBuffer sb = new StringBuffer();
        sb.append("Tree: <");
        if (root != null) 
           DFformat(root,sb);
        sb.append(">");
        return sb.toString();
    }


    // pre:  n diverso da null
    // post: appende a sb una stringa che rappresenta il sottoalbero con 
    //       radice n
    private void DFformat(TreeNode n, StringBuffer sb) {

        sb.append(" " + n.key.toString() + " ");


        if (n.child != null) {
            sb.append("<");
            DFformat(n.child,sb);
            sb.append("> ");
	}
        if (n.sibling != null) 
           DFformat(n.sibling,sb); 

    }




    // esercitazione 6: secondo esercizio


    // pre: k >= 0
    // post: ritorna true se tutti i nodi interni dell'albero hanno esattamente
    //       k figli; ritorna false altrimenti
    public boolean kfigli(int k) {
	return check_kfigli(root, k);
    }


    private boolean check_kfigli(TreeNode n, int k) {

	if (n == null)
	    return true;

	if (n.child != null) { // controllo il numero dei figli
	   TreeNode index = n.child;
	   int conta = 0;
	   while (index != null) {
	       conta++;
	       index = index.sibling; 
	   }
	   if (conta != k)
	       return false;
	}
        
        return check_kfigli(n.child,k) && check_kfigli(n.sibling,k);
    }



    // pre: k >= 0
    // post: ritorna true se l'albero e' k-ario completo; 
    //       ritorna false altrimenti
    public boolean kcompleto(int k) {
	return check_kcompleto(root, k) != -2;
    }


    // post: ritorna l'altezza di n se l'albero radicato in n e' k-completo
    //       ritorna -2 altrimenti
    private int check_kcompleto(TreeNode n, int k) {

	if (n == null || n.child == null) 
	    return -1;


        int res = check_kcompleto(n.child, k);
	if (res == -2)
	   return -2;
	int conta = 1;
	TreeNode index = n.child.sibling;
        while (index != null) {
	   conta++;
           int temp = check_kcompleto(index, k);
	   if (temp == -2 || temp != res)
		return -2;
	   index = index.sibling;
        }
	if (conta != k)
	    return -2;
	else 
	    return res+1;
    }



}