/* **********************************
        ESAME DEL 18/07/2002
   ********************************** */

public class Esame_18_07_2002 {
  public static void main(String[] args) {
    
    //creo la lista
    ListaDbl l = new ListaDbl();
    
    /*la riempio di 10 nodi di oggetti "Dati" contenenti
      numeri casuali nella chiave numerica
    */
    for (int k=0; k<10; k++)
      l.InsertTail(new Dati("prova",(int)(Math.random()*5 + 1)));
    
    //Ordino la lista
    ListDblSortBySelection(l);
    //Stampo la lista
    Stampa(l);
    //Mostra la chiave col più alto numero di occorrenze
    System.out.println("Chiave col più alto numero di occorrenze: "
                       + KeyMaxRepeat(l));
  }
  
  public static void Stampa(ListaDbl lista) {
    lista.rewind();
    try {
      for (;;) System.out.println(lista.getNextElem());
    } catch (BottomOfListException e) {}    
  }
  
  /* Scrivere un metodo statico in Java che, data in input una lista
     disordinata di oggetti doppiamente concatenata, ne ordini gli
     elementi ridefinendo opportunamente i riferimenti tra gli oggetti.
     Si utilizzi l'algoritmo del Selection Sort. Ammettere che gli
     oggetti possano avere chiavi ripetute. Assumere che la chiave
     sia un intero.
  */
  public static void ListDblSortBySelection(ListaDbl lista) {
    //ordina lista con Selection Sort
    NodoDbl i = lista.getHead(), j, least;
    for (; i.getNext() != null; i = i.getNext()) {
      for (j = i.getNext(), least = i; j != null; j = j.getNext())
        if ( ((Comparable)j.getInfo()).compareTo(least.getInfo()) < 0)
          least = j;
      if (i != least) {
        //swap(i, least)
        Object tmp = i.getInfo();
        i.setInfo(least.getInfo());
        least.setInfo(tmp);
      }
    }
  }
  
  /* Scrivere un metodo statico Java che, data in input una
     lista ordinata di oggetti doppiamente concatenata con
     chiavi ripetute, restituisca la chiave col maggior
     numero di occorrenze.
  */
  public static int KeyMaxRepeat(ListaDbl lista) {
    NodoDbl i = lista.getHead();
    int val = 0, old = 0, max = 0, cntoccor = 0, maxocc = 0;
    for (; i != null; i = i.getNext()) {
      //preleva valore dalla lista dall'oggetto "Dati"
      val = ((Dati)i.getInfo()).getVal();
      if (val != old) {         //***C'è un nuovo valore, occupiamoci del preced.:***
        if (max < cntoccor) {   //il n° di occorr preced. era > max?
          max = cntoccor;       //Si, aggiorna il max xkè il num cercato è...
          maxocc = old;         //...finora, quello precedente!
        }                       //***Occupiamoci del numero nuovo:****
        cntoccor=1;             //è la prima occorrenza
        old = val;              //da adesso sarà il riferim "precedente"
      }
      else                      //val è uguale al numero precedente, quindi...
        cntoccor++;             //...aggiorna il conteggio delle occorrenze
    }                           //***FINE DEL CICLO***
    if (val == old)             //L'ultimo numero era uguale al preced?
      if (max < cntoccor)       //SI? Potrebbe essere quello con max occorrenze?
        maxocc = old;           //Si! L'ultimo numero è quello cercato.
    return maxocc;
  }
}

//Classe di oggetti da inserire nella lista
class Dati implements Comparable {
  private String info;
  private int val;
  //constructor
  public Dati() {
    this("", 0);
  }
  public Dati(String i, int v) {
    info = new String(i);
    val = v;
  }
  
  public int getVal() {return val;}
  
  //Stabilisce criterio di ordinamento
  public int compareTo(Object o) {
    return
    ((val > ((Dati)o).getVal()) ? 1 :
    (val < ((Dati)o).getVal()) ? -1 : 0);
  }
  
  //Ridefinisce toString per restituire un valore
  public String toString() {
    return val + " " + info;
  }
}