/**
  Compito del 24-Dic-2001
  
  Il database viene realizzato con un array non ordinato.
  La chiave del dizionario sia il nome dello studente.
  
  @author A. Luchetta
  @version 28-11-2003
  @version 21-Nov-2005
*/

public class ScuolaHashTable
{
  // costanti
  private final int HASHTABLE_SIZE = 101;

  // variabili di esemplare
  private ListNode[] studenti;
  private int numeroStudenti;

  public ScuolaHashTable()
  {
    // bucket senza nodo sentinella (nodo head)
    // altre volte abbiamo usato il bucket con nodo sentinella
    studenti = new ListNode[HASHTABLE_SIZE];
    numeroStudenti = 0;
  }

  /**
  Aggiunge alla lista interna una nuova istanza di classe studente,
  verificando che il nome non sia gia' presente, nel qual caso non
  viene eseguita alcuna azione.
  Complessita' temporale: O(n/HASHTABLE_SIZE)
  @param nome nome dello studente
  */
  public void aggiungiStudente(String nome)
  {
    // accesso all'array tramite chiave ridotta calcolata
    int h = hash(nome);          // chiave ridotta calcolata tramite funzione di hash
    ListNode nodo = studenti[h]; // primo nodo del bucket

    // Studente da ricercare
    Studente studente = new Studente(nome);
    Coppia nuovoStudente = new Coppia(nome, studente);
    
    while (nodo != null)
    {
      Coppia questoStudente = nodo.getElement();
      if (questoStudente.equals(nuovoStudente))
        return;
      else
        nodo = nodo.getNext();
     }

     // inserimento in testa al bucket
     // altre volte abbiamo inserito in coda, ma e' piu' scomodo
     studenti[h] = new ListNode(nuovoStudente, studenti[h]);
     numeroStudenti++;
  }

  /**
    Aggiorna le informazioni interne per riportare che il dato studente ha sostenuto
    il dato esame col dato voto.
    Complessita' temporale: in media O(n/HASHTABLE_SIZE)
    @param studente nome dello studente
    @param esame nome dell'esame di cui si inserisce il voto
    @param voto voto dell'esame
  */
  public void aggiornaCurriculum(String studente, String esame, int voto)
  {
    // accesso all'array tramite chiave ridotta
    int h = hash(studente);      // chiave ridotta calcolata tramite funzione di hash
    ListNode nodo = studenti[h]; // primo nodo del bucket

    Coppia studenteDaAggiornare = new Coppia(studente, new Studente(studente));

    while (nodo != null)
    {
      Coppia questoStudente = nodo.getElement();
      if (questoStudente.equals(studenteDaAggiornare))
      {
        questoStudente.getAttributo().aggiungiEsame(esame, voto);
        break;
      }
      else
        nodo = nodo.getNext();
    }
  }

  /**
    scrive nello standard output la lista degli studenti, il numero di esami sostenuti, e la media dei voti.
    La lista dovra' essere ordinata nell'ordine della media.
    Complessita' temporale: e' quella dell'ordinamento:
    - O(n^2) in caso di ordinamento per selezione o inserimento
    - O(n log n) in caso di ordinamento per fusione
  */
  public void stampa()
  {
    // array di studenti
    Studente[] lista = toArray();

    // Ordinamento tramite classe Ordinatore
    Ordinatore sorter = new Ordinatore(lista);
    sorter.ordina();

    // stampa degli oggetti di classe studente
    for (int i = 0; i < numeroStudenti; i++)
      System.out.println(lista[i]);
  }

  // classe ListNode per realizzare i bucket
  private class ListNode
  {
    private Coppia element;
    private ListNode next;

    public ListNode(Coppia unaCoppia, ListNode prossimoNodo)
    {
      element = unaCoppia;
      next = prossimoNodo;
    }

    // metodi accessori
    public Coppia getElement() { return element;}
    public ListNode getNext() { return next; }
  }

  /*
    metodo privato per il calcolo della chiave ridotta
    @param s la stringa di cui si vuole calcolare il codice di hash
    @return il codice di hash (nell'intervallo [0, HASHTABLE_SIZE - 1]

    per calcolare il codice di hash si puo' usare in alternativa il metodo hashCode()
    della classe String:
    int h = s.hashCode() % HASHTABLE_SIZE
    s Stringa di cui si vuole calcolare il codice di hash
    ***ATTENZIONE se h è negativo, cambiarlo di segno!!!
  */
  private int hash(String s)
  {
    final int HASH_MULTIPLIER = 31;
    
    int h = 0;
    
    for (int i = 0; i < s.length(); i++)
      h = (HASH_MULTIPLIER * h + s.charAt(i)) % HASHTABLE_SIZE;
       
    return h;
  }
  
  // metodo privato per ricavare un array che contiene gli studenti
  private Studente[] toArray()
  {
    Studente[] arrayStudenti = new Studente[numeroStudenti];

    int j = 0;
    for (int i = 0; i < HASHTABLE_SIZE; i++)
    {
      ListNode nodo = studenti[i];

      while (nodo != null)
      {
        arrayStudenti[j++] = nodo.getElement().getAttributo();
        nodo = nodo.getNext();
      }
    }

    return arrayStudenti;
  }

  private class Coppia
  {
    // variabili di istanza
    private String chiave;
    private Studente attributo;
    
    // costruttore
    public Coppia(String ch, Studente att)
    {
      chiave = ch;
      attributo = att;
    }

    // metodi accessori
    public String getChiave() { return chiave; }
    public Studente getAttributo() { return attributo; }

    // override del metodo boolean equals(Object obj) della classe Object
    public boolean equals(Object obj)
    {
      Coppia altraCoppia = (Coppia) obj;
      return chiave.equals(altraCoppia.chiave);
    }
  }
  
  public static void main(String args[])
  {
    ScuolaHashTable scuola = new ScuolaHashTable();
    scuola.aggiungiStudente("Rossi");
    scuola.aggiungiStudente("Bianchi");
    scuola.aggiungiStudente("Verdi");
    scuola.aggiornaCurriculum("Rossi", "Fondamenti di Informatica 1", 23);
    scuola.aggiornaCurriculum("Rossi", "Matematica A", 19);
    scuola.aggiornaCurriculum("Rossi", "Fisica 1", 24);
    scuola.aggiornaCurriculum("Bianchi", "Fondamenti di Informatica 1", 18);
    scuola.aggiornaCurriculum("Bianchi", "Matematica A", 19);
    scuola.aggiornaCurriculum("Bianchi", "Fisica 1", 20);
    scuola.aggiornaCurriculum("Verdi", "Fondamenti di Informatica 1", 30);
    scuola.aggiornaCurriculum("Verdi", "Matematica A", 30);
    scuola.aggiornaCurriculum("Verdi", "Fisica 1", 27);

    scuola.stampa();
  }
}