/**
  * classe TR
  * realizza un dizionarion con una hashtable
  * Esercizio di programmazione del 6-Dic-2007
  *
  * @author A. Luchetta
  */
  
public class TR  // -- dizionario
{
   //variabili statiche
   private final static int HASHTABLE_DIM = 89;
   
   // variabili di esemplare
   private ListNode[] v;
   
   /**
      inizializza una tabella vuota
   */
   public TR()
   {
      v = new ListNode[HASHTABLE_DIM];
      for (int i = 0; i < v.length; i++)
         v[i] = new ListNode();
   }

   /**
      aggiungi una coppia al contenitore
   */
   public void aggiungi(String s1, String s2)
   {
      ListNode n = findNode(s1);
      Coppia c = new Coppia(s1, s2);
      
      if (n.next == null)
         n.next = new ListNode(c, null);
      else
         n.next.element = c;         
   }
   
   /**
      restituisce l'attributo associato alla chiave s
      @return l'attributo associato alla chiave data
   */
   public String traduci(String s)
   {
      ListNode n = findNode(s);
      
      if (n.next == null)
         return null;

      return n.next.element.att;
   }
   
   /**
      restituisce la descrizione testuale
      @return descrizione testuale una coppia per riga
   */
   public String toString()
   {
       String tmp = "";
       
       for (int i = 0; i < v.length; i++)
       {
          ListNode n = v[i].next;
          
          while (n != null)
          {
             tmp = tmp + n.element + "\n";
             n = n.next;
          }
       }
        
       return tmp;
   }
   
   /* 
      funzione di hash. Restituisce una chiave ridotta per la stringa data
      @param s stringa di cui calcolare la chiave ridotta
      @return un numero intero compreso nell'intervallo [0, HASHTABLE_DIM - 1]
   */
   
   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)) % HASHTABLE_DIM;
         
      return h;   
   }
   
   /*
     trova la coppia che contiene la chiave data
     se la chiave e' presente, ritorna il nodo precedente
     se la chiave non e' presente restituisce l'ultimo nodo della lista
     @return nodo precedente al nodo che contiene la coppia con la chiave data
      se la chiave e' presente, l'ultimo nodo del bucket se la chiave non e'
      presente
   */  
   private ListNode findNode(String ch)
   { 
      ListNode n = v[hash(ch)];
      
      /*
         attenzione: se si usa il metodo hashCode della classe String
         si deve calcolare il valore assoluto della chiave ridotta h
         (il cui valore puo' essere negativo) e poi calcolare con
         l'operazione modulo il resto della divisione per HASHTABLE_DIM
      
         int h = ch.hashCode();
         h = Math.abs(h) % HASHTABLE_DIM;
         ListNode n = v[h];
      
      */ 
      
      while (n.next != null)
      {
         if (n.next.element.chiave.equals(ch))
            break;
            
         n = n.next;   
      }
      
      return n;
   }


   // classe interna
   class Coppia
   {
      String chiave;
      String att;
      
      public Coppia(String c, String a)
      {
         chiave = c;
         att = a;
      }
      
      public String toString()
      {
         return chiave + " " + att;
      }
   }
   
   // classe interna 
   class ListNode
   {
      Coppia element;
      ListNode next;
      
      public ListNode(Coppia e, ListNode n)
      {
         element = e;
         next = n;
      }
      
      public ListNode()
      {
         this(null, null);
      }
   }
}