/* **************************************************************
   Esame del 12/12/2002
   Definire una classe Java TreeList per una lista
   linkata semplice in modo che i singoli nodi possano
   contenere radici di alberi binari.
   
   Scrivere un metodo Java per la classe TreeList che ordini
   la lista con l'algoritmo dell'Insertion Sort in base alle
   altezze degli alberi.
   **************************************************************/

public class TreeList {
  
  //testa della lista
  private NodeTree head;
  private NodeTree pointer;
  private boolean firstTime = true;
  
  //costruttori
  public TreeList() {
    head = null;
  }
  public TreeList(IntBST t) {
    head = new NodeTree(t);
  }
  
  //metodi pubblici
  public boolean isEmpty() {
    return (head == null);
  }
  
  public void insertHead(IntBST t) {
    head = new NodeTree(t, head);
  }

  public void insertTail(IntBST t) {
    if (isEmpty())
      insertHead(t);
    else {
      NodeTree aux = head;
      for (; aux.getNext() != null; aux = aux.getNext());
      aux.setNext(new NodeTree(t));
    }
  }
  
  public void rewind() {
    if (!isEmpty())
      pointer = head;
  }
  
  public IntBST getNextElem() {
    if (isEmpty())
      throw new EmptyListException();
    else {
      if (firstTime) {
        rewind();
        firstTime = false;
      }
      if (pointer == null)
        throw new BottomOfListException();
      else {
        IntBST aux = pointer.getTree();
        pointer = pointer.getNext();
        return aux;
      }
    }
  }
  
  /* ****************************************************************
     Ordinamento INSERTION SORT in base
    alle altezze degli alberi
     *************************************************************** */
  public void ListSort() {
    NodeTree i, j, prevExt, prevInt, tmp;
    
    //Ciclo esterno: parte dal secondo nodo fino alla fine (i!=null)
    for (i = head.getNext(), prevExt = head;
         i != null; prevExt = i, i = i.getNext()) {
           
      //Ciclo che scorre dal 1°nodo -> i (o fino i <= nodi precedenti)
      for (j = head, prevInt = null;
           j != i && ((Comparable)i).compareTo(j) >= 0;
           prevInt = j, j =j.getNext());
        
      if (((Comparable)i).compareTo(j) < 0) {
          //stacca nodo i-esimo (conserva in temp)
          tmp = i;
          prevExt.setNext(i.getNext());
          //riattaccalo...
          if (prevInt == null) {   //...in testa alla lista
            tmp.setNext(head);
            head = tmp;
          }
          else {                //... oppure tra prev e j
          prevInt.setNext(tmp);
          tmp.setNext(j);
          }
      }
    }
  }
  
}

//Classe Nodo per TreeList
/* Questa classe stabilisce un criterio di ordinamento basato
   sull'altezza dell'albero BST che contiene. E' sufficiente confrontare
   il nodo con un altro nodo usando il metodo ridefinito compareTo()
   Es: if (nodoX.compareTo(nodoY) < 0) ...
*/
  
class NodeTree implements Comparable {
  private IntBST tree;
  private NodeTree next;
    
  //costruttori  
  public NodeTree(IntBST t) {
    this(t, null);
  }
  public NodeTree(IntBST t, NodeTree link) {
    tree = t;
    next = link;
  }
  
  //metodi pubblici
  public IntBST getTree() {return tree;}
  public void setTree(IntBST t) {tree = t;}
  public NodeTree getNext() {return next;}
  public void setNext(NodeTree link) {next = link;}
  
  //stabilisce criterio di ordinamento
  public int compareTo(Object th) {
    return (
      (tree.altezza() < ((NodeTree)th).getTree().altezza())? -1 :
      (tree.altezza() > ((NodeTree)th).getTree().altezza())? 1 : 0
    );
  }
  
}