/*
  Scrivere un metodo Java che legga da uno stream di Input
  una sequenza di interi e costruisca un albero binario bilanciato
  (utilizzare eventualmente una struttura dinamica di supporto).
  Definire e implementare tutte le classi accessorie utilizzate.
*/

import java.io.*;

public class Esame_18_06_2002_bis {
  public static void main(String[] args) {
    TreeFromStream();
  }
  
  public static MiniBST TreeFromStream() {
    MiniConsoleReader r = new MiniConsoleReader();
    myDato input;
    MiniBST tree = new MiniBST();
    
    System.out.println("Digita numeri da inserire nell'albero" +
                       "\n(digita '0' oppure <Invio> per finire la sequenza)");
    while(true) {
      try {
      System.out.print("Numero: ");
      input = new myDato(r.readInt());
      } catch (ConsoleReaderException e) {input = null;}
      if (input == null) break;
        insertBalancedTree(tree, input.getKey());
        tree.print();
    }
  
    return tree;  
  }
    
  /* inserisce un nuovo nodo all'interno di un albero cercando di bilanciarlo,
     indipendentemente dalla sua chiave.
     Usa l'attraversamento in ampiezza scansionando l'albero orizzontalmente;
     appena si trova un "buco" libero viene aggiunto il nodo.
  */
  public static void insertBalancedTree(MiniBST tree, int val) {
    IntBSTNodo p = tree.root;
    if (tree.root == null)
      tree.root = new IntBSTNodo(val);  //albero vuoto? Crea primo nodo!
    else {
      MiniCoda c = new MiniCoda();
      c.enQueue(p);
      while (!c.isEmpty()) {
        MiniCoda liv = new MiniCoda();
        while (!c.isEmpty()) {
          IntBSTNodo n = (IntBSTNodo)c.deQueue();
          if (n.left != null) liv.enQueue(n.left);
          else {
            n.left = new IntBSTNodo(val);
            return;
          }
          if (n.right != null) liv.enQueue(n.right);
          else {
            n.right = new IntBSTNodo(val);
            return;
          }
        }
        c = liv;
      }
    }
  }
}

//La mia classe di oggetti che contiene una chiave intera
class myDato implements Comparable {
  private int key;
  public myDato(int val) {
    key = val;
  }
  public int getKey() {
    return key;
  }
  public int compareTo(Object o) {
    return (
      (key < ((myDato)o).getKey()) ? -1 :
      (key > ((myDato)o).getKey()) ?  1 : 0
    );
  }
  
  public String toString() {
    return "" + key;
  }
}


//*******************CLASSI ACCESSORIE**************************
//Mini lista ad oggetti (serve a MiniCoda)
class MiniLista {
  private Nodo head;
  public MiniLista() {
    head = null;
  }
  public Nodo getHead() {
    return head;
  }
  public boolean isEmpty() {
    return (head == null);
  }
  
  public void insertTail(Object val) {
    if (isEmpty())
      head = new Nodo(val);
    else {
      Nodo aux = head;
      for (; aux.getNext() != null; aux = aux.getNext());
      aux.setNext(new Nodo(val));
    }
  }
  public Object deleteHead() {
    if (isEmpty())
      throw new EmptyListException();
    else {
      Object val = head.getInfo();
      head = head.getNext();
      return val;
    }
  }
  
}

class Nodo {
  private Object info;
  private Nodo next;
  //costruttori
  public Nodo(Object val) {this(val, null);}
  public Nodo(Object val, Nodo n) {
    info = val;
    next = n;
  }
  //metodi pubblici
  public void setInfo(Object val) {info = val;}
  public Object getInfo() {return info;}
  
  public void setNext(Nodo n) {next = n;}
  public Nodo getNext() {return next;}  
}


/* Mini albero BST adatto all'esercizio (gestisce INTERI)
   come vuole l'esercizio.
*/
class MiniBST {
  protected IntBSTNodo root;
  public MiniBST() {
    root = null;
  }
  public boolean isEmpty() {
    return (root == null);
  }
  
  
  public boolean insert(int val) {
    if (isEmpty())
      root = new IntBSTNodo(val);
    else {
      //cerca dove inserire
      IntBSTNodo p = root, prev = null;
      while (p != null) {
        if (p.key == val) return false;
        prev = p;
        if (p.key < val) p = p.right;
        else p = p.left;
      }
      if (prev.key < val)
        prev.right = new IntBSTNodo(val);
      else
        prev.left = new IntBSTNodo(val);
    }
    return true;
  }
  
  public void print(IntBSTNodo p, int level) {
    if (p != null) {
      print(p.right, level + 1);
      for (int k = 0; k < level; k++) System.out.print("\t\t");
      System.out.println(p.key);
      print(p.left, level + 1);
    }
  }
 
  public void print() {
    System.out.println("\nStruttura orizzontale dell'albero:");
    print(root, 0);
  }
}

class IntBSTNodo {
  protected int key;                    //chiave a numeri interi
  protected IntBSTNodo left, right;     //riferimento nodo sx e dx
    
  //costruttori
  public IntBSTNodo() {
    left = right = null;
  }
  
  public IntBSTNodo(int val) {
    this(val, null, null);
  }
  
  public IntBSTNodo(int val, IntBSTNodo lt, IntBSTNodo rt) {
    key = val;
    left = lt;
    right = rt;
  }
}

//Mini-coda ad oggetti (serve per il metodo insertBalancedTree)
class MiniCoda {
  private MiniLista q;
  public MiniCoda() {
    q = new MiniLista();
  }
  public boolean isEmpty() {
    return q.isEmpty();
  }
  public void enQueue(Object val) {
    q.insertTail(val);
  }
  public Object deQueue() {
    if (isEmpty())
      throw new CodaEmptyException();
    else
      return q.deleteHead();
  }
    
}

//Mini Lettore di valori numerici da tastiera
class MiniConsoleReader {
  private BufferedReader reader;
    
  //costruttore
  public MiniConsoleReader() {
    reader = new BufferedReader(new InputStreamReader(System.in));
  }
  
  public int readInt() {
    int r;
    try {
      String inputString = reader.readLine();
      r = Integer.parseInt(inputString);
    } catch (NumberFormatException e) {
      throw new ConsoleReaderException();
    } catch (IOException e) {
      throw new ConsoleReaderException();
    }
    return r;
  }
}

//eccezione personalizzata
class ConsoleReaderException extends RuntimeException {
  public ConsoleReaderException() {super("Errore Formato di lettura");}
  public ConsoleReaderException(String msg) {super(msg);}
}