/**
  * 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) nel caso peggiore
   public void insert(Comparable key, Object x)
   {
      Pair p = new Pair(key, x);
      int index = findIndex(p);

      if (index != -1)
         v[index] = p;
      else
      {
         if (vSize >= v.length)
            resize();
         
         int j;
         for (j = vSize; j > 0 && p.compareTo(v[j - 1]) < 0; j--)
            v[j] = v[j - 1];

         v[j] = p;
         vSize++;
      }
   }
   
   // O(log n)
   public Object find(Comparable key)
   {
      int index = findIndex(new Pair(key, null));
      if (index != -1)
         return v[index].x;
      else
         throw new NoSuchElementException();
   }

   // O(n) nel caso medio e peggiore
   public void remove(Comparable key)
   {
      int index = findIndex(new Pair(key, null));
      if (index != -1)
      {
         for (int i = index; i < vSize - 1; i++)
            v[i] = v[i + 1];
            
         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(log n)
   private int findIndex(Pair p)
   {
      return binarySearch(v, 0, vSize - 1, p);
   }
   
   private int binarySearch(Object[] a, int from, int to, Pair target)
   {
      if (from > to)
         return -1;
         
      int mid = (from + to) / 2;
      if (target.compareTo(v[mid]) == 0)
         return mid;
      else if (target.compareTo(v[mid]) < 0)
         return binarySearch(a, from, mid - 1, target);
      else
         return binarySearch(a, mid + 1, to, target);
   }

   class Pair implements Comparable<Pair>
   {
      Comparable key;
      Object x;
      
      Pair(Comparable k, Object obj)
      {
         key = k;
         x = obj;
      }
      
      public int compareTo(Pair p)
      {
         return key.compareTo(p.key);
      }
      
      public String toString()
      {
         return key + " " + x;
      }
   }

}