/*
  Scrivere un metodo Java NON facente uso di ricorsione, il quale
  attraversi un albero binario a apartire dalla radice, livello
  per livello, da destra a sinistra, memorizzando l'attraversamento
  in una lista concatenata.
      public Lista IterDxSxLevelVisit()
  Definire in maniera completa le classi e i metodi utilizzati
  (solo quelli necessari)
*/

public class II_Prova_Itinere_15_05_2003 {
  
  public static void main(String[] args) {
    //crea e riempie lista
    myBST tree = new myBST();
    for (int k=0; k<10; k++)
      tree.insert(new Integer((int)(Math.random()*100+1)));
    //attraversa albero
    myLista l = tree.IterSxDxLevelVisit();
    //stampa lista e albero
    System.out.println("Elenco valori Lista:");
    l.print();
    System.out.println("\nVisualizzazione Albero");
    tree.print();
  }
}

//Classe Albero
class myBST {
  private myNodoBST root;
  private Object info;
  //builder
  public myBST() {
    root = null;
  }
  //public method
  public myNodoBST getRoot() {
    return root;
  }
  public boolean isEmpty() {
    return (root == null);
  }
  public void insert(Object o) {
    if (isEmpty())
      root = new myNodoBST(o);
    else {
      myNodoBST p = root, prev = null;
      while (p != null) {
        if ( ((Comparable)p.getInfo()).compareTo(o) == 0) return;
        prev = p;
        if ( ((Comparable)p.getInfo()).compareTo(o) > 0) p = p.getLeft();
        else p = p.getRight();
      }
      if ( ((Comparable)prev.getInfo()).compareTo(o) > 0)
        prev.setLeft(new myNodoBST(o));
      else
        prev.setRight(new myNodoBST(o));
    }
  }
  private void print(myNodoBST p, int liv) {
    if (p != null) {
      print(p.getRight(), liv + 1);
      for (int k=0; k<liv; k++) System.out.print("\t\t");
      System.out.println(p.getInfo());  
      print(p.getLeft(), liv + 1);
    }
  }
  public void print() {
    print(root, 0);
  }
  //Restituisce una Lista con i nodi ordinati per livello
  //(Attraversamento in ampiezza alto/basso, sinistra/destra)
  public myLista IterSxDxLevelVisit() {
    myLista l = new myLista();
    myCoda c = new myCoda();
    myNodoBST p = root;
    if (p == null) return null;
    c.enQueue(p);
    while (!c.isEmpty()) {
      p = (myNodoBST)c.deQueue();
      l.insertTail(p.getInfo());
      if (p.getRight() != null) c.enQueue(p.getRight());
      if (p.getLeft() != null) c.enQueue(p.getLeft());
    }
    return l;
  }

}

//classe per Albero
class myNodoBST {
  private Object info;
  private myNodoBST left, right;
  //builder
  public myNodoBST(Object o) {
    this(o, null, null);
  }
  public myNodoBST(Object o, myNodoBST l, myNodoBST r) {
    info = o; left = l; right = r;
  }
  public myNodoBST getLeft() {
    return left;
  }
  public myNodoBST getRight() {
    return right;
  }
  public void setLeft(myNodoBST l) {
    left = l;
  }
  public void setRight(myNodoBST r) {
    right = r;
  }  
  public Object getInfo() {
    return info;
  }
  public void setInfo(Object o) {
    info = o;
  }
  
}

//Coda ad oggetti
class myCoda {
  private myLista elem;
  //builder
  public myCoda() {
    elem = new myLista();
  }
  //public method
  public boolean isEmpty() {
    return elem.isEmpty();
  }
  public void enQueue(Object o) {
    elem.insertTail(o);
  }
  public Object deQueue() {
    if (isEmpty())
      throw new EmptyMyCodaException();
    return elem.deleteHead();
  }
  public Object getHead() {
    return elem.getHead().getInfo();
  }
}

//classe di errore per myCoda
class EmptyMyCodaException extends RuntimeException {
  public EmptyMyCodaException() {super("Coda Vuota!");}
}

//Lista ad oggetti
class myLista {
  private myNodo head;
  //builder
  public myLista() {
    head = null;
  }
  //public method
  public boolean isEmpty() {
    return (head == null);
  }
  public myNodo getHead() {
    return head;
  }
  public void insertHead(Object o) {
    head = new myNodo(o, head);
  }
  public void insertTail(Object o) {
    if (isEmpty())
      head = new myNodo(o, head);
    else {
      myNodo n = head;
      for (; n.getNext() != null; n = n.getNext());
      n.setNext(new myNodo(o));
    }
  }
  public Object deleteHead() {
    if (isEmpty())
      return null;
    else {
      myNodo n = head;
      head = head.getNext();
      return n.getInfo();
    }
  }
  public void print() {
    for (myNodo n = head; n != null; n = n.getNext())
      System.out.print(n.getInfo() + "\t");
      System.out.println();
  }
}

//Nodo per Lista semplicem concatenata
class myNodo {
  private Object info;
  private myNodo next;
  //builder
  public myNodo(Object o) {
    this(o, null);
  }
  public myNodo(Object o, myNodo n) {
    info = o;
    next = n;
  }
  public Object getInfo() {return info;}
  public void setInfo(Object o) {info = o;}
  public myNodo getNext() {return next;}
  public void setNext(myNodo n) {next = n;}
  
}