/**
  * Fondamenti di Informatica 1 - gr. 89
  * Prova pratica di programmazione in data 1 Settembre 2008
  * classe MyMap Map
  * realizza un dizionario
  *
  * @author Adriano Luchetta
  * @version 26-09-2008
  *
  */
import java.util.NoSuchElementException;

public class MyMap implements Map
{
   private static final int CAPACITY = 97;
   
   private ListNode[] v;
   private int vSize;
   
   public MyMap()
   {
      v = new ListNode[CAPACITY];
      for (int i = 0; i < v.length; i++)
         v[i] = new ListNode();
      vSize = 0;
   }
   
   // O(n/CAPACITY)
   public void insert(Comparable key, Object x)
   {
      Pair p = new Pair(key, x);
      ListNode n = findNode(key);
      if (n.next != null)
         n.next.element = p;
      else
      {
         n.next = new ListNode(p, null);
         vSize++;
      }
   }

   // O(n/CAPACITY)
   public Object find(Comparable key)
   {
      ListNode n = findNode(key);

      if (n.next != null)
         return n.next.element.x;
      else
         throw new NoSuchElementException();
   }
   
   // O(n/CAPACITY)
   public void remove(Comparable key)
   {
      ListNode n = findNode(key);

      if (n.next != null)
      {
         n.next = n.next.next;
         vSize--;
      }
      else
         throw new NoSuchElementException();
   }
   
   public boolean isEmpty()
   {
      return vSize == 0;
   }

   public int size()
   {
      return vSize;
   }
   
   public String[] toStringArray()
   {
      String[] s = new String[vSize];
      int j = 0;
      for (int i = 0; i < v.length; i++)
      {
         ListNode n = v[i];
         while (n.next != null)
         {
            s[j++] = n.next.element.toString();
            n = n.next;
         }
      }
      return s;
   }

   // O(n/CAPACITY)
   private ListNode findNode(Comparable key)
   {
      int h = Math.abs(key.hashCode()) % CAPACITY;

      ListNode tmp = v[h];
      
      while (tmp.next != null)
      {
         if (key.compareTo(tmp.next.element.key) == 0)
            return tmp;
         tmp = tmp.next;
      }
      
      return tmp;
   }

   class Pair
   {
      Comparable key;
      Object x;
      
      Pair(Comparable k, Object obj)
      {
         key = k;
         x = obj;
      }
      
      public String toString()
      {
         return key + " " + x;
      }
   }

   class ListNode
   {
      Pair element;
      ListNode next;
      
      ListNode(Pair e, ListNode n)
      {
         element = e;
         next = n;
      }
      
      ListNode()
      {
         this(null, null);
      }
   }

}