class Voce {
  public String parola;
  public String definizione;
}


public class Dizionario3 {
  //costante
  private static final int dimIniz = 5;

  //rappresentazione degli oggetti
  private Voce[] array;
  private int numElem;

  //metodi pubblici
  public Dizionario3() {
    array = new Voce[dimIniz];
    numElem = 0;
  }

  public String cerca(String parola) {
    for (int i = 0; i < numElem; i++)
      if(array[i].parola.compareTo(parola) == 0)
        return array[i].definizione;
      else if (array[i].parola.compareTo(parola) > 0)
        return null;
      // else continua con il ciclo     
    return null;
  }

  public void inserisci(String parola, String definizione) {
    if (numElem == array.length) {
      //ingrandisci l'array
      Voce[] aux = new Voce[array.length*2]; // Crea array aux piu' grande.
      for(int i = 0; i < numElem; i++)       // Copiaci gli elementi
        aux[i] = array[i];                   // dell'array originale.
      array = aux;           // Sostituisci nuovo array all'array originale.
    }
    // nell'array c'e' spazio per la nuova voce
    
    Voce c = new Voce();
    c.parola = parola;
    c.definizione = definizione;


    //trova la posizione dove inserire parola
    int k = 0;
    while (k < numElem && array[k].parola.compareTo(parola) <= 0)
      k++;

    // sposta in avanti di una posizione
    // tutti gli elementi dell'array dalla pos k in poi;
    for (int i = numElem; i > k; i--)
      // se k == numElem, il corpo del ciclo non viene eseguito
      array[i] = array[i-1];
    array[k] = c;
    numElem++;
  }

  public void elimina(String parola) {
    // trova la possibile posizione di parola
    int k = 0;
    while(k < numElem && array[k].parola.compareTo(parola) < 0)
      k++;

    if (k < numElem && array[k].parola.equals(parola)) {
      // sposta indietro di una posizione 
      // tutti gli elementi dell'array dalla pos k in poi 
      for(int i = k; i < numElem-1; i++)
        array[i] = array[i+1];
      array[numElem-1] = null;
      numElem--;
    }

    // se array troppo vuoto, rimpiccioliscilo
    if (numElem > dimIniz && numElem < array.length/4) {
      Voce[] aux = new Voce[array.length/2];
      for(int i = 0; i < numElem; i++) 
        aux[i] = array[i];
      array = aux;
    }
  }

  public void eliminaTutte(String parola) {
    // trova la possibile posizione di parola
    int k = 0;
    while (k < numElem && array[k].parola.compareTo(parola) < 0)
      k++;

    // determina quanti elementi devono essere eliminati;
    // tutti gli elementi da eliminare stanno in posizioni consecutive
    int n = 0;
    while (k+n < numElem && array[k+n].parola.equals(parola))
      n++;

    if (n > 0) {
      // sposta indietro di n posizioni tutti gli elementi dell'array
      // dalla posizione k+n in poi
      for (int i = k; i < numElem-n; i++)
        array[i] = array[i+n];

      // elimina i riferimenti agli ultimi n elementi spostati
      for (int i = numElem-n; i < numElem; i++)
        array[i] = null;

      numElem = numElem - n;
    }

    // se array troppo vuoto, rimpiccioliscilo
    if (numElem > dimIniz && numElem < array.length/4) {
      Voce[] aux = new Voce[array.length/2];
      for(int i = 0; i < numElem; i++) 
        aux[i] = array[i];
      array = aux;
    }
  }

  public String toString() {
    String ris = "numElem: " + numElem + ", dimArray: " + array.length + "\n";
    for (int i = 0; i < numElem; i++)
      ris = ris + array[i].parola + ": " + array[i].definizione + "\n";

    //il codice seguente inserisce nella stringa anche gli elementi non
    //significativi, per verificare che vengano effettivamente posti a null
    //for (int i = 0; i < array.length; i++)
    //  ris = ris + i + " " +
    //    ((array[i] == null)? "null\n" : (array[i].parola + ": " +
    //                                     array[i].definizione + "\n"));
    return ris;
  }    
}