/**
  * MyMap
  * realizzazione con array ordinato
  * 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 = 1;

   private Pair[] v;
   private int vSize;

   /**
     inizializza un dizionario vuoto      
   */
   public MyMap()
   {
      v = new Pair[DIM];
      vSize = 0;
   }

   /**
      restituisce il numero di elementi presenti nel contenitore
      @return il numero di elementi nel contenitore
   */
   public int size()
   {
      return vSize;   
   }
   
   /**
      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)
      @param key la chiave
      @param x l'attributo   
   */
   public void insert(Comparable key, Object x)
   {
      Pair p = new Pair(key, x);
      int i =  search(p);
      
      if (i < 0)
      {
         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++;
      }
      else
         v[i] = p;      
   }

   /**
      se la chiave e' presente nel dizionario restituisce l'attributo
      associato, altrimenti genera l'eccezione java.util.NoSuchElementException
      complessita' temporale: O(logn)
      @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);
      int i = search(p);
      
      if (i < 0)
         throw new NoSuchElementException();
         
      return v[i].attr;     
   }
   /**
      se la chiave e' presente elimina la coppia key/x dal dizionario,
      altrimenti genera l'eccezione java.util.NoSuchElementException
      complessita' temporale: O(n)
      @param key la chiave
      @throws java.util.NoSuchElementException se la chiave non e' presente   
   */
   public void remove(Comparable key)
   {
      Pair p = new Pair(key, null);
      int i = search(p);
      
      if (i < 0)
         throw new NoSuchElementException();
         
      for (int j = i; j < vSize - 1; j++)
         v[j] = v[j + 1];
         
      v[vSize - 1] = null;
      vSize--;
   }
   
   /*
      se la coppia non e' presente restituisce -1, altrimenti
      restituisce l'indice al quale si trova la coppia
      ricerca binaria
      complessita' temporale: O(logn)
   */
   private int search(Pair p)
   {
      return binSearch(v, 0, vSize - 1, p);
   }
   
   private static int binSearch(Comparable[] a, int from, int to, Pair t)
   {
      if (from > to)
         return -1;
         
      int mid = (from + to) / 2;
      if (a[mid].compareTo(t) == 0)
         return mid;
      else if (a[mid].compareTo(t) < 0)
         return binSearch(a, mid + 1, to, t);
      else
         return binSearch(a, from, mid - 1, t);                  
   }
   
   /*
      ridimensiona dinamicamente l'array
      complessita' temporale: O(n)
   */
   private void resize()
   {
      Pair[] a = new Pair[2 * v.length];
      System.arraycopy(v, 0, a, 0, vSize);
      v = a;
   }
   

   /*
      classe interna Pair
   */
   class Pair implements Comparable<Pair>
   {
      Comparable key;
      Object attr;
      
      public Pair(Comparable k, Object x)
      {
         key = k;
         attr = x;
      }
      
      public int compareTo(Pair c)
      {
         return key.compareTo(c.key);
      }
   }
}