/** DconArrayOrdinato.java --  dizionario con array ordinato
  * Prova di programmazione del 24-Sett-2003
  * Effettua il calcolo della frequenza delle parole in un  testo
  * tramite un dizionario.
  * Il dizionario e' realizzato con un array ordinato riempito
  * parzialmente
  * @author F. Bombi modificato da A. Luchetta
  * @version 27-Nov-2006
  */
import java.util.NoSuchElementException;

public class DconArrayOrdinato implements Dizionario
{
   private final int ARRAY_DIM = 1000;
   
   private Coppia[] v;
   private int vSize;

   /**
      inizializza un contenitore vuoto
   */
   public DconArrayOrdinato()
   {
     v = new Coppia[ARRAY_DIM];
     vSize = 0;
   }

   /* restituisce l’indice della coppia con chiave x
      se la chiave non e' presente, rstituisce -1
      Complessita' temporale:  O(log n)
   */
   private int trovaIndice(String x)
   {
      int da = 0;
   	  int a = vSize - 1;
      Coppia coppia = new Coppia(x,1);//coppia da cercare, 1 e' un valore qualsiasi
      while (da <= a) //bisezione iterativa
      {  int m = (da + a) / 2;
   	   if (coppia.compareTo(v[m]) == 0) //trovato
   	     return m;
   	   else if (coppia.compareTo(v[m]) < 0 )
   	     a = m -1; //cerco a sinistra
   	   else
           da = m + 1; //cerco a destra
      }      
      return -1; //non trovato
   }
   
   /**
     inserisce la coppia key/value nel dizionario
     La chiave e' univoca.
     L’inserimento va sempre a buon fine:
     se la chiave non esiste, la coppia
     viene aggiunta al dizionario;
     se la chiave esiste già, il valore ad
     essa associato viene sovrascritto con
     il nuovo valore
     Complessita' temporale O(n)
     @param key chiave comparabile
     @param value valore associato alla chiave
     @throws ArrayIndexOutOfBoundsException se il dizionario
     e' pieno
   */
   public void inserisci(String chiave, int attributo)
   {
     Coppia c = new Coppia(chiave, attributo);

     //verifica presenza
     int i = trovaIndice(chiave);

     if (i == -1)
     {
       // inserimento ordinato
       int j;
       for(j = vSize; j > 0 && c.compareTo(v[j-1]) < 0; j--)
      	   v[j] = v[j-1];
      	
       v[j] = c;
       vSize++;
     }
     else
       v[i] = c;
   }
   
  /**
     verifica se e' presente la chiave specificata
     Complessita' temporale O(log n)
     @param x chiave per la verifica
     @return true se la chiave e' presente, false altrimenti
  */
   public boolean presente(String x)
   {
      int i = trovaIndice(x);
      return i != -1;  
   }

   /**
      restituisce il valore associato alla chiave specificata
      nel dizionario.
      Complessita' temporale O(log n)
      @param key chiave per la ricerca
      @return valore associato alla chiave se la chiave e'
      presente, null altrimenti
      @throws java.util.NoSuchElementException se la coppia
      <chiave, valore> non e' presente nel dizionario
   */
   public int cerca(String x) throws NoSuchElementException
   {
     int i = trovaIndice(x);
     if (i != -1)
       return v[i].att;
 
     throw new NoSuchElementException("Cerca " + x);
   }
 
  /**
     restituisce i dati del dizionario in un array di lunghezza
     pari al numero di coppie contenute nel dizionario.
     NB: l'array restituito e' diverso dall'array usato
     come variabile di esemplare della classe per memorizzare
     le coppie.
     Complessita' temporale O(n)
     Nell'array di ritorno vengono poste copie delle coppie
     del dizionario
     @return array contenente le coppie del dizionario
  */
   public Coppia[] toArray() //O(n)
   {
      Coppia[] tmp = new Coppia[vSize];
 
      for (int i = 0; i < vSize; i++)
        tmp[i] = new Coppia(v[i].ch, v[i].att);
 
      return tmp;
   }
}