/** DconTabellaHash.java --  dizionario con tabella hash
  * Prova di programmazione del 24-Sett-2003
  * Effettua il calcolo della frequenza delle parole in un  testo
  * tramite un dizionario.
  * Il dizionario e' realizzato con una tabella hash.
  * @author F. Bombi modificato da A. Luchetta
  * @version 27-Nov-2006
  */
import java.util.NoSuchElementException;

public class DconTabellaHash implements Dizionario
{
  // parte privata della classe
  private static final int HASHTABLE_DIM = 97;

  private ListNode[] v;
  private int size; //num. elementi nel dizionario

  public DconTabellaHash() //il costruttore
  {
    v = new ListNode[HASHTABLE_DIM];
    size = 0;

    //inizializzazione dei bucket con liste concatenate vuote
    for (int i = 0; i < HASHTABLE_DIM; i++)
      v[i] = new ListNode(null, null); //lista concatenata vuota
  }

  /*
    calcola l'hashCode della stringa s
    NB: il codice restituito e' nell'intervallo 0 <= hasCode < HASHTABLE_DIM
    @param s stringa di cui calcolare il codice di hash
    @return il codice di hash
  */
  private static 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);
       h = h % HASHTABLE_DIM;   // il codice calcolato e' sempre >= 0
    }

 	  return h;
  }

   /*
    se la chiave String x non e' presente, ritorna
    l'ultimo nodo del bucket, altrimenti ritorna il
    riferimento al nodo che precede quello contenente la
    chiave String x.
    NB: se la lista concatenata e' vuota ritorna l'header del bucket
    @param chiave con cui effettuare la ricerca
    @return il nodo precedente al nodo che contiene la chiave specificata
    se la chiave e' presente, l'ultimo nodo del bucket se la chiave non e' presente
   */
   private ListNode trovaNodo(String x)
   {
      ListNode tmp = v[hash(x)]; //header del bucket
  
      while (tmp.next != null)
        if ((tmp.next.element.ch).equals(x))
          break;
        else
          tmp = tmp.next;
               
      return tmp;
   }

   /**
     inserisce la coppia key/value nel dizionario
     La chiave e' univoca.
     L’inserimento va sempre a buon fine:
     se la chiave non esiste, la coppia
     viene aggiunta al dizionario;
     se la chiave esiste già, il valore ad
     essa associato viene sovrascritto con
     il nuovo valoreComplessita' temporale O(n/M)
     @param key chiave comparabile
     @param attributo valore associato alla chiave
   */
   public void inserisci(String chiave, int attributo)
   {
      ListNode nodo = trovaNodo(chiave);

      Coppia nuovaCoppia = new Coppia(chiave, attributo);
   
      if (nodo.next != null)
         nodo.next.element = nuovaCoppia;
      else
      {  nodo.next = new ListNode(nuovaCoppia, null);
        	size++;
      }
   }
 
  /**
     verifica se e' presente la chiave specificata
     Complessita' temporale O(n/M)
     @param x chiave per la verifica
     @return true se la chiave e' presente, false altrimenti
  */
   public boolean presente(String x)
   {
      ListNode nodo = trovaNodo(x);
      return nodo.next != null;
   }
   
   /**
      restituisce il valore associato alla chiave specificata
      nel dizionario.
      Complessita' temporale O(n/M)
      @param key chiave per la ricerca
      @return valore associato alla chiave se la chiave e'
      presente, null altrimenti
      @throws java.util.NoSuchElementException se la coppia
      <chiave, valore> non e' presente nel dizionario
   */
   public int cerca(String x) throws NoSuchElementException
   {
       ListNode nodo = trovaNodo(x);

       if (nodo.next != null)
         return nodo.next.element.att;
   
      throw new NoSuchElementException();
   }

   /**
      restituisce i dati del dizionario in un array di lunghezza
      pari al numero di coppie contenute nel dizionario.
      NB: l'array restituito e' diverso dall'array usato
      come variabile di esemplare della classe per memorizzare
      le coppie.
      Complessita' temporale O(n)
      Nell'array di ritorno vengono poste copie delle coppie
      del dizionario
      @return array contenente le coppie del dizionario
   */
   public Coppia[] toArray() // restituisce copie!!!
   {
     Coppia[] c = new Coppia[size];
 
     int j = 0;
     for (int i = 0; i < HASHTABLE_DIM; i++)
     {
       ListNode nodo = v[i];
       while (nodo.next != null)
       {
         String chiave = nodo.next.element.ch;
         int attributo = nodo.next.element.att;
         Coppia copia = new Coppia(chiave, attributo);
         c[j++] = copia; //copia della Coppia
 
         nodo = nodo.next;
       }
     }
 
     return c;
   }

   //classe interna
   class ListNode
   {
      Coppia element;
      ListNode next;
    	  
      ListNode(Coppia e, ListNode n)
      {  element = e;
         next = n;
      }
   }
}