/**
  * 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 = 1;
   
   private Pair[] v;
   private int vSize;
   
   public MyMap()
   {
      v = new Pair[CAPACITY];
      vSize = 0;
   }
   
   // O(n)
   public void insert(Comparable key, Object x)
   {
      int index = findIndex(key);
      if (index != -1)
         v[index] = new Pair(key, x);
      else
      {
         if (vSize >= v.length)
            resize();
         
         v[vSize] = new Pair(key, x);
         vSize++;
      }
   }
   
   // O(n)
   public Object find(Comparable key)
   {
      int index = findIndex(key);
      if (index != -1)
         return v[index].x;
      else
         throw new NoSuchElementException();
   }
   
   // O(n)
   public void remove(Comparable key)
   {
      int index = findIndex(key);
      if (index != -1)
      {
         v[index] = v[vSize - 1];
         v[vSize - 1] = null;

         vSize--;
      }
      else
         throw new NoSuchElementException();
   }
   
   public boolean isEmpty()
   {
      return vSize == 0;
   }

   public int size()
   {
      return vSize;
   }
   
   public String[] toStringArray()
   {
      String[] s = new String[vSize];
      for (int i = 0; i < vSize; i++)
         s[i] = v[i].toString();
      return s;
   }
   
   private void resize()
   {
      Pair[] tmp = new Pair[2 * v.length];
      for (int i = 0; i < v.length; i++)
         tmp[i] = v[i];
      v = tmp;
   }
   
   // O(n)
   private int findIndex(Comparable c)
   {
      for (int i = 0; i < vSize; i++)
         if (v[i].key.compareTo(c) == 0)
            return i;
            
      return -1;
   }

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

}