/*
  ******* Prova di verifica del 5.6.03 - Primo turno *******
  Sia L una lista semplicemente concatenata di oggetti la cui chiave
  sia un valore intero. Ammettere che gli oggetti possano avere
  chiavi ripetute.
  Si scriva un metodo Java che riordini la lista L disordinata,
  in modo decrescente in base al valore delle chiavi.
  Si utilizzi l'algoritmo del Bubble Sort.
*/

public class Verifica_05_06_03 {
  public static void main(String[] args) {
    //Test metodo
    MyLista l = new MyLista();
    for (int k = 0; k < 10; k++)
      l.insertHead(new Dato((int)(Math.random()*100+1)));
    
    l.stampa();                 //prima della "cura"
    BubbleSortList(l);
    l.stampa();                 //Dopo la "cura"
  }
  
  
  /* Bubble sort modificato ma "speculare" nelle direzioni dei cicli
     rispetto all'originale, quindi equivalente.
     Ciclo esterno: intero "i" dal numero dei nodi -> 2°nodo (decrescente)
     Ciclo interno: dal 1° nodo -> al nodo i-esimo -1 (crescente)
  */
  public static void BubbleSortList(MyLista l) {
    for (int i = l.getNumNodi(); i > 1; i--) {
      int cnt = 1;
      for (MyNodo n = l.getHead(); cnt < i;
          cnt++, n = n.getNext()) {
        if ( ((Dato)n.getInfo()).compareTo(n.getNext().getInfo()) < 0) {
          //swappa
          Dato tmp = (Dato)n.getInfo();
          n.setInfo(n.getNext().getInfo());
          n.getNext().setInfo(tmp);
        }
      }
    }
  }
}

class Dato implements Comparable {
  private int val;
  private Object altro;
  //costruttore
  public Dato(int valore) {
    val = valore;
    altro = null;
  }
  
  public int getVal() {
    return val;
  }
  public void setVal(int valore) {
    val = valore;
  }
  
  public int compareTo(Object o) {
    return (
    (val < ((Dato)o).getVal()) ? -1 :
    (val > ((Dato)o).getVal()) ?  1 : 0
    );
  }
}

class MyLista {
  private MyNodo head;
  //costruttore
  public MyLista() {
    head = null;
  }
  //metodi pubblici
  public MyNodo getHead() {
    return head;
  }
  public void insertHead(Object o) {
    head = new MyNodo(o, head);
  }
  public int getNumNodi() {
    int cnt = 0;
    for (MyNodo n = head; n != null; n = n.getNext(), cnt++);
    return cnt;
  }
  public void stampa() {
    for (MyNodo n = head; n != null; n = n.getNext())
      System.out.print("\t" + ((Dato)n.getInfo()).getVal());
    System.out.println();
  }

}

class MyNodo {
  private Object info;
  private MyNodo next;
  //costr
  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;}
}