/**
  * MyMap
  * realizzazione con hashTable
  * Prova pratica di programmazione del 9-1-2008
  * @author A. Luchetta
  */
  
import java.util.NoSuchElementException;

public class MyMap implements Map
{
   private static final int DIM = 97;
   
   private ListNode[] v;
   private int size;
   
   public MyMap()
   {
      v = new ListNode[DIM];
      for (int i = 0; i < v.length; i++)
         v[i] = new ListNode();

      size = 0;
   }
   
   /**
      restituisce il numero di elementi presenti nel contenitore
      @return il numero di elementi nel contenitore
   */
   public int size()
   {
      return size;
   }

   /**
      se la chiave non e' presente, inserisce la coppia key/x nel
      dizionario, altrimenti sovrascrive la coppia presente con la coppia
      key/x
      complessita' temporale: O(n/DIM)
      @param key la chiave
      @param x l'attributo
   */
   public void insert(Comparable key, Object x)
   {
      Pair p = new Pair(key, x);
      ListNode n = search(p);

      if (n.next != null)
         n.next.element = p;
      else
      {
         n.next = new ListNode(p, n.next);
         size++;
      }
   }

   /**
      se la chiave e' presente nel dizionario restituisce l'attributo
      associato, altrimenti genera l'eccezione java.util.NoSuchElementException
      complessita' temporale: O(n/DIM)
      @param key la chiave
      @return l'attributo associato alla chiave, se presente
      @throws java.util.NoSuchElementException se la chiave non e' presente
   */
   public Object find(Comparable key) throws java.util.NoSuchElementException
   {
      Pair p = new Pair(key, null);
      ListNode n = search(p);

      if (n.next == null)
         throw new NoSuchElementException();

      return n.next.element.attr;
   }

   /**
      la chiave e' presente elimina la coppia key/x dal dizionario,
      altrimenti genera l'eccezione java.util.NoSuchElementException
      complessita' temporale: O(n/DIM)
      @param key la chiave
      @throws java.util.NoSuchElementException se la chiave non e' presente   
   */
   public void remove(Comparable key) throws java.util.NoSuchElementException
   {
      Pair p = new Pair(key, null);
      ListNode n = search(p);

      if (n.next == null)
         throw new NoSuchElementException();

      n.next = n.next.next;
      size--;
   }

   /*
      se la coppia non e' presente restituisce -1, altrimenti
      restituisce l'indice al quale si trova la coppia
      ricerca binaria
      complessita' temporale: O(n/DIM)
   */
   private ListNode search(Pair p)
   {
      ListNode n = v[p.hashCode()];
      
      while (n.next != null)
      {
         if (n.next.element.compareTo(p) == 0)
            return n;
            
         n = n.next;
      }
      
      return n;
   }

   /*
      classe interna Pair
   */
   class Pair implements Comparable<Pair>
   {
      Comparable key;
      Object attr;
      
      Pair(Comparable c, Object x)
      {
         key = c;
         attr = x;
      }
      
      public int compareTo(Pair p)
      {
         return key.compareTo(p.key);
      }
      
      public int hashCode()
      {
         int h = key.hashCode();
         return (h >= 0 ? h : -h) % DIM;
      }
      
   }
   
   /*
      classe interna ListNode
   */
   class ListNode
   {
      Pair element;;
      ListNode next;
      
      ListNode(Pair p, ListNode n)
      {
         element = p;
         next = n;
      }
      
      ListNode()
      {
         this(null, null);
      }
   }
}