/**
  * Fondamenti di Informatica 1 - gr. 89
  * Prova pratica di programmazione del 15 Settembre 2008
  * classe D
  * realizza un dizionario mediante un array ordinato
  *
  * @author Adriano Luchetta
  * @version 5-09-2008
  *
  */
import java.util.NoSuchElementException;

public class D implements Dictionary
{
   private static final int CAPACITY = 1;
   
   private Pair[] v;
   private int vSize;
   
   public D()
   {
      v = new Pair[CAPACITY];
      vSize = 0;
   }
   
   // O(n) nel caso peggiore
   public void insert(String key, int x)
   {
      Pair p = new Pair(key, x);
      int index = findIndex(key);

      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 int find(String key)
   {
      int index = findIndex(key);
      if (index != -1)
         return v[index].x;
      else
         throw new NoSuchElementException();
   }

   // O(n) nel caso medio e peggiore
   public int remove(String key)
   {
      int index = findIndex(key);
      if (index != -1)
      {
         int x = v[index].x;
         for (int i = index; i < vSize - 1; i++)
            v[i] = v[i + 1];
            
         vSize--;

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

   public int size()
   {
      return vSize;
   }
   
   public String[] toSortedArray()
   {
      String[] s = new String[vSize];
      for (int i = 0; i < vSize; i++)
         s[i] = v[i].toString();

      return s;
   }
   
   public int total()
   {
      int total = 0;

      for (int i = 0; i < vSize; i++)
         total += v[i].x;
         
      return total;   
   }
   
   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(String s)
   {
      return binarySearch(v, 0, vSize - 1, s);
   }
   
   private int binarySearch(Object[] a, int from, int to, String target)
   {
      if (from > to)
         return -1;
         
      int mid = (from + to) / 2;
      if (target.compareTo(v[mid].key) == 0)
         return mid;
      else if (target.compareTo(v[mid].key) < 0)
         return binarySearch(a, from, mid - 1, target);
      else
         return binarySearch(a, mid + 1, to, target);
   }

   class Pair implements Comparable<Pair>
   {
      String key;
      int x;
      
      Pair(String k, int n)
      {
         key = k;
         x = n;
      }

      public int compareTo(Pair p)
      {
         return key.compareTo(p.key);
      }

      public String toString()
      {
         return key + " " + x;
      }
   }

}