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

public class DconArrayNonOrdinato implements Dizionario
{
  private final int DIM_ARRAY = 1000; //array di lunghezza fissa

  private Coppia[] v;   // array riempito parzialmente
  private int vSize;    // num. coppie nel dizionario

  /*
     inizializza un dizionario vuoto
  */
  public DconArrayNonOrdinato()
  {
    v = new Coppia[DIM_ARRAY];
    vSize = 0;
  }

  /**
    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 valoreComplessita' 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)
  {
    // ricerca lineare con sentinella
    v[vSize] = new Coppia(chiave, attributo);
    int i;
    for (i = 0; !chiave.equals(v[i].ch); i++)
      ;
      
    // inserimento della coppia nel dizionario
    if (i == vSize)
      vSize++;
    else
      v[i] = v[vSize];
  }
  
  /**
     verifica se e' presente la chiave specificata
     Complessita' temporale O(n)
     @param x chiave per la verifica
     @return true se la chiave e' presente, false altrimenti
  */
  public boolean presente(String x)
  {
     // ricerca linerare
     for (int i = 0; i < vSize; i++)
       if (x.equals(v[i].ch)) // trovato
         return true;

     return false;
  }

  /**
     restituisce il valore associato alla chiave specificata
     nel dizionario.
     Complessita' temporale O(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
  {
    // ricerca linerare
    for (int i = 0; i < vSize; i++)
      if (x.equals(v[i].ch))
        return v[i].att; // trovato
    // non trovato, si lancia l'eccezione
    throw new NoSuchElementException();
  }

  /**
     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()
  {
    //array da restituire
    Coppia[] tmp = new Coppia[vSize];

    // Copia delle coppie!
    for (int i = 0; i < vSize; i++)
      tmp[i] = new Coppia(v[i].ch,v[i].att); //copia

    return tmp;
  }
}