/**
  * MyMap
  * realizzazione minima con array non ordinato
  * Prova pratica di programmazione del 9-1-2008
  * @author A. Luchetta
  */

import java.util.NoSuchElementException;

public class MyMap implements Map //--ADT dizionario
{
   private static final int DIM = 1;

   private Pair[] v;
   private int vSize;

   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();
         v[vSize++] = p;
      }
      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(n)
      @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
   {
      int i = search(new Pair(key, null));
      
      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) throws java.util.NoSuchElementException
   {
      int i = search(new Pair(key, null));
      
      if (i < 0)
         throw new NoSuchElementException();
         
      v[i] = v[vSize - 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 lineare
      complessita' temporale: O(n)
   */
   private int search(Pair p)
   {
      for (int i = 0; i < vSize; i++)
         if (v[i].compareTo(p) == 0)
            return i;
            
      return -1;
   }
   
   /*
      ridimensiona dinamicamente l'array
      complessita' temporale: O(n)
   */
   private void resize()
   {
      Pair[] a = new Pair[2 * v.length];
      System.arraycopy(v, 0, a, 0, v.length);
      v = a;      
   }

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