//package Tree;

//import Pila.*;

/**
 * Title:        Implementazione ADT Tree
 * Description:  Esercitazione per lo studio di due implementazioni dell'adt Albero (Tree).
 * Copyright:    Copyright (c) 2000
 * Company:      Università degli Studi di Verona
 * @author Roberto Posenato
 * @version 1.0
 */

public class BinaryTree {

  public static final byte PREORDINE = -1,
    INORDINE = 0,
    POSTORDINE = 1;

  private BinaryNode radice;

  public BinaryTree() {
    radice = new BinaryNode();
  }

  public BinaryTree(Object o) {
    radice = new BinaryNode(o);
  }

  public boolean isEmpty() {
    return (radice == null);
  }

  public BinaryNode getRoot() {
    return radice;
  }

  public void setRoot(BinaryNode n) throws NullPointerException {
    if (n == null) throw new NullPointerException();
    radice = n;
  }

  void visita(BinaryNode n) {
    System.out.print(" " + n.elemento);
  }


  public void visitaIterativa(int ordine) {
    visitaOrdineI(radice, ordine);
  }
  private void visitaOrdineI(BinaryNode nodo, int ordine) {
    Pila  pila = new PilaArray(),
          pilaVisitati = new PilaArray();

    BinaryNode n;
    pila.push(nodo);
    while (! pila.eVuota()) {
      n = (BinaryNode) pila.pop();
      if (n != null) {
        if (ordine == PREORDINE) {
          visita(n);
          pila.push(n.figlioDx);
          pila.push(n.figlioSx);
        } else {
          if (ordine == INORDINE) {
            if (pilaVisitati.eVuota() || (! pilaVisitati.top().equals(n)) ) {
              pila.push(n);
              pila.push(n.figlioSx);
              pilaVisitati.push(n);
            } else {
              visita(n);
              pilaVisitati.pop();
              pila.push(n.figlioDx);
            }
          } else {
            if (pilaVisitati.eVuota() || (! pilaVisitati.top().equals(n)) ) {
              pila.push(n);
              pila.push(n.figlioDx);
              pila.push(n.figlioSx);
              pilaVisitati.push(n);
            } else {
              visita(n);
              pilaVisitati.pop();
            }
          }
        }//fine else casi di visita
      }//if n!=null
    }//while
  }
  public void visita(int ordine) {
    visitaOrdine(radice, ordine);
  }
  private void visitaOrdine(BinaryNode nodo, int ordine) {
    if (nodo != null) {
      if (ordine == PREORDINE) {
        visita(nodo);
        visitaOrdine(nodo.figlioSx, ordine);
        visitaOrdine(nodo.figlioDx, ordine);
      } else {
        if (ordine == INORDINE) {
          visitaOrdine(nodo.figlioSx, ordine);
          visita(nodo);
          visitaOrdine(nodo.figlioDx, ordine);
        } else {
          visitaOrdine(nodo.figlioSx, ordine);
          visitaOrdine(nodo.figlioDx, ordine);
          visita(nodo);
        }
      }
    }
  }


  public void insert(Object item) {
    radice = insertItem(item, radice, null);
  }
  private BinaryNode insertItem(Object item, BinaryNode nodo, BinaryNode padre) {
    int result;
    if (nodo == null) { // definisco un nuovo nodo
      BinaryNode n = new BinaryNode(item);
      n.padre = padre;
      return n;
    } else { //cerco posizione dove inserire l'elemento
      if ( (result=((Comparable) item).compareTo(nodo.elemento))  < 0 ) {
        nodo.figlioSx = insertItem(item, nodo.figlioSx, nodo);
        return nodo;
      } else {
        if (result == 0)
          return nodo;
        else {
          nodo.figlioDx = insertItem(item, nodo.figlioDx, nodo);
          return nodo;
        }
      }
    }
  }


  public BinaryNode find (Object item) {
    BinaryNode node = radice;
    int result;

    while (node != null) {
      if ( (result = ((Comparable) item).compareTo(node.elemento)) < 0) {
        node = node.figlioSx;
      } else
        if (result == 0)
          return node;
        else
          node = node.figlioDx;
    }
    return node; //ritorn null se la ricerca è fallita
  }

  public void delete(Object item) {
    BinaryNode daCancellare = find(item);
    if (daCancellare == null)
      return;
    else
      deleteNode(daCancellare);
  }

  /**
   * deleteNode(daCancellare)
   * cancella il nodo daCancellare mantenendo l'ordine dell'albero.
   */
  private void deleteNode(BinaryNode daCancellare) {
    BinaryNode temp; /* mantiene il riferimento al nodo che andrà a sostituire
                      * il nodo daCancellare
                      */

    if (daCancellare.figlioSx == null) /* non c'è il figlio sx, prendo il dx,
                                        * che può essere null
                                        */
       temp = daCancellare.figlioDx;
    else {
      if (daCancellare.figlioDx == null) //esiste solo figlio sx
        temp = daCancellare.figlioSx;
      else { // ci sono entrambi i figli...
        if (daCancellare.figlioSx.figlioDx == null) { //se il figlioSx ha solo figlioSx
          temp = daCancellare.figlioSx;
          temp.figlioDx = daCancellare.figlioDx;
          temp.figlioDx.padre = temp;
        } else {
          temp = inOrderPrec(daCancellare); /* cerco nodo precedente nella
                                             * sequenza di visita in ordine
                                             */
          daCancellare.elemento = temp.elemento; //scambio gli elementi
          deleteNode(temp); //cancello il nodo temp
          temp = daCancellare; //allineo daCancellare e temp per gli aggiustamenti successivi
        }
      }
    }
    //ora si può fare la sostituzione di daCancellare con temp
    if (daCancellare == radice) {//se è root, aggiusta il padre a null
      radice = temp;
      if (radice != null) radice.padre = null;
    } else {
      if (daCancellare.padre.figlioSx == daCancellare) //daCancellare è figlio sx
        daCancellare.padre.figlioSx = temp;
      else
        daCancellare.padre.figlioDx = temp;
      if (temp != null)
        temp.padre = daCancellare.padre;
    }
  }

  /**
   * Restituisce il nodo precedente nell'ordine naturale dell'albero.
   * Questo nodo è il nodo più a dx del sottoalbero sx.
   */
  BinaryNode inOrderPrec(BinaryNode node) {
    if (node == null)
      return null;
    node = node.figlioSx;
    if (node != null)
      while (node.figlioDx != null)
        node = node.figlioDx;
    return node;
  }

  public String toString() {
    return stampa(radice, 0);
  }

  private String stampa(BinaryNode node, int identazione) {
    StringBuffer output = new StringBuffer();
    if (node != null) {
      output.append(stampa(node.figlioDx, identazione + 1));
      for (int i=1; i <= identazione; i++)
        output.append("     ");
      output.append(node.elemento.toString()+"\n");
      output.append(stampa(node.figlioSx, identazione + 1));
    }
    return output.toString();
  }
}