class Entry {
  String word;
  String definition;
}


public class Dictionary2 {
  // constant
  private static final int DIMINIT = 5;

  // representation of the objects
  private Entry[] array;
  private int numElem;

  // public methods


  // constructs a dictionary that can have an unlimited number of entries
  public Dictionary2() {
    array = new Entry[DIMINIT];
    numElem = 0;
  }

  // searches for word in the dictionary;
  // if word is found, the corresponding definition is returned;
  // otherwise null is returned
  public String search(String word) {
    for (int i = 0; i < numElem; i++)
      if(array[i].word.equals(word))
        return array[i].definition;
    return null;
  }

  // inserts the entry formed by word and definition in the dictionary
  public void insert(String word, String definition) {
    if (numElem == array.length) {
      // enlarge the array
      Entry[] aux = new Entry[array.length*2]; // create bigger aux array
      for(int i = 0; i < numElem; i++)         // copy the element of the
        aux[i] = array[i];                     // original array
      array = aux;               // replace the original array with the new one
    }

    // now in the array there is room for the new entry, and we can insert it
    Entry c = new Entry();
    c.word = word;
    c.definition = definition;
    array[numElem] = c;
    numElem++;
  }

  // removes an entry corresponding to word, if it exists,
  // otherwise it does nothing;
  // if there is more than one entry corresponding to word, a randomly chosen
  // one is removed;
  public void remove(String word) {
    // initially, we proceed as in Dictionary1, but we use a boolean variable
    // to exit the loop as soon as we have eliminated an element
    boolean found = false;
    for (int i = 0; i < numElem && !found; i++)
      if (array[i].word.equals(word)) {
        array[i] = array[numElem-1];
        array[numElem-1] = null;
        numElem--;
        found = true;
      }

    // if the array is too empty, shrink it
    if (numElem < array.length/4) {
      int newDim = (DIMINIT > numElem*2)? DIMINIT : numElem*2;
      Entry[] aux = new Entry[newDim];
      for(int i = 0; i < numElem; i++) 
        aux[i] = array[i];
      array = aux;
    }
  }       

  // removes all entries corresponding to word
  // (if theres is no such entry, does nothing);
  public void removeAll(String word) {
    // initially, we proceed as in Dictionary1
    for (int i = 0; i < numElem; i++)
      if (array[i].word.equals(word)) {
        array[i] = array[numElem-1];
        array[numElem-1] = null;
        numElem--;
      }

    // if the array is too empty, shrink it
    if (numElem < array.length/4) {
      int newDim = (DIMINIT > numElem*2)? DIMINIT : numElem*2;
      Entry[] aux = new Entry[newDim];
      for(int i = 0; i < numElem; i++) 
        aux[i] = array[i];
      array = aux;
    }
  }

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

    // the following code inserts in the string also the non-significant
    // elements, which allows us to check whether they are set to null
    /*
      for (int i = 0; i < array.length; i++)
        res = res + i + " " +
          ((array[i] == null)? "null\n" : (array[i].word + ": " +
                                           array[i].definition + "\n"));
    */
    return res;
  }
}