/*
  ESAME di PROGRAMMAZIONE II E LABORATORIO DEL 18/06/2003
  -----------------------------------------------------------------------------
  Scrivere un metodo Java statico che, utilizzando l'algoritmo del Selection Sort,
  riordini una lista semplicemente linkata. Ogni nodo della lista contiene,
  come campo, un tipo Object. Il riordino deve avvenire spostando completamente
  i nodi.
  Definire inoltre una classe di oggetti completamente ordinabile da usare
  per il metodo precedente. Ogni oggetto contiene due chiavi a valori interi
  key1 e key2, con key1 chiave primaria. La key1 puņ essere con ripetizioni.
  In caso di uguaglianza di key1 l'ordinamento procede con key2.
*/

public class Esame_18_06_2003 {
  
  public static void main(String[] args) {
    //Crea lista e la riempie di numeri casuali
    Lista mylista = new Lista();
    for (int k = 0; k < 10; k++)
      mylista.insertHead(new Dato(
        (int)(Math.random()*10 + 1),
        (int)(Math.random()*100 + 1)
      ));
    //Stampa della lista  
    System.out.println("\n**************************************************");
    System.out.println("Ordinamento una lista semplicemente concatenata di " +
                       "\noggetti con doppia chiave. (Algoritmo Selection Sort)");
    System.out.println("**************************************************");
    System.out.println("Lista non ordinata:");
    mylista.print();
    SelectionSort(mylista);
    System.out.println("Lista ordinata:");
    mylista.print();
  }
  
  //Il metodo richiesto:
  public static void SelectionSort(Lista l) {
    Nodo i, j, least, tmp, previ, prevj, prevleast = null;
    for (i = l.getHead(), previ = null; i.getNext() != null;
          previ = i, i = i.getNext())
    {
      for (j = i.getNext(), prevj = i, least = i; j != null;
            prevj = j, j = j.getNext())
      
        if ( ((Comparable)j.getInfo()).compareTo(least.getInfo()) < 0) {
          least = j;            //Nuovo minore: least
          prevleast = prevj;    //Nodo precedente a least
        }
        
      if (least != i) {
        //scambia nodi
        tmp = least;
        prevleast.setNext(least.getNext());
        if (previ == null) {
          tmp.setNext(l.getHead());
          l.setHead(tmp);
        }
        else {
          previ.setNext(tmp);
          tmp.setNext(i);
        }
        i = tmp;     //Porta indietro i di un nodo
      }
    }
  }

}


//classe di oggetti ordinabile
class Dato implements Comparable {
  private int key1, key2;       //le chiavi primaria e secondaria
  private Object more;          //altre informazioni...
  //costruttori
  public Dato(int v1) {
    this(v1, 0, null);
  }
  public Dato(int v1, int v2) {
    this(v1, v2, null);
  }
  public Dato(int v1, int v2, Object o) {
    key1 = v1;
    key2 = v2;
    more = o;
  }
  //Metodi pubblici
  public int getKey1() {
    return key1;
  }
  public int getKey2() {
    return key2;
  }
  public Object getMore() {
    return more;
  }
  //ridefinizione di compareTo
  public int compareTo(Object o) {
    if (key1 != ((Dato)o).getKey1())
      return ( (key1 < ((Dato)o).getKey1()) ? -1 :
               (key1 > ((Dato)o).getKey1()) ?  1 : 0);
    else
      return ( (key2 < ((Dato)o).getKey2()) ? -1 :
               (key2 > ((Dato)o).getKey2()) ?  1 : 0);
      
  }
  //ridefinizione di toString
  public String toString() {
    return "" + key1 + "(" + key2 + ")";
  }
}


//La classe lista
class Lista {
  private Nodo head;
  //costruttore
  public Lista() {
    head = null;
  }
  //metodi pubblici
  public Nodo getHead() {
    return head;
  }
  public void setHead(Nodo h) {
    head = h;
  }
  public boolean isEmpty() {
    return (head == null);
  }
  public void insertHead(Object o) {
    head = new Nodo(o, head);
  }
  //metodo per la stampa della lista
  public void print() {
    for (Nodo aux = head; aux != null; aux = aux.getNext())
      System.out.print(((Dato)aux.getInfo()) + "\t");
    System.out.println("\n");
  }
}


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