package insiemehash;

import java.util.*;
import java.lang.reflect.Array;


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


public class InsiemeHash implements Set {

  Nodo[] tavola;  
  int dimtavola;

  int numelem;
  int diminiziale;

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

  public int size() {
    return numelem;
  }

  public boolean isEmpty() {
    return numelem == 0;
  }

  public boolean contains(Object key) {
    int pos = hash(key,dimtavola);
    Nodo l = tavola[pos];
    while (l!=null) {
      if (l.key.equals(key)) return true;
      l = l.next;
    }
    return false; //key non presente sulla tavola
  }

  public boolean add(Object key) {
    int pos = hash(key,dimtavola);
    Nodo l = new Nodo(null, tavola[pos]); 
    tavola[pos] = l;
    while (l.next!=null) {
      if (l.next.key.equals(key)) {
        tavola[pos] = tavola[pos].next;
        return false;
      }
      l = l.next;
    }
    l.next = new Nodo(key,null);
    numelem++;
    tavola[pos] = tavola[pos].next;
    if (estTroppoCarica()) rehash(dimtavola*2);
    return true;
  }

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

  public Iterator iterator() {
    return new IteratorInsiemeHash(this);
  }


  // bulk operations
  public boolean containsAll(Collection c) {
    Iterator it = c.iterator();
    while (it.hasNext()) {
      Object e = it.next();
      if (!contains(e)) return false;
    }
    return true;
  }

  public boolean addAll(Collection c){ 
    throw new UnsupportedOperationException("addlAll() non e' supportata");
  }
  public boolean removeAll(Collection c) {
    throw new UnsupportedOperationException("removeAll() non e' supportata");
  }
  public boolean retainAll(Collection c) {
    throw new UnsupportedOperationException("retainAll() non e' supportata");
  }
  public void clear() {
    throw new UnsupportedOperationException("clear() non e' supportata");
  }

  // array operations
  public Object[] toArray() {
    Object[] a = new Object[size()];
    int i = 0;
    Iterator it = iterator();
    while (it.hasNext()) {
      a[i] = it.next();
      i++;
    }
    return a;
  }

  public Object[] toArray(Object[] a) {
    if (a.length < size()) {
      //prendi il tipo degli elementi di a
      Class elemClass = a.getClass().getComponentType(); 
      //costruisci un array il cui tipo degli elementi e' quello in a
      a = (Object[])Array.newInstance(elemClass,size());
    }
    //riempi l'array con gli elementi della collezione
    int i = 0;
    Iterator it = iterator();
    while (it.hasNext()) {
      a[i] = it.next();
      i++;
    }
    for (; i < a.length; i++) 
      a[i] = null;
    return a;
  }



  // funzioni speciali ereditate da Object
  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=l.next;
      }
      s = s + "\n";
    }
    s = s + "------------------fine tavola-----------------\n";
    return s;
  }


  // funzioni ausiliarie

   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, 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);
  }
}