package tavolahash;

class Nodo {
  Object key;
  Object info;
  Nodo next;
  Nodo(Object k, Object i, Nodo n) {
    key = k;
    info = i;
    next = n;
  }
}

public class TavolaHash {

  private Nodo[] tavola;
  private int dimtavola;

  private int numelem;
  private int diminiziale;

  private static double FATTORECARICO = 0.75;
  private static int DIMINIZIALE = 31;
  
  public TavolaHash(int dim) {
    if (dim%2 == 0) dim++; //vogliamo che la dim sia dispari
    diminiziale = dim;
    dimtavola = dim;
    tavola = new Nodo[dimtavola];
    numelem = 0;    
  }
 
  public TavolaHash() {
    this(DIMINIZIALE);
  }    


  public Object cerca(Object key) {
    int pos = hash(key,dimtavola);
    Nodo l = tavola[pos];
    while (l!=null) {
      if (l.key.equals(key)) return l.info;
      l = l.next;
    }
    return null; //key non presente sulla tavola
  }
  
  public void inserisci (Object key, Object info) {
    int pos = hash(key,dimtavola);
    Nodo l = new Nodo(null, null, tavola[pos]); 
    tavola[pos] = l;
    while (l.next!=null) {
      if (l.next.key.equals(key)) {
        tavola[pos] = tavola[pos].next;
        return;
      }
      l = l.next;
    }
    l.next = new Nodo(key,info,null);
    numelem++;
    tavola[pos] = tavola[pos].next;
    if (estTroppoCarica()) rehash(dimtavola*2);
  }

  public void elimina (Object key) {
    int pos = hash(key,dimtavola);
    Nodo l = new Nodo(null, null,tavola[pos]); //nodo generatore
    tavola[pos] = l;
    while (l.next!=null) {
      if (l.next.key.equals(key)) {
        l.next = l.next.next;
        numelem--;
        break;
      }
      l = l.next;
    }
    tavola[pos] = tavola[pos].next;
    if (estTroppoPocoCarica()) rehash(dimtavola/2);
  }

  private boolean estTroppoCarica() {
    return 
      ((double)numelem)/dimtavola > FATTORECARICO; 
  }

  private boolean estTroppoPocoCarica() {
    return dimtavola > diminiziale && 
      ((double)numelem)/dimtavola < FATTORECARICO/3; 
  }

  private void rehash(int nuovadim) {
    if (nuovadim%2 == 0) nuovadim++; //vogliamo che la dim sia dispari    
    Nodo[] nuovatav = new Nodo[nuovadim];
    for (int i = 0; i < dimtavola; i++) {
      Nodo l = tavola[i]; 
      while(l != null) {
        int pos = hash(l.key,nuovadim);
        nuovatav[pos]= new Nodo(l.key, l.info,nuovatav[pos]); //inserisco
        //in testa
        l=l.next;
      }
    }
    dimtavola = nuovadim;
    tavola = nuovatav;
  }

  private static int hash(Object key, int dimtavola) {
    return Math.abs(key.hashCode() % dimtavola);
  }

  public String toString() {
    String s = "-----------------inizio tavola----------------\n";
    
    for (int i = 0; i < dimtavola; i++) {
      Nodo l = tavola[i]; 
      s = s + i + ": ";
      while(l != null) {
        s = s + "(" + l.key + "," + l.info +") ";
        l=l.next;
      }
      s = s + "\n";
    }
    s = s + "------------------fine tavola-----------------\n";
    return s;
  }

}